アルゴリズム論特論（塩田）第10回 (4) $p-1$ 法
補題
次は $p-1$ 法と呼ばれる素因数分解法です。
Lemma 10 $m!$ が $p-1$ の倍数となる $m$ が必ず存在する。
証明 $p-1$ の素因数分解を
$p-1=r_1^{e_1} \times r_2^{e_2} \times \cdots \times r_k^{e_k}$
とすれば $\displaystyle{m=\max_{1 \leqq i \leqq k}\,(r_i^{e_i})}$ でOKです。(証明終)
例えば $p=181$ なら $p-1=180=2^2 \times 3^2 \times 5^1 = 4 \times 5 \times 9$ ですから $m=\max\{4,5,9\}=9$ の階乗 $9!$ は $180$ の倍数になります。
( 本当は既に $6!$ が $180$ の倍数です。)
Cor.11 $\gcd(b,n) = 1$ ならば、ある $m$ が存在して $\gcd(b^{m!} - 1, n) \geqq p$.
証明 L'a 10 の $m$ を取れば、フェルマの小定理により
$\displaystyle{b^{m!}=(b^{p-1})^{m!/(p-1)} \equiv (1)^{m!/(p-1)} \equiv 1 \pmod p}$
従って $b^{m!}-1$ と $n=pq$ の $\gcd$ は $p$ 以上になります。(証明終)
$p-1$ 法
上の系を利用すると次のような素因数分解法が作れます。
Algorithm 12（ p-1 法）
- 入力：RSA modulus $n$
- 出力：$n$ の素因子 $p$, $q$
while True:
$b =$ ( $2$ 以上 $n$ 未満の乱数 )
$m = 1$
while $m \lt$ ( $m$ の上限 ) :
$m = m + 1$
$b = b^m \,\%\, n$
$d = \gcd(b - 1, n)$
if $d = n$ :
break
elif $d \gt 1$ :
$p = d$, $q = n / p$ を出力
内側ループの中の $b$ は、(最初の $b$)$^{m!} \ \%\, n$ ですから、いつかは $\gcd(b - 1, n) \geqq p$ となります。
ただ、運悪く $\gcd(b - 1, n) = n$ となってしまったらこれ以上ループを回しても仕方が無いので最初に戻って $b$ を取り換えます。
Prop.13 Alg.12 は $p-1$ が小さな素因数しか持たないときに有効である。
証明 $p-1$ が小さな素因数しか持たなければ
L'a 10 の $m$ が比較的小さいので。(証明終)
Ex.14
p - 1 の素因数の上限を決めてください。
10000
RSA modulus n のビット数を設定してください。
2048
n = 27725514686523991152703953656443670394994073094079645621104755273492645150601240648134150236982652922644626095274478124530942923726138884894271831233978292385908421670492181977083202012992669321035433852427029919124612285929546778661688704782112093489476315801125649203215749705949748618343520621724552088918136145796793931399781258710793350529005598033651389634070676952371300954422005164380443384006833044077234976719258158544523128068260205354651320360457395843325934732338783691009760806692065711082908764969525657975813309170377642676035630023146488103867727178594215357570883370704693697349854992528661816872049 ( 2048-bit )
p - 1 法 開始しました。
p = 7314773654684679278511813336641222875365390312518900577846521616118628647247955238057332917608153594084214617336148266561608460418924712980369334633055654870332106042639709994807294794574090020175061139333027589944222004847630200104791390643642891124645346703699876592158885283889152000000000000000000000000001 ( 1030-bit )
q = 3790344854863341007511803659094356698406937334029337036027634566111944040780085305476017487785592216781012933384463213230076009840334541563748223507582054435962745739792535656430403644599191791853700285800436786151243611525943176895261924461381731471222896255336495178933087592245697349854992528661816872049 ( 1019-bit )
b = 19690964316362281109544103760720011330076798215089788552611979157791660127896609462932975127626785794787261978406482100311509629429934159971988017915483170917054379189603160844231641133453497105520455337785193425287008785558477180302251375047077146866855034717767869211047768879244163005136921963971912082839064966113602001895712566328414051838000265893189983251088860228640088378627632268936045818760185918295420944254409360815852042630683579077715124185935852094337114742503297930102303004298278398027334882214901964511499444280919413661175368679891421550315859125310255871540692202568104940786804715423989012023148
m = 7321
検算 :
p * q = 27725514686523991152703953656443670394994073094079645621104755273492645150601240648134150236982652922644626095274478124530942923726138884894271831233978292385908421670492181977083202012992669321035433852427029919124612285929546778661688704782112093489476315801125649203215749705949748618343520621724552088918136145796793931399781258710793350529005598033651389634070676952371300954422005164380443384006833044077234976719258158544523128068260205354651320360457395843325934732338783691009760806692065711082908764969525657975813309170377642676035630023146488103867727178594215357570883370704693697349854992528661816872049
計算時間 = 8.425666332244873