The algorithm tries to generate a prime, Q, by generating random numbers and then testing them for primality. It loops around until it finds a prime, or until MAX_ITERATIONS is exceeded. MAX_ITERATIONS is set to 5, which is usually too low to find a prime.
Ian, is this your code?
Assignee: wtc → mcgreer
This is my code. I believe the number does need to be larger. I seem to remember the frequency of primes in 1024-bit numbers being about 1/300, so I suggest 500 (this operation is fairly fast). I also want to change the number of Miller-Rabin primality tests to 50, which is what FIPS-186 specifies. patch forthcoming.
Please don't change "the number of Miller-Rabin primality tests to 50" until we can discuss it more. I believe it is unnecessary. I don't want to elaborate here. I'd say that the limit ought to be a function of the size of the prime, and ought to be at least twice the frequency. That is, if the frequency is really 1/300 then I'd do up to 600.
I got the number 50 from FIPS 186, section 2.1. I thought mpp_pprime was an implementation of Miller-Rabin, so I assumed that 50 would be the correct number. Is that not the case?
The requirement is to produce a number whose probability of being non-prime is less than 1/(4**50). Doing Miller-Rabin 50 times will assure that, but is overkill for very large values. 1/(4**n) is the upper bound for probability that the test will declare a composite number prime. As the numbers get larger, the probability of a pseudoprime goes down. That is why mpp_make_prime adjusts the number of tests according to the size of the number. You'll find that quite a few other libraries also do this. I'm looking for a citable reference on this (other than third party source code).
First , I need to correct what I wrote above. The FIPS 186-1 requirement is that a "robust primality test" be used on q and p to determine if they're prime (Appendix 2.2, steps 4 and 11. A footnote in that appendix defines "robust primality test" as "one where the probability of a non-prime number passing the test is at most 2**-80." In the Handbook of Applied Cryptography, Table 4.4, part of note 4.49 (page 148) shows t, the number of MR tests that must be run on a k-bit candidate, for which the probability is at most (1/2)**80. Section 4.4.3, especially note 4.57 (pages 150-151) state that for randomly chosen 160 bit numbers (q), 18 MR tests is enough, and that 5 is more than enough for all valid values of L (bits in P). I'm going to replace the code in mpp_make_prime with code that implements table 4.4. So, 50 is way overkill. Please use the values 18 and 5 for q and p respectively.
I verified the patch by checking the values in HAC table 4.4. I will attach a revised patch for the PQG bug. In it, the maximum number of iterations to attempt to generate a prime is fixed at 600. Nelson, I read from your comments that this should be sufficient? I don't believe it should be neccessary to make this number a function of the size of the prime, since it's really just there to prevent the library from spinning out of control.
Ian, your patch looks good to me.
Please check in the fix.
I have checked in the patch to pqg.c.
My patch is also checked in. Ian, is this bug realy to be marked resolved/fixed?
Yes, I believe so. Marking as fixed.
Status: NEW → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.