# My Weblog

## Solovay–Strassen primality test

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. Wikipedia suggests that for any odd prime p and integer a $a^{\frac {p-1} 2 } \equiv(\frac a p )\mod p$ where $\left(\tfrac{a}{p}\right)$ is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to $\left(\tfrac{a}{n}\right)$, where n can be any odd integer.Given an odd number n

$a^{\frac {n-1} 2} \equiv \left(\frac{a}{n}\right) \pmod n$

holds for various values of a. If n is prime then this congruence is true for all a.Jacobi code is take from here.

import Data.List
import System.Random

powM :: Integer -> Integer -> Integer -> Integer
powM a b m
| b == 0 = 1
| b == 1 = mod a m
| odd b  =  mod ( a * powM ( mod ( a^2 ) m ) ( div b 2 ) m ) m
| otherwise =  mod ( powM ( mod ( a^2) m  ) ( div b 2 ) m ) m

jacobi::Integral a => a -> a -> a
jacobi a n
| a == 0 = if n == 1 then 1 else 0
| a == 2 && ( mod n 8 == 1 || mod n 8 == 7 ) = 1
| a == 2 && ( mod n 8 == 3 || mod n 8 == 5 ) = -1
| a >= n = jacobi ( mod a n ) n
| even a = jacobi 2 n * jacobi ( div a 2 ) n
| mod a 4 == 3 && mod n 4 == 3 = -jacobi n a
| otherwise = jacobi n a

isProPrime :: Integer -> Integer -> Bool
isProPrime n a
| gcd a n /= 1 = False
| otherwise = powM a ( div ( n - 1 ) 2 ) n == mod ( jacobi a n ) n

solovayStrassen :: Integer -> IO Bool
solovayStrassen n
| n < 2 = return False
| n == 2 = return True
| even n = return False
| otherwise = return.isProPrime n =<< randomRIO ( 2 , n-1 )