Pseudo prime tests (Was: Re: _mp_alloc vs ALLOC)
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Fri Jun 8 13:04:08 CEST 2012
Ciao,
Il Mar, 5 Giugno 2012 11:34 pm, Torbjorn Granlund ha scritto:
> 1. mpz_pprime_p, for doing some trial dividing and unspecified
> probabilistic primality tests to specified probability.
I'd like to keep the "Return 2 if n is definitely prime" feature of the
current _probab_prime_ function.
> 2. mpz_notdiv_pprime_p, like mpz_pprime_p but without trial dividing.
Do we really need a new function for this? An additional parameter should
be enough.
> 3. mpz_millerrabin, replacing the current internal function with the
> same name (but with different parameters).
This can be useful if we decide to export it, but it (slightly) slows down
the repeated use, because nm1, one, nredc, q and k must be recomputed at
each call.
Moreover, the comment to this function says: "FIXME: Stay in REDC,
requires reimplementation of mpz_powm". In this case we should require an
already redcified base argument. A loop like the one in _pprime_p will
then use the random numbers generated by _urandomm as redcified...
Or we can write a mpn_redc_millerrabin, and use it for all the mpz
functions above.
> 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.)
But I fear mpz_millerrabin doesn't use them the best way: nm1 is redcfied
too early, then it's compared to the non redcfied result of _powm,
possibly giving a wrong "composite" answer on prime numbers! Moreover we
don't need to use the redcfy function on both 1 and (n-1). I attach a
working copy.
About the redcfy interface: _modredc can be used both after a
multiplication, or after a (sequence of) subtraction/addition?
Regards,
Marco
--
http://bodrato.it/software/strassen.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pprime_p.c
Type: text/x-csrc
Size: 4724 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120608/2016cad0/attachment.bin>
More information about the gmp-devel
mailing list