私は現在 Fiege-Fiat Shamir を研究しており、二次剰余にこだわっています。私が考えている概念は理解していますが、それらを計算する方法がわかりません。たとえば、どのように計算しますか
v | x^2 = v mod 21 | x =?
___________________________________
1 x^2 = 1 mod 21 1, 8, 13, 20
4 x^2 = 4 mod 21 2, 5, 16
7 x^2 = 7 mod 21 7, 14
9 x^2 = 9 mod 21 3, 18
15 x^2 = 15 mod 21 6, 15
16 x^2 = 16 mod 21 4, 10, 11, 17
18 x^2 = 18 mod 21 9, 12
列 x=? の意味がわかりません。計算されます。誰かが方法を説明するのを手伝ってくれますか?
21右側の列は、左側の列の値と等しい二次剰余をもつ (モジュラス)より小さい正の整数を示します。したがって、たとえば、整数1, 8, 13およびすべて はmodulo20に等しい二次剰余を持ちます。これは、それらの平方がmoduloに合同であることを意味します。例えば、121121
8 * 8 = 64 = 63 + 1 = 21 * 3 + 1 =. 0 + 1 mod 21 =. 1 mod 21
=.ここで、合同モジュロを表すために使用してい21ます。同様に、
13 * 13 = 169 = 168 + 1 = 21 * 8 + 1 =. 0 + 1 mod 21 =. 1 mod 21
と
20 * 20 = 400 = 399 + 1 = 21 * 19 + 1 =. 0 + 1 mod 21 =. 1 mod 21.
これらの数を見つけることは、平方根 mod を見つけることと呼ばれnます。中国剰余定理を使用してそれらを見つけることができます(モジュラスを因数分解できると仮定して)。