ソフィー･ジェルマン素数 (Sophie Germain prime)
小中学生向け短編小説集のひとつで，フランスの女性数学者ソフィー･ジェルマンの13歳のころと現代の14歳の少女との時空を超えた友情のお話です．たまたまですが，同じ年に｢天球のハルモニア｣というソフィー･ジェルマンの少女時代を描いた漫画が発行されています．
｢Pが素数で、(2P+1)も素数である場合、このPを『ソフィー・ジェルマン素数』という｣ のだそうです。ソフィーが提唱したこの素数は、暗号理論において、素因数分解アルゴリズムの攻撃に耐えうる整数Nを決定するのにとても便利･･････なのだそうですが、何を言っているのか、実は、書いている僕にもよくわかりません。（著者）
この文章の意味を考えてみましょう．まずソフィー･ジェルマン素数ですが，pも2p+1も素数であるとき， pをソフィー･ジェルマン素数，2p+1を安全素数 (safe prime) といいます．次の表の〇のような場合です．
上の文章中，｢素因数分解アルゴリズム｣ とは，こうすれば素因数分解ができるという手順のことで，その ｢攻撃に耐える｣ ということは ｢素因数分解されにくい｣ という意味になります．
RSAという暗号を作る際，素因数分解するのが難しい巨大な数を使うほど解読されにくいということを利用します．
・大きな素因数を持つ数は素因数分解が困難
・大きな安全素数2p+1は，2pがpという大きな素因数を持つ（例えば上の表で，2p+1=107のとき，2pがp=53という大きな素因数を持つ）
なので，安全素数は素因数分解されにくい整数を求めるのに有効，すなわち ｢素因数分解アルゴリズムの攻撃に耐えうる整数Nを決定するのにとても便利｣ ということになります．
ところで，Wikipediaの｢ソフィー･ジェルマン素数｣のページに，説明なしで ｢2と3を除くソフィー･ジェルマン素数は6n−1の形の素数である｣ と書かれています．証明してみましょう．
(証明) すべての整数は6m, 6m+1, 6m+2, 6m+3, 6m+4, 6m+5 (mは整数)と書ける
このうち3より大きい素数は6m+1または6m+5の形しかない
p=6m+1のとき，2p+1=2(6m+1)+1=12m+3 は3の倍数となり素数にならない
p=6m+5のとき，2p+1=2(6m+5)+1=12m+11 はmの値によって素数になる可能性がある
よって，2と3を除くソフィー･ジェルマン素数は6m+5(または6n−1)の形しかない (QED)
0 件のコメント:
コメントを投稿