RE: IPS security draft: SRP groups

[vince_cavanna@agilent.com]

Hi Paul,

I suspected as much, since I don't have a supercomputer on my desktop. Mathematica apparently also has the capability to perform a mathematical proof of primality and to produce a "certificate" using which Mathematica's results may be independently and easily verified. When I attempted to perform the proof on the smallest modulus (the one with 768 bits) my computer was rendered useless for over 20 minutes which just happened to be my threshold of tolerance for this morning. I will try again when I leave the office tonight and if I get any useful  results I will look deeper into the method.

Vince



|-----Original Message-----
|From: Paul Koning [mailto:ni1d@arrl.net]
|Sent: Friday, July 12, 2002 7:15 AM
|To: vince_cavanna@agilent.com
|Cc: Black_David@emc.com; ips@ece.cmu.edu; tom@arcot.com
|Subject: RE: IPS security draft: SRP groups
|
|
|>>>>> "vince" == vince cavanna <vince_cavanna@agilent.com> writes:
|
| vince> Hi David, I can't prove so, but Mathematica from Wolfram
| vince> certifies as prime (in a matter seconds) all five moduli
| vince> specified in the iSCSI security draft for use in SRP! I used
| vince> the PrimeQ built-in function. PrimeQ first tests for
| vince> divisibility using small primes, then uses the Miller­Rabin
| vince> strong pseudoprime test base 2 and base 3, and then uses a
| vince> Lucas test. I have not explored the nature of these tests.
|
|Miller-Rabin is a probabilistic test.  As for "Lucas" -- the Handbook
|of Applied Cryptography lists "Lucas-Lehmer primality test for
|Mersenne numbers".  That suggests that this test has no meaning for
|numbers that aren't Mersenne numbers (such as randomly chosen
|numbers). 
|
|So I think you have a probabilistic primality test here, similar to
|what Tom did.  That's certainly useful confirmation, but it doesn't
|sound like we have the primality proofs yet.  (Unfortunately, HAC is
|not sufficiently helpful in pointing to an algorithm to to so...)
|
|    paul
|