在數論中，透過模冪和費馬小定理來證明素數的素性可以使用費馬素性檢驗。費馬小定理指出，如果 \( p \) 是素數，而 \( a \) 是任意整數且 \( a \) 不被 \( p \) 整除，則滿足以下關係：

\[
a^{p-1} \equiv 1 \mod p
\]

這表示，如果我們選擇一個隨機的 \( a \)，並計算 \( a^{p-1} \mod p \)，如果等式成立，則 \( p \) 很可能是素數。

### 証明過程
1. **選擇整數 \( a \)**：隨機選擇一個 \( a \) 使得 \( 1 < a < p \) 且 \( a \) 不被 \( p \) 整除。
2. **計算模冪**：計算 \( a^{p-1} \mod p \)。
3. **檢查結果**：
   - 如果 \( a^{p-1} \equiv 1 \mod p \)，則 \( p \) 可被視為素數候選。
   - 如果結果不是 1，則 \( p \) 確定不是素數。

然而，這個方法不能保證所有輸出為 1 的 \( p \) 都是素數，因為存在某些合成數（如卡米爾數）會產生偽素數的情況。為了解決這個問題，可以透過多次測試不同的 \( a \) 值，或者結合其他檢查方法如米勒-拉賓測試來進一步確認。

### 實務應用
在實務上，這個檢驗方法在密碼學中扮演重要角色，特別是在生成密鑰和加密演算法中。下面是幾個應用範例：

1. **RSA 加密**：RSA 加密法依賴於兩個大的素數的乘積，這些素數的選擇需要有效的方法來檢驗其素性以確保安全性。
2. **數位簽名與鑑別**：許多數位簽名演算法需要生成大素數以確保嘉賓的身份，透過費馬素性檢驗可以快速篩選出可能的素數。
3. **隨機數生成器**：每當生成隨機密鑰時，使用費馬小定理來確認所選數字的素性會提升密碼系統的安全性。

總之，透過模冪和費馬小定理進行素性檢驗不僅提供了理論上的保證，也在現實中的計算和網絡安全中展現了重要的應用價值。
在數論中，如何透過模冪和費馬小定理來證明某一特定素數的素性，並且這個證明在實務上有哪些應用，例如在密碼學中的角色？
這是**數論的主題列表**。參照

* 趣味數學主題列表

## 因數

* 因數：b 可以被 a 整除。即稱 a 是 b 的因數。
  * 最大公因數：能夠整除多個整數的最大正整數。
  * 最小公倍數：能夠被多個整數整除的最小正整數。
  * 輾轉相除法：求最大公因數的算法。
  * 互素：多個整數的最大公因數為 1。
  * 歐幾里德引理：在歐幾里得《幾何原本》中提出，和三個整數整除和互質關係有關的定理
  * 貝祖等式：得名於法國數學家艾蒂安・貝祖，有關最大公因數的定理。
* 合成數：除了 1 和自身以外，還有其他正因數的自然數。
  * 高合成數：任何比此數小的自然數，其因數數目均比這個數的因數數目少。
* 奇數和偶數：除以 2 餘 1 的自然數，以及除以 2 會整除的自然數。
* 素數：其正因數只有 1 和自身的自然數。
* 素因子：本身是素數的因數。
  * 素因子表：條列自然數的素因數。
* 素數公式：只產生素數的公式。
* 整數分解：以質因數的乘積來表示自然數。
  * RSA 破譯競賽：分解安全用 RSA 密碼的比賽。
* 算術基本定理：每個大於 1 的自然數，若本身不是質數，就可以寫為 2 個或以上的質數的積
* 無平方數因數的數：其因數中不包括平方數的自然數
* 平方數：可以寫成某整數平方的數。
* 整值多項式：在變數是整數時，其值恆為多項式的多項式。

## 分數

* 有理數
* 單位分數
* 最簡分數
* 二進分數
* 循環小數
* 法里數列
  * Ford circle
  * Stern-Brocot tree
* 古埃及分數
* Engel 展開式

## 模算術

* 蒙哥馬利算法
* 模冪
* 線性同餘方程
* 逐次代換法
* 中國剩餘定理
* 費馬小定理
  * 費馬小定理的證明
