Re: mpz_powm crashes with modulus>2^2100000

[Torbjorn Granlund]

address@hidden (Paul Zimmermann) writes:

  ... values each of 268Ko, i.e. a total of about 4.4Go!!!

For those that don't speak geek French, Ko = kilo octettes, Go =
giga octettes.  An "octette" is what is known as "byte" in geek
English.  :-)

  The workaround (which I think will be in the next gmp release) is to have
  a hard limit for the parameter 'k' in mpz_powm. For example kmax=7 seems
  reasonable, which gives a table of 2^6 elements at most, i.e. about 17Mo
  in your case. Since the cost is proportional to 1+1/(k+1), with k=7 you
  loose only about 6% wrt the "optimal" k=15.

The development sources use a cap of 10.
Perhaps that is a bit high.

  Below is a patch that limits k to 7, and in addition prints some information
  to show the progress in the computation. For computing 3^p mod p for
  p=3*2^2145353+1 on an old PIII-500, I estimate it will take about 120 days.

That's a lot, in particular as this code isn't as fast as it
could be.  The current mod code is a log factor too slow.

You may want to spend a day or two writing special code for this
case, utilizing an asymptotically efficient REDC, or perhaps Barett
division.  You should get around a 2x improvement for your operands.

--
Torbjörn

"spam, spam, spam, egg and spam" -- Monty Python