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
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
More information about the Python-list
mailing list