# Jacobi Symbol

1. Apr 12, 2007

### nick727kcin

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.

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