Pseudo prime tests

[bodrato at mail.dm.unipi.it]

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