[Courses] [security] Crypto Scientists Crack Prime Problem

[Jacinta Richardson]

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   |