1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Jacobi Symbol

  1. Apr 12, 2007 #1
    Jacobi Symbol - Binary

    NOTE: if its past 8:30 AM Eastern Time, dont worry about it. thanks for the consideration

    The Question:
    Exercise 13.1. Develop a “binary” Jacobi symbol algorithm, that is, one
    that uses only addition, subtractions, and “shift” operations, analogous to
    the binary gcd algorithm in Exercise 4.1.



    heres the algorithm that i came about with so far:

    Note: it is right, except for the fact that there cant be mod, division, multiplication, etc.

    can you guys please help me out?




    t := 1;
    while (a > O and a < O) do

    .........while (a mod 2 = O) do
    ................a = a/2;
    ................if (n mod 8 = 3) or (n mod 8 = 5) then t := -t;

    .........if (a < n) then
    ................interchange(a,n);
    ................if (a mod 4 = 3) and (n mod 4 = 3) then t = -t;

    .........a := (a-n)12;
    .........if (n mod 8 = 3) or (n mod 8 = 5) then t = -t;

    if (n = I) then return(t) else return(O).
     
    Last edited: Apr 12, 2007
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?