math/big: infinite loop in Int.ModSqrt for p = 1

[sylvainpelissier]

When passing p=1 in ModSqrt function, the code goes in infinite loop:

go/src/math/big/int.go

Line 940 in 3463852

for Jacobi(&n, p) != -1 {

The Jacobi symbol will gives one for ever.

For example: https://go.dev/play/p/37ExZ6Y-Hdp

[ALTree]

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.

[ALTree]

cc @griesemer @FiloSottile as per owners.

[gopherbot]

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

[hopehook]

Other examples of causing infinite loop in Int.ModSqrt:

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

[gopherbot]

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

[ianlancetaylor]

Rolling forward to 1.20.

[griesemer]

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

[rolandshoemaker]

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.

[gonzalochief]

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.