But what values of p should we even check?
Using Euler's Criterion we have that: 13^((p-1)/2)≡ 1 mod p if there is an x such that x^2 ≡ 13 mod p
Equivalently this is when the Legendre symbol is equal to 1
Now we know what values of p to check and furthermore x^2 ≡ 13 mod p has a solution.
A common technique to extend this to solve x^2 ≡ 13 mod p^2 is the following:
Solve x^2 ≡ 13 mod p using Tonelli-shanks algorithm
Use Hensel's lemma to lift it to get the solution x^2 ≡ 13 mod p^2
After reading the Tonelli-shanks algorithm wiki page, I found https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/ which implements the algorithm along with some minor improvements, I will be adding both the Tonelli-Shanks algorithm and the Legendre symbol to my essential functions
Originally I solved the problem using the below method, but I didn't fully understand what I was doing. I took Number Theory this semester and learned why this method works and how to do it in a manner that I believe is more understandable! I will add the new method below
Using f(x) = x^2 - 13, and e = 2, we can easily find solutions to x^2 = 13 (mod p) and then find solutions for n
Enter an integer (yourinput)
Code will output SR(yourinput)