Possible to optimize for base 2 fermat primality test using shifts?

[Marco Bodrato]

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/