勒讓德符號（legendre symbol）是一種數(shù)論工具，它用于表示模p的二次剩余與二次非剩余。
18世紀，法國數(shù)學(xué)家阿德利昂·瑪利·埃·勒讓德（Adrien-Marie Legendre）在研究二次剩余的過程中，引入了一種記號表示二次剩余，該記號后來被稱作勒讓德符號。在這一時期，其他數(shù)學(xué)家也對勒讓德符號進行了研究，如萊昂哈德·歐拉和高斯等人。
勒讓德符號有一系列性質(zhì)，如互轉(zhuǎn)律等。相關(guān)定理包括費馬小定理、歐拉判別準則、高斯引理等，其中歐拉準則可以用于性質(zhì)的證明。應(yīng)用勒讓德符號的性質(zhì)，可以求解勒讓德符號以及同余方程。雅可比符號為勒讓德符號的推廣形式。此外，該符號還可以作為設(shè)計密碼的一個重要工具，應(yīng)用在概率密碼系統(tǒng)、塑性型檢測、因數(shù)分解等領(lǐng)域。
定義
勒讓德符號有下列定義：如果，則；如果，則；如果,則。
其中，叫作勒讓德符號的分子，叫作它的分母。
簡史
18世紀，法國數(shù)學(xué)家阿德利昂·瑪利·埃·勒讓德在研究二次剩余的過程中，引入了一種記號表示二次剩余，該記號后來被稱作勒讓德符號。1785年，他獨自發(fā)現(xiàn)了互轉(zhuǎn)律，并證明了其中的一部分。798年，勒讓德出版《數(shù)論隨筆》(Essai sur la théorie des nombres)，并于1808年再版此書，書名是《數(shù)論》(Théorie des nombres)，在1830年增補了第三版，分為兩卷。
關(guān)于勒讓德符號的性質(zhì)，其他數(shù)學(xué)家在同一時期進行了研究。長城歐拉已經(jīng)在1783年發(fā)現(xiàn)了互轉(zhuǎn)率，但沒有給出嚴密的證明。直到1796年，高斯第一次給出了互轉(zhuǎn)率的嚴格證明，并認為該定律是平方剩余的基本定理。
相關(guān)概念
二次剩余
二次剩余也稱平方剩余，二次非剩余也稱平方非剩余，其定義為：若并且有解，就稱是模的二次剩余，記作，否則稱是模的二次非剩余，記作。其中，表示所有模的二次剩余的集合，表示所有模的二次非剩余的集合。
同余
同余是數(shù)論中的基本概念，其定義為：給定一個正整數(shù),把它叫作模，如果用去除任意兩個整數(shù)與所得的余數(shù)相同，則稱， 關(guān)于模同余，記作；否則稱，關(guān)于模不同余。
二次同余式是含有未知數(shù)的高次同余式中的簡單情況。
當時，同余式 可以化作一個二項的二次同余式，其中。該式可寫為 。該同余式可能是可解的，也可能是不可解的。假使它至少有一個解，那么叫作模的平方剩余，否則，叫作平方非剩余。
性質(zhì)
勒讓德符號有如下6種常用性質(zhì)，可以用于相關(guān)的數(shù)論計算。
性質(zhì)1
假使，那么。
證明：假設(shè)，于是有。因此，和或者同時是模的平方剩余，或者同時是非平方剩余。
性質(zhì)2
。
證明：根據(jù)長城歐拉判別法則可知，同余式的解是。
性質(zhì)3
。
證明：假使，那么，根據(jù)歐拉判別法則，有。假使，那么，根據(jù)歐拉判別法則，有。
性質(zhì)4
。
證明：假設(shè)是模的平方剩余，而是模的平方非剩余，則：。根據(jù)歐拉判別法則有：，。其中，，。
把這些同余式逐項相乘，可以得到。再根據(jù)歐拉判別法則，當時，有，當 時，有，即。
再由，得。
性質(zhì)5
。
證明：把公式變形后，可得。
假定，則，且當時，有，因此有。
性質(zhì)6
假使,是兩個不同的奇素數(shù)，那么。該性質(zhì)也叫“平方剩余的反轉(zhuǎn)定律”或"互轉(zhuǎn)律”。
證明：假設(shè)，其中是一素數(shù)。于是是一偶數(shù)，因此，類似可得,則。
之后可證得，即，等式兩邊乘以，再由，可得。
說明：對于給定的整數(shù)，求素數(shù)，使是模的平方剩余或非平方剩余的問題，利用性質(zhì)6解決起來十分方便。這是因為，性質(zhì)6可以把求模的問題轉(zhuǎn)化為給定模求，使是模的平方剩余或非平方剩余的問題。
相關(guān)定理
費馬小定理
皮耶·德·費瑪小定理可以用來計算余數(shù)問題，該定理由費馬（Pierre de Fermat）于1640年提出，1736年由萊昂哈德·歐拉證明。
其定義為：如果是質(zhì)數(shù)，而整數(shù)不是的倍數(shù)，那么。
該定理可變形為：若是質(zhì)數(shù)，則對任意整數(shù)，都有。
歐拉判別準則
歐拉準則是判別二次剩余的準則，又叫歐拉判別條件，上述勒讓德符號的性質(zhì)大多可以通過該準則進行證明。
其內(nèi)容為：若，則是模的平方剩余的充分必要條件是；而是模的平方非剩余的充分必要條件是，且若是模的平方剩余，則形如的二次同余式恰好有兩個解。
高斯引理
高斯引理可以代替萊昂哈德·歐拉判別法，來計算勒讓德符號得值。高斯引理的描述為：假使為奇素數(shù)，。若各數(shù)模的最小正剩余中，恰有個大于，則。
其他素數(shù)相關(guān)定理
定理1：設(shè)是相異的奇素數(shù)，當或者時，如果，則；當或時，如果，則；當或時，如果，但不滿足，則。
定理2：同余式有解的必要條件是：當時，；當時，并且。若上述條件成立，則有解，并且當或1時，解數(shù)是；當時，解數(shù)是；當時，解數(shù)是。
定理3：若，則。
定理4：設(shè)是形如的質(zhì)數(shù)，，則是雙數(shù)，。
定理5：若，，則為模的一個簡化剩余系。
計算
求解勒讓德符號
題目：計算勒讓德符號的值。
解答：用高斯引理來計算。
，求出，，，，，，，，，，，，，，。
這些數(shù)被除時所得的余數(shù)分別為：。
其中，共有個余數(shù)是大于的，所以。
求解同余方程
題目：求解同余式。
解答：因，因此有四解。把寫成，代入原同余式后得到，由此得，故是適合的一切整數(shù)，再代入同余式得到。由此得，故是適合的一切整數(shù)。同理得是適合的一切整數(shù)。
因此，是所求的四個解。
相關(guān)推廣
雅可比符號是勒讓德符號的推廣，其等式的右端就是勒讓德符號。雅可比符號的具體描述如下：設(shè)奇數(shù)，，是素數(shù)，定義，則稱為雅可比符號。當本身是奇素數(shù)時，雅可比符號即為勒讓德符號。在使用雅可比符號計算勒讓德符號時，不用求素因子的分解。
雅可比符號具有類似于勒讓德符號的一些性質(zhì)。
性質(zhì)1：假設(shè)，那么。
性質(zhì)2：。
性質(zhì)3：。
性質(zhì)4：。
性質(zhì)5：。
應(yīng)用
數(shù)學(xué)
勒讓德符號常應(yīng)用于不定方程的求解，如，對于不定方程，有正整數(shù)解的充分與必要條件是，即或。另外，丟番圖方程的正整數(shù)解，一直是國內(nèi)外學(xué)者熱衷的研究題目。在求解該方程時，可以使用勒讓德符號等相關(guān)內(nèi)容，使用數(shù)學(xué)軟件證明該不定方程沒有正整數(shù)解，最終可得出它全部的16組整數(shù)解。
密碼學(xué)
勒讓德符號是設(shè)計密碼的一個重要工具，常被應(yīng)用在概率密碼系統(tǒng)、塑性型檢測、因數(shù)分解等領(lǐng)域。
例如，在BBS偽隨機數(shù)產(chǎn)生器的算法結(jié)構(gòu)中，用勒讓德符號迭代計算產(chǎn)生隨機數(shù)，解決了BBS隨機數(shù)產(chǎn)生器的安全性問題。
在基于密碼和水印的數(shù)字版權(quán)保護技術(shù)中，勒讓德符號可以構(gòu)造適合混淆Java程序的不透明謂詞簇，結(jié)合水印與混淆技術(shù)，提出了基于身份標識的Java程序水印方案。
參考資料 >
術(shù)語在線.術(shù)語在線.2024-02-22