- #1
pureouchies4717
- 99
- 0
Jacobi Symbol - Binary
NOTE: if its past 8:30 AM Eastern Time, don't 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 can't 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).
NOTE: if its past 8:30 AM Eastern Time, don't 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 can't 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: