■素数性判定(その1)

現代社会において,インターネット通信やクレジットカード決済の安全性・信頼性を担保しているものは巨大な素数の存在です.巨大な素数をp,qとすると,pとqを掛け合わせてn=pqを得るの易しいが,nをpとqに素因数分解するのは非常に困難である(不可能に近い)という原理に基づいています.ここでは素数性の判定法の基本となるフェルマーの小定理について紹介します.

===================================

【1】フェルマーの小定理

pが素数で,aがpの倍数でないとき,フェルマーの小定理

  a^p-1=1  (mod p)

が成り立ちます.たとえば,p=17,a=3の場合

  3^16=2532160・17+1

この定理は両辺にaを乗じた形で表されることもありますが,その場合,aがpの倍数でないという条件は不要です.すなわち,

pが素数のとき,すべての整数aに対して,フェルマーの小定理

  a^p=a  (mod p)

が成り立つ.

===================================

【2】古代ギリシャ 

 古代ギリシャ人はn=2,3,5,7のとき,2^n−1が素数になることを知っていました.nが素数でないときには素数を表さないことは明らかですから,それとは逆に,すべての素数に対して,2^n−1は素数になると考えていたようです.nが素数であることは2^n−1が素数であるための必要条件です.しかし,逆の十分性は成り立ちません.

  2^2−1=3  (素数)

  2^3−1=7  (素数)

  2^5−1=31  (素数)

  2^7−1=127  (素数)

  2^11−1=2047=23・89  (非素数)

  2^13−1=8191  (素数)

フェルマーの定理の応用性は高く,

  2^4−1=15  (非素数)

  2^6−1=63  (非素数)

  2^8−1=255  (非素数)

  2^9−1=511=7・73  (非素数)

  2^12−1=1023=3・341  (非素数)

などはすぐ判定できます.

===================================