Re: mpz_powm crashes with modulus>2^2100000

[Jens Kruse Andersen]

Paul Zimmermann wrote:
> It is my fault. I'm the original author of the current mpz_powm code.
> I wrote it to optimize the computer time, without taking into account
> the memory used. For your example (exponent and modulus of 2145355 bits)
> the mpz_powm function will first create an auxiliary table containing
> x^(2i+1) for i < 2^15, i.e. 2^14 values each of 268Ko, i.e. a total of
> about 4.4Go!!!
>
> 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.
>
> 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.

I inserted the patch including all printf. My earlier sent test program still
crashes with p=2^2100000+1 after outputting:
Calling mpz_powm_ui...Done. Calling mpz_powm...k=1
computing x^2

Note the test program only tries to compute 3^3 mod p, the exponent is tiny
and the patch does not change k.
I am running under Windows XP with 256 MB physical memory.

Before my first mail, I had already made my own workaround by writing my own
proth_powm and skipping mpz_powm completely. That worked and did not slow down
my program, so you don't have to make a patch for my sake. I just reported the
problem for others but I will be happy to test your patches if the problem is
platform dependant.

The prp test of p=3*2^2145353+1 had completed with my workaround. Just for
speed, before finding the powm bug, I had written my own proth_mod optimized
for modulus p=k*2^n+1, unsigned long k. This can be done with bitshifts and
_ui operations and is extremely fast compared to the generic mpz_mod. I
combined mpz_mul and my proth_mod and the resulting modular exponentiation
became 5.3 times faster than mpz_powm for p=54767*2^1337287+1, taking 40 hours
on my 1333 MHz Athlon XP with 133 MHz ram.
p=3*2^2145353+1 took 4.5 days for my program, which only makes a base 2^32
Fermat prp test as a side effect. My purpose is to find the _smallest_ e for
which (2^32)^e mod p = 1. This e is the order of 2^32 for modulus p. George
Marsaglia has a good and efficient rng based on huge Proth primes and he asked
me to write a program capable of computing the period which is the order of
2^32. I installed GMP for this purpose and my original program called mpz_powm
with small exponents near the end of the order computation - after saving to
file, so the 4.5 day run was not lost when it crashed. With my workaround, it
took the program a couple of minutes from the restore file to find the order
e=2^2145347 for p=3*2^2145353+1. This is probably the longest known period for
an rng - and possibly the largest modular exponentiation performed with GMP. I
would not have computed this with mpz_powm on an old PIII-500!

BTW, I see you have also worked on CYF no. 11 at
www.shyamsundergupta.com/canyoufind.htm
You sure were patient, I wonder if a factor of 10^999+13 will ever be found.
It is a little surprising to me that factoring efforts already fails at the
14th titanic number but I guess it is just a coincidence that the first hard
number comes so early. You better get started on gmp-ecm 6.0 after
mpz_powm :-)

--
Jens Kruse Andersen