mpz_millerrabin

[Paul Leyland]

On Mon, 2008-01-21 at 16:53, Niels Möller wrote:

> in the code.
> 
> >   I have difficulty imagining any useful changes to the current
> >   interface of this function,
> >   
> >     int mpz_millerrabin (mpz_srcptr n, int reps)
> 
> On second thought, for composite input, it might be useful to return
> the witness that exposed the compositeness.

Another possiblity may be to allow an argument which gives a list
(either with a count, or zero terminated) of bases which are
exponentiated within the test.

If a "probability of failing" is introduced into a future
implementation, *please* ensure that the probability is meaningful ---
that it is, it includes priors.   For instance, the well-known 1/4 per
test is an absolute worse case scenario.  It assumes that the number
being tested is selected from a vanishingly small fraction of integers.

If one knows nothing about an integer N, other than it is not divisible
by any small primes (and all primes are small if it's required that N is
to be tested against all smaller ones) then it is overwhelmingly likely
that a single test to a randomly chosen base in the range 3 to N-3 will
correctly indicate that N is prime.  (Avoiding 0, \pm 1 and \pm 2 mod N
is a good idea...)

I don't have the reference to hand which documents these probabilities. 
I can dig it up and post it if anyone would prefer me to perform the
Google search.


Paul

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-devel/attachments/20080121/71de640a/attachment.bin