* 歐拉函數
  * 非互補歐拉商數
  * 非歐拉商數
* 歐拉定理
* 威爾遜定理
* 原根
  * Multiplicative order
  * 離散對數
* 二次剩餘
  * 歐拉準則
  * 勒讓德符號
  * 高斯引理
* 平方同餘
* Luhn 算法
* 模 n 密碼分析
* 戴德金和

## 素性檢驗和素因子分解

_主要標題：計算數論，算法數論_

* 試除法
* 埃拉托斯特尼篩法
* 素性判定法則
  * 可能性算法
* 費馬素性檢驗 (應用費馬小定理)
  * 偽素數
  * 卡米歇爾數
  * 歐拉偽素數
  * 歐拉 - 雅克比偽素數
  * 斐波那契偽素數
  * 可能素數
* 米勒 - 拉賓檢驗
* 盧卡斯 - 萊默檢驗法
* 盧卡斯 - 萊默檢驗法在梅森素數上的運用
* AKS 素性檢驗
* NewPGen
* 整數分解
  * Pollard p-1 法
  * Pollard's rho algorithm
  * Lenstra 橢圓曲線分解法
  * 二次篩選法
  * 特殊數域篩選法
  * 普通數域篩選法
  * 秀爾演算法
* RSA 破譯競賽
  * FAFNER

## 數論函數

* 積性函數
* 加性函數
* 狄利克雷卷積
* 默比烏斯函數
  * 默比烏斯倒置算法
* 除數函數
* 因數函數
* 劉維爾函數
* 整數分拆
  * 貝爾數
  * 蘭道函數
  * 五邊形數定理
* Erdős–Kac theorem

## 解析數論

* 孿生素數
  * 孿生素數猜想（哈代 - 李特爾伍德第一猜想）
  * Brun 常數
* 表兄弟素數
* 四胞胎素數
* 六質數
* 三胞胎素數
* 索菲熱爾曼素數
* 坎寧安鏈
* 哥德巴赫猜想
  * 弱歌德巴赫猜想
* 哈代 - 李特爾伍德第二猜想
* Schinzel's hypothesis H
* 華林問題
  * Brahmagupta 等式
  * 歐拉四平方和恆等式、
  * 四平方和定理
  * 的士數
  * 一般化的士數
* 士的數
* Schnirelmann 密度
* 和集
* 蘭道 - 拉馬努金常數
* 謝爾賓斯基數
  * Seventeen or Bust

## 代數數論

_見代數數論主題列表_

## 二次型

* Unimodular lattice
* 費馬平方和定理

## L 函數

* 黎曼 ζ 函數
  * 在 ζ(2) 上的貝塞爾問題
  * Hurwitz ζ 函數
* 狄利克雷級數
* 歐拉積
* 素數定理
  * Offset logarithmic integral
  * 勒讓德常數
  * 斯奎斯數
  * 勃蘭特假定
    * 勃蘭特假定的證明
    * 證明所有素數的倒數之和發散
  * 克拉姆猜想
* 黎曼猜想
  * 希爾伯特－波利亞猜想
  * 廣義黎曼猜想
  * 默滕斯函數、默滕斯猜想、Meissel-Mertens 常數
  * De Bruijn-Newman 常數
* Dirichlet character
* 狄利克雷 L 函數
* 狄利克雷定理
  * Linnik 定理
* 函數方程 (L 函數)
* Chebotarev's density theorem
* 局部 ζ 函數
  * 魏伊猜想
* 模形式
  * modular group
  * Congruence subgroup
  * 赫克算子
  * 尖點形式
  * 模曲線
  * 拉馬努金 - 彼得森猜想
* Birch 和 Swinnerton-Dyer 猜想
* 自守形式
* 塞爾伯格跡公式
* 阿廷猜想
* Sato-Tate 猜想
* 郎蘭茲綱領
* 谷山 - 志村猜想

## 丟番圖方程

* 勾股數
* 配爾方程
* 橢圓曲線
  * Nagell-Lutz 定理
  * Mordell-Weil 定理
  * 阿貝爾簇算法
* 費馬大定理
* 莫德爾猜想
* 歐拉猜想
* abc 猜想
* 卡塔蘭猜想
* Pillai 猜想
* Hasse 定則
* 丟番圖集合
* Matiyasevich 定理
* 1729
* 馬爾可夫方程

## 丟番圖逼近

* 無理數
  * 二次無理數
  * 整數平方根
  * 代數數
    * Pisot-Vijayaraghavan 數
  * 超越數
    * _e_
    * 圓周率 π
    * 化圓為方
    * 林德曼 - 魏爾斯特拉斯定理
    * 希爾伯特第七問題
    * 格爾豐德 - 施奈德定理
  * 埃爾德什 - 波溫常數
* 劉維爾數
* 連分數
  * Khinchin 常數
  * 非普遍連分數
* 克羅內克定理
* 圖埃–西格爾–羅特定理
* Prouhet-Thue-Morse 常數
* 格爾豐德 - 施奈德常數
* 貝亞蒂定理
* 李特爾伍德猜想
* Discrepancy 函數
  * Low-discrepancy sequence
  * Illustration of a low-discrepancy sequence
  * Constructions of low-discrepancy sequences
  * Halton 序列
* 數的幾何
  * 閔可夫斯基定理
  * 皮克定理
  * Mahler's compactness theorem
* 馬勒定理

## 篩選方法

* Large sieve

## 有名的素數

* 卡倫素數
* 歐拉素數
* 費馬素數
* 梅森素數
  * 新梅森猜想
  * GIMPS
* 紐曼 - 尚克斯 - 威廉士素數
* 瓦格斯塔夫素數
* 沃爾 - 孫 - 孫素數
* 韋伊費列治素數
* 威爾遜素數
* Wolstenholme 素數
* 胡道爾素數

## 組合數論

* Covering system
* Erdös-Ginzburg-Ziv 定理
* 多項式法
* 范德瓦爾登定理
* Szemerédi 定理
* 倒數和發散

## 偽隨機數

* 偽隨機數發生器
  * 偽隨機性（Pseudorandomness）
  * 密碼學安全偽隨機數生成器（Cryptographically secure pseudo-random number generator）
* 平方取中法
* Blum Blum Shub
* ISAAC：1993 年開發的隨機數生成器演算法。
* 線性同餘發生器：一種產生偽隨機數的方法。
* 梅森旋轉算法：1997 年開發的偽隨機數方法。
* 時滯斐波那契生成器：用於改進線性同餘生成器的偽隨機數生成器。
* 線性反饋移位暫存器
* 互縮生成器（Shrinking generator）
* 流加密（Stream cipher）

## 歷史

* _Disquisitiones Arithmeticae_
* _On the Number of Primes Less Than a Given Magnitude_
* _Vorlesungen über Zahlentheorie_
這是**數論的主題列表**。參照

* 趣味數學主題列表

## 因數

* 因數：b 可以被 a 整除。即稱 a 是 b 的因數。
  * 最大公因數：能夠整除多個整數的最大正整數。
  * 最小公倍數：能夠被多個整數整除的最小正整數。
  * 輾轉相除法：求最大公因數的算法。
  * 互素：多個整數的最大公因數為 1。
  * 歐幾里德引理：在歐幾里得《幾何原本》中提出，和三個整數整除和互質關係有關的定理
  * 貝祖等式：得名於法國數學家艾蒂安・貝祖，有關最大公因數的定理。
* 合成數：除了 1 和自身以外，還有其他正因數的自然數。
  * 高合成數：任何比此數小的自然數，其因數數目均比這個數的因數數目少。
* 奇數和偶數：除以 2 餘 1 的自然數，以及除以 2 會整除的自然數。
* 素數：其正因數只有 1 和自身的自然數。
* 素因子：本身是素數的因數。
  * 素因子表：條列自然數的素因數。
* 素數公式：只產生素數的公式。
* 整數分解：以質因數的乘積來表示自然數。
  * RSA 破譯競賽：分解安全用 RSA 密碼的比賽。
* 算術基本定理：每個大於 1 的自然數，若本身不是質數，就可以寫為 2 個或以上的質數的積
* 無平方數因數的數：其因數中不包括平方數的自然數
* 平方數：可以寫成某整數平方的數。
* 整值多項式：在變數是整數時，其值恆為多項式的多項式。 ## 初等數論的主題

