[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: mpz_powm crashes with modulus>2^2100000
From: |
Torbjorn Granlund |
Subject: |
Re: mpz_powm crashes with modulus>2^2100000 |
Date: |
12 Mar 2003 16:21:07 +0100 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 |
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