Understanding and implementing the Tonelli-Shanks algorithm (1)

Introduction

Given an odd prime number $ p $ and an integer $ n $ that is not $ 0 $

x^2 \equiv n\ {\rm mod}\ p

If $ x \ not \ equiv 0 $ exists, then $ n $ is said to be ** Quadratic Residue ** modulo $ p $, if no such $ x $ exists. For example, $ n $ is said to be ** Quadratic Nonresidue **.

For example, $ n = 2 $ is a quadratic residue modulo $ p = 7 $ ($ x = 3 $ etc. is the solution), but $ n = 3 $ is a quadratic non-residue.

Now, it's not too difficult to determine if it's a quadratic residue.

First, define the ** Legendre symbol ** below.

\left(\begin{array} nn\\\ p \end{array}\right) := n^{\frac{p-1}{2}}

At this time, the following holds (the proof is a little difficult, so I will omit it here).

\left(\begin{array} nn\\\ p \end{array}\right) \equiv \begin{cases} 1 \ {\ rm mod} \ p \ Leftrightarrow n is quadratic residue \\\ -1 \ {\ rm mod} \ p \ Leftrightarrow n is a square non-remainder \end{cases}

In fact, if $ n = 2, p = 7 $

\left(\begin{array} nn\\\ p \end{array}\right) = 2^{\frac{7-1}{2}} = 8 \equiv 1\ {\rm mod}\ 7

And if $ n = 3, p = 7 $

\left(\begin{array} nn\\\ p \end{array}\right) = 3^{\frac{7-1}{2}} = 27 \equiv -1\ {\rm mod}\ 7

is.

In this article, I'll write about how to find the square root $ x $ if you find that $ n $ is a quadratic residue. Below, unless otherwise noted, all $ \ equiv $ are $ {\ rm mod} \ p $.

When p is a prime number divided by 4 and has a remainder of 3

In this case it's actually easy

x = \pm n^{\frac{p+1}{4}}

Is the answer. In fact, because it is assumed that $ n $ is a quadratic residue

\left(\begin{array} nn\\\ p \end{array}\right) = n^{\frac{p-1}{2}} \equiv 1

Is established,

x^2 = n^{\frac{p+1}{2}} = n^{\frac{p-1}{2}} \cdot n \equiv n

It will be. For example, if $ n = 2, p = 7 $

x = \pm 2^{\frac{7+1}{4}} = \pm 4 \equiv 3, 4\ {\rm mod}\ 7

It will be.

When p is a prime number that is left over by dividing by 4

This is the ** Tonelli-Shanks algorithm ** that we will cover this time.

Symbol naming is basically based on Wikipedia.

Step 1.

Divide $ p-1 $ until it divides by $ 2 $,

p-1 = Q \cdot 2^S

($ Q $ is an odd number and $ S $ is a positive integer).

Step 2.

Randomly choose a number that is ** square non-remainder ** modulo $ p $ and let it be $ z $.

I say "randomly", but since the number of quadratic residues and non-quadratic residues is half each between $ 1 $ and $ p-1 $, it is as small as $ z = 1, 2,… $. There is no problem in terms of calculation amount even if you hit all in order.

You can check if it is a quadratic reciprocity by using the Legendre symbol above, and of course by its definition.

z^{\frac{p-1}{2}} \equiv -1

is.

Step 3.

First, define the four numbers $ M_0, c_0, t_0, R_0 $ as follows.

\begin{cases} M_0 = S\\\ c_0 = z^Q\\\ t_0 = n^Q\\\ R_0 = n^{\frac{Q+1}{2}} \end{cases}

Step 4.

Make a loop statement and a recurrence formula as follows.

  1. If $ t_i \ equiv 1 $, then $ \ pm R_i $ is the square root of $ n $ and exits the loop statement.

  2. If not, update the value as follows:

