主題
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。

參見

相伴, 尤拉判別法, 雅可比符號, 克羅內克符號, 勒讓德符號, 模乘法群, 積性函式, 二次, 二次非剩餘, 二次互反定理, 黎曼猜想

使用 探索

參考文獻

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.

在 中被引用

二次剩餘

請引用本文為

Weisstein, Eric W. "二次剩餘." 來自 --一個 資源. https://mathworld.tw/QuadraticResidue.html

學科分類