0

我目前正在研究 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= 列怎么办?是计算出来的。谁能帮我解释一下方法?

4

1 回答 1

2

右列显示小于21(模)的正整数,其二次余数等于左列中的值。因此,例如,整数1, 8, 1320都具有等于1模的二次余数21。这意味着它们的平方与1模一致21。例如,

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.

Finding these numbers is called finding square roots mod n. You can find them using the Chinese Remainder Theorem (assuming that you can factor the modulus).

于 2009-12-22T15:45:31.310 回答