Possible to optimize for base 2 fermat primality test using shifts?
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat Apr 13 10:48:56 UTC 2019
Ciao,
Il Ven, 12 Aprile 2019 4:44 am, Hans L ha scritto:
> Hello,
> I've been learning to use GMP library lately and doing some experimenting
Great!
> with searching for various specific types of prime numbers.
specific types often deserves specific testing functions...
> I noticed the mpz_probab_prime_p does a fermat primality test of base 210
Yes, the released version does, but the new developing version does not
any more. Removed with: https://gmplib.org/repo/gmp/rev/d417bcef18e6
> I guess what I'm proposing is a new function signature such as:
>
> void mpz_powm_2exp(mpz_t rop, const mpz_t exp, const mpz_t mod)
> Set rop to (2 raised to exp) modulo mod.
> I've only just read a little bit about how k-ary window exponentiation
> works, the math behind it is still pretty new and difficult to me. So,
> I'm not really clear if its directly applicable to drop in lshifts as
> replacements for multiplications. But it seems that with k <=
I do not think it depends on the k-ary window, but it depends on the
representation we use for numbers...
The manual ( https://gmplib.org/manual/Modular-Powering-Algorithm.html )
says that GMP uses "REDC method by Montgomery" to speed-up modular
operations. If you use lshifts, that you have to use plain modular
functions. Maybe it's worth, maybe it's not. You should test it.
> One last thing comment I have is regarding the code for setting k, which
> looks up the bitcount in this array:
> static mp_bitcnt_t x[] =
> {0,7,25,81,241,673,1793,4609,11521,28161,~(mp_bitcnt_t)0};
>
> However, I noticed that wikipedia cites an equation for optimal setting of
> k, which results in different values than these:
> https://en.wikipedia.org/wiki/Exponentiation_by_squaring#2k-ary_method
>>From citation source:
> "For optimal efficiency, k should be equal to the smallest integer
> satisfying lg(n) <= k*(k+1)*2^(2k) / (2^(k+1)-k-2))"
> Cohen, H.; Frey, G., eds. (2006). *Handbook of Elliptic and Hyperelliptic
> Curve Cryptography*
Unfortunately I did not read the book and I do not know how this formula
was obtained. Using large k:s also means using a large amount of memory.
Limiting that, can be a good idea.
Moreover, your message starts speaking about "specific types of prime
numbers". Let's take Proth's numbers (
https://en.wikipedia.org/wiki/Proth_number ) i.e. numbers of the form
b*2^m+1 with b < 2^m.
Proth theorem suggest us to test a^(b*2^(m-1)).
Should we use lg(n)=m-1 in the formula above? Or should we use lg(b) instead?
What about even sparser exponents? Should we use 2*popcount(n) instead of
size_in_bits(n) to estimate the best window size? They should be almost
equivalent on average.
Ĝis,
m
--
http://bodrato.it/papers/
More information about the gmp-discuss
mailing list