\begin{cases} M_ {i + 1} = \ left (\ left (t_i \ right) ^ {2 ^ {j}} \ equiv The minimum j that satisfies 1, but 0

… It became hard to see at once.

I think there are such things, but I will explain them in order.

Preparation

We have set up a number of recurrence formulas, but in reality, the following holds regardless of the value of $ i $.

\begin{cases} \left(c_i\right)^{2^{M_i -1}} \equiv -1\\\ \\\ \left(t_i\right)^{2^{M_i -1}} \equiv 1\\\ \\\ \left(R_i\right)^2 \equiv t_i \cdot n \end{cases}

We will check in order using mathematical induction.

First formula

\left(c_i\right)^{2^{M_i -1}} \equiv -1

Indicates. First, if $ i = 0 $,

\left(c_0\right)^{2^{M_0 -1}} = \left(z^Q\right)^{2^{S -1}} = z^{Q \cdot 2^{S -1}}

Here, from Step 1, $ \ frac {p-1} {2} = Q \ cdot 2 ^ {S-1} $, so

z^{Q \cdot 2^{S -1}} = z^\frac{p-1}{2}

This is equal to $ -1 $ as we defined it in Step 2.

Next, we show that it holds for $ i + 1 $, assuming that it holds for $ i $.

\left(c_{i+1}\right)^{2^{M_{i+1} -1}} = \left(\left(c_i\right)^{2^{M_i - M_{i+1}}}\right)^{2^{M_{i+1} -1}} = \left(c_i\right)^{2^{M_i - 1}}

And since it is assumed that it holds for $ i $, this is also $ -1 $.

Second formula

\left(t_i\right)^{2^{M_i -1}} \equiv 1

Indicates. $ i = 0 $, but just like the first time

\left(t_0\right)^{2^{M_0 -1}} = \left(n^Q\right)^{2^{S-1}} = n^{Q \cdot 2^{S-1}} = n^\frac{p-1}{2}

This is equal to $ 1 $ from the definition of the Legendre symbol, as it is assumed that $ n $ is a quadratic residue.

Next, about $ i + 1 $, this is a slightly complicated proof.

\left(t_{i+1}\right)^{2^{M_{i+1} -1}} = \left(t_i \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}}\right)^{2^{M_{i+1} -1}} = \left(t_{i}\right)^{2^{M_{i+1} -1}} \cdot \left(c_{i}\right)^{2^{M_i -1}}

Now, pay attention to $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} $.

Square this to get $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1}}} $, which is $ 1 $ from the definition of $ M_ {i + 1} $ in Step 4. Is equal to.

So what is the number that squares to $ 1 $? Speaking of which, of course, there are only $ 1, -1 $, $ 2 $ [^ 2].

However, this time it will not be $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv 1 … ( \ ast $). Because, if this is true, "Step 4.

\ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 Minimum j

Is defined as $ M_ {i + 1} , but the above formula ( \ ast $) holds even with $ j = M_ {i + 1} -1 $. " Because it will occur.

Therefore, it becomes $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv -1 $.

Also, $ \ left (c_ {i} \ right) ^ {2 ^ {M_i -1}} $ has just been proved to be $ -1 $ from the $ 1 $ th expression, so as a result,

\left(t_{i}\right)^{2^{M_{i+1} -1}} \cdot \left(c_{i}\right)^{2^{M_i -1}} \equiv (-1) \cdot (-1) = 1

It will be.

Third formula

\left(R_i\right)^2 \equiv t_i \cdot n

Indicates. If $ i = 0 $,

\left(R_0\right)^2 = \left(n^{\frac{Q+1}{2}}\right)^2 = n^{Q+1} = n^Q\cdot n = t_0 \cdot n

Also, in the case of $ i + 1 $

\left(R_{i+1}\right)^2 = \left(R_i \cdot \left(c_i\right)^{2^{M_i - M_{i+1}-1}}\right)^2 = \left(R_i\right)^2 \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}}

It holds for $ i $, that is, it assumes $ \ left (R_i \ right) ^ 2 \ equiv t_i \ cdot n $.

\left(R_i\right)^2 \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}} \equiv t_i \cdot n \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}}

From the definition, $ t_ {i + 1} = t_i \ cdot \ left (c_i \ right) ^ {2 ^ {M_i --M_ {i + 1}}} $

t_i \cdot n \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}} = t_{i+1} \cdot n

Now we have proved all $ 3 $ expressions.

Resolve each question

First

What does "If $ t_i \ equiv 1 $, then $ \ pm R_i $ is the square root of $ n $"?

I will explain from. That said, the $ 3 $ th of the formula shown above

\left(R_i\right)^2 \equiv t_i \cdot n

It is clear if you look at it. In other words, if $ t_i $ is updated and it becomes $ t_i \ equiv 1 $ at some point, the above formula will be at that point.

\left(R_i\right)^2 \equiv n

Has the same meaning as.

next,

Will it be an infinite loop?

is. In other words, there may be no $ i $ such that $ t_i = 1 $.

To do that, we first need to explain the monotonous decrease of $ M_i $. $ M_ {i + 1} $

$ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv The minimum j that satisfies 1, but 0 <j <M_i $

But does such $ j $ really exist in $ 0 <j <M_i $ in the first place?

In fact, that's the $ 2 $ th formula shown above.

\left(t_i\right)^{2^{M_i -1}} \equiv 1

Guarantees. In other words, I searched $ j = 1, 2,… $, and even if I was unlucky and it was $ \ left (t_i \ right) ^ {2 ^ {j}} \ not \ equiv 1 $, $ j When = M_i -1 $, it becomes $ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 $ and satisfies the condition as $ M_ {i + 1} $.

Therefore, $ M_ {i + 1} $ is always less than $ M_i -1 $ (it is difficult to understand because there is a subscript ...).

M_{i+1} \leq M_i -1 < M_i

Now we can say the monotonous decrease of $ M_i $, and one day it will be $ M_ {end} = 1 $.

At this time, $ 2 $ of the formula shown above

\left(t_i\right)^{2^{M_i -1}} \equiv 1

