# [Courses] [security] Crypto Scientists Crack Prime Problem

Jacinta Richardson jarich at perltraining.com.au
Wed Aug 14 11:34:44 EST 2002

```Oops.  Sorry, just noticed a typo that might confuse...

> The Rabin Miller algorithm uses the property of strong pseudoprimes in
> checking for primality.  We can determine whether a number is a strong
> pseudoprime to a given base using the following theorem:
>
> 	Let 'n' be a positive integer and 'a' be a number randomly chosen
> 	between 1 and 'n'.  Let n - 1 = 2^(st) where 't' is an odd
> 	integer.
> 	If either:
> 		a^m  =~ 1 mod n  or
> 		(a^t)^(2^i)  =~ -` mod n

should be:
(a^t)^(2^i)  = -1 mod n

> 	Then 'n' is either a prime number or a strong pseudo prime to base
> 	'a'.

Jacinta

--
("`-''-/").___..--''"`-._          |  Jacinta Richardson	    |
`6_ 6  )   `-.  (     ).`-.__.`)  |  Perl Training Australia    |
(_Y_.)'  ._   )  `._ `. ``-..-'   |      +613 9354 6001 	    |
_..`--'_..-_/  /--'_.' ,'           | contact at perltraining.com.au |
(il),-''  (li),'  ((!.-'              |   www.perltraining.com.au   |

```

More information about the Courses mailing list