The Shanks-Tonelli algorithm requires n to be a quadratic NONresidue, but the existing code was searching for any n that IS a quadratic residue. The comment below already reflects the correct version, so this mistake was probably just a typo.
If it would help, I'm happy to add a minimal demo proving it works now and didn't before. (Where would I put that?)
bqi343
commented
2 years ago
The Shanks-Tonelli algorithm requires n to be a quadratic NONresidue, but the existing code was searching for any n that IS a quadratic residue. The comment below already reflects the correct version, so this mistake was probably just a typo.
If it would help, I'm happy to add a minimal demo proving it works now and didn't before. (Where would I put that?)