Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm to find square root of a quadratic residue mod p

  1. Feb 14, 2015 #1
    I'm going through an explanation in a number theory book about Tonelli's algorithm to find the square roots of a quadratic residue modulo ##p## where ##p## is prime, i.e. I want to solve ##x^2 \equiv a \pmod{p}## with ##(\frac{a}{p}) = 1##. The book goes as follows:

    Let ##p - 1 = 2^s t##, where ##t## is odd.

    By Euler's criterion, ##A^{2^{s-1}} \equiv 1## where ##A = a^t##, so the order of ##A## divides ##2^{s-1}##.

    Let ##d## be a quadratic nonresidue mod ##p## and ##D = d^t##.

    By Euler's criterion, ##D^{2^{s-1}} \equiv -1## so the order of ##D## is exactly ##2^s##. Similarly, the order of ##D^{-1}## is ##2^s##.

    Since the group ##U(p)## of units mod ##p## is cyclic, ##A## is in ##\langle D^{-1} \rangle##, the cyclic subgroup generated by ##D^{-1}##. Moreover, ##A \equiv D^{-2u}## where ##u## is some integer ##0 \leq u < 2^{s-1}##.

    Then, ##a^tD^{2u} \equiv 1##, so ##a^{t+1}D^{2u} \equiv a##. Thus, a solution is ##x \equiv a^{(t+1)/2}D^u##.


    I got stuck where it says ##A## is an even power of ##D^{-1}##. Can someone explain this?
     
  2. jcsd
  3. Feb 18, 2015 #2
    Note1 : the sentence "since the group U(p) of units modulo p is cyclic" is very confusing in my opinion. The right justification should be: if w is a primitive root modulo p, then [itex]w^t[/itex] is of order [itex]2^s[/itex] and generates all the elements of order dividing [itex]2^s[/itex]. So, the group of all such element is cyclic of order [itex]2^s[/itex]. Since D is of order [itex]2^s[/itex], [itex]D^{-1}[/itex] is a generator of this group.

    Note2 : the answer to your question is: let [itex]A = D^{-\alpha}[/itex], with [itex]0\leq \alpha\leq 2^s[/itex]. Since the order of A divides [itex]2^{s-1}[/itex], say [itex]2^i[/itex], and since the order of [itex]D^{-1}[/itex] is [itex]2^{s}[/itex], there holds [itex]-\alpha 2^i = k2^s[/itex], with [itex]i\leq s-1[/itex]. Hence [itex]\alpha[/itex] is multiple of 2, say [itex]\alpha = 2u[/itex], with [itex]0\leq 2u\leq 2^s[/itex]. Hence [itex]u\leq 2^{s-1}.[/itex]
     
    Last edited: Feb 18, 2015
  4. Feb 19, 2015 #3
    Thank you for clarifying.

    I wonder why my book made that last inequality a strict one, since that would just lead to ##x = - a^{(t+1)/2}## which is also a solution.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Algorithm to find square root of a quadratic residue mod p
Loading...