[pycrypto] getStrongPrime() implementation

[don at amberfisharts.com]

Hi,

> [I should correct the terminology I used in my previous email: 
> mpz_probab_prime_p doesn't implement a deterministic test (as I suggested); 
> it implements the probabilistic Rabin-Miller test deterministically.  As a
> result, the theoretical guarantee normally provided by the Rabin-Miller 
> probabilistic test (at most a 25% false positive probability per
> iteration) is void.]

Yes. I realized this yesturday when I looked at the gmp code. Do you have any idea why they did go for the non-deterministic version (and not seed the PRNG)? 
I think the PRNG bug you mentioned earlier can't have anything to do with it because a potential attacker would have no influence on when the test is performed and thus when (and with what seed) the PRNG is seeded.

>>Maybe one could then later replace/extend it to a Baillie–PSW primality
>>test which has no pseudo-prime numbers up to at least 10^15.
> 
> Yes.  Of course, for crypto, we really only need to worry about primes 
> larger than 2^2047 (10^616).   Does Baillie-PSW offer a theoretical
> maximum probability of error like Rabin-Miller does?

Baillie-PSW is just a combination of (as I understand it) a single Rabin-Miller-Tests followed by a strong Lucas-Selfridge test.
There seems to be no pseudoprimes below 2^64 (not yet confirmed) [1] and others seem to estimate that there are non below 10000 [2].
As that may be I couldn't find a mathamatical proof of any boundary so if we are worried about that we could still do n Rabin-Miller test to get the mathamaticly proven probability of 4^{-n} and then do a Lucas test for better *assumed* probability.
There are some concerns that the Lucas test might not be computationally feasable for large numbers [1]. 
So for now this is just an option one can take a look at once the other parts are in place because it wouldn't replace anything but rather extend it.

>>> - We'll need some unit tests to do some basic sanity checks on the output
>>>    of this new function?
>>I agree. but what do you have in mind exactly? do you want to do an 
>>*exact* primality test? 
> 
> No. :)
> 
> Basically, I just want to test for obvious coding errors.  For example, we
> could check for "primes" that are even, or wrong sized primes (e.g if you 
> ask for a 2048-bit prime and get a 2047-bit number instead).  We could also 
> test a new isPrime() by including some pseudoprimes that currently fool 
> isPrime (Thomas R. Nicely has generated some).

I see. This sounds reasonable.


BTW, is there a certain Python version you want to support?
I ask because yesturday I caught myself writing "x = x if y else z". I'll replace that particular line with the equivalent "if ... else ..." construct, but it made me wonder if there are any further constraints.


OK, so I'll work on these (supporting randfunc, probabilistic Rabin-Miller-Test, python versions and unit tests) and send in a patch when I think it's review worthy.
I might even get it done until the weekend. let's see about that.


sincerely yours
//Lorenz


[1] http://www.trnicely.net/misc/bpsw.html
[2] http://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test