信息安全数学基础

夏秋月

[color=rgba(0, 0, 0, 0.75)]欧拉定理、费马小定理

具体的定理内容以及证明，我在前几章已经记录过。

• 欧 拉 定 理 ： 设 n ∈ N + , a ∈ Z , ( a , n ) = 1 , 则 a φ ( n ) ≡ 1 ( m o d n ) 欧拉定理：设n\in N^+,a\in Z,(a,n)=1,则a^{\varphi(n)}\equiv 1(mod n)欧拉定理：设n∈N+,a∈Z,(a,n)=1,则aφ(n)≡1(modn)
• 费 马 小 定 理 ： 设 n 为 素 数 , a ∈ Z , 则 a n ≡ a ( m o d n ) 费马小定理：设n为素数,a\in Z,则a^n\equiv a(mod n)费马小定理：设n为素数,a∈Z,则an≡a(modn)
  

可以看出，费马小定理的条件更严格，要求是n为素数，而欧拉定理只要求a与n互素即可，并没有要求n本身为素数。

目前我学习到的素性检测算法都是以费马小定理作为依据，应该是因为费马小定理的条件，必须是素数。下面我具体来谈谈我学习到的几个素性检测算法。

[color=rgba(0, 0, 0, 0.75)]