Random Prime Generator/Modular Arithmetic

Bryan Olson fakeaddress at nowhere.org
Sun Mar 5 11:57:46 EST 2006

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

 > 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


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.


More information about the Python-list mailing list