Jacobi Symbol (Haskell)
From LiteratePrograms
The Jacobi symbol satisfies the six properties listed below, and these can be used to compute the Jacobi symbol in polynomial time.
-
<<property 1>>= jacobi a n | even a = jacobi 2 n * jacobi (a `div` 2) n
-
For ,.
<<property 2>>= | a >= n = jacobi (a `mod` n) n
- For odd coprimes a and n, .
<<property 3>>= | a `mod` 4 == 3 && n `mod` 4 == 3 = - jacobi n a | otherwise = jacobi n a
- .
<<property 4>>= jacobi 1 _ = 1
- .
<<property 5>>= jacobi 2 n = case n `mod` 8 of 1 -> 1 3 -> -1 5 -> -1 7 -> 1
- .
<<property 6>>= jacobi 0 _ = 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 can be run from the command line with the arguments on the command line
<<jacobi.hs>>= import System.Environment jacobi symbol main = do args <- getArgs let a = read (args !! 0) b = read (args !! 1) print (jacobi a b)
Download code |