Jacobi Symbol (Erlang)

From LiteratePrograms

Other implementations: Erlang | Haskell | Python

The Jacobi symbol satisfies the six properties listed below, and these can be used to compute the Jacobi symbol in polynomial time.

1. <<property 1>>=
   jacobi(A, N) when A rem 2 =:= 0 ->
       jacobi(2, N) * jacobi(A div 2 + A rem 2, N);
   

2. For ,.

   <<property 2>>=
   jacobi(A, N) when A >= N ->
       jacobi(A rem N, N);
   

3. For odd coprimes a and n, .

   <<property 3>>=
   jacobi(A, N) when A rem 4 =:= 3, N rem 4 =:= 3 ->
       -jacobi(N, A);
   jacobi(A, N) ->
       jacobi(N, A).
   

4. .

   <<property 4>>=
   jacobi(1, _N) ->
       1;
   

5. .

   <<property 5>>=
   jacobi(2, N) ->
       case (N rem 8) of
           1 -> 1;
           3 -> -1;
           5 -> -1;
           7 -> 1
       end;
   

6. .

   <<property 6>>=
   jacobi(0, _N) ->
     0;
   

From these properties we can come up with a polynomial time algorithm.

The function always complete as property 1 can be used to remove all even factors, and these will end at property 4. The odd factors will be reduced by property 2 if and if a < n property 3 will swap a and n and property 2 will again reduce a until it matches property 4 or property 6.

<<jacobi symbol>>=
property 4
property 5
property 6
property 1
property 2
property 3

This is an escript, it can be run from the command line on unix type computers.

<<jacobi>>=
#!/usr/bin/env escript
main([A, P]) ->
    io:fwrite("~p~n", [xjacobi(string:to_integer(A), string:to_integer(P))]).
xjacobi({A, _}, {B, _}) ->
    jacobi(A, B).
    jacobi symbol