hermann on Tue, 13 Jun 2023 10:58:11 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Why is "x*Mod(1/y, p)" 28.7% faster than "Mod(x/y, p)" ? |
"##" measures time in milliseconds.So I use a very big prime (1million decimal digits) and its sqrtm1 = sqrt(-1) (mod p) to see 3-digit millisecond runtimes, from this Pari/GP script:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1.smallest_known_1million_digit_prime.gp323ms is 28.7% faster than 453ms, what is the reason that "x*Mod(1/y, p)" outperforms "Mod(x/y, p)"?
$ head /proc/cpuinfo | grep name model name : 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz $ gp-2.15 ... ? \r sqrtm1.smallest_known_1million_digit_prime.gp 1000000-digit prime p (3321925 bits) [M,V] = halfgcd(sqrtm1, p) *** last result computed in 282 ms. [x,y] = [V[2], M[2,1]] *** last result computed in 0 ms. sqrtm1 = lift(Mod(x/y, p)) *** last result computed in 451 ms. done, all asserts OK ? r = Mod(sqrtm1, p); ? sqrtm1^2 % p == p-1 %16 = 1 ? ? Mod(x/y, p) == r %17 = 1 ? ## *** last result computed in 453 ms. ? x*Mod(1/y, p) == r %18 = 1 ? ## *** last result computed in 323 ms. ? Regards, Hermann.