Pseudo prime tests (Was: Re: _mp_alloc vs ALLOC)

[Torbjorn Granlund]

  What I think is unacceptable is that if a composite passes the test, it
  also passes the test when invoked a second time because the bases it's
  tested against are always the same. That's the why of a version that
  accepts a random state. So, a new function is recommendable in any case.
  That applies to mpz_millerrabin as well, of course, which is the one
  actually doing the PRNG calls.
  
  And while on that subject, there was also a request for a M-R test
  function accepting a specific base as parameter:
  http://gmplib.org/list-archives/gmp-devel/2002-December/000075.html
  
  And a suggestion to return the witness that proved the compositeness:
  http://gmplib.org/list-archives/gmp-devel/2008-January/000766.html
  
  In that message, Torbjörn also says that it'd be nice for a function
  called millerrabin to do a M-R test only, not also a Fermat test.

OK, I hacked something that could be a start for new functions.  These
are possible function names and interfaces, we might want to change
either or both before putting these in GMP.

New functions:

1. mpz_pprime_p, for doing some trial dividing and unspecified
   probabilistic primality tests to specified probability.

2. mpz_notdiv_pprime_p, like mpz_pprime_p but without trial dividing.

3. mpz_millerrabin, replacing the current internal function with the
   same name (but with different parameters).

The new code makes use of redc functions at the mpz level, which I wrote
several years ago.  (Such functions could also at some point be made
part of the public GMP interface.)

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pprime_p.c
Type: application/octet-stream
Size: 4420 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120605/d15a5955/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: redcify.c
Type: application/octet-stream
Size: 2126 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120605/d15a5955/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: redcify.h
Type: application/octet-stream
Size: 1469 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120605/d15a5955/attachment-0002.obj>
-------------- next part --------------

-- 
Torbjörn