Binary Jacobi Symbol Algorithm: Add, Subtract & Shift

[pureouchies4717]

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).

 

[mighty2000]

Hi there,

Thank you for sharing your algorithm for the binary Jacobi symbol. It seems like you have a good start, but there are a few things that need to be adjusted in order to make it a fully functional algorithm.

Firstly, the Jacobi symbol is defined for odd numbers, so the while loop should be while (a > 0 and a < n). This will also take care of the issue of division by 0.

Secondly, the algorithm should use only addition, subtraction, and "shift" operations. This means that the mod and division operations need to be replaced with bitwise operations, such as AND, OR, and XOR.

Thirdly, the algorithm should check for the special cases where n is equal to 2 or 3 separately, as they have different rules for calculating the Jacobi symbol.

Lastly, the algorithm should return 1 if the result is 1, -1 if the result is -1, and 0 if the result is 0.

I hope this helps and good luck with your algorithm!