素数生成

ウィキペディア小見出し辞書

素数生成

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/16 13:48 UTC 版)

「Guarded Horn Clauses」の記事における「素数生成」の解説

エラストテネスのふるいを使い素数生成を行うプログラム例を示す。 gen_primes(Max,Primes) :- gen(2,Max,Ns), sift(Ns,Primes). gen_primes/2を実行すると、gen/3とsift/2の2つのプロセスが生成される。gen/3はMaxまでの自然数のストリームを生成し、sift/2はそれをふるいにかけ素数のストリームをPrimesに返す。gen/3とsift/2とはそれぞれ並行して動き、gen/3で生成された自然数のストリームは変数Nsを介して順次sift/2に渡される。プロセス間の同期は、ストリームの各要素が具体化されるまで待つ、という形で自然に表現される。 gen/3、sift/2の各プログラムはそれぞれ以下のようになる。gen/3は、自然数のストリームを順次生成しMaxを超えたら終了する。sift/2は、2,3,5,7,..などの各素数の倍数をストリームから取り除くfilterプロセス（ふるい）を順に生成しながら、求まった素数を順次ストリームの要素として返す。各filterプロセスは変数を介して直列に繋がれていくため、自然数のストリームから素数のみのストリームを求めることができる。 gen(N0,Max,Ns0) :- N0=Max | Ns0=[].sift([Prime|Xs1],Zs0) :- Zs0=[Prime|Zs1], filter(Prime,Xs1,Ys), sift(Ys,Zs1).sift([], Zs0) :- Zs0=[].filter(Prime,[X|Xs1],Ys0) :- X mod Prime=\=0 | Ys0=[X|Ys1], filter(Prime,Xs1,Ys1).filter(Prime,[X|Xs1],Ys0) :- X mod Prime=:=0 | filter(Prime,Xs1,Ys0).filter(_, [], Ys0) :- Ys0=[].

素数生成

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/12 22:09 UTC 版)

「Concurrent Prolog」の記事における「素数生成」の解説

エラストテネスのふるいを使い素数生成を行うプログラム例を示す。 gen_primes(Max,Primes) :- integers(2,Max,Ns), sift(Ns?,Primes). gen_primes/2を実行すると、integers/3とsift/2の2つのプロセスが生成される。integers/3はMaxまでの自然数のストリームを生成し、sift/2はそれをふるいにかけ素数のストリームをPrimesに返す。integers/3とsift/2とはそれぞれ並行して動き、integers/3で生成された自然数のストリームは変数Nsを介して順次sift/2に渡される。読み出し専用標記により変数Nsによるintegers/3からsift/2へのデータフローの方向が表現され、プロセス間の同期はストリームの各要素が具体化されるまで待つという形で自然に表現される。 integers/3、sift/2の各プログラムはそれぞれ以下のようになる。integers/3は、自然数のストリームを順次生成しMaxを超えたら終了する。sift/2は、2,3,5,7,..などの各素数の倍数をストリームから取り除くfilterプロセス（ふるい）を順に生成しながら、求まった素数を順次ストリームの要素として返す。各filterプロセスは変数を介して直列につながれていくため、自然数のストリームから素数のみのストリームを求めることができる。 integers(N0,Max,[N0|Ns1]) :- N0=Max | true.sift([Prime|Xs1],[Prime|Zs1]) :- filter(Prime,Xs1?,Ys), sift(Ys?,Zs1).sift([], []).filter(Prime,[X|Xs1],[X|Ys1]) :- 0 is X mod Prime | filter(Prime,Xs1?,Ys1).filter(Prime,[X|Xs1],Ys0 ) :- otherwise | filter(Prime,Xs1?,Ys0).filter(_, [], []).

素数生成

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/15 05:03 UTC 版)

「RSA暗号」の記事における「素数生成」の解説

桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。 (なお、拡張リーマン予想が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。 2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したが、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。