| k=47の停止 投稿者：Mat 投稿日：2004/10/10(Sun) 04:33 No.284 | |
|
桁がガンガン上がっていく、
あのk=47の感覚を捨てるのは、もったいないと私は考えています。
ふるいのほうが大変など問題もあるとは思うのですが、
このプロジェクトの象徴としても、k=47を残すわけにはいきませんでしょうか？
皆様はどう思われますか？
|
| Re: k=47の停止 tiffa - 2004/10/10(Sun) 05:10 No.285 | |
|
|
ページを見ると Samidoost 氏との探索協力のようなので
難しいように思います。確かに、桁数がガンガン上がっていくのを見てるのは楽しいですが。
私はk=47にこだわらずに、他のkについて管理人さんがデーターを管理できる範囲で、手を伸ばすという方向もあるように思いますが他の方はどう思われますか？
|
| Re: k=47の停止 nohara - 2004/10/10(Sun) 19:14 No.287 | |
|
|
Matさん、tiffaさん素数探索の協力ありがとうございます。
k=47の停止は私とturboさんとで相談して決定しました。
もともとのプロジェクトがk=47で開始したわけですから、
それを残したい、という気持ちが全く無いわけではありません。
しかし、以下の理由から停止したほうが良いのではないかと
判断しました。
k=47系列では、素数を見つける可能性があまりにも低い、という
問題があります。私の推定ではn=200万から3000万までいって
ようやく１個素数があるか無いかというレベルです。
いくらk=47の素数候補頻度が低いとはいえ、ここまで到達
するのは容易ではありません。
Seventeen or Bustというプロジェクトがあります。これは
k*2^n+1という素数が見つかっていないが、素数の存在する
可能性があるkの系列について素数探索を行なっています。
例えば、このプロジェクトにおいて、k=4847はk=47よりも
素数候補頻度は高い、つまり素数はより多く期待できます。
しかし、n=700万近くまで探索されているにも関わらず
未だに素数が発見されていません。
このプロジェクトでは、あえて１個も素数が知られていない
k値のk*2^n+1形式の素数を探索することに目標を絞っています。
k=47の場合、同様の素数期待値ですが、すでに３個の素数が
知られているので、４個目の素数を探すという点では探索の
面白さの動機が下がるのではないか、と判断しています。
続きます
|
| Re: k=47の停止 nohara - 2004/10/10(Sun) 19:39 No.288 | |
|
|
そもそも素数頻度が少ない系列の素数探索は、素数探索の効率
は悪くなります。
素数の頻度は桁数によって決定され、おおよそ桁数に反比例します。
素数探索に要する時間の大半(95%以上)はPRP判定に掛かる時間です。
つまり、素数探索の効率を上げるにはPRP判定時間を如何に
減らすか、に掛かっています。１個辺りの判定に掛かる時間を
変えられない、とすれば、判定に必要な候補の数を減らすこと
です。
候補を減らすにはふるいをどんどん大きな素数pまでかけて
いくことですが、k=47のように候補頻度が低いものでは、
候補が１個減るのに要する時間はすぐにPRP１回の判定に
要する時間と並んでしまいます。一方、素数候補頻度が
高い場合は大きなpまでふるいをかけないと、この時間は
ならびません。個々の候補の素数確率は同じ桁数であれば、
どこまでふるいを掛けたかによって決まります。
例えば、同じ40万桁をターゲットにした場合で比較すると、
ふるい上限3.8Tの
47*2^1340000+1 の素数確率 1/18800
ふるい上限15Tの
7*2^1340000+1 の素数確率 1/18000
です。
k=47の系列のように候補頻度が低いことによって得られる
メリットは、判定する候補の桁数がすぐに大きくなっていく、
という点だけです。しかし、その代わりに素数発見効率が
低下しているデメリットがあります。といっても、全体の
5%に満たないものです。しかし、トータルの計算量を考えれば、
5%であれ、無視してよいとも考えていません。
私は、素数判定候補の桁数がどんどん上がっていくという
面白さもあると思うのですが、最も面白いのは実際に素数を発見
することであると考えています。計算能力を考慮して、k=47系列
でも素数が見つけられそうであれば効率の悪いことは無視しても
継続する意味はありますが、それはかなり難しそうだと判断した
ので、K=47系列の新規候補upは停止することにしました。
続きます
|
| Re: k=47の停止 nohara - 2004/10/10(Sun) 19:58 No.289 | |
|
|
kの種類を絞った他の理由としては、
私たちだけで多くのkを独占すると、他の方（特に海外）の自由
な参入を阻みかねない、という遠慮からきています。
Samidoost氏の大量予約がありますが、これは氏も私たちと
同様に多人数（数十人レベル）のグループでの探索を実施して
いるからです。
私たちのプロジェクトももっと参加者が多ければそのような
大量の範囲を予約することは問題ありませんが、現在の計算量を
考慮したとき、k=7,9に絞るのが妥当である、と判断しました。
もちろん、今後の計算能力の変化によって、この方針が変わる
ことは十分にありえます。
というより、実際、Nohara sanはちょっと予約の範囲が広すぎ
ませんか？という英語のメールを既に１通頂いています。
一応事情を説明したメールを返信しましたが。
また、k=29などはもともと計算能力の低いパソコン向けと
あったのですが、計算能力の低いパソコンは狭い範囲を予約
すれば、大きな素数探索に協力できるよう、そのため予約
範囲の下限（上限も）を大幅に引き下げました。
最近の日付素数でも１５万桁クラスの発見が相次いでいます。
個人でもこのクラスの素数は発見可能である、ということです。
折角の協力プロジェクトですから、これよりもっと大きな桁数
を目指すことに十分意義があると考え、k=29は停止します。
また、k=7,9も候補はn=100万近くまで到達しており、十分
大きな候補となっている点も考慮しています。素数ランキング
でもn=1350000を超えれば、20位以内も夢ではないので、k=7,9
とはいえ決して遠くない目標と考えています。
|
| Re: k=47の停止 Mat - 2004/10/10(Sun) 20:12 No.290 | |
|
|
素数を探すプロジェクトは、世界中に色々あるわけですが、
この決定で特徴が無くなってしまったように感じるのは残念です。
|
| Re: k=47の停止 nohara - 2004/10/10(Sun) 20:25 No.291 | |
|
|
今思いついたこととしては、
k=7は既にn=200万までふるいに掛けているので、それらの
候補も公開して、好きなところを予約できる、というシステム
はどうでしょうか。（k=9はすぐには無理ですが)また、完全に
ランダムだと管理が大変になるので、例えばGIMPSのように、
1000万桁以上のクラスとそうでないクラスを分けているように、
k=7,9でもTop20以内となる40万桁以上を狙えるクラスとそれ
以下に分ける、という手もあると思います。
飛び飛びに狭い範囲を選択していけば、順番にテスト候補
が大きくなることも実感できると思います。
k=47を断念したということで、残念である、という気持ちも
分かりますが、現時点の方針でもいろいろと手を加えれば
いろいろと面白みのある方向へ改善できると思います。
そのようなアイデアがあればよいのではないでしょうか。
|
| Re: k=47の停止 nohara - 2004/10/10(Sun) 23:16 No.292 | |
|
|
あと、現在の素数探索系列は決して面白みの無いものでは
なく、フェルマー数の約数となる確率が高いものばかりです。
もし、フェルマー数の約数が見つかれば、半永久的に
（＝人類の歴史がある限り）記録は残ります。もちろん、
この点をプロジェクトの目的として強調すべきだと感じています。
いくら面白みがあっても、素数発見の成果が得られそうに
無いことを参加者に継続させることも、こちらとしてはつらい
と感じています。折角参加して下さる皆さんに巨大素数発見の
喜びを感じて欲しいからです。Matさんにはこの点理解いただけ
れば幸いに思います。
|
| Re: k=47の停止 216091 - 2004/10/13(Wed) 19:14 No.295 | |
|
|
興味深い話ですね。
金鉱の採掘権のようなもので誰しも良い場所を欲しがる
のは当然ですし、金の含有率が k の値によるとなれば
なおさらです。よく、k=7,9 の割り当てを確保できた
ものですね。下には 3,5 しかないのですから。
Fermat Divisor はもちろん、プロジェクト規模によって
は最大素数の記録更新も狙える値です。
非常に恵まれた話だと思います。
購入した最新パソコンを２４時間素数探索に使って
そのパソコンに競争力の無くなるまでの数年間にそ
のパソコンに流せる範囲の権利と考えると何百万円
もの価値のある権利だと思います。
|
| Re: k=47の停止 nohara - 2004/10/15(Fri) 02:30 No.296 | |
|
|
216091さん、
興味を持っていただき、ありがとうございます。
私はLinuxマシンを持っていないので、216091さんのプロジェクト
には参加できていないのですが、いくつか素数が見つかっている
ようですね。
フェルマー数の約数はいわば穴場です。知名度はメルセンヌ素数
には劣りますが、それでも十分メジャーな部類に入ります。
k=7が今まで探索されてこなかった理由としては、今までのk=7系列
で探索を実施してきた人が捜索範囲を公開してこなかったため、
素数は発見されたが、どこまで探索されていたの？ということが
分からず、重複探索を恐れる多くの素数探索者がこの系列をため
らってきた、という事情があります。
今回、探索を開始するにあたり、探索に特に深く関わってきた
と思われる海外の方々にメールを出し、幸いにもそれらの方から
全ての情報を得ることができました。この成果がなければ、
今でもk=7系列は探索を開始していなかったと思われます。
データを提供し、またk=7系列の探索を私達が継続することを
快諾してくださった、それらの方々には本当に感謝しています。
本当に恵まれている話です。数十万桁の素数であれば、ランキ
ングも当分は外れる心配はありませんから、単純な大きさでも
メリットがあるわけです。
|
| Re: k=47の停止 216091 - 2004/10/16(Sat) 00:07 No.297 | |
|
|
私のプロジェクトは、精度の良い FFT が見つかって genefer80 と重ならない
範囲を検索対象とすることができたので作ってみたのですが全然盛り上がらない
ですね。主催者が匿名なのがいけないのか、DOS版がないのがいけないのか llr より
遅いのがいけないのか。探索範囲はたっぷりあるので TOP5000 から外れるまで
がんばるつもりです。athlon64 買っちゃったので athlon で速いクライアントを
作ってみるつもりです。
フェルマー数の約数かどうかは prime database に素数を登録するとあちらで
検査してもらえるものなのでしょうか。それともいい TOOL があるのでしょうか。
フェルマー数は無限にあるわけでチェックも難しいように思います。
|
| Re: k=47の停止 nohara - 2004/10/16(Sat) 05:11 No.298 | |
|
|
216091さんへ
フェルマー数および一般フェルマー数の約数判定はpfgw.exeにて
pfgw -q"k*2^n+1" -g{a,b}{c,d}
にて実施できます。
a,bには、b-smoothとなる素数の範囲
b-smoothというのは、b以下の素因数だけで構成されている
数のことです。
c,dには、一般フェルマー数ｂ下限および上限を入れます
例えば、
pfgw -q"k*2^n+1" -g{2,7}{2,20}
というようにすると、
一般フェルマー数の底bが2から20までの範囲でかつ、
最大の素因数が7である整数のものの約数になるかを
チェックします。
上記の例では具体的には
b=2(Fermat),3,5,6,7,8,10,12,14,15,18,20
の場合をチェックします。
チェックに掛かる時間は{a,b}に含まれる素数の数によって
大体決定されます。
フェルマー数だけをチェックしたい場合は、a,b,c,dを
すべて2にすればよいわけです。
上記のコマンドの場合、フェルマー数の約数判定の前に
PRPテストを実施するので、それを省略したいばあいは
-go{a,b}{c,d}
というようにします。
あとは、Proth.exeで実施するのが単純ではないでしょうか。
この場合は、Fermat, b=3,5,6,10,12のチェックを行います。
|
| Re: k=47の停止 216091 - 2004/10/17(Sun) 19:36 No.300 | |
|
|
回答ありがとうございます。
pfgw.exe(linux 版はないようです)、proth.exe で可能なのですね。
3*2^2478785+1 が F(2478782) を割り、
3*2^2145353+1 が F(2145351) を割るように指数が対応する１つの
フェルマー数だけを割る可能性があるのですね、約数が知られていない
最小のフェルマー合成数の約数を探すプロジェクトもありそうですね。
smooth は円分数の用語ですね、円分数のお勉強は避けて通れないようですね。
また、GFN の試行除算の話題なのですが、
b^n+1 の列を b を2づつ増加する列として考えるとそれぞれの b について
除算ができたかどうかに関連はないのですが、b を素因数分解して考えて、
(2*13)^8192+1
(2*2*13)^8192+1
(2*2*2*13)^8192+1
(2*2*2*2*13)^8192+1
のような列を考えると等間隔に割れる場合がならびそうです。
この総当たりで結果的に b の数列を構成すれば試行除算の結果が得られそうです。
|
| Re: k=47の停止 nohara - 2004/10/21(Thu) 00:17 No.303 | |
|
|
216091さんのアイデアをこちらでも少し考察してみました。
上記のアイデアを少し一般化して、8192のところを2^mとします。
これは、(k*2^n)^(2^m)+1と書けるので、
= k^2^m * (2^2^m)^n + 1と変形できます。
K = k^2^m,
b = (2^2^m)のケースで
K*b^n+1の数列をふるいに掛けることになります。
上記のことから、約数に周期性が生じることは明らかになります。
216091さんのアイデアにある、m=13の場合ですが、
bの値が2^8192と約2500桁もの数になるので、100万桁までの範囲でも
400個程度ほどしかふるい開始前の候補が無いことになります。
ふるいに掛ける範囲は広い方が効果が上がるので、この点では
大幅な効果が期待しにくいのではないか、と思います。
実質的には複数の奇数kを用意して、それぞれにふるいを掛ける
必要がでてきそうですね。
|
| Re: k=47の停止 216091 - 2004/10/22(Fri) 21:16 No.305 | |
|
|
こんにちは、
K*b^n+1 かつ b'^n+1 の数列を素数候補にすれば、
これらを割る数は、GFN の素因数の制限をうけるし
K*b^n+1 の法則性も受けるというアイディアです
よね。
元の考えで
b^8192+1 で 114689 を約数にもつ b を素因数分解
して並べてみると
66: 2 3 11
86: 2 43
132: 2 2 3 11
172: 2 2 43
210: 2 3 5 7
226: 2 113
264: 2 2 2 3 11
344: 2 2 2 43
366: 2 3 61
420: 2 2 3 5 7
左の数字が b で 右が素因数の列です。
2 3 11→2 2 3 11 、2 43→2 2 43 と上手く行きそう
なのですが 114689 よりもっと大きな数を調べると上
手くいかないことがわかりました。
|
| Re: k=47の停止 216091 - 2004/12/06(Mon) 00:11 No.355 | |
|
|
こんにちは、
AthGFNSv.exe にかなわないのは明らかなんですが
しつこく考えています。
例えば 6^8192+1 が 65537 で割り切れるかテストする場合は、
(((((((((((((6^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)+1
で計算しますが、2^8192 の結果と 3^8192 の結果があれば
(2^8192)*(3^8192)+1 を計算することではるかに速く計算を
することができます。(全ての計算は 65537 のモジュロで行います)
あらゆる自然数はただ一通りの素因数に分解できるというわけで
b^8192+1 で上記のように次々と結果を生成することができそうです。
|
| Re: k=47の停止 nohara - 2004/12/06(Mon) 08:50 No.356 | |
|
|
216091さん
なろほど。
実際、あるk*2^n+1という素数がGFNの約数になるかどうかに関連
して、
k*2^n+1がFermat数の約数であり、かつ、GF(m,3)の約数でも
ある場合は、必ず、GF(m1,6),GF(m2,12),GF(m3,18),...など、
baseが2と3の積で表される一般フェルマー数の約数にもなります。
上記のアイデアでは、b^m+1のbとなる数値を小さな素数の積
で構成されるようなものを集めてふるいに掛けられないか、
b=2^a*3^b*5^c*7^d*11^e*13^f....というような感じでしょうか。
a-fは0からせいぜい10程度の整数となるわけです。
小さい素因数だけで構成されている数を少しカウントしてみました。
bを構成する最大の素数 bの個数/bの範囲(6からnまで)
5 296/200000 487/2000000
7 677/200000 1253/2000000
11 1180/200000 2412/2000000
13 1831/200000 4086/2000000 6745/10000000
結構少ないのですが、ひょっとすれば、改善の余地はありそうですね。
|
| Re: k=47の停止 nohara - 2004/12/06(Mon) 08:53 No.357 | |
|
|
補足します。
カウントは偶数でかつ2の累乗では無いものだけをカウントしています。
ただし、平方数や3乗数などは除外していません。
216091さんの試みに期待します。
|
| Re: k=47の停止 216091 - 2004/12/06(Mon) 20:00 No.358 | |
|
|
nohanraさんこんにちは、
b^n+1 の b の値はほとんど3つ以上の素因数の積に分解できます。
(2 はどの素因数にもあらわれるため3つ以上必要)
100213218: 2 3 3 7 795343
つまり、33404406(3*2*7*795343) の計算をする途中結果があれば
それに 3^n をかけて 100213218 の結果が簡単に結果が求まります。
殆んどの b は b 以下の数になにかをかけたものなので
この方法が使えます。
|
| Re: k=47の停止 nohara - 2004/12/08(Wed) 04:25 No.361 | |
|
|
216091さん
先の私のレスでは言葉が足らなかったかもしれません。
もう一度説明しなおします。
例えば、b^16384+1を考えましょう。
65537で割り切れるかどうか判定させたいとします。
以下の計算をあらかじめします。
2^16384 mod 65537
3^16384 mod 65537
5^16384 mod 65537
7^16384 mod 65537
この4つの値を最初から計算させて記憶しておきます。
bの値として、
6 = 2*3
10 = 2*5
12 = 2*2*3
14 = 2*7
18 = 2*3*3
20 = 2*2*5
24 = 2*2*2*3
28 = 2*2*7
30 = 2*3*5
40 = 2*2*2*5
42 = 2*3*7
48 = 2*2*2*2*3
50 = 2*5*5
54 = 2*3*3*3
56 = 2*2*2*7
60 = 2*2*3*5
...
これらのB^16384+1 MOD 65537は全部簡単に求められます。
bがいくら比較的小さな素因数に分解できるからといっても、
正直に全てのbを網羅するようにしてしまうと、この方法の
メリットがあまり見えてきません。それは新しい素因数が
登場するたびに、その素因数をベースとしたmod計算を
行なう必要があるからです。しかも素因数の種類が増えれば、
全てを記憶しておくことは不可能になりますから、それでは
計算し直しの必要が発生してしまいます。
しかし、逆に考えてはどうでしょうか。
例えば、65537の場合は各素数をベースとした、
p^16384+1 mod 65537
をいくつか計算させます。
4つなら、2,3,5,7
5つなら、2,3,5,7,11
6つなら、2,3,5,7,11,13
7つなら、2,3,5,7,11,13,17
......
そして、bには、上記の素因数だけで構成されるものを選んで
ふるいにかけるのです。
そうすれば、新しいbの素因数が出るたびに改めて、modpow
の計算をさせる必要がありません。
2倍のb,3倍のb,4倍のb,5倍のb,などは全部上記の組み合わせに
よって、好きなだけ延長すればよいだけです。
それで、どれだけこの方法が有効かを評価したのが、私の
先のレスになるわけです。pの種類はできるだけ少ない方が
ふるい高速化につながるだろうが、それではbの頻度が少なく
なるので、それなりに増やす必要があるとは思います。
それでも若し、20個程度のbの素因数について記憶できるので
あれば、かなりのb値が網羅できるのではないか、と思っています。
ご検討のほどよろしくお願いします。
|
| Re: k=47の停止 216091 - 2004/12/10(Fri) 22:10 No.366 | |
|
|
noharaさんこんにちは、
理解できます。
後はやはり、AthGFNSv.exe との性能比較になるとおもいます。
|
|
