Solve $x^2 \equiv 6 (mod~97)$.
There is an algorithm in my book.
Initialization: I1: Determine the integers $k,m$ such that $p-1= m \cdot 2^k$, where $k \geq 1$ and m is odd.
Then $97 - 1 = 3 \cdot 2^5$ , so $k = 5$ and $m = 3$.
I2: Find $q$, a quadratic non-residue $(mod~97)$.
let $q = 5$, since $x^2 \equiv 5(mod~97)$.
I3: Let $b \equiv q^m(mod~p)$
Thus, $b \equiv 5^3(mod~97) \Leftrightarrow 125 \equiv 28 (mod~97)$.
I4: $t \equiv a^{[(m+1)/2]}(mod~p)$
Thus, $t \equiv 2^{[(3+1)/2]}(mod~97) \equiv 4 (mod~97)$.
I5: $n \equiv a^m (mod~p)$
So, $n \equiv 2^3 (mod~97) \equiv 8 (mod~97)$.
Then go to Main Routine.
Step 1: Find the least $j \geq 0$ such that $n^{2^j} \equiv 1 (mod~p)$
Step 2: If $j > 0$, go to step 3; if $j = 0$, go to step 6.
Step 3: Set $c \equiv b^{2^(k-j-1)} (mod~p)$.
Step 4: Replace $t$ by $tc$ and $n$ by $nc^2$.
Step 5: Go to step 1.
Step 6: Terminate. The solutions are $x \equiv \pm t(mod~p)$.
I don't really understand how to continue on the main Routine. Can someone please help me? Thank you.
First we can compute the Legendre symbol $(6/97)=(2/97)\cdot (3/97)=1\cdot 1=1$ using quadratic reciprocity, so we know that there is a solution. In fact, $54^2\equiv 6$ mod $97$. So $x=54$ is a solution. To find a solution, there are several algorithms, e.g., Pocklington's algorithm, Tonelli–Shanks algorithm, and others. Try one of these, and you will be successful. Copy a program of such an algorithm and modify it yourself, so that it prints every intermediate step.