Random Prime Generator/Modular Arithmetic

[Tuvas]

Re: Random Prime Generator/Modular Arithmetic

Bryan Olson wrote:[color=blue]
> Tuvas wrote:[color=green]
> > Okay, I don't know if your farmiliar with the miller-rabin primality
> > test,[/color]
>
> Paul is familiar with it. When he referred to your Miller-Rabin
> test, he meant all the rounds.
>[color=green]
> > but it's what's called a probabalistic test. Meaning that trying
> > it out once can give fake results.[/color]
>
> In the sense that some composites will pass as prime for some
> bases.
>
>[color=green]
> > For instance, if you use the number
> > 31 to test if 561 is prime, you will see the results say that it isn't.[/color]
>
> 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.[/color]

I mis-stated. If you try 31 in the Miller-Rabin test.
[color=blue][color=green][color=darkred]
>>>Mod(31,561). is_strong_pseud o_prime()[/color][/color][/color]
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:[color=blue][color=green][color=darkred]
>>>Mod(16,561). is_strong_pseud o_prime()[/color][/color][/color]
True
[color=blue]
>
>
> Your current Miller-Rabin test, in
>
> http://www.geocities.com/brp13/Python/modular.html
>
> in method Mod.is_strong_p seudo_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.
>[/color]

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.
[color=blue]
>
> Note that Python has modular exponentiation built in.
>
> pow(base, power, modulus)[/color]


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.
[color=blue]
>
> 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[/color]

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

[Bryan Olson]

Re: Random Prime Generator/Modular Arithmetic

Tuvas wrote:
[...][color=blue]
> 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:
>[color=green][color=darkred]
>>>>Mod(16,561) .is_strong_pseu do_prime()[/color][/color]
>
> True[/color]

Hmmm...my M-R tester disagrees...

Ah, there's another bug in is_strong_pseud o_prime().
While your exponent 'x' is even, you do the test with x,
not necessarily x/2.

Incidentally, the lowest base for which 561 is strongly
pseudo-prime is 50.


--
--Bryan

[Tuvas]

Re: Random Prime Generator/Modular Arithmetic

Ahh, I see, I missed doing the last step in my M-R test. Hmmm. Well,
got that one fixed now, time for a new release I guess. Sigh. I do seem
to be going through them rather quickly...

[Tuvas]

Re: Random Prime Generator/Modular Arithmetic

Okay, now I get the correct number of 561 pseudoprimes, 5, so I can
assume that it is indeed working right. Whew. Thanks for the help on
that one. Now, I only wish I could change the answer to my last
homework assignment... Oh well.

[Bryan Olson]

Re: Random Prime Generator/Modular Arithmetic

Tuvas wrote:[color=blue]
> Okay, now I get the correct number of 561 pseudoprimes, 5, so I can
> assume that it is indeed working right.[/color]

Your code now looks right, so I'm guessing "5" was a typo,
perhaps because "5" is just below "8" on the numeric keypad.


You can simplify your loop like:

def is_strong_pseud o_prime(a, n):
# check for n == 2 and/or other input validation omitted
if pow(a, n - 1, n) != 1:
return False
x = n - 1
while x % 2 == 0:
x = x / 2
y = pow(a, x, n)
if y == n - 1:
return True
elif y != 1:
return False
return True


For time efficiency, I prefer a slightly longer version that does
all the square-root-checking in the course of the one modular
exponentiation.

def is_mr_pseudopri me(n, w):
""" Pass positive integers n and w, with w < n.
Return true iff n is prime or a strong base-w pseudo-prime.
"""
assert n == long(n) and w == long(w) and 1 < w < n
power = n - 1
pow2 = 0
while power % 2 == 0:
power /= 2
pow2 += 1
r = pow(w, power, n)
for _ in xrange(pow2):
prev = r
r = r * r % n
if r == 1:
return prev in (1, n - 1)
return r == 1


--
--Bryan

[Tuvas]

Re: Random Prime Generator/Modular Arithmetic

Actually, there was a small bug fix that I found, and I had a teacher
who told me once that there was only 5 pseudoprimes. I realized that
large numbers of prime numbers were returning false, and discovered the
root of the problem, which was that my M-R test ended too late... But,
it works now, thankfully.

I may switch soon to an upgraded version of the code, to be more
efficient. But for now, I'm just glad to have it work!