Jacobi Symbol (Haskell)

From LiteratePrograms

Jump to: navigation, search
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 | even a         = jacobi 2 n * jacobi (a `div` 2)  n
    
  2. For ,.
    <<property 2>>=
               | a >= n         = jacobi (a `mod` n) n
    
  3. For odd coprimes a and n, .
    <<property 3>>=
               | a `mod` 4 == 3 &&
                 n `mod` 4 == 3 = - jacobi n a
               | otherwise      = jacobi n a
    
  4. .
    <<property 4>>=
    jacobi 1 _ = 1
    
  5. .
    <<property 5>>=
    jacobi 2 n = case n `mod` 8 of
                   1 -> 1
                   3 -> -1
                   5 -> -1
                   7 -> 1
    
  6. .
    <<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
Views