Jacobi Symbol (Haskell)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Erlang | Haskell

\left[\frac{a}{n}\right] = \prod_{i-1}^{t} \left[ \frac{a}{p_i}\right]^{k_i}

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

  1. \left[\frac{ab}{n}\right] = \left[\frac{a}{n}\right] \left[\frac{b}{n}\right] 
    <<property 1>>=
jacobi a n | even a         = jacobi 2 n * jacobi (a `div` 2)  n
  2. For a \equiv b \pmod{n},\left[\frac{a}{n}\right] = \left[\frac{b}{n}\right]. 
    <<property 2>>=
           | a >= n         = jacobi (a `mod` n) n
  3. For odd coprimes a and n, \left[\frac{a}{n}\right] = (-1)^{\frac{a-1}{2}\frac{n-1}{2}} \left[\frac{n}{a}\right]. 
    <<property 3>>=
           | a `mod` 4 == 3 ||
             n `mod` 4 == 3 = - jacobi n a
           | otherwise      = jacobi n a
  4. \left[\frac{1}{n}\right] = 1. 
    <<property 4>>=
jacobi 1 _ = 1
  5. \left[\frac{2}{n}\right] = \begin{cases} -1 & \mbox{for } n \equiv 3 \mbox{ or } 5\pmod{8} \\ 1 & \mbox{for } n \equiv 1 \mbox{ or } 7\pmod{8} \\ \end{cases}. 
    <<property 5>>=
jacobi 2 n = case n `mod` 8 of
               1 -> 1
               3 -> -1
               5 -> -1
               7 -> 1
  6. \left[\frac{0}{n}\right] = 0. 
    <<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 a \geq n 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
Retrieved from "http://en.literateprograms.org/Jacobi_Symbol_%28Haskell%29"
Personal tools