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! -- http://mail.python.org/mailman/listinfo/python-list
