Given an odd prime number $ p $ and an integer $ n $ that is not $ 0 $
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.
At this time, the following holds (the proof is a little difficult, so I will omit it here).
In fact, if $ n = 2, p = 7 $
And if $ n = 3, p = 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 $.
In this case it's actually easy
Is the answer. In fact, because it is assumed that $ n $ is a quadratic residue
Is established,
It will be. For example, if $ n = 2, p = 7 $
It will be.
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 $,
($ 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.
is.
Step 3.
First, define the four numbers $ M_0, c_0, t_0, R_0 $ as follows.
Step 4.
Make a loop statement and a recurrence formula as follows.
If $ t_i \ equiv 1 $, then $ \ pm R_i $ is the square root of $ n $ and exits the loop statement.
If not, update the value as follows:
… It became hard to see at once.
What does "If $ t_i \ equiv 1 $, then $ \ pm R_i $ is the square root of $ n $"?
Isn't it an infinite loop?
I want to actually code and move / Show me an example
I think there are such things, but I will explain them in order.
We have set up a number of recurrence formulas, but in reality, the following holds regardless of the value of $ i $.
We will check in order using mathematical induction.
Indicates. First, if $ i = 0 $,
Here, from Step 1, $ \ frac {p-1} {2} = Q \ cdot 2 ^ {S-1} $, so
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 $.
And since it is assumed that it holds for $ i $, this is also $ -1 $.
Indicates. $ i = 0 $, but just like the first time
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.
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
Is defined as $ M_ {i + 1}
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,
It will be.
Indicates. If $ i = 0 $,
Also, in the case of $ i + 1 $
It holds for $ i $, that is, it assumes $ \ left (R_i \ right) ^ 2 \ equiv t_i \ cdot n $.
From the definition, $ t_ {i + 1} = t_i \ cdot \ left (c_i \ right) ^ {2 ^ {M_i --M_ {i + 1}}} $
Now we have proved all $ 3 $ expressions.
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
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.
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.
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 ...).
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
With
Now that the value of $ t $ is $ 1 $, we no longer loop infinitely.
The example of Wikipedia is quoted as it is.
Find $ x $ ($ n = 5, p = 41 $). First, using the Legendre symbol
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
And since it is a square non-remainder, let $ z = 3 $.
Step 3.
In other words
Step 4.
From here, enter the loop until $ t_i = 1 $.
When $ i = 0 $
When $ i = 1 $
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.
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