最速の素数判定アルゴリズム
■ このスレッドは過去ログ倉庫に格納されています
0001 刺身定食
NGNG文献を読んでみたのですが、サッパリわかりません。
日本で完璧に理解している方、たまたまこのスレ
見ていたら、ついでに教えてください。
マジです。
0002デフォルトの名無しさん
NGNG理解できないのならあきらめるしかないでしょう。
他人をたよるのはよくありません。
0003デフォルトの名無しさん
NGNGその「さっぱり」って言葉がやるきねぇなぁと他人に感じさせるので、
そういう聞き方では知識ナルシスト以外教えてくれないと思われ。
0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNGデータとして保持しておくものだよ。
32bit整数MAXまでの素数リストがあれば実用上何も問題なし。
http://arch.arch.kumamoto-u.ac.jp/hagane/yamanari/joho2/kougi3.html
http://www.hotwired.co.jp/news/news/technology/story/2234.html
0006デフォルトの名無しさん
NGNG神父もびっくりだな
0007デフォルトの名無しさん
NGNG日本のチームはあるの？
京都産業大学なんか大学でチームつくってそうだな。
0008デフォルトの名無しさん
NGNG100万って、どのくらいなんだ？
100万文字ってなんKB？
0009デフォルトの名無しさん
NGNG0010デフォルトの名無しさん
NGNGBCDで持つとして、100万桁=50万バイト=5000キロバイト=5メガバイト
0011特殊早大生理論（広末涼子）
NGNG0013頭プアー
NGNG0014デフォルトの名無しさん
NGNG整数環の素元のこと
0015デフォルトの名無しさん
NGNG扱えるユニットがあるので
それで扱える桁数かな、とオモタわけ。
5MB程度ならいけるな、100万桁．．．．
ところで素数って正の数かしら？
0016 刺身定食
NGNG0017デフォルトの名無しさん
NGNGそのリストと照らし合わせる判定方法にすれば
それこそ速い遅いの問題ではないっていってるんだが？
通じないか？
0018デフォルトの名無しさん
NGNGリストってお前、500bitとか1000bitとかの素数まで全部保持するつもりか？
0019デフォルトの名無しさん
NGNG>32bit整数MAXまでの素数リストがあれば実用上何も問題なし。
って言ってんだろ?
0020デフォルトのやる気なし
NGNGHNにちょっとだけワラタ。 (^◇^;
0022デフォルトの名無しさん
NGNGメモリ管理とか考える方が先。
エラストテネスで32bitMAXまでの素数リストを作ろうと思っても
メモリがオーバー風呂して出来なかったYO。
あと、何万桁を計算する手法も考えるべき。
32bitとかそういうレベルじゃなく
それでいて素数判定が早いというのには意味があるが
実用的かどうかというと全然実用的じゃないと思う。
学術的には意味はありそうだな。
0023デフォルトの名無しさん
NGNGRabinの定理というものが知りたかったのか...
で、その定理の詳細ページどこかにない？
0024デフォルトの名無しさん
NGNGこれって適当に答え提出して「これは素数だ」って言い張ったらどうなるのだろう？
0025デフォルトの名無しさん
NGNGhttp://www.em.cache.waseda.ac.jp/research/complexity.html
確率性アルゴリズム
補題３
n≧2 が素数である必要十分条件は 0＜a＜n なる任意の a に対して
a^(n-1) ≡ 1 (mod n) が成り立つことである．
補題４
n が奇数の合成数ならば，
次の条件を満たす整数 0＜a＜n が少なくとも (n-1) / 2 個存在する
a^(n-1) ≡ 1 (mod n) が成り立たないか，または，
2i | (n - 1), 1＜gcd(a^((n-1)/2i -1), n)＜n を満たす整数 i が存在する．
これを使って 適当に乱数で検査して 素数らしさが十分だったら、それで
いいってのが１が欲しい乱数の作成方法でしょ？
0026デフォルトの名無しさん
NGNG素数が注目されているのは暗号化技術に必要だから、
例えば、公開鍵暗号には２つの素数 p,qが必要。
この素数p,qと別の数 e,dの関係が
e*d=n; n % (p-1)*(q-1) == 1 になるように e,dを見つけて
e と nを公開鍵 dを秘密鍵とする
暗号化は (平文^ e) % n として行い 解読は (暗号文^d) % nとする
この一連の流れが巧くゆくのはそれは p,qが素数だったからだけど
実際に必要なのは e,d,n
逆にこの一連の流れさえ巧くゆくなら p,qが素数であったかかどうか
を問い詰める必要はない。 逆に考えれば、素数らしいｐ、ｑさえあ
れば、試してみて復元出来るならそれでいい。
という事で、p,qがホントに素数かどうかより 素数らしい値を手軽に
得られる方法でいいという理屈。
002726
NGNG○ n=p*q; (e*d) % (p-1)*(q-1) == 1
0028デフォルトの名無しさん
NGNGMax32ビットの素数リストすら作れない、
メモリの確保が不可能だ。
37万くらいまでなら泥臭い方法で出来たけど。
10桁ですら、とてもとても。
0029デフォルトの名無しさん
NGNG0030デフォルトの名無しさん
NGNGこのあたりまでのリストなら
ならなんとか....
0031デフォルトの名無しさん
NGNGエラストネスのふるいを使えばどうでしょうか？
基本的にある数Nが素数かどうかはN^1/2までの約数が無いかを調べればよいので、
N^1/2を超える最小の1からのすべての素数の積(変な日本語ですいません)
までのパターンがあれば、後はNをその積で割った余りを検証すればよいのでは？
1*2*3*5*7*11*13*・・・・・・って計算していって0xFFFFを超えた数を見つければ
良いと思います。
003231
NGNGエラストテネス？恥ずかしい・・・
003331
NGNG0034デフォルトの名無しさん
NGNG中途半端な知識だな。
それはRSAな。
○RSA∈公開鍵暗号
×RSA＝公開鍵暗号
×RSA∋公開鍵暗号
003554
NGNG何の略か忘れたけど・・・
003634
NGNGRSA暗号は発案者三人の頭文字をとっている。
Rivest
Shamir
Adleman
で、こいつらが作った会社の名前もRSAセキュリティ
0037デフォルトの名無しさん
NGNG>>31
つかってるよ。
ただ、エラスネスするためには
配列やリストを用意しなければいけないんだけど
Booleanの配列で
32bit個の入れ物をつくっちまうと
メモリオバなのよ。
直接メモリのビットを見ればいいんだけどねえ。
軟弱プログラマだからやり方しらないよ。
0038荒井注
NGNGエラトステネスだバカヤロー
0039デフォルトの名無しさん
NGNGかかった（PenMMX266）ので途中で断念した。時間かけ
ればできるけど、それでもまだ１０桁だよ。１００万桁なんて
想像できん。
0040デフォルトの名無しさん
NGNG0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNGどういうアルゴリズムを使うわけ？
素数の定義からは逃げられないよ。
0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNG激しく同意。
0045デフォルトの名無しさん
NGNGめちゃくちゃややこしいし
一つの数が素数か否かを判断するのにも
膨大な時間がかかる。
この部分を分散計算するという考えそのものが思いつきもしない。
ｳﾂﾆｬ
0046デフォルトの名無しさん
NGNGBCDや１００進法で 500KByte 掛算時のΣai*biで桁溢れがおきないから大丈夫
でも、素数かどうか判定するのはどうかな？
１の言うRabinの定理で確実に素数らしい奴の予想をつけといて、それを皆で割って
みるしかないとすると、 参加者が何人いてもあんまり助けにならないよね
0047デフォルトの名無しさん
NGNG>素数とは、1、3、5、7、11、13など、
>1およびその数自体でしか割り切れない数
大学４年生にもなってはじめてしりましたよ。
0048デフォルトの名無しさん
NGNG....99999677/99999703/99999721/99999773/99999787/99999821/99999827/99999839/99999847/99999931/99999941/99999959/99999971/99999989/
0049デフォルトの名無しさん
NGNG重箱隅だが2も素数だよ。
0050デフォルトの名無しさん
NGNG0051デフォルトの名無しさん
NGNGで、メモリ直読みでエストラネスをやってみようか。
符号なし32bitMAX程度は出したいですね。
4294967295
でも
符号なし64bitMaxの18446744073709551616
は出来そうにない...
これでも100ﾏｿ桁まであと....
0052デフォルトの名無しさん
NGNGすごい桁数扱えるのね。
妙な所を
きっちりと作ってやがんな＞＞MS
0053デフォルトの名無しさん
NGNG0054デフォルトの名無しさん
NGNG0056デフォルトの名無しさん
NGNG>>53-54どこみていっているんだ？
005756
NGNG0058デフォルトの名無しさん
NGNG10^(10^6)〜(10^(10^6) + 2^24) の範囲には素数がありそうだと思える
これらの全部のフラグをたてといて、
Rabinのアルゴリズムで最後迄残った数個に絞り込むのはそれほど大変じゃない筈
後は、これが素数かどうかを証明する方法だなあ・・・
0059デフォルトの名無しさん
NGNG１と自分以外で割り切れるかどうか、試せばいいんじゃないの？
0060デフォルトの名無しさん
NGNGいや、あの、それじゃ１命令10GHzで多桁除算が出来たたとしてもさ
10^(10^6)/10^10 = 10^(10^6-10)秒かかるんだよ
10^(10^6) のオーダだとフルイに使うメモリにしたって
世界中のパソコンのハードディスク足したって足りはしないさ。
006158=60
NGNGそれから √n迄でいいから、上の計算よりずっと少なくて
√(10^(10^6) )/10^10 = 10^(1000-10)=10^990秒でいい
0062デフォルトの名無しさん
NGNGFFT方式だとどれくらい早くなるのかな？
0063デフォルトの名無しさん
NGNGハゲしく同意
フルイにかけるメモリ確保すら問題
0064デフォルトの名無しさん
NGNGだれか量子コンピュータを作ってよ。
0065デフォルトの名無しさん
NGNGfor (c=2;c<√(a+b);c++)
{
if(cが素数でないなら)continue;
if( (a+b) % c !=0) goto 素数でない
}
だったらいいんでしょ？
(a+b)%c = (a%c + b%c)%c だよね？
a=1000000! としとけば、100万迄の a%cはゼロだから
計算量は100万分の１になるんじゃないかな？
0066デフォルトの名無しさん
NGNG0067デフォルトの名無しさん
NGNGn! = n^n * e^(-n) * SQRT(2*pi*n) e^(1/(12*n) - 1 / (360 * n^3) + θ/(1260 * n^5))
(0<θ<1)
です。
006865
NGNG100万分の１じゃなくて100万分の節約ってだけだな
0069非65
NGNGLog[2.0,Gamma[1000000.0]] ≒ 1.85 10^7
1000000!は10進数で約557万桁、約1850万ビットの数ですか....
想像つきませんね。
0070デフォルトの名無しさん
NGNG100万桁よりも長い最初の素数 5万ドル
10億桁よりも長い最初の素数に対する最高金額の25万ドル
だからなあ
0071デフォルトの名無しさん
NGNGhttp://www.eff.org/awards/coop.html
狙うならもう１桁上だね
0072デフォルトの名無しさん
NGNG求めるならメルセンヌ素数を求めたいね。
0074デフォルトの名無しさん
NGNGなんで桁数が10進法で上昇しなければならないんだ？
意味わからん。
0076 １
NGNG僕が参考にしていた文献です。
これをもとにして、高速な素数判定ソフトを作りたかったんですが、
無学なもので、内容が理解できませんでした。
そういう悲しい事情です。
【参考文献】
「アルゴリズムの基礎」
五十嵐善英、西谷泰昭 共著
コロナ社
ISBN4-339-02348-5 \3,000
≪8.5 Rabinの素数判定アルゴリズム（P168−170）≫
0077デフォルトの名無しさん
NGNG32bitのintの最大値
2147483647
は素数なんだけど、これを泥臭く2.3.4....2147483646でわってみる判定方法で
やったとしても今のマシンなら数分(今試したよ)なのだから
高速素数判定ソフトを作っても
何の意味もないような気がする。
32bitや64bitを超えた数値を扱う方法は
アルゴリズム以外の面で実装が大変だ
>>1さんは
その辺りの事、わかってらっしゃいますか？
2147483647までの素数列を全て求めるときの
高速アルゴがあるのなら教えてもらいたい。
アルゴリズムというより
そのデータを保持するメモリ管理の方が知りたいな。
0078デフォルトの名無しさん
NGNGソースはこれから辿って下さい
http://search.net-newbie.com/php/function.gmp-prob-prime.html
0079１
NGNG実装が大変なんですか。あまりよくわかっていませんが、
桁が多いと、扱える変数（？）がなくなると言うことですか？
それにともなって、細工が必要になるのかな。素人でスマン。
＞2147483647までの素数列を全て求めるときの
＞高速アルゴがあるのなら教えてもらいたい。
僕が最初、試したアルゴリズムは、
６ｎ±１（ｎ≧１、ｎは自然数）を、素数の候補として、
手当たり次第に√（６ｎ±１）に達するまで、
（６ｎ±１）ｍｏｄ（既に得られてる素数）＝０
を判定する方法をとったんですが。これってダメ？
でも、これだと、2147483647までできないと思う。
やってみてもいないし。メモリ管理に至っては全然です…
0080デフォルトの名無しさん
NGNG0081デフォルトの名無しさん
NGNG○ 2^31
それから2^31迄の全ての素数を入れるのに必要なメモリは
およそ 4*( 2^31/ ln(2^31)) だいたい 400Mバイトだから フラグで記録した方が効率がいい
0082１
NGNG>>78
＞やったとしても今のマシンなら数分(今試したよ)なのだから
＞高速素数判定ソフトを作っても
＞何の意味もないような気がする。
＞その高速判定は、あくまでも確率的な判定方法ですよ
文献によると、
≪Rabinらはこの方法により、２＾ｐ−１なる形の整数が素数であるかどうかの判定を計算機を用いて行った。1<p<500の全ての整数についての判定をたった数分で行い、全ての判定は正しかったと報じている。この方法は素数であるかどうかを判定するどの決定性アルゴリズムより桁違いに速く、サンプル数ｍを適当な大きさにすることにより、誤りの確率をきわめて低くすることができる。≫
≪例えば、ｍ＝５０のとき、誤り確率は約千兆分の１となり、基本演算の所要時間が１μsで、３万時間連続稼働している間に１度の割にしか基本演算の誤動作が生じない計算機よりも信頼性が高い判定方法である。≫
とあります。
これ見て、作ってみたいなと思ったわけです。
0083１
NGNGアドバイスありがとう。そういう計算方法も知らなかったんです。理系だけど。ちょっとやってみます。
0084デフォルトの名無しさん
NGNGでいいからね
0085デフォルトの名無しさん
NGNG＞ n が奇数の合成数ならば，
＞ 次の条件を満たす整数 0＜a＜n が少なくとも (n-1) / 2 個存在する
＞ a^(n-1) ≡ 1 (mod n) が成り立たないか，または，
＞ 2i | (n - 1), 1＜gcd(a^((n-1)/2i -1), n)＜n を満たす整数 i が存在する．
X ≡Y mod n は 両辺の nの剰余が等しいという意味。
もしかして gcdという関数が判らないのか？
0086デフォルトの名無しさん
NGNGU32* GetSosu(void)
{
U32 *p;
int i, j;
p = malloc(sizeof(*p) * 2);
p[0] = 1;
p[1] = 2;
for(i = 3; i != 1; i += 2){
/* 素数判定 */
for(j = 1; (j <= p[0]) && ((i >> 1) > p[j]); j++){
if(0 != i % p[j]) break; /* 素数発見 */
}
if(j > p[0]){
/* 新しい素数を追加 */
p[0]++;
p = realloc(sizeof(*p) * (p[0] + 1));
p[p[0]] = i;
}
}
return(p);
}
仕事が忙しいから作ってみたよ。
テストはしてないんで、
コンパイルが通るかどうかは知らない。
何とか方とか難しいことは知らない。
っていうか、実は素数の定義自体も自信ない。
速度も別に気にしてない(毎回realloc()とかしてるし)。
あと、メモリ確保できなかった時の対処もしてない。
とりあえず、答えが出るのが何時になるかは知らないが
出せないなんて事は無と思う。
0087デフォルトの名無しさん
NGNGhttp://www.ml-labo.com/download.htm
これはどうだ
アルゴリズム(ラビン法): 予め決められた整数L と判定対象の整数p に対して以下を実行.
p = 素数の候補;
p = 1 + 2 k w を満たす k と w を計算（ただし, w は奇数）;
以下を L 回繰り返す {
1 < a < p なる a をランダムに生成;
y = a w mod p;
j = 0;
while ( ( j < k ) and ( y ≠ 1 ) and ( y ≠ p -1 ) ) {
y = y 2 mod p ;
j = j+1;
};
if ( ( j = k ) or (( j > 0 ) and ( y = 1 )) ) p は素数でない;
};
途中の whileが gcd だ。 意味が判らなければ gcd とユークリッド で検索してみろ
0088１
NGNGそうなんです。わかりません。gcdという関数の存在も今知りましたが、
それでも、文章の意味が分からないんです。
しかも、どこにツッコミ入れられているかもわからないんです。
つきはなさないで下さいね。
0089１
NGNGお忙しい中、ありがとうございます。
力不足ですいません。
時間かかりますけど、やってみます。
0090デフォルトの名無しさん
NGNGShorのアルゴリズムも、Rabinと同程度に確率的な判定法でしかないっす。
0091デフォルトの名無しさん
NGNG0092デフォルトの名無しさん
NGNGShorのアルゴリズムとは
0093デフォルトの名無しさん
NGNG和田秀夫 / 遊星社
最新の資料ではないがよくまとまっているし、プログラムコードも入っている。
専門家でなければ必読。
0094デフォルトの名無しさん
NGNG日本の東北大の教授とかが書いたやつなんてコードに無駄なとこ多くて読む気がうせる
0095デフォルトの名無しさん
NGNGこれだね
http://www.geocities.co.jp/SiliconValley-Oakland/8522/data/mformula.txt
モジュラベキとかgcdとか関数を増やしてけば使えるかも・・・でも
既に1000桁扱える１０進basicとかあるからなあ
アドバンテージはメモリがある限り桁数増やせる点だけど、今のアルゴリズム
じゃ掛算が遅くてダメだな
0096デフォルトの名無しさん
NGNGおおざっぱに書くと
１．Ｎを素因数分解したいとする。
----- 因数が見つかるまで２〜５を繰り返す ------
２．Nと互いに素で x<N な x を取ってくる
３．x^r == 1 (mod N) になる最小の自然数 r を計算
４．rが偶数になる確率は1/2程度。
５．rが偶数の時 gcd( N, x^(r/2)±1 ) のどっちかが、1やNでないNの約数を与える確率も1/2程度。
-------------------------------------------
ステップ３．を計算するのは量子コンピュータじゃないと死ねるので結局まだ実現不可だけど。
0097デフォルトの名無しさん
NGNG掛算で 10進 40万桁超で正しい答えが得られない筈
掛算途中の桁あげを処理しないといけない
でもこの修正をやっても実際は遅くて使い物にならないから意味ないけどね
function s100Mul(const a,b:s100):s100;
var i,ia,iaL,iaH:integer;
var cy,ecy:integer;
begin
SetLength(Result,Length(a)+Length(b));
cy:=0;
for i:=0 to High(Result) do
begin
iaL:=Max( 0,i-High(b));
iaH:=Min(High(a),i );
ecy:=0;
for ia:= iaL to iaH do
begin
cy:=cy+a[ia]*b[i-ia];
if cy>100000 then
begin
cy :=cy-100000;
ecy:=ecy +1000;
end;
end;
Result[i]:=(100+(cy mod 100)) mod 100;
cy:=ecy+(cy-Result[i]) div 100;
end;
s100CyNorm(Result,cy);
end;
0098デフォルトの名無しさん
NGNG2.3.5.7.9.
10を調べると2で割れるから素数ではなく
11を調べるとこれまでリストした全ての素数のうち
11/2=5以下のもので割り切れないから素数
2.3.5.7.9.11.
12を調べると2で割れるから素数ではなく
13を調べるとすべての素数で割り切れないから素数
2.3.5.7.9.11.13.
14を調べると2で割り切れるから
15を...3で割り切れる
16を...2で割り切れる
17を...これまでリストした全ての素数のうち
17/2=8以下のもので割り切れないから素数
2.3.5.7.9.11.13.17
とやっていくと
計算量が減り、まあまあ高速に素数リストが出来て
メモリのことも考慮しなくていいようになるかも。
ダメ？
0099デフォルトの名無しさん
NGNGここは！！！
http://www.ie.u-ryukyu.ac.jp/ie/mirror/www.iip.ie.u-ryukyu.ac.jp/yuu/c_html/sosuu.html
010099
NGNG0101デフォルトの名無しさん
NGNGそれより計算量が多かったり低速だったりする方法って思いつかないぞ。(w
√N を計算するより N/2 以下の素数全部で割ってみる方がマシってこと？
■ このスレッドは過去ログ倉庫に格納されています