Miller-Rabin test iterations for prime generation - LUT approach

[Brett Hale]

One of the 'TODO list' projects mentions probable
prime testing with a specified error bound, rather
than a repetition count. For probable prime
verification, the Miller-Rabin test cannot assume an
error-probability better than: 4^-t, since the
candidate may be a deliberately constructed
pseudoprime. For prime generation with randomly
selected k-bit candidates, Damgaard, Landrock and
Pomerance provide much stronger bounds, with further
refinements by Burthe.

Hoping that it may be useful, I've attached a utility
that calculates an iteration threshold table (i.e.,
k-threshold values) for a given error-probability. I'm
not sure of the etiquette of posting a 400 line C
source to this list, so apologies in advance. I use
the results in my own Miller-Rabin test
implementation, where the number of trials, if zero,
will default to the number of trials required for p(k,
t) <= 2^-128. A similar idea could be applied to
mpz_probab_prime_p. Passing (0) for 'reps' could make
reps default to a value with a controlled
error-probability. A diff is attached demonstrating
this approach.

I think a precomputed table for 2^-80 or 2^-128 would
be reasonable, as long as 'reps' can be explicitly
set. Even if the maintainers do not consider this to
be appropriate for mpz functions, it may still be
useful to others in example / demo code.

--

Brett Hale.

Send instant messages to your online friends http://au.messenger.yahoo.com 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mrtab.c
Type: application/octet-stream
Size: 12172 bytes
Desc: 2969937675-mrtab.c
Url : http://gmplib.org/list-archives/gmp-devel/attachments/20070116/ed55464d/attachment.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pprime_p.lut.diff
Type: application/octet-stream
Size: 1178 bytes
Desc: 3592265105-pprime_p.lut.diff
Url : http://gmplib.org/list-archives/gmp-devel/attachments/20070116/ed55464d/attachment-0001.obj