Random Prime Generator/Modular Arithmetic

[Tuvas]

Bryan Olson wrote:
> 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.

I mis-stated. If you try 31 in the Miller-Rabin test.

>>>Mod(31,561).is_strong_pseudo_prime()
True

However, 561 is not prime, it is divisible by 3, 11, and 17.

Actually, I did another test, and realized that it was indeed a bug in
the code. Yikes. Oh well, thanks for the help in identifying it!

An example that would be alot easier is this:
>>>Mod(16,561).is_strong_pseudo_prime()
True

>
>
> 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.
>

The reason for the modulos class, well, was more of a practice than
anything else.

I could indeed just use functions, but I needed the Mod class for a few
other things, and figured it was just easier to program it once and use
it for anything rather than anything else.

>
> Note that Python has modular exponentiation built in.
>
>     pow(base, power, modulus)


Nice to see that Python supports modular exponentiation. I'll have to
remember that one. Probably the next time I do an update to the code,
I'll just use it instead, it's probably faster than mine.

>
> 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

Overall, I guess another update is coming soon. Thanks for the help in
debuging again!