Re: Pari/GP "halfgcd()" implementation

[hermann@stamm-wilbrandt.de]

On 2023-06-08 23:32, Vincent Delecroix wrote:
> If you want to use PARI/GP from Python you might want to have
> a look at https://pypi.org/project/cypari2/
>
> > > > import cypari2
> > > > pari = cypari2.Pari()
> > > > pari.halfgcd(123612348, 1342457)
> [[38, -3499; -101, 9300], [12181, 2952]~]
>
> Best
> Vincent
Thank you, that is cool !

I did "pip install cysignals" as required o project page.
But "pip install cypari2" still failed.
"sudo apt search cypari" showed that python3-cypari2 is available under 
64bit Raspberry PiOS.
After "sudo apt install python3-cypari2" all is fine.

Works (a bit confusing is that Python indices are 0-based, while Pari 
indices are 1-based):

pi@pi400-64:~/RSA_numbers_factored/python $ python -q
> > > from RSA_numbers_factored import RSA, digits
> > > l,n,p,q = R.get(129)[0:4]
> > > [x,y] = R.square_sums(129)[0]
> > > x**2 + y**2 == n
True
> > > sqrtm1 = x * pow(y, -1, n) % n
> > > sqrtm1**2 % n == n-1
True
> > > import cypari2
> > > pari = cypari2.Pari()
> > > [M,V] = pari.halfgcd(sqrtm1, n)
> > > [x,y] = [V[1],M[1,0]]
> > > x**2 + y**2 == n
True
> > > digits(n)
129
> > >