Python

【python】任意のビット数の素数をランダムに生成するプログラムの作り方解説

この記事では任意のサイズの素数を生成するpythonプログラムについて解説します。

「任意のサイズ」というのは、ビット数を指定できるという意味です。例えば10ビットの素数を作る場合、29~210-1の範囲にある10ビットの素数のいずれかを出力することになります。

プログラムの流れとしては、

  1. 指定したビット数の乱数を生成する
  2. 生成した乱数が素数かどうかをチェックする
  3. チェックを通過したらそれを素数として出力する

という感じになります。素数のチェックを通過しなかった場合また①のステップに戻り、素数がたまたま乱数として生成されるまで①と②をループします。

素数かどうかのチェックには、素数判定のアルゴリズムを用います。素数判定アルゴリズムはいくつか存在しますが、今回はミラーラビン法というアルゴリズムを使用します。ミラーラビン法の実装に関しては過去に記事を書いたので、そちらもご覧ください。

素数判定アルゴリズムの”ミラーラビン法”をpythonで実装するこの記事では素数判定アルゴリズムである”ミラーラビン法”をpythonで実装する方法について解説します。ミラーラビン法は"ミラーラビンテ...

pythonプログラムの例と解説

import random
import MillerRabin as mr

def PNG(n):
    while True:
        """Step1 nビットの乱数mを生成"""
        m = random.randint(2**(n-1),2**n-1)
        
        """Step2 素数判定"""
        if mr.MRPT(m,50) == True:
            return m

 

乱数を生成するためのrandomモジュールをインポートします。またミラーラビン法の関数を使用するために、過去に書いたプログラムにMillerRabinという名前を付けてインポートしました。名前が長いのでmrという名前をつけておきます。

定義する関数の名前PNGというのはPrimeNumberGeneration(素数生成)の頭文字です。

まずは「while True:」で無限ループをつくります。乱数がたまたま素数になるまで無限に操作を繰り返すからです。

次にStep1としてnビットの乱数mを生成します。「random.randint(x,y)」でx~yの範囲の整数を乱数として出力することができます。これのためにrandomモジュールをインポートしました。

nビットの数というのは2n-1~2n-1の範囲にある数の事です。したがってxに2**(n-1), yに2**n-1を入れれば、nビットの乱数を生成することができます

後は「Step2:素数判定」です。生成された乱数mが素数であるかをチェックして、もし素数であれば、そのmが出力として帰ってきてプログラムは終了です。もしmが素数でなければまた6行目からやり直して素数がでるまで繰り返します。

MRPT(p,t)のpは素数判定したい数値、tは素数判定の精度に関するパラメータをいれます。パラメータは50にしておきます。詳しい話は前出のミラーラビン法実装の解説記事をご覧ください。

mr.MRPT(m,50)と入れることで、mが素数であればTrue,素数でなければFalseと帰ってきます。なのでmr.MRPT(m,50)とTrueが一致すればmを出力すればよいです。これが10行目、11行目の記述です。

注意点

このプログラムは、n=1を入れるとバグります。無限ループから抜け出せなくなります。

n=1の場合、2**(n-1) =1, 2**n-1 = 1なので常にm=1となります。1は素数ではないため素数判定を通過できませんが、素数判定に渡される数字は常に1なので、一生Trueはでません。なのでプログラムは終了しません。

値をいれて動作確認をしてみる

実際に数値を入れて試してみます。先ほどのプログラムの下に以下の記述を追加します。

n = 
for i in range(10):
   print(PNG(n))

 

nにいくつか値をいれて、出力される値を確認してみましょう

n=3

出力結果

5
7
7
5
7
5
5
7
5
5

3ビットは4~7なので、素数は5と7の二つ。それがちゃんと出力されています。

n=10

出力結果

1009
907
991
997
827
811
911
929
541
523

少し値を大きくしてn=10を試してみました。10ビットは512~1023の範囲の数ですが、ここら辺になってくると本当に素数なのかパッとはわかりませんね。ちゃんとそれっぽい数が10個出力されているので、正しく動いていそうです。

n=50

出力結果

991184641413209
968816360349679
808130905212259
711449259903133
672264780098893
783793118516663
589602139631809
871790315473787
665165186070773
783330867962033

この辺になると人力では素数かどうか判別するのに時間がかかるでしょうが、瞬間的に10個の素数を吐き出してくれます

n=100

出力結果

700512392775088966400688102949
982170845937799541458331694673
775629583507884931067526881887
1179347338337180199717246712439
1233106444322252832065443456973
860627983364469621719078224813
1049002089587589333624909905603
1196324948650133460244042769063
953002948643724691353930822179
1171227393886388928884419561177

よくわかんない大きな数字が出てきました。処理速度もまだ一瞬で終わる感じです。

n=512

出力結果

8702474761314652867450396237487664885872698800560780225820743566430558476521969805568320290341266719072007036447262134392800220725422227594494139993013087
7439018415904748008497830630473873280533663609581786880207544200477207319786458036192908421641493276524240982643471815810099253371971135508920473563545379
6770765643381819503812455050943292918439267356523072554735484104280304455879030333207895671339119519338746819853898998313369045924847162149716817614762217
11252438820326594356609298276305591317389577560191958622307208648725058094117575361219917530173296780684710082657153340540467348030622901527120507581795659
12629070804476665499082118192439331718182354549560971193929593703024529920243087698011753631930825325633993599167272922942420345534995518728549542582132133
8498743731258696960361510590532102554694036850046924168815507569215544726395455932619252887488300249975175258059609867308071521873096448477202983886248813
11926025583852575468205429646423190118725911211604864756182772515967801263330400878481067365475015733091258826820874281690287269578072695576101456636044927
10565077040149207618114221787909034956522708754942206676169563264113350422667381787675801276308654954332715032033206569669988110831431580026679742478716249
8492612894939015980289364961119685887918963229998203121636548142033303373403120366354299903982081217058595440422078734652005617937336240822094707276245871
9127986350534293498611768254866377648000704956897870806475592112073102484301306480831033410061479684141232223484517938970383717998989513894227793757135079

このくらいのサイズになると、処理がもっさりしてきますね。RSA暗号ではこの辺の大きさから使われる可能性があります。最近は1024ビットが多いのかな。

高速化の方法

私のPCとこのプログラムの組み合わせだと、512ビットくらいからモッサリし始めました。

暗号通信は私が使用しているPCよりもっと性能が悪い端末で行う場合もありますし、鍵長がもっと長い場合もあります。もうちょっとアルゴリズムを高速化したいところですね。

素数判定を高速化するアイデアにユークリッド互除法などの軽いプログラムでわかりやすい素数をふるい落としておくという「ふるい」の考え方があります。

ミラーラビンなどの素数判定プログラムは結構重いです。なので重いプログラムに数字に渡す数字を軽いプログラムであらかじめ厳選しておこうという考え方です。

たとえばユークリッド互除法を活用し3の倍数を予めふるい落としておけば、乱数mは1/3の確立で3の倍数でありますから、ミラーラビンの負担が2/3になります。3だけでなく、5,7,11…とふるい落とす範囲を広げればさらにミラーラビンの負担は減りますね。ちなみに2に倍数はミラーラビン側ではじけるようにしてあるので大丈夫です。

例えるならば忙しい上司に相談事を持ち込む前に、上司より暇な先輩に相談する、といった感じでしょうか。先輩で解決できることはそこで解決して、どうしてもという話だけ上司に持っていくというようなことです。

ふるいを活用した高速化に関する解説もいずれしたいと思っています。