The Ada Program: jacobi.adb

  1 -- jacobi.adb:  function to compute Jacobi symbol J(A,N)
  2 
  3 function Jacobi (A,N: Positive) return Integer is
  4    R: Integer;
  5 begin
  6    if A=1 then
  7       return 1;
  8    elsif A mod 2 = 0 then
  9       R := Jacobi (A/2,N);
 10       --  R * ((-1) ** (((N**2)-1)/8))
 11       if (((N**2)-1)/8) mod 2 = 0 then return R; else return -R; end if;
 12    else
 13       R := Jacobi (N mod A, A);
 14       -- R * ((-1) ** ((A-1)*(N-1)/4))
 15       if (((A-1)*(N-1))/4) mod 2 = 0 then return R; else return -R; end if;
 16    end if;
 17 end Jacobi;