* 素數
  * 偽素數
  * 費馬素數
  * 梅森素數
  * 孿生素數
  * 三胞胎素數
  * 四胞胎素數
  * x²+1 素數
  * 六素數
  * 表兄弟素數
* 素數判定法則
* 因數
  * 整除性的問題
  * 最大公因數
  * 輾轉相除法
  * 質因數分解
* 素數公式
* 埃拉托斯特尼篩法
* 有趣的數
  * 完全數
    * 多重完全數
  * 自守數
  * 金蘭數（Amicable Triple）
  * 親和數
  * 擬形數
  * 純元數
  * 迴文數
  * 卡普列加數
* 連分數
  * 配爾方程
* 幻方
* 原根
* 同餘
  * 二次剩餘
  * 不定方程
* 倒數的性質
* 數論函數
  * 歐拉函數
  * 取整函數
* 經典的定理
  * 歐拉定理
  * 費馬小定理
  * 費馬大定理
  * 中國剩餘定理
  * 威爾遜定理
  * 素數定理
  * 二次互反律
  * 四平方和定理
  * 算術基本定理
  * 整數數列
    * 階乘
    * 法來數列
    * 斐波那契數列
  * 看起來很簡單的猜想、定理
    * 哥德巴赫猜想
    * 卡塔蘭猜想
    * 角谷猜想
    * 歐德斯 - 史特勞斯猜想
    * 孿生素數猜想 這是**數論的主題列表**。參照

* 趣味數學主題列表

## 因數

* 因數：b 可以被 a 整除。即稱 a 是 b 的因數。
  * 最大公因數：能夠整除多個整數的最大正整數。
  * 最小公倍數：能夠被多個整數整除的最小正整數。
  * 輾轉相除法：求最大公因數的算法。
  * 互素：多個整數的最大公因數為 1。
  * 歐幾里德引理：在歐幾里得《幾何原本》中提出，和三個整數整除和互質關係有關的定理
  * 貝祖等式：得名於法國數學家艾蒂安・貝祖，有關最大公因數的定理。
* 合成數：除了 1 和自身以外，還有其他正因數的自然數。
  * 高合成數：任何比此數小的自然數，其因數數目均比這個數的因數數目少。
* 奇數和偶數：除以 2 餘 1 的自然數，以及除以 2 會整除的自然數。
* 素數：其正因數只有 1 和自身的自然數。
* 素因子：本身是素數的因數。
  * 素因子表：條列自然數的素因數。
* 素數公式：只產生素數的公式。
* 整數分解：以質因數的乘積來表示自然數。
  * RSA 破譯競賽：分解安全用 RSA 密碼的比賽。
* 算術基本定理：每個大於 1 的自然數，若本身不是質數，就可以寫為 2 個或以上的質數的積
* 無平方數因數的數：其因數中不包括平方數的自然數
* 平方數：可以寫成某整數平方的數。
* 整值多項式：在變數是整數時，其值恆為多項式的多項式。 **模冪**（英語：modular exponentiation）是一種對模進行的冪運算，在計算機科學，尤其是公開密鑰加密方面有一定用途。

模冪運算是指求整數 $b$ 的 $e$ 次方 $b^{e}$ 被正整數 $m$ 所除得到的餘數 $c$ 的過程，可用數學符號表示為 $c=b^{e}{\bmod {m}}$ 。由 $c$ 的定義可得 $0\leq c<m$ 。

例如，給定 $b=5$ ， $e=3$ 和 $m=13$ ， $5^{3}=125$ 被 13 除得的餘數 $c=8$ 。

指數 $e$ 為負數時可使用擴展歐幾里得算法找到 $b$ 模除 $m$ 的模逆元 $d$ 來執行模冪運算，即：

　
: $c=b^{e}{\bmod {m}}=d^{-e}{\bmod {m}}$ ，其中 $e<0$ 且 $b\cdot d\equiv 1{\pmod {m}}$ 。

即使在整數很大的情況下，上述模冪運算其實也是易於執行的。然而，計算模的離散對數（即在已知 $b$ ， $c$ 和 $m$ 時求出指數 $e$ ）則較為困難。這種類似單向函數的表現使模冪運算可用於加密算法。