[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