Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/rsa_test.gp

Last active September 5, 2023 19:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Hermann-SW/50514eaf06b4d91ec6bcee5e49732dff to your computer and use it in GitHub Desktop.
Save Hermann-SW/50514eaf06b4d91ec6bcee5e49732dff to your computer and use it in GitHub Desktop.
Download ZIP
PARI/GP test script wrt kronecker(), chinese(), and prime factors of rsa numbers
Raw
rsa_test.gp
\r RSA_numbers_factored.gp
test(v)=
{
if(#v<4,
break());
my([l,n,p,q]=v,pnr,qnr,sqrtm1);
if ((p%4!=1)||(q%4!=1),
break());
forprime(t=2,oo,
if(kronecker(t,p)==-1,
pnr=t;break()));
forprime(t=2,oo,
if(kronecker(t,q)==-1,
qnr=t;break()));
sqrtm1=chinese(Mod(pnr,p)^((p-1)/4),Mod(qnr,q)^((q-1)/4));
print(l," ",centerlift(sqrtm1^2));
};
{
foreach(rsa,v,
test(v));
}
@Hermann-SW
Copy link
Author

Hermann-SW commented Sep 5, 2023 •
edited

https://pari.math.u-bordeaux.fr/archives/pari-users-2309/msg00000.html

hermann@i7-11850h:~/RSA_numbers_factored/pari$ gp -q < rsa_test.gp 
validate(rsa): ✓
59 -1
129 -1
180 -1
230 -1
768 -1
hermann@i7-11850h:~/RSA_numbers_factored/pari$

Uses this repo:
https://github.com/Hermann-SW/RSA_numbers_factored

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment