PHP中gmp_legendre()函數詳解：如何判斷平方剩餘與二次非剩餘

gitbox 2025-06-10

在PHP 中， gmp_legendre()是GMP 擴展提供的一個函數，用於計算勒讓德符號（Legendre Symbol）。該函數在數論中有著廣泛應用，特別是在判斷一個整數是否是某個素數模下的平方剩餘時非常有用。

函數定義如下：

 int gmp_legendre(GMP $a, GMP $p)

其中， $a是被判斷的整數， $p是一個奇素數，兩個參數都必須是GMP 類型。

勒讓德符號是一種數學記號，用於表示某個整數是否為素數模下的二次剩餘。數學定義如下：

(a/p) = a ^(p?1)/2 mod p

這裡的a是任意整數， p是一個奇素數。其結果含義如下：

接下來我們通過兩個示例分別說明如何使用gmp_legendre()來判斷一個整數是否是平方剩餘或二次非剩餘。


$a = gmp_init(5);
$p = gmp_init(7);
$ls = gmp_legendre($a, $p);
if ($ls == 1) {
    echo "$a 是 $p 的平方剩餘";
} else {
    echo "$a 不是 $p 的平方剩餘";
}

輸出結果將會是：“5 是7 的平方剩餘”。


$a = gmp_init(5);
$p = gmp_init(11);
$ls = gmp_legendre($a, $p);
if ($ls == -1) {
    echo "$a 是 $p 的二次非剩餘";
} else {
    echo "$a 不是 $p 的二次非剩餘";
}

該代碼的輸出將會是：“5 不是11 的二次非剩餘”。

在調用gmp_legendre()函數時，需要注意以下幾點：

gmp_legendre()是一個實用的PHP 數學函數，適用於判斷整數是否是素數模下的平方剩餘。它不僅是學習PHP 與數論結合的好工具，也在密碼學、算法競賽等領域有實際應用價值。在使用時只需注意GMP 類型和參數要求，即可順利完成勒讓德符號的計算。