My Weblog

Blog about programming and math

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 )   
About these ads

June 23, 2011 - Posted by | Programming | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 268 other followers

%d bloggers like this: