Last updated in 2016:
https://gmplib.org/devel/GMPng
What happened to "Modexp, bᵈ mod m" section topic: "Use special code for
when b is much smaller than m, avoiding REDC representation and table
precomputation."
For my application m is a 100Ks digits prime "=1 (mod 4)", d=p/4, and b
is smallest quadratic non-resiidue of m. That can be computed quickly
with kronecker symbol:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/c%2B%2B/sqrtm1.cc
// deterministic fast search for smallest quadratic non-residue
b = 2;
while (mpz_kronecker(b.get_mpz_t(), p.get_mpz_t()) != -1) {
mpz_nextprime(b.get_mpz_t(), b.get_mpz_t());
}
std::cerr << "smallest quadratic non-residue prime: " << b << "\n";
Most times smallest quadratic non-residue is single digit, or lower
2-digit prime.
It took 26h to compute that "powm()" for smallest known 1million digit
prime with i7_11850H; expected runtime with 7600X CPU is 19.2h.
https://github.com/Hermann-SW/QuadraticRegression/blob/master/sqrtm1___.py
pi@pi400-64:~/QuadraticRegression $ python sqrtm1___.py
y = 7.950524562496551e-08x² - 0.011528213946191843x + 914.8718066871961
? f(x) = 7.950524562496551e-08*x^2 - 0.011528213946191843*x +
914.8718066871961 %11 =
(x)->7.950524562496551e-08*x^2-0.011528213946191843*x+914.8718066871961
? f(1000000)/3600
%12 = 19.136639857072461972222222222222222222
?
But the number I am really interested in (largest known prime "=1 (mod
4)", rank 9: https://t5k.org/primes/lists/all.txt)
8 2^32582657-1 9808358 G9 2006 Mersenne 44
9 10223*2^31172165+1 9383761 SB12 2016
10 2^30402457-1 9152052 G9 2005 Mersenne 43
would take roughly 80 days to compute sqrtm1 (above "powm()")
sequentially with 7600X ...
? f(9383761)/3600
%13 = 1914.8802571909706918476056601972222222
? f(9383761)/3600/24
%14 = 79.786677382957112160316902508217592593
?
Any other ideas on speeding up "powm(_, qnr, p/4, p)" with millions
digits prime p somehow?
Regards,
Hermann.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
