原根（Primitive Root）是與整數(shù)階有關(guān)的一個數(shù)論概念。其定義為：設(shè)m>1，(a,m)=1，t是使at≡1(mod m)成立的最小正整數(shù)，則稱t為a關(guān)于模m的階數(shù)，若a關(guān)于模m的階數(shù)是φ(m)，就稱a為模m的一個原根。
原根的歷史可追溯至18世紀數(shù)論問題的研究。1785年，阿德利昂·瑪利·埃·勒讓德（Legendre）在給出二次互反律的同時還給出了模的原根的構(gòu)造。1801年，高斯（Carl Friedrich Gauss）在他的著作《算術(shù)研究》中，證明了一個原根的性質(zhì)，即正整數(shù)中只有，，和存在原根。20世紀50年代開始，一些學(xué)者對原根的上下限進行了討論，中原地區(qū)數(shù)論專家王元證明了模的最小原根的結(jié)果為。1962年，伯吉斯（Burgess）得到了和王元同樣的結(jié)果，且說明了所隱含的常數(shù)僅取決于。而對于原根的上限，1981年，格羅斯瓦爾德（Emil Grosswald）進行了猜測：如果，則，其結(jié)果被其他學(xué)者做出了驗證和進一步探索。
原根具有一些基本性質(zhì)，如，如果模有原根，則它恰有個原根。它可以用于數(shù)論中著名定理——費馬小定理的證明。消去法可以用于求解原根，但是計算過程較為復(fù)雜。此外，原根在現(xiàn)實世界中應(yīng)用廣泛，如密碼學(xué)中，它是實現(xiàn)Diffie-Hellman密鑰交換協(xié)議的一個核心參數(shù)，直接影響協(xié)議的安全性。
定義
根據(jù)歐拉定理，當，時，，因此在的正方冪，，，中，必有正整數(shù)存在，使得，于是給出：
階數(shù)、原根：設(shè)，，是使成立的最小正整數(shù)，則稱為關(guān)于模的階數(shù)；若關(guān)于模的階數(shù)是，則稱為模的一個原根。
簡史
早期研究
原根的歷史可追溯至18世紀數(shù)論問題的研究。1785年，勒讓德（Legendre）在給出二次互反律的同時還給出了模的原根的構(gòu)造。1801年，高斯（Carl friedrich Gauss）在他的著作《算術(shù)研究》中證明了一個原根的性質(zhì)，即正整數(shù)中只有，，和存在原根。1927年，埃米爾·阿廷（Artin, E.）猜測：如果一個正整數(shù)非平方數(shù)，則存在無窮多個素數(shù)以為原根。特別地，他猜想 等都是無限多個素數(shù)的原根，這個猜想迄今仍未獲得證明。
后續(xù)發(fā)展
后來，一些學(xué)者對原根的上下限進行了討論。20世紀50年代，中國數(shù)論專家王元證明了模的最小原根。李·弗里德蘭德（Fridlander）和薩利（Salié）分別獨立證明了存在一個正常數(shù)，使得對于多個無窮素數(shù)，。1962年，伯吉斯（Burgess）得到了和王元同樣的結(jié)果，且說明了所隱含的常數(shù)僅取決于。而對于原根的上限，1981年，格羅斯瓦爾德（Emil Grosswald）進行了猜測：如果，則，其結(jié)果被其他學(xué)者做出了驗證和進一步探索。
舉例
有原根
例1（模9的原根）：設(shè)整數(shù)，這時，則有
成表如下表：
因此，和是模的原根。
無原根
例2（模8無原根）：但是，并不是每個整數(shù)都有原根。考慮模，小于而與互素的整數(shù)為，即全體奇數(shù)。由此可知。如果是偶數(shù)，那么，因此，即所有的偶數(shù)都不可能是模的原根。如果是奇數(shù)，那么可證，因此所有奇數(shù)也不可能是模的原根，所以模沒有原根。
相關(guān)概念
簡化剩余系
定義：若一個模的剩余類中的數(shù)與互素，則稱之為一個與模互素的剩余類，這樣的剩余類共有類，從每一個類中取出一個數(shù)作為代表，所得到的個數(shù)就稱為模的一個簡化剩余系。或者說，在模的一個完全剩余系中，與互素的數(shù)的全體稱為模的一個簡化剩余系。
原根與簡化剩余系：設(shè)是模的一個原根，若通過模的最小非負完全剩余系，則是通過模的一個簡化剩余系。
性質(zhì)
存在性
（1）給定任意模，原根不一定是存在的，實際上，只有在是四者之一時原根才存在。即，模有原根的充分必要條件是，其中是奇素數(shù)，。
推論1：設(shè)是奇素數(shù)，則模的原根存在。
推論2：設(shè)是模的一個原根，則或者是模的原根。
推論3：設(shè)是一個奇素數(shù)，則對任意正整數(shù)，模的原根存在。
推論4：設(shè)，是模的一個原根，則與中的奇數(shù)是模的一個原根。
（2）若整數(shù)，的所有不同素因數(shù)是，則是模的原根的充分必要條件是。
（3）若模有原根的存在，則恰有個對模不同余的原根，它們由集合中的數(shù)給出。
個數(shù)
（1）如果模有原根，則它恰有個原根。
相關(guān)定理
費馬小定理
定理：若為素數(shù)，，則。
原根證法：因為素數(shù)恒有原根，所以當時，有，即。
求解方法
消去法
原根的求法是對原根的一種刻畫，基本思想可表示為：若對模奇素數(shù)的階為，，則不是模的原根。因此要求的原根，先列出模的簡化剩余系：
（7.1.1）
首先取，求得對模的階為，若，則即為的原根。若，則在（7.1.1）消中去各數(shù)。在（7.1.1）中剩下的數(shù)中再取一數(shù)，重復(fù)以上方法，直到（7.1.1）中剩下 個數(shù)，因為奇素數(shù)恰有個原根，因此這個數(shù)都是的原根。上述求原根的方法稱為消去法。
例題
例題：求模的最小正原根并根據(jù)此求出的一個原根，其中是正整數(shù)。
解：求解此題需引入下述命題。
命題1：設(shè)且的所有不同的素因數(shù)為，則是模的原根當且僅當。
首先，有，其次由知不是模的原根。因為
，
根據(jù)命題1知是模的原根，從而是模的最小正原根。又因為
，
，
故，說明，可知是的原根。另外由是奇數(shù)和原根性質(zhì)知也是的一原根。
相關(guān)算法
高效原根生成算法
生成模原根最原始的思想就是：通過逐個計算，求出的次數(shù)，由此判斷是否為原根，這種算法是指數(shù)算法，實現(xiàn)效率低。經(jīng)典的加速方法將完全分解為，通過計算是否成立來生成原根，這個算法能夠在一定程度上提高效率，但是最大整數(shù)的分解沒有多項式算法。1997年，埃里希·巴赫（Erich Bach）利用部分分解的思想給出了依賴于ERH的確定的多項式時間算法。
求解離散對數(shù)算法
離散對數(shù)：離散對數(shù)是一種基于同余運算和原根的一種對數(shù)運算。在實數(shù)中的一般對數(shù)定義為，含義是對于給定的，求出一個數(shù)，使得。相似地，在其他任何群中可以定義離散對數(shù)使得的整數(shù)，其中執(zhí)行的是群上的冪運算。離散對數(shù)在某些特殊情況下可以快速計算，但是一般而言沒有具有非常高效率的方法來計算離散對數(shù)。在精心選擇或是構(gòu)造的群中，并不存在有效求解離散對數(shù)的算法，因此公鑰密碼學(xué)中的幾個重要算法，如ElGamal公鑰加密算法，是以離散對數(shù)的求解困難性保障算法的安全性的。
求離散對數(shù)：簡單以上的離散對數(shù)為例，首先定義素數(shù)的本原根：素數(shù)的本原根是中的一個元素，其冪可以遍歷中的所有元素。若是素數(shù)的一個本原根，那么：
集合與完全等價。
對任意整數(shù)和素數(shù)的本原根，有唯一的冪使得
稱該指數(shù)是以為底的的模離散對數(shù)，記為。
類似理論
半原根
設(shè)是大于的整數(shù)，，若對模的階為，則稱是模的一個半原根。
充要條件
設(shè)，則模的半原根存在的充要條件是為下列4種情況之一。
（1）（）；
（2）（，為奇質(zhì)數(shù)）；
（3）（，為奇質(zhì)數(shù)）；
（4）（、是兩個不同的奇質(zhì)數(shù)，）。
設(shè)，用表示在模的一個簡化剩余系中，關(guān)于模的半原根的個數(shù)。由半原根的定義知，與模的簡化剩余系的選取無關(guān)。
應(yīng)用
工程學(xué)
在工程學(xué)領(lǐng)域，自動交換光網(wǎng)絡(luò)（ASON）控制協(xié)議采用通用多協(xié)議標簽交換（GMPLS）控制協(xié)議族，其路由部分主要為開放式最短路徑優(yōu)先（OSPF）協(xié)議。針對OSPF協(xié)議的安全模式，可采取一種基于DES算法改進的加密機制，通過優(yōu)化S盒的設(shè)計，使其次序隨密鑰而變化，抵抗破譯時的差分密碼分析，達到進一步增強DES算法加密強度的目的。通過初始置換矩陣的精心設(shè)計，利用原根理論來實現(xiàn)密鑰的動態(tài)生成算法，同時使得f函數(shù)和密鑰相關(guān)，最終可以更加安全地進行網(wǎng)絡(luò)信息的傳送。
密碼學(xué)
原根和指數(shù)在密碼學(xué)中應(yīng)用很多，較為經(jīng)典的包括了Diffie-Hellman密鑰交換協(xié)議、ElGamal加密、DSA數(shù)字簽名等。Diffie-Hellman密鑰交換是一個可以使通信雙方在不可信信道上建立共享密鑰，并使之應(yīng)用于后繼對稱密鑰加密通信系統(tǒng)的一種密碼協(xié)議。而本原根是實現(xiàn)Diffie-Hellman密鑰交換協(xié)議的一個核心參數(shù)，它直接影響協(xié)議的安全性。對于大素數(shù)，通過快速確定本原根，可以節(jié)約運算成本，加強保密通信的性能。
計算機科學(xué)
在計算機科學(xué)中，隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，圖像成為互聯(lián)網(wǎng)上表達和傳輸信息的一種重要載體，其安全性問題日益受到人們的關(guān)注，數(shù)字圖像的置亂和隱藏成為信息安全技術(shù)中的一個研究熱點。一種圖像置亂算法采用線性同余偽隨機數(shù)發(fā)生器技術(shù)，根據(jù)RGB圖像像素值的特性，可以計算出LCG迭代公式中的值及其原根，通過實驗可以得出置亂的最小正周期。研究表明，該算法置亂效果顯著，可以作為圖像隱藏的預(yù)處理和后期處理的一種良好方法。
參考資料 >
Primitive Root.mathworld.2024-06-20
Primitive Root Modulo n - Order of Magnitude of Primitive Roots.Liquisearch.2024-06-13