Legendre Symbol

We are given the prime $p$$p$ and the integers to find the quadratic residue in $p$$p$. The exact values of the prime is given in this link

Using Legendre Symbol and Euler's criterion, a number $a$$a$ can have three cases:

But when the prime is of the form $4k+3$$4k + 3$, then using Euler's criterion, if a number $a$$a$ indeed has a quadratic residue, then:

Multiply both sides by $a$$a$:

Denote the quadratic residue of $a$$a$ to be $r$$r$, by definition of quadratic residue:

Combining the two equations above, we have:

Taking the square root of both sides:

Hence, the positive quadratic residue of $r$$r$ is given by $a^{\frac{p+1}{4}}\mathrm{mod}p$$a^{\frac{p + 1}{4}} \mod p$

Otherwise, for the general case, we can use algorithms like Tonelli-Shanks and Cipolla's algorithm.

With this, we can easily solve the challenge by appending the following code to output.txt:

xxxxxxxxxx
print("Prime in form of 4k + 3:", p % 4 == 3)

for i in ints: 
    if pow(i, (p - 1) // 2, p) == 1:
        print(pow(i, (p + 1) // 4, p))