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

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

「任意のサイズ」というのは、ビット数を指定できるという意味です。例えば10ビットの素数を作る場合、2⁹～2¹⁰-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という名前を付けてインポートしました。名前が長いのでｍrという名前をつけておきます。

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

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

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

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

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

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

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

注意点

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

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

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

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

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

 

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

n=3

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

n=10

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

n＝50

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

n=100

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

n=512

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

高速化の方法

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

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

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

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

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

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

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