## 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 where is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to , where n can be any odd integer.Given an odd number 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 )

Advertisements

No comments yet.

## Leave a Reply