Random Prime Generator/Modular Arithmetic

[Bryan Olson]

Tuvas wrote:
> Okay, I don't know if your farmiliar with the miller-rabin primality
> test,

Paul is familiar with it. When he referred to your Miller-Rabin
test, he meant all the rounds.

 > but it's what's called a probabalistic test. Meaning that trying
> it out once can give fake results.

In the sense that some composites will pass as prime for some
bases.


 > For instance, if you use the number
> 31 to test if 561 is prime, you will see the results say that it isn't.

That's not an instance of a fake result; Miller-Rabin has that
one right. When Miller-Rabin says a number is composite, it is
always correct.


Your current Miller-Rabin test, in

   http://www.geocities.com/brp13/Python/modular.html

in method Mod.is_strong_pseudo_prime(), looks buggy. Obviously
you want "cut()" not "cut", and "if 1:" cannot fail. In my opinion,
the Mod class is not such a good idea; just use functions.


Note that Python has modular exponentiation built in.

    pow(base, power, modulus)

with positive integer arguments will return base**power % modulus.


Finally, though most introductory crypto courses don't cover it,
RSA requires "padding" of the plaintext data. Google RSA + Padding
for more. Or ask on sci.crypt.


-- 
--Bryan