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

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

Note that 100% of computing time is spent factoring the modulus. If many
square roots must be computed for the same modulus, then the factorization
should be precomputed.

We have an internal function for this (Zn_ispower), underlying issquare:

install(Zn_ispower, "lGGGD&");
N = 71641520761751435455133616475667090434063332228247871795429;
faN = factor(N);

? Zn_ispower(41, faN, 2, &r);
%1 = 1  \\ it's a square

? r
%2 = Mod(19404231649676781033243368819091487975254979923473930822898, ...)

? r^2
%3 = Mod(41, ...)

Cheers,

      K.B.

* hermann@stamm-wilbrandt.de [2024-10-01 10:38]:
> 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.
> 

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/