Mod operation

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> Consider n = 500. This is what I get on may laptop (x86_32):
>
>   mpn_toom42_mul	1000      0.001056473
>   mpn_mullow_n           500      0.000491507
>   mpn_mulmod_bnm1       1000      0.000952538
> ----------------------------------------------
>                                   0.002500518
>
> To compare with
>
>   mpn_redc_n            1000      0.008734385

Torbjörn spotted a bug in the redc_n benchmarking. A more correct value
is

    mpn_redc_n            1000      0.002336027

so redc_n is a bit faster.

Corresponding figures on shell.gmplib.org are

  mpn_toom42_mul  1000      0.000200253
  mpn_mullow_n     500      0.000093544
  mpn_mulmod_bnm1 1000      0.000179546
----------------------------------------
                            0.000473343

and

  mpn_redc_n      1000      0.000437466

So multiplication by m3 = (B^3 mod m) seems to be a quite expensive way
to reduce the input in size.

Regards,
/Niels