Pseudo prime tests
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Mon Jun 11 19:15:43 CEST 2012
Ciao,
Il Lun, 11 Giugno 2012 12:32 pm, Torbjorn Granlund ha scritto:
> bodrato at mail.dm.unipi.it writes:
> 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.
>
> I agree. (Perhaps the current powm code could then invoke that code.)
I mean something different. I mean we should have a function
_millerrabin (mpz_t redcified_base, mpz_redc_t nredc)
So that we can directly generate the redcified_base with mpz_urandomm.
> About the redcfy interface: _modredc can be used both after a
> multiplication, or after a (sequence of) subtraction/addition?
>
> I don't think that would work, since it multiplies by B^(-n) mod m.
> Only after multiplying two residues in the special B^n format, it will
> work as expected to divide out B^n.
So, linear combinations of redcified numbers must be reduced with _mod.
While "bilinear" (combinations of degree-2 products) must be reduced with
_modredc... Right?
The div_by_2 trick I used in stronglucasselfridge should work with
redcified numbers too...
Best regards,
m
--
http://bodrato.it/software7combinatorics.html
More information about the gmp-devel
mailing list