With

\left(t_{end}\right)^{2^{M_{end} -1}} \equiv 1 \Rightarrow t_{end} \equiv 1

Now that the value of $ t $ is $ 1 $, we no longer loop infinitely.

Example

The example of Wikipedia is quoted as it is.

x^2 \equiv 5 \ {\rm mod}\ 41

Find $ x $ ($ n = 5, p = 41 $). First, using the Legendre symbol

\left(\begin{array} 55\\\ 41 \end{array}\right) = 5^{\frac{41-1}{2}} = 5^{20} \equiv 1\ {\rm mod}\ 41

And make sure that $ 5 $ is a quadratic residue.

Step 1.

Let $ p-1 = Q \ cdot 2 ^ S $, that is, $ 41-1 = 5 \ cdot 2 ^ 3 $. $ Q = 5, S = 3 $.

Step 2.

Choose the number $ z $ that is the square non-remainder. Using the Legendre symbol, $ 1, 2 $ is a quadratic residue, but $ 3 $ is

\left(\begin{array} 33\\\ 41 \end{array}\right) = 3^{\frac{41-1}{2}} = 3^{20} \equiv -1\ {\rm mod}\ 41

And since it is a square non-remainder, let $ z = 3 $.

Step 3.

\begin{cases} M_0 = S\\\ c_0 = z^Q\\\ t_0 = n^Q\\\ R_0 = n^{\frac{Q+1}{2}} \end{cases}

In other words

\begin{cases} M_0 = 3\\\ c_0 = 3^5 \equiv 38\\\ t_0 = 5^5 \equiv 9\\\ R_0 = 5^{\frac{5+1}{2}} \equiv 2 \end{cases}

Step 4.

From here, enter the loop until $ t_i = 1 $.

\begin{cases} M_ {i + 1} = \ left (\ left (t_i \ right) ^ {2 ^ {j}} \ equiv The minimum j that satisfies 1, but 0

When $ i = 0 $

\begin{cases} M_ {1} = \ left (\ left (9 \ right) ^ {2 ^ {j}} \ equiv 1 minimum j \ right) = 2 \\\ \\\ c_{1} = \left(38\right)^{2^{3 - 2}} \equiv 9\\\ \\\ t_{1} = 9 \cdot \left(38\right)^{2^{3 - 2}} \equiv 40\\\ \\\ R_{1} = 2 \cdot \left(38\right)^{2^{3 - 2-1}} \equiv 35 \end{cases}

When $ i = 1 $

\begin{cases} M_ {2} = \ left (\ left (40 \ right) ^ {2 ^ {j}} \ equiv 1 minimum j \ right) = 1 \\\ \\\ c_{2} = \left(9\right)^{2^{2 - 1}} \equiv 40\\\ \\\ t_{2} = 40 \cdot \left(9\right)^{2^{2 - 1}} \equiv 1\\\ \\\ R_{2} = 35 \cdot \left(9\right)^{2^{2 - 1-1}} \equiv 28 \end{cases}

Since $ t_2 = 1 $, the answer is $ \ pm R_2 = 28, 13 $.

In fact, $ 13 ^ 2 \ equiv 28 ^ 2 \ equiv 5 \ {\ rm mod} \ 41 $ does hold.

Implementation

It has become long, so I will turn it to here.

[^ 1]: A simple proof is $ i ^ 2 \ equiv (pi) ^ 2 $, so there are many variations of square numbers squared from $ 1 $ to $ p-1 $. There are also $ \ frac {p-1} {2} $ pieces. However, although I say "at most", there is no other duplication. This can be shown by reductio ad absurdum assuming $ i ^ 2 \ equiv (i + k) ^ 2 $.

[^ 2]: It holds only for the prime number $ p $. For composite numbers, $ x ^ 2 \ equiv 1 \ {\ rm mod} \ 24 $, which is $ x $, $ x = 1 $ and $ x = -1 \ equiv 23 $, as well as $ x = 5 $, etc. It will be considered. The reason why the prime number $ p $ has only $ x = \ pm 1 $ can be easily proved by factoring $ x ^ 2-1 $.

Recommended Posts

Understanding and implementing the Tonelli-Shanks algorithm (2)
Understanding and implementing the Tonelli-Shanks algorithm (1)
Behind the graph drawing algorithm and Networkx
Full understanding of the concepts of Bellman-Ford and Dijkstra
Euclidean algorithm and extended Euclidean algorithm
Understanding the Tensor (2): Shape
Rabbit and turtle algorithm
Understanding the meaning of complex and bizarre normal distribution formulas
Understanding and implementing the Tonelli-Shanks algorithm (2)
Understanding and implementing the Tonelli-Shanks algorithm (1)
GAN and VAE
[Introduction to Style GAN] Mayu Yu and anime smiled ♬
GAN: DCGAN Part3 --Understanding Wasserstein GAN
Python and DB: Understanding DBI cursors
About understanding the 3-point reader [...]
Touch the mock and stub