It does indeed go into an infinite loop. Thanks for reporting.

The method's documentation says

The modulus p must be an odd prime.

and 1 is not a prime, but going into an infinite loop is still not the best way to handle an invalid parameter.

cc @griesemer @FiloSottile as per owners.

Change https://go.dev/cl/394077 mentions this issue: math/big: infinite loop in Int.ModSqrt for p = 1

Other examples of causing infinite loop in Int.ModSqrt:

• p = -1
• p = -9
• p = 9

Change https://go.dev/cl/402457 mentions this issue: math/big: limit search for non-square in ModSqrt

Rolling forward to 1.20.

@rolandshoemaker There's a pending CL. Should this move to 1.23?

I think we can probably move this to backlog for now, it is unclear if we want to fix this with the particular method in the CL, and it's a relatively low priority problem.

Hi,
I was going through this issue, and the only way to avoid getting an error on the implementation of the Tonelli-Shanks algorithm is to verify and validate that p is in fact a prime number.
The Jacobi function works when p is an odd integer, but the TS algorithm requires that p belongs to a subset of of integers which are primes.
The issue with that validation is that there are only two ways to achieve it:

1. using a deterministic method, such as the AKS primality test. This method is computationally intensive, as it needs to compute polynomial modulus as part of the algorithm.
2. Using a probabilistic method, such as the one proposed on https://go.dev/cl/394077

I am working on an alternative using AKS, by implementing an IsPrime() function, but the proposed change above might be an acceptable solution. Please let me know if a deterministic solution is of interest. This would eliminate any edge case that could come from using a probabilistic method to test if p is prime.