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.gp

323ms 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.