Re: What is the Mathematica "PowerMod[a, 1/2, m]" equivalent in PARI/GP?

[hermann@stamm-wilbrandt.de]

On 2024-10-01 07:38, Loïc Grenié wrote:
> > PowerMod[] can deal with non-prime modulus — how can this be
> > computed with PARI/GP?
> >
> > pi@raspberrypi5:~ $ time wolframscript -code
> "PowerMod[41,1/2,71641520761751435455133616475667090434063332228247871795429]"
> > 15567422879070002639383923810785206745982804843948310703484
> >
> > real    0m59.452s
> > user    0m0.341s
> > sys     0m0.071s
> > pi@raspberrypi5:~ $
>
>      Presumably issquare is your solution.
>
> my(r);issquare(Mod(41,71641520761751435455133616475667090434063332228247871795429),&r);r
> cpu time = 2,615 ms, real time = 2,644 ms.
> %1 = Mod(19404231649676781033243368819091487975254979923473930822898,
> 71641520761751435455133616475667090434063332228247871795429)
>
>       Best,
>
>              Loïc
Thank you, exactly what I searched for.
And PARI/GP is much faster than Mathematica for that computation!

First I overclocked my 2.4GHz default frequency Raspberry Pi5 to 3GHz.
Mathematica does now need 50 seconds instead of 59 seconds before:

pi@raspberrypi5:~/RSA_numbers_factored/pari $ freq
min=cur=3000000=max
pi@raspberrypi5:~/RSA_numbers_factored/pari $ time wolframscript -code 
"PowerMod[41,1/2,71641520761751435455133616475667090434063332228247871795429]"
15567422879070002639383923810785206745982804843948310703484

real	0m50.558s
user	0m0.360s
sys	0m0.063s
pi@raspberrypi5:~/RSA_numbers_factored/pari $


As said, PARI/GP is much faster(!), only 4 seconds:

pi@raspberrypi5:~/RSA_numbers_factored/pari $ gp -q 
RSA_numbers_factored.gp
? [,n,p,q]=RSA.get(59)
[59, 71641520761751435455133616475667090434063332228247871795429, 
200429218120815554269743635437, 357440504101388365610785389017, [2, 2; 
3, 2; 946790500267, 1; 5880369817360553, 1], [2, 3; 41, 1; 149, 1; 
1356913, 1; 2739881, 1; 1967251783951, 1]]
? issquare(Mod(41,n),&r);
? ##
  ***   last result: cpu time 4,167 ms, real time 4,168 ms.
? lift(r^2)
41
? #digits(n)
59
?

pi@raspberrypi5:~/RSA_numbers_factored/pari $


Having a (faster) method for that computation on PARI/GP opens up all my 
x86_64 CPUs
including my faster AMD 7950X PC. While Mathematica use is free on 
Raspberry single
board computers, Raspberry CPUs are much slower than the x86_64 CPUs I 
have and with
PARI/GP they can do the computations much faster.


Regards,

Hermann.