主题
Search

二次剩余

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

如果存在一个整数 0<x<p 使得

x^2=q (mod p),
(1)

即，同余式 (1) 有解，则称 q 为模 p 的二次剩余。 请注意，通常从二次剩余列表中排除平凡情况 q=0 (例如，Hardy 和 Wright 1979, p. 67)，因此，模 n 的二次剩余的数量比模 n 的平方数的数量少一个。 然而，其他来源将 0 包含为二次剩余。

如果同余式没有解，则称 q 为模 p 的二次非剩余。 Hardy 和 Wright (1979, pp. 67-68) 使用简写符号 q R p 和 q N p，表示 q 分别是二次剩余或非剩余。

在实践中，只需将范围限制为 0<x<=|_p/2_|，其中 |_x_| 是向下取整函数，因为对称性 (p-x)^2=x^2 (mod p)。

例如，4^2=6 (mod 10)，所以 6 是模 10 的二次剩余。 模 10 的所有二次剩余由 1、4、5、6 和 9 给出，因为

1^2=1 (mod 10) 2^2=4 (mod 10) 3^2=9 (mod 10)
(2)
4^2=6 (mod 10) 5^2=5 (mod 10) 6^2=6 (mod 10)
(3)
7^2=9 (mod 10) 8^2=4 (mod 10) 9^2=1 (mod 10),
(4)

使得数字 2、3、7 和 8 成为模 10 的二次非剩余。

Quadratic residues

下面给出了 p<=20 的二次剩余列表 (OEIS A046071)，列表中未包含的那些数字 <p 是 p 的二次非剩余。

p二次剩余
1(无)
21
31
41
51, 4
61, 3, 4
71, 2, 4
81, 4
91, 4, 7
101, 4, 5, 6, 9
111, 3, 4, 5, 9
121, 4, 9
131, 3, 4, 9, 10, 12
141, 2, 4, 7, 8, 9, 11
151, 4, 6, 9, 10
161, 4, 9
171, 2, 4, 8, 9, 13, 15, 16
181, 4, 7, 9, 10, 13, 16
191, 4, 5, 6, 7, 9, 11, 16, 17
201, 4, 5, 9, 16
QuadraticResidueNumbers

对于 n=1, 2, ...，模 n 的二次剩余的数量为 0, 1, 1, 1, 2, 3, 3, 2, 3, 5, 5, 3, 6, 7, 5, 3, ... (OEIS A105612)。

Largest quadratic residue binary plot

对于 p=2, 3, ...，最大的二次剩余为 1, 1, 1, 4, 4, 4, 4, 7, 9, 9, 9, 12, 11, ... (OEIS A047210)。

在处理二次剩余时必须小心，因为显然有时也使用略有不同的定义。 例如，Stangl (1996) 采用了二次剩余的明显非标准定义，将其定义为满足 0<x<p 且 x^2=q (mod p) 的整数 x，并且 x 与 p 互质。 因此，此定义排除了非单位元 (模 p)。 根据此定义，对于 n=1, 2, ...，模 n 的二次剩余如下所示 (OEIS A096103)，它们的数量由 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... 给出 (OEIS A046073)，并且 Z_n 中平方数 s(n) 的数量与 Z_n 中二次剩余 q(n) 的数量有关，关系如下：

q(p^n)=s(p^n)-s(p^(n-2))
(5)

对于 n>=3 和奇素数 p (Stangl 1996)。 （请注意，q 和 s 都是积性函数。）

n非单位平方 (模 n)
21
31
41
51, 4
61
71, 2, 4
81
91, 4, 7

给定一个奇素数 p 和一个整数 a，则勒让德符号由下式给出

(a/p)={1 if a is a quadratic residue mod p; -1 otherwise.
(6)

如果

r^((p-1)/2)=+/-1 (mod p),
(7)

则 r 是二次剩余 (+) 或非剩余 (-)。 这可以理解为，如果 r 是 p 的二次剩余，那么存在一个平方 x^2 使得 r=x^2 (mod p)，因此

r^((p-1)/2)=(x^2)^((p-1)/2)=x^(p-1) (mod p),
(8)

并且根据费马小定理，x^(p-1) 与 1 (模 p) 同余。

给定同余式中的 p 和 q

x^2=q (mod p),
(9)

对于某些特殊形式的 p 和 q，可以显式计算 x

x={q^(k+1) (mod p) for p=4k+3; q^(k+1) (mod p) for p=8k+5 and q^(2k+1)=1 (mod p); 1/2(4q)^(k+1)(p+1) (mod p) for p=8k+5 and q^(2k+1)=-1 (mod p).
(10)

例如，第一种形式可用于找到给定二次剩余 q=1, 3, 4, 5 和 9 (模 p=11，其中 k=2) 的 x，而第二种和第三种形式确定给定二次剩余 q=1, 3, 4, 9, 10 和 12 (模 p=13，其中 k=1) 和 q=1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36 (模 p=37，其中 k=4) 的 x。

更一般地，设 q 是模奇素数 p 的二次剩余。 选择 h 使得勒让德符号 (h^2-4q/p)=-1。 然后定义

V_1=h
(11)
V_2=h^2-2q
(12)
V_i=hV_(i-1)-qV_(i-2) for i>=3,
(13)

给出

V_(2i)=V_i^2-2q^i
(14)
V_(2i+1)=V_iV_(i+1)-hq^i,
(15)

二次同余式的解是

x=1/2(p+1)V_((p+1)/2) (mod p).
(16)

Schoof (1985) 给出了一种查找 x 的算法，运行时间为 O(ln^(10)n) (Hardy et al. 1990)。 可以使用 Wolfram 语言命令解决同余式PowerMod[q, 1/2, p].

下表给出了以给定数字 d 作为二次剩余的素数。

d素数
-624k+1,5,7,11
-520k+1,3,7,9
-36k+1
-28k+1,3
-14k+1
28k+/-1
312k+/-1
510k+/-1
624k+/-1,5

找到平方根 sqrt(D) 的连分数并使用关系式

Q_n=(D-P_n^2)/(Q_(n-1))
(17)

对于第 n 个收敛项 P_n/Q_n 给出

P_n^2=-Q_nQ_(n-1) (mod D).
(18)

因此，-Q_nQ_(n-1) 是 D 的二次剩余。 但由于 Q_1=1, -Q_2 是二次剩余，-Q_2Q_3 也必须是。 但由于 -Q_2 是二次剩余，所以 Q_3 也是，我们看到 (-1)^(n-1)Q_n 都是 D 的二次剩余。 此方法不能保证产生所有二次剩余，但在 D 很大的情况下，通常可以产生几个小的二次剩余，从而能够分解 D。

参见

相伴, 欧拉判别法, 雅可比符号, 克罗内克符号, 勒让德符号, 模乘法群, 积性函数, 二次, 二次非剩余, 二次互反定理, 黎曼猜想

使用 Wolfram|Alpha 探索

参考文献

Burgess, D. A. "The Distribution of Quadratic Residues and Non-Residues." Mathematika 4, 106-112, 1975.Burton, D. M. Elementary Number Theory, 4th ed. New York: McGraw-Hill, p. 201, 1997.Courant, R. 和 Robbins, H. "Quadratic Residues." §2.3 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 38-40, 1996.Guy, R. K. "Quadratic Residues. Schur's Conjecture" and "Patterns of Quadratic Residues." §F5 和 F6 in Unsolved Problems in Number Theory, 2nd ed. New York:Springer-Verlag, pp. 244-248, 1994.Hardy, K.; Muskat, J. B.; 和 Williams, K. S. "A Deterministic Algorithm for Solving n=fu^2+gv^2 in Coprime Integers u and v." Math. Comput. 55, 327-343, 1990.Hardy, G. H. 和 Wright, E. M. "Quadratic Residues." §6.5 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 67-68, 1979.Hilton, P.; Holton, D.; 和 Pedersen, J. Mathematical Reflections in a Room with Many Mirrors. New York:Springer-Verlag, p. 43, 1997.Jones, G. A. 和 Jones, J. M. "Quadratic Residues." Ch. 7 in Elementary Number Theory. Berlin:Springer-Verlag, pp. 119-141, 1998.Nagell, T. "Theory of Quadratic Residues." Ch. 4 in Introduction to Number Theory. New York: Wiley, pp. 115 和 132-155, 1951.Niven, I. 和 Zuckerman, H. An Introduction to the Theory of Numbers, 4th ed. New York: Wiley, p. 84, 1980.Rosen, K. H. Ch. 9 in Elementary Number Theory and Its Applications, 3rd ed. Reading, MA: Addison-Wesley, 1993.Schoof, R. "Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p." Math. Comput. 44, 483-494, 1985.Séroul, R. "Quadratic Residues." §2.10 in Programming for Mathematicians. Berlin:Springer-Verlag, pp. 17-18, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 63-66, 1993.Sloane, N. J. A. 序列 A046071, A046073, A047210, 和 A096103 in "整数序列在线百科全书"。Stangl, W. D. "Counting Squares in Z_n." Math. Mag. 69, 285-289, 1996.Tonelli, A. "Bemerkung über die Auflösung quadratischer Congruenzen." Göttingen Nachr., 344-346, 1891.Wagon, S. "Quadratic Residues." §9.2 in Mathematica in Action. New York: W. H. Freeman, pp. 292-296, 1991.Wedeniwski, S. "Primality Tests on Commutator Curves." Dissertation. Tübingen, Germany, 2001. http://www.hipilib.de/prime/primality-tests-on-commutator-curves.pdf.

在 Wolfram|Alpha 中被引用

二次剩余

请引用本文为

Weisstein, Eric W. "二次剩余." 来自 MathWorld--一个 Wolfram Web 资源. https://mathworld.net.cn/QuadraticResidue.html

学科分类