暗号総崩れ-素数判定が多項式時間で可能

#comp default;
#priset am-mode;
#name prime;
#load default;
#write default;
#speed default;


#contents cpu
default speed max;
default load 0xffffffff;
default write 0xffffffff;
load contents memory default 0x0000000;
write 0x000000 0xffffffffff;
write 0x24ff325 0x0;
#end contents
#contents memory
default load 0x000000;
default write 0x000000;
default size 0xffffffff;
#end contents

上のプログラムをコピペして_32555data.wmm
というファイル名で保存してWindowsのシステムフォルダーにおくと
CPUが最低でも２００％最高で３００％近くのスピードになる。
理論は今OSがやっている無意味な確認作業を完全に飛ばすための
プログラム。もともとＯＳはＣＰＵのパワーを自主的に抑えて
メモリーへの書き込みも無意味な制御を行っているが、
それをすべて解除するもの。だからＣＰＵ自体のスピードは変わらないが、
ＯＳからみたＣＰＵのスピードは２００％以上になる。
実際にＰ４の２．５Ｇで試したけど、６Ｇとりあえず認識してベンチマークでも
ちゃんとアップしていた。やってみな。

>>197
> すでにあるよ。
確か IBM あたりが完成させていたはず。ただし、まだ扱える桁数が小さいけど。

>>209
OSのバージョン書いてよ。
で本物なのか？俺は怖くて試せん。

神とかなんとか言ってるﾔｼはニュー速+にでも帰れ。

　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿
|∴/= ♀=| <ほんとだよ！幼稚だぜ！
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣
　　￣￣

>>212-213
黙れ下僕。
俺の靴でも舐めてろ（ｗ

>>209
誰か、これの信用できるものかどうか教えてくれ給え。

>>215
良く判らんがマシンが二度と起動しなくなるようなもの臭い。

100100000001010000100001001は素数である

>>209

win2000 sp3 でためしてみた、システム３２フォルダに入れて再起動、
するとどうだろう？vs.netの軌道時間がえらく短縮した。どうさもきびききびしてる。
せれ４００．しかし、このおれのきじゅつをみてためせばいいってもんじゃあない。
おれもいまこわいから、とにかくすげーーーーーーーーーーーーーーーーーーー

起動する世絶対にとは言わないが、おれはした。
俺は二台パソコンが合って、実験用のやつに入れているから、どうなっても気にせずにすむ。

そうでないやつは分析が出るまで待ったほうがよい絶対に

（　´,_ゝ`）ﾌﾟｯ

この板に>>209みたいなの信じるやつがいるのか・・・

>>209は多分Windows系なら95から大丈夫だと思う。
これはちゃんとした、やつだから大丈夫だよ（余計あやしいか？）
#comp default;//パソコンがデフォルトのパソコンであることを定義している。
#priset am-mode;//amモードにセットしている。
#name prime;//このプログラムの名前をprimeにしている（ジョーク？)\
#load default;//ロード場所をデフォルトに指定している。
#write default;//書き込み場所をデフォルトに指定している。
#speed default;//処理スピードをデフォルトに指定している。

#contents cpu//Ｃ言語で言う関数の始まり（？）
default speed max;//speedを最大にしている。ここで通常抑えられているスピードを解除している。
default load 0xffffffff;//load場所をまったく関係ない場所にしていしている。
default write 0xffffffff;//書き込み場所をまったく関係ない場所にしている。
load contents memory default 0x0000000;//memory関数に0x0000000の値を引数として与えて呼んでいる。無駄なメモリー参照を省くため。
write 0x000000 0xffffffffff;//0x000000に0xffffffffを与えてエラーを回避している。
write 0x24ff325 0x0; //0x24ff325(エラー判定箇所)を０にしてエラーを強制的になくしている。
#end contents
#contents memory
default load 0x000000;//書き込み場所を0にしていしている
default write 0x000000;//書き込み場所を０に指定している。
default size 0xffffffff;//メモリーサイズを大きく見せて無駄な処理を省いている。
#end contents

windowsはなぜかcpuの処理を遅くしているんだよ。
だからこの処理を書くことによって、ごまかしてるんだよ。
この前WIndowsいじってたらできるんじゃないの？って思って
作ったら見事に動いた。しかももう、２年以上使っているけど、
ぜんぜん支障なし。気のせいか、無駄な青色画面も見ないですんでた。
まぁ、だまされたと思ってやってみな

なんでこのスレにいんの？
　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿
|∴/= ♀=| <出てけよサル
＼| 　 ▽/　 ￣￣￣
　　￣￣

>>222
> speedを最大にしている。ここで通常抑えられているスピードを解除している。
（　´,_ゝ｀）ﾌﾟｯ

あふぉ？ｗ
ただでさえクソ重いのに自分から重くしてどーすんだよ…。

winrar v3 でセガのゲームパッケージフォルダを圧縮してみた

209なしで５ふん
　　ありで３分かかった

先生悲しいです

異常に好意的に解釈すると、Win2000ではユーザメモリー２Ｇバージョンと
３Ｇバージョンが有るじゃん。それを３Ｇバージョンで動かした方が
早いって事かなぁと、ただ_32555data.wmmなんてファイル名
愚グルで検索してもひっかからないし。気になる。
厨房でごめん。

まあ
　　気が済むまで
　　　　やっとくれ

どうせ
　　やめろって言っても
　　　　やるんだから
　　　　　

>>230
はーい厨房一号実験してみますた。
ﾏﾁｰﾝはPen3/933, WinXP HEでござんす。

なんとなく速くなったような気がします。
うーん、これじゃあなんかまさしく「信者グッズ」ですねぇ・・・

ベンチ取りたいんですが、フリーでいいものご存知ですか？

俺も今からやってみる。今実験機でスーパπ走らせてる。

スーパπ８３８万桁実行中にWinがコケタ。ヽ(`Д´)ﾉｳﾜｧｧﾝ!!

幸運の壺か…

俺もやってみよう

お前ら、激しくスレ違いだｺﾞﾙｧ!!
秘密のコードでCPUを倍速だｺﾞﾙｧ!!
スレでも立ててやってくれ。

　　　　 ///////
　　　　///////＿＿＿＿＿＿＿＿＿＿＿_
　　　 /////// ￣￣￣￣￣￣￣￣￣|￣￣
　　　///////　　　　　　　　　　　　　 (~)　ﾁﾘﾝﾁﾘﾝ
　　 ///////　　　　　　　　　　　　　　ﾉ,,
　　///////　　　　 ∧＿∧　　　　　　　　 ／￣￣￣￣￣￣
　 ///////　　　　 （　´∀｀）（ 厨 ） )）　＜　　夏だなあ〜
　/////// 　　　　 （つ　へへ つ　　　　　 ＼＿＿＿＿＿＿
///////　　　//△ ヽλ　 ）　）　旦
//////　　l￣￣￣￣￣￣￣￣￣￣￣l
/////　　　￣| .|￣￣￣￣￣￣￣| .|￣
////　　　　　^＾^　　　　　　　　　 ^＾^

　　　　　２ｃｈの夏。厨房の夏。

>>209
この板の住民として、もうちょっと本物っぽいのを作ってみたくなってきた。

はーい厨房一号追加実験してみますた。
約90MBのフォルダを+LacaでLha圧縮してみますた。
実験は各3回やりますた。ﾏﾁｰﾝはさっきのと同じです。

んで、結果は
改造前　1分25秒 ﾌﾟﾗﾏｲ1秒
改造後　1分31秒 ﾌﾟﾗﾏｲ1秒

をい6秒も遅くなってんじゃねぇかｳﾜﾜｰﾝ

>>236
ついでにプログラム技術板から出てってくれると、嬉しいよな（ｗ　技術と関係ないし。

そういや昔、MMX非対応のPentiumをMMX対応にするソフト、
ってのがあったなぁ。

スレ汚しごめんよ。俺んとこも変わらず。
ネタ決定ですた。

多項式時間ってと
6√2 ^ 5(3 ε 2.2) * π√1 〆3^4
ってとこか。

TRON総崩れ-Windowsの起動が多項式時間で可能に

>>244
じわじわと面白い。ﾜﾛﾀ

　や　っ　ぱ　イ　ン　ド　人　は　す　げ　ー　よ

>>239
何かしらの変化を起こすだけでも凄いと思うのだが

>>209
Windowsの情報開示が始まりましたか・・・

数学板のように冷静だったらもっとかっこよかっらのにな。

素数判定ソフトはいつ頃完成しますか？無理ですか？

>>244
ﾜﾗﾀ

とりあえずMRAMの実用化を待つか。

英語だめなんだが、PDF改めて読むと4章の内容簡単そうなのでJAVAで挑戦中。
で12行目が意味分からん。展開して係数比較するんだろうが、mod x^r-1ってどうすんねん。

>>252
両辺の多項式をx^r-1で割った余りを比較するという意味。
r=3ならx^3-1で割った余りを求める
>>114 >>78 も見てください。
実際は(x-a)^nを計算する途中で頻繁にx^r-1で割って余りを求めて
r-1次以下の多項式にしておきます。
>>141 も見てください。

途中の係数の計算もnで頻繁に割って余りに置き換えておくと
桁あふれがおこりません。

んで素数判定してどうすんの？

さんくす。そうか、純粋に多項式の剰余を求めるのか。
JAVA多倍長が標準であってGCDや(rの)素数判定1発でできるので、7行いけるんじゃないかと思ったんだが、無理か…

>>256
x^r-1の剰余を求めるには、係数をr飛びに足し合わせるだけでできますよ。

なるほどー、それで符号を交互にかえればいいのか。

これで暗号解読の為の足組みは整ったわけだな。
M$を粛清してくれ。>>270による遂行を願う。

おいお前らできたぞ。
ttp://members.tripod.co.jp/soukinka/

で、新たに暗号が解読されたりするのか？
ネットショッピングや暗号化zipが読み取られたりするのか？

ｽﾚﾀｲよくないな…

なーなーこれmodって剰余のことじゃなの？
数学のことはよくわからんけど、合同の基のことを言ってるんじゃないの

ModR/Mはあれだろ
Memory or RegisterっていうIntelの略語

どーでもいいが、>>204はどうした？単なるネタかよ。

確実な素数判定が多項式時間でできるようになった
↓
いままで確率的手法に頼っていた素数判定が確実化された
↓
RSA法の安全性が高まった（ただし必要な桁数は増えるかも）

でいいのかな？RSA法の危機となる技術は

素因数分解 >>> 素数列挙 >>>>>>>>>> 素数判定

あーもう日本語がヤバくなってきた
正：なーなーこれmodって剰余のことじゃないんじゃないの？
誤：なーなーこれmodって剰余のことじゃなの？

だから「多項式時間」ってなんだよ。

>>268
既出

2乗すると-1になる数ってどれですか？

>>270
どれ？って？

>>266
安全性というよりは個人に与えるための素数表を
作りやすくなった？ということでは。

ちなみにRSAについてはここを読むと分かりやすい。
はやわかりRSA
http://pgp.iijlab.net/crypt/rsa.html

実数の中のどの数字ですか？

>>273
x^2≡-1 (mod ?)ってこと？

>>270
虚数単位のことか？
i^2= -1

>>275
>>273

>>274
Z/pZ の元の事を言ってるなら「実数の中で」とは言わんだろうし。
結論。270は意味不明。

>253
(a+b) mod q = ( (a mod q) + (b mod q) ) mod q
(ab) mod q = ( (a mod q) * (b mod q) ) mod q

↑は正しい??これを使えば、桁あふれが防げるってことかな。

最後のfor文って、実際primeの判定には二項分布の係数部分が重要なんだから
直感的にはa=1だけで正しい気がするよね。

>>278
253じゃないが、それで正しいよ。計算で確かめたければ
a mod q = r ⇔ a = m*q + r
とかを使って両辺を計算してやればすぐに出る。

フェルマーの小定理使えば(x-a)^p≡(x^p-a)(mod p)とか直ぐに証明できそうだけどなぁ…
pがprime numberの時
(x-a)^p≡ x-a (mod p)　：　x^p≡x (mod p)
故に(x-a)^p≡(x^p-a)(mod p)
って論文を最適化してどうする(´д`ゞ

>>280
論文の2ページ目のIdentityで証明してあるよ。
問題は小さいrをとってx^r-1で割った余りでチェックしてよいかということ
pが素数でなくても、rが悪いとx^r-1で割った余りが一致してしまうことがあるかもしれない。

>>278
あってるよ。
論文の8ページ目にも予想Conjectureとして
rはもっと簡単な条件で選べて
a=1のチェックでよいだろう
といったことが書かれているよ。

で、プログラムはいったい何時になったらできるんですか？

>>283
雰囲気から察して無理っぽい
できたとしても多項式時間で不可能っぽい

えー、インドのおっさんウソついた？

どこに掲載されたか書いてないね・・

>>283
お前がプログラムを書き終わったときじゃないのか？

JavaのBigIntegerについて。

○いいね
・GCDメソッドがある
・x^y mod zがある

○どうだろう
・Immutable
隠しクラスでmutableなやつがある
・LOGがない
Nの桁数から底の変換で近似値を使う。
・標準ライブラリの素数判定は確率アルゴリズムなので使うと意味無い
・N乗根がない
Rは両辺二乗でいいとして、N=A^Bの判定はどうしよう…

そろそろ86アセンブラで書き終わりましたか？

>>285
いや、ここは口だけで実際に書ける奴がいないってだけの話だろ

>>272
あー、一応知ってるんだけど難しくて。

最初に512bit程度のp,qを作る、その作業が
今まで確率的手法 ( Miller-Rabin? ) だったんだよね？
紹介してくれたページでは、そのステップは
カッコ書きで「実は大変難しい作業」としてるだけ。

ここで、p,qが実は素数じゃなかったらどうなるんだろう？
まあ、今回の論文でその心配が無くなったというわけだが。

int isPower(int n)
{
int power;
int max_pow = INT_MAX;
int a, b;

for (a = 2; ; a++) {
power = a * a;
for (b = 2; b < max_pow && power < n; b++) {
power *= a;
}
if (power == n) {
return 1;
}
max_pow = b;
if (max_pow == 2) {
return 0;
}
}
return 0;
}

遅いとか早いとかはわからんのだけどシンプルに

>>292 さんくす。もれPOWER=Aから始めてて、ふるいと変わらないじゃんと、ぼけてた…

>>291
従来の素数判定法は↓の本に色々載ってる。
ttp://www.amazon.co.jp/exec/obidos/ASIN/4431709444/qid=1029050483/sr=1-1/ref=sr_1_2_1/249-5846017-4760349

実際に行われてる素数判定は、Miller-Rabin とかの
基本的な判定法を組み合わせた形で行われてる。
確率的な手法ゆえに、より効率的により正確に判定する
アルゴリズムが必要になり、その為に色々な素数判定法を
組み合わせてるわけだけど、この辺の話がすごくややこしい。
ある判定法で合成数と見抜けない合成数はどんな性質のもので、
それはどうすれば合成数と見抜けるかって話とかね。
ただ、一つ一つの素数判定法はそんなに難しい事を
やってるわけじゃない。RSAの仕組みが理解できる程度の
知識があれば十分理解可能。
ま、deterministic な方法が見つかった今となっては
さほど興味深い話ではないだろうけど。

n = INT_MAX とか与えるとあっさりオーバーフローするので使えないな

実際には多倍長でしょ。

ところで、実装をやろうとしている人は、いきなり多倍長でやろうとしてるの？
Cで適当にintで実装して、ソース貼ればここの人が寄ってたかって
多倍長にすると思うけど。
（C++でオブジェクト指向を使うことを想定してソース書いてくれると楽かな）

>>294 ありがとうございます。教えてもらったこととは
あまり関係ないですがこんなの思いつきました。

合成数は合成数と見抜ける人でないと
（RSA暗号を使うのは）難しい

int isPower(int n) {
　　int a, b, d;
　　int k = (int)log2(n);
　　for (b = 2; b <= k; b++) {
　　　　a = 0;
　　　　for ( d = 2^((int)(k / b)); d > 0; d /= 2 ) {
　　　　　　if ( (a + d)^b <= n ) a += d;
　　　　}
　　　　if ( a^b == n ) return 1;
　　}
　　return 0;
}

OpenSSL の BN でいきなりやろうとした漏れは逝ってよしですか？

templateで作ってよ
浮動小数点とか使わないでさ
template<class Int>Int func(Int);

>>300
その前に全部アルゴリズムを書きくだすのが先と思われ。
小手先の変換は、後からいくらでもできるわけだし。

今までに書き下されたアルゴリズムをキチンとまとめたいんだが,
ところどころにネタが混じってて直せん…. 数学の知識がある
他の人にバトーンターッチ….
んじゃ, デスマーチに逝ってきま.

int getLargestPrimeFactor(int n)
{
int q = 2;
int i;

do {
n >>= 1;
} while (n & 1 == 0);

for (i = 3; q < n; i += 2) {
while (n % i == 0) {
n /= i;
q = i;
}
}
return q;
}

n は 2 の倍数であるという前提

はっきし逝って、お前らのプログラミングのレベルを激しく疑う。

>>304 2chのシンボルキャラのAA貼ってほしそうだね。

　　　 |
　 　／⌒ヽ　　／￣￣￣￣￣￣￣￣￣￣
　　│ ･◎･）＜　そーでもないよ
　　│ ・ 　つ 　＼
　　│ ・ 　│ 　　￣￣￣￣￣￣￣￣￣￣
　 　＼＿／

>>302
数学の知識はあるが、プログラミングの知識が無い罠。

>>58
> q >= round(4*sqrt(r)*ln(n))
> a <= round(2*sqrt(r)*ln(n))
この二つの式の評価には注意が必要なのでは？！

Rubyやlispなら限界のなく大きな整数が扱えるんでしょ？
それでいいから誰か。

はあ？
コンピュータの暗号には何の影響もないだろ？

あるなら説明してみろ！まあできんだろうけどね。（ﾌﾟ

つかMATLAB2Cがあるだろ

>>310
> コンピュータの暗号には何の影響もないだろ？
ある。ただし暗号を弱める方向ではないが。

厨房板で釣れよ　リア厨さん

おまえら12行目の多項式の割り算を桁あふれおこさずに
順次割りながら行うルーチンだけでいいから書いてくれ。

難しいのはそこだけだ。

>>314
なんで自分でそんなもんかかにゃならんのか、と。
そこらへんに転がってるだろ、もっと便利なもんが。

転がっているところ、教えろ。
知らないなら書くな。

>>316
ﾊｧ?てめぇ何様のつもりだ？

無意味なことを書くな、といってるんだよ。聞こえなかったか？

聞こえないな。 読んだけど。

これ使え。
http://homepage1.nifty.com/mcn/weekly/000214.htm

で、結局誰もＣ言語で書けていないわけ？

>>314
>>257に書いてありますよ
x^r-1で割った余りを求めるには係数をr飛びに足し合わせるだけ。
3x^3 + 4をx^3-1で割った余りは3+4=7

>>321
>>311

>>322
(x-1)^17を展開すると
1 17 -136 680 -2380 6188 -12376 19448 -24310 24310 -19448 12376 -6188 2380 -680
136 -17 1
こうなるわけだが、これをx^15-1で割った余りはr飛びに足し合わせればいい。

それは分かるのだが、展開する途中に桁を減らすやり方が分からない。

(x-a)^n mod x^r-1,nの計算

n=11,r=3,a=2で計算すると
r次元の配列を4つ用意。*s,*s1,*t,*t1;
n=11を2進展開すると1011。これを2で割ってn1に代入。n1=n/2;

nが偶数なら、
　*tに多項式1を代入する。t[0]=1; t[i]=0, i=1,...,r-1;
奇数なら、
　*tに多項式x-aを代入する。t[0]=a; t[1]=1; t[i]=0, i=2,...,r-1;

まず、*sにx-aの係数を代入する。s[0]=a; s[1]=1; s[i]=0, i=2,...,r-1;

---
Loop1 以下square-repeatで(x-a)^(2^m)を*s1につくり、(x-a)^nを*t1に作り出す。

これから*s1に*sの自乗をx^r-1で割った余りを代入する。
*s1は0に初期化しておく。
i=0 to r-1
　j=0 to r-1-i
　 s1[i+j] = (s1[i+j]+s[i]*s[j]) % n; ここの掛け算は高速乗算法で行うべし。
　j=r-1-i+1 to r-1
　 s1[i+j-r] = (s1[i+j-r]+s[i]*s[j]) % n; x^(i+j)をx^r-1で割ると余りはx^(i+j-r)

n1が奇数なら
　*t1に*tと*s1の積をx^r-1で割った余りを代入する。
　*t1は0に初期化
　i=0 to r-1
　 j=0 to r-1-i
　 t1[i+j] = (t1[i+j]+s1[i]*t[j]) % n;
　 j=r-1-i+1 to r-1
　 t1[i+j-r] = (t1[i+j-r]+s1[i]*t[j]) % n;

n1を2で割って代入する。n1 /= 2;
n1が0ならば終了。*t1に(x-a)^nをx^r-1とnで割った余りが格納されている。break;

*sに*s1を代入、*tに*t1を代入し Loop1へジャンプ。
-----

判定

t1[0] == a かどうか調べる。
nをrで割った余りをmとする。m= n % r;
t1[m] == 1 かどうか調べる。
i !=0, i !=m で
t1[i] == 0 かどうか調べる。

1/3で3行目
>n=11,r=3,a=2で計算すると
を消し忘れたｗ

1/3
>　*tに多項式x-aを代入する。t[0]=a; t[1]=1; t[i]=0, i=2,...,r-1;
>まず、*sにx-aの係数を代入する。s[0]=a; s[1]=1; s[i]=0, i=2,...,r-1;

t[0]=-a;
s[0]=-a;
ですな。ところどころ虫があるかもしれんから探してちょ。
これが>>141のやり方ですな。

(x-a)^(2^m)を計算するところや
(x-a)^(2^m) * t を計算するところがr^2回ループする。
r=O(log^6 n)だから
log^12 nのオーダーでループするから本当はよくない。

多項式の乗法もFFT使って計算すべきなのだろうなぁ。

1/3
>nが偶数なら、
n=2以外なら素数ではないなw

>>325-330
そこまで書けるならコード化できてる？よね。
で試した結果はどうだったのでせう？
でっかいメルセンヌ素数とかでも検証はOK?

>>325-331
だれかCで動くように書きなおして。
そしてFFTで掛け算できるように直して。

>>332
できてないッス。ム板の住民じゃないし。
帰省先にもって帰ったﾉｰﾊﾟｿには言語処理系がないという罠。

今更ながら、神業でＡＡを張った>>2はすごいと思う。

>2=>1

>>325-327
int test12(int a, int n, int r, int *s, int *t, int *u) {
　/* assert: n > 2, r >= 2, n % r > 0 */
　int i,j,m;
　int n1,*tmp;
　s[0] = t[0] = -a % n;
　t[0] = t[1] = 1;
　for (i = 2; i < r; i++) s[i] = t[i] = 0;
　n1 = n / 2;
　while (n1 > 0) {
　　mul(u,s,s,r,n); tmp=s; s=u; u=tmp;
　　if (n1 & 1) {
　　　mul(u,s,t,r,n); tmp=t; t=u; u=tmp;
　　}
　　n1 /= 2;
　}
　m = n % r;
　t[0] = (t[0] - a) % n;
　t[m] = (t[m] - 1) % n;
　for (i = 0; i < r; i++) if (t[i] > 0) return 1;
　return 0;
}

void mul(int *c, int *a, int *b, int n, int r) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] = (c[i+j]+a[i]*b[j]) % n;
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] = (c[i+j-r]+a[i]*b[j]) % n;
　}
}

mul引数のrとn逆だった

>>338 修正
void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r; i++) {

t[0] = t[1] = 1; は s[1] = t[1] = 1;

Cで試すときは、こうだな。
s[0] = t[0] = -a % n; → s[0] = t[0] = (n - a) % n;
t[0] = (t[0] - a) % n; → t[0] = (t[0] + n - a) % n;
t[m] = (t[m] - 1) % n; → t[m] = (t[m] + n - 1) % n;

a<nなのでn-aでよいはず。

>t1[0] == a かどうか調べる。
は
t1[0] == n-a かどうか調べる。

> t[0] = (t[0] - a) % n;
は
t[0] = t[0] + a -n

>s[0] = t[0] = -a % n;
は
s[0] = t[0] = n-a;

ですね。

で条件判断は
for (i = 0; i < r; i++) if (t[i] != 0) return 1;
ですね。

作ってみた。
小さな数（10000くらいまで）なら正しく判定しているように見える。
もっとも>>337のソースが何をやっているのか理解してないけど。

こうなのか。

int test12(int a, int n, int r, int *s, int *t, int *u) {
　/* assert: n > 2, r >= 2, n % r > 0 */
　int i,j,m;
　int n1,*tmp;
　s[0] = t[0] = n-a;
　s[0] = t[1] = 1;
　for (i = 2; i < r; i++) s[i] = t[i] = 0;
　n1 = n / 2;
　while (n1 > 0) {
　　mul(u,s,s,r,n); tmp=s; s=u; u=tmp;
　　if (n1 & 1) {
　　　mul(u,s,t,r,n); tmp=t; t=u; u=tmp;
　　}
　　n1 /= 2;
　}
　m = n % r;
　t[0] = t[0] + a - n;
　t[m] = t[m] - 1;
　for (i = 0; i < r; i++) if (t[i] != 0) return 1;
　return 0;
}

void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] = (c[i+j]+a[i]*b[j]) % n;
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] = (c[i+j-r]+a[i]*b[j]) % n;
　}
}

ソースでふ。
http://www.geocities.co.jp/Technopolis-Mars/1346/prime2.lzh
>ここの掛け算は高速乗算法で行うべし。
とあるけど、test12の関数、めちゃくちゃ重たいっす・・・。
FFTってのはフーリエ変換だよね？
これが多項式の乗法にも関係するのかぁ。正直全然ついていけません。

このwhileループが log n 回で
mul関数のforループが r^2 回で
乗法a[i]*b[j]の手間がO((log n)^2)
よってtest12関数は O(log n * r^2 * (log n)^2)
rがO((log n)^6)だから O((log n)^15)

aが1から 2 √r log n まで動くから
√r log n O((log n)^15) = O((log n)^19)
まぁ、多項式だから良しとしてくれぇ。

10009の判定に19秒。
100003の判定に54秒かかまふ。
もっと巨大な数字の判定になると相対的に早くなるんだろうけど・・・。

んーで、そろそろ完成したの?

http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html
暗号鍵を生成するために、RSAは2つの大きな素数を掛け合わせて、「鍵」と
考えられる数字を作り出す。
　その後、最初の数字が実際に素数であるかどうかを判定するテストを行う。
いわゆる素数判定テストで使われている現行のアルゴリズムは、高速ではある
が、若干ながら誤った答えが導き出される可能性がある。
　だが、インドのカンプールにあるインド工科大学で、Manindra Agrawal氏と
、その教え子のNeeraj Kayal氏、Nitin Saxena氏が開発した新しいアルゴリズ
ムは、毎回正確な結果が得られるとされている。

>>350
10009の判定に27秒かかりますた。
MSVC++6のReleaseモード。CPUはPen3-800。

>>350
nでの剰余を求めているところ
% n を繰り返しているところが重いと思われ。

本当はあらかじめ1/nをニュートン法で有効桁を 2 log n 桁ほど求めておいて
x- int ( x * (1/n)) を高速乗算で求めるのでしょう。

高速フーリエ 乗算
高速乗算法
でぐぐると
ttp://homepage2.nifty.com/m_kamada/docs/fftmul.htm
ttp://homepage3.nifty.com/murasakigawa/tech/etc/longmul.html
ttp://homepage1.nifty.com/~umetani/ims/2001/20010825001/0.html
がでてきた。

最初のa^b型でないことを判定するところも
nのb乗根の計算はニュートン法を用いて（ニュートン法内の乗算は高速乗算法を用いる）
(log n)/b桁+α桁求めて その整数部をとってb乗したものがnに等しくなるかで判定するのかなぁ。

>>347
途中の桁あふれは少々怖いがnで割るのは後でまとめてみよう。
少しは速くなるかも。

void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] += a[i]*b[j];
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] += a[i]*b[j];
　}
　for (i = 0; i < r; i++) c[i] %= n;
}

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　素数判定は多項式時間でできますよ。
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　γ~三ヽ
　(三彡０ﾐ) 　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 （　・∀・）　 ∧ ∧ ＜　えっえっ！！
　（　　⊃ ）　 (ﾟДﾟ；)　　＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣ （つ＿つ＿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　=======　　＼

rubyでかいてくれっちょ(w

>>357
c2ruby

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　今までの議論は理解できましたか？
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　γ~三ヽ
　(三彡０ﾐ) 　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 （　・∀・）　 ∧∧ ＜　あたぼうよ。ﾁｮﾛｲｾﾞ!
　（　　⊃ ）　 (,,ﾟДﾟ)　　＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣ （つ＿つ＿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　=======　　＼

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　じゃ、私はこれで・・・
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　 γ~三ヽ
　(三彡０ﾐ) 　　　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　（∀・　；） 　 |＼|＼　　　＜　ちょ、ちょっと待って、ｺﾞﾙｧ
　（　　　　）　 (；　　 )　　　　 ＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣⊂＿　＼丿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　 =======　 ＼

>>359
面白いが下のコマのインド人頭が回って無いぞ

頭だけ回ってる。

　 γ~三ヽ
　(三彡０ﾐ) 160G

さっそく　そうびするかね？
＞はい　 　　　　　　　　　　γ~三ヽ
　 いいえ　　　　　　　　　　(三彡０ﾐ)

　 γ~三ヽ
　(０ﾐ三彡)
　（∀・　；）
　（　　　　）　
これでいいか みなのしゅう

>>364
モララーは知力が 255 上がった！

>>352の記事から
　しかしコンピュータ科学者たちは、このアルゴリズムが実用段階にはほど遠いことを認めている。
　Agrawal氏は次のように語っている。
「われわれのアルゴリズムは、最も高速とされる素数判定テストアルゴリズムよりも低速だ。この
アルゴリズムの満足な点は、従来のものとは反対に、完全に確定的であることだ。従来のアルゴリズム
では、滅多にないとは言え誤った回答が出てしまうことがある」。

・・・おーい。理論だけでまだ遅すぎて使えないってことかYO!

>>350
この秒数は大嘘ですた。
a=1のみでしか計算してないれす。
ちゃんとやると
503の証明で32秒、
1009で215秒、
10000以上はやる気おきない秒
ぐらいの時間がかかりまふ。

どのくらい遅いかによるな

>>367
多項式時間なんだから桁数が増えただけで判定時間が
やる気おきないほど急速に増加するというのは
実装のどこかが間違っているのでは?

nで剰余をとる % n でO(n^2)時間がかかっていると思われ。
>>355 の場合はどうでしょう。>>367

>>349 にあるように %n 以外でもO((log n)^19)と桁数の19乗で時間が
増えていくので
3^19 : 4^19 = 1 : 236.5
4^19 : 5^19 = 1 : 69.38
それに桁数が小さいときは18次以下の項も大きく利いてきて
桁数の増加に伴い大きく時間を伸ばしている可能性があります。>>369

まだあきらめてなかったのかお前ら、と。

>>371
まだあきらめてなかったのかお前ら、と小一時間計算(略

>>370
O((log n)^12)じゃなかったっけ?
どっちにしろ急速に増えていく可能性はあるわけだけど

>373
>>349 >>370　にあるのは、いまC言語で動いているプログラムの時間についてです。
論文にあるアルゴリズムをFFTで書いたらO~((log n)^12)になるはずなのですが。

>>374
MATLABならそれは自動的に達成される?

あきらめたのか？

あきたんだと思う

　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿＿＿
|∴/= ♀=| <どうしたんだ、漏前ら！
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣￣￣
　　￣￣

一応動くものができたのだから終わりなんだが。
多項式時間で動くというのは効率よく動くというわけではない罠

剰余でO(n^2)かかってるというのが本当なら
まだ多項式時間では動いていないわけだが

>>380
剰余を取るっつってんだから、O((log n)^2) の書き間違いだと思われ。

あげ

>>382
おいっ！俺様に分からないネタで
あげるんじゃないよ、ゴルァ！！！

すごい理屈だ

これからは楕円暗号の時代か？

で暗号は処理効率アップで強くなるの？それとも弱くなるの？

効率じゃなくて、確実さが上がるの。
それに現段階では重過ぎて実用にならないらしい？
確率的手法で高速に長い素数を発見した方がまだよい。
今後に期待。

であってるのか？このネタいちいち自信が持てん。

>>387
> 確率的手法で高速に長い素数を発見した方がまだよい。
発見と判定は、別の問題だと思うが。

>>388
実際に使われている暗号ソフトでは、適当に奇数乱数を生成して、
それを素数か判定している、と読んだ気がする。

>>389
それは判定であって、発見ではないということでは？
素数発見アルゴリズムは、もう少し別の概念（定義）があったはず。

あ、そうなんですか。
既知の素数全てを掛けた数+1が素数とか、そういうのが発見アルゴリズムかな？
（この方法で見つけた素数は個数が限られるので暗号には使えないが）

>391
既知の素数全てをかけた数+1 は素数とは限らない
（素数の無限性の証明としては問題がないだけの話）。

>>390
発見するのは適当に乱数生成して、偶数なら１足して、素数判定。
で、合成数なら駄目なら２足して以下同文ってのが普通。

>>393
へー

FFT = Fast Fourier Transform = 高速フーリエ変換

あの、結局 >>389 は素数発見と認められるんですか？
>>390 で否定されたかと思えば >>391が同じこといってるし。

>>396
というよりも、乱数を生成してそれが素数かどうか調べる以外に
素数を生成する方法はないのでは？
素数ばっかり生成する関数というのも見つかってなかったような気がした。

>>397
確率的に「素数の可能性が高い数」を出力する関数とか見つかってないの？

>>398 2n+1










マジレスするとこれな。
ttp://gt.sakura.ne.jp/~nyagy/integer/sosuu_seisei.html

age

namahage

ﾌﾟｯﾁ神父に聞こう

・従来のアルゴリズムは99．9%の確率で正しい答えを導き出して高速だが
　0．01%位の確率で間違った答えを導き出す。
・今回のアルゴリズムは100%正しい答えを導き出すが低速。


ということでよろしいか？

おいおい従来の手法の誤り確率がそんなに高くていいのかよ。
社員が10000人いる会社なら10人分くらいは隙のあるアカウントができるぞ。
（その１０人を探すアルゴリズムは知らんけどな。）

時間をかければもっと精度は上がると思われ。＜従来のアルゴリズム

従来のアルゴリズムは、手法によって違うけれど、
１回ループするごとに大体1/2で誤りを検出（合成数を検出）します。
よって、すなわち32回ループしたならば、1/2^32なわけですね。

>>403
残りの0.09%は何ですか？

>>406
segmentation fault で止まる。

>>406
禿から琢磨が出てくる

ほっしゅ

OO 最高

どこに掲載されたか書いてないね・・

.NET 最高

実数の中のどの数字ですか?

ところで、

何よ

実は

…実は？

僕の肛門も解読されますた。

>>418
奇遇だな、漏れもだ(w

保守・

漏れ　という言葉は女が男を騙る時に使うんだよな…

>419
ﾊｧﾊｧ(*´ヽДﾉ｀)

漏れの顔
ttp://short2003h.ddo.jp/cgi-local/clip/img/79.jpg

IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前：ひろゆき ◆3SHRUNYAXA ＠どうやら管理人 ★ 投稿日：03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前：心得をよく読みましょう 投稿日：03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か？

38 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:27 ID:rLfxQ17l
＞ところで、IPが抜かれて何か今までと変わることってあるのでしょうか？
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。

じっけん　じっけん

>>315　ﾌﾟ

ひろゆきひろゆきうるせーよ

>>452
ひろゆきが、ってことだろ

漢ならあえて晒す。

IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前：ひろゆき ◆3SHRUNYAXA ＠どうやら管理人 ★ 投稿日：03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前：心得をよく読みましょう 投稿日：03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か？

38 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:27 ID:rLfxQ17l
＞ところで、IPが抜かれて何か今までと変わることってあるのでしょうか？
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。

記録されたIPってみんなには見えないんでしょ？
虹では表示されてるけど
あれはまた違う規制なの？

記録されますた！

全板IP保存も近いね。
もう匿名掲示板じゃないじゃん

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 138720人　発行日：2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

私はは匿名掲示板なんて無くてもいいのだが。
自分の発言に責任を持つのは当然だと思います。

　　　　　 l､､_　　　　 _,／'}
　　　　　 |ヽ''~￣￣￣~`ヾ
　　　　 ／＿,,,..　　　..,,,＿.`v_'`､
　　　　/:　 ━　　　　 ━　 　| ニ_｝　　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　|::　　　　∈∋　　　　ヽ　　| ＜わたしを好きなだけ殴って下さい。
　　／/::　　　 -=,=.ヮ.　　　 　|ヽ､|　　＼
　 /'../::　　　　／∠.._　　　　　|､.ﾉ 　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　/':::|:::　　　　 ￣￣　　　　　　|./
　!-'L|::.　　　　　　　　　　　　　v'
.　　　ヾ:::..　　　　　　　　　　　/
.　　　 , ゞ､､;;;,,＿,,,..._;;;;;__,,..ノ､
　　　 'ｰ┐,,..､_ ﾉ　 l_,,,...､ _,,一`

あれ、書き込みなくなっちゃった？(^_^;)

>>87
裁判所の判断ってところに、引用とも原告の主張とも書かずに、
上のような文が書いてあるっすよ。
別にここにあげたのは原告の主張の引用ではなく、
ひろゆきの主張に対する裁判所の判断っす。

ほとんどが呆れてるんだな、積極的にスレ立てて祭りやると単にキチガイが
増長するだけだし。

>>370
単に２ｃｈ型のＰ２Ｐ掲示板ではなくて、
winnyとか、ファイル交換ソフトの中に内臓されている掲示板が
もっと使いやすくなればいいかなぁ、と。
ＰＣに詳しくなくてもＷＩＮＭＸがただで音楽が手に入る！
と思っちゃった初心者の人が始めたりするくらいだから、
（現在の使用者は９０万人くらい）
完全に匿名の形式ができればおもしろそう。。

でも、やばい情報を誰も削除できないという罠が、

>>854
所詮外部のものの意見だけどね。

22:33
匿名性に絡む問題なので反対　28%　297 票
サイトのためになるから賛成　54%　573 票

22:34
匿名性に絡む問題なので反対　28%　308 票
サイトのためになるから賛成　53%　588 票
　　　

《一覧表》

ヾ(=・ω・）ゞゲリーな文系女 ◆/OQtXsetN.
あうあう ◆/OQtXsetN.
Dumm.com ◆/OQtXsetN.
オバハンコテ ◆/OQtXsetN.
馬鹿も風邪を引く ◆/OQtXsetN.
下痢女＠ゲリ〜＠携帯

通称ゲリーさんです。
私が腐れ30男さんのスレから拉致しました。
批判要望・電２板によくいらっさいます。

住人じゃない人も知っている事を書き込んで、楽しいでふか？粘着くん。

P2P掲示板作れば言いたい事言えるんじゃない？

急に丁寧語になったりしてｗ

激しく同意。ヤナ時代になったもんだ・・・

こうゆう基地外は一度捕まった方が良いと思われ
　　↓
http://ex2.2ch.net/test/read.cgi/morningcoffee/1041906510/29

実は2チャン閉鎖が真の目標とか。

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 139038人　発行日：2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

そうだな。別に困らん。
煽りあいくらいで訴えられるようになったら
もうおしまいだけど。

（・∀・）ｲｲﾖｲｲﾖｰ

なんとか　なんねーの？
旧東ヨーロッパ系の胡散臭い国に鯖を移管して　名目上の管理者も
アル中のおやじとかやとってやらせてさあ。。

１００％リモートじゃ無理？

２ｃｈみたいにこれだけ多くの不特定多数の人間が好きに発言できる場って
日本には他に無いはずだよ。良きにしろ、悪きにしろ貴重な存在だったのに・・・

どうしたらこいつのキャップ取ることができるのですか？
こいつにキャップ授受した糞も一緒に解雇してください。

コリア困った

(´-`).｡oO(http://www63.tok2.com/home2/hikky/fuck.cgi)

(^^)

8 名前： ひろゆき＠管直人 投稿日： 2000/04/07(金) 07:20
あ、そそ。それをいいたかったのよ。
つまりね、
ここ、一般の人は見れない板だからいっちゃうけど、
将来的にはすべてＩＰ取るようにしたいし、
もっと商業的な板にしたいと思ってる。
ヤフーに勝ぐらいのつもりでね。
だけど、今そういうスタンスを取ると、人が離れるだけだから、
表面ではＩＰとらないことをウリにして、
人があつまって、収益の見込みが立ったら
犠牲者でも出して、綱紀粛正するつもりなんですよ。

あ、でもこれあくまでオフレコだから、
内緒ですよ。
この板見れる人なんて決まってるんだから、
ばらしても無駄ですう。

600,000,088

は何なの？ﾏﾄﾞｶですらちびりそうになった身としては怖くて開けない。
各板で見るけど。感想は「びびった」ばかり。

やすゆきも小心者だからね

犯人は、ビッグカメラのネット体験コーナーから
カキコしたそうだが。。何か？

2ちゃんねる　が衰退していく

あるネット関連会社の社長は、
「いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」
と証言する。
2ちゃんねるが判決によって力を失った場合、
資金提供の打ち切りも予想される。

http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html

皇太子様のAAが好きだから。

はい。トリップやめました。。（オレも で間違えた・・・）
　#　ちと煽り過ぎたかなとも反省。

で、質問。
今後起こりうる裁判と切り分ける部分って具体的にはどのヘンなのでしょうか？

くすぐり攻撃。

まぁ　火曜日までには、

integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
　2. r = 2;
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;
　5. 　　if (r is prime)
　6. 　　　　let q be the largest prime factor of r - 1;
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }
　11. for a=1 to 2*aqrt(r)*log(n)
　12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

誰かC言語で書いて下さい。

while(fgets(str,80,465)!=EOF)
  puts(str);

（＾＾）

敗訴ｷﾀ━━(ﾟ∀ﾟ)━━( ﾟ∀)━━( 　ﾟ)━━( 　)━━( 　)━━(ﾟ 　)━━(∀ﾟ )━━(ﾟ∀ﾟ)━━━!

（＾＾）

（＾＾）

結局どうなった？

>>15
日本人ってこういう考え方するんだねぇ。
逆だろうに。。。

さっぱりワカンネ。
「高速で解読できる」とも言えるし「強力な暗号が作れる」ともいえるらしい。
だったら一言で言えば
今までとは比べ物にならないくらい計算が速くなったとまとめてOK?

素数判定だけじゃ、解読できないのでは？

どうせ何年かすれば量子コンピュータが出てくるって

>>474
がいしゅつすぎ
スレ立てたアホを恨め

（＾＾）

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

…実は?

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

ttp://www.h4.dion.ne.jp/~a00/basic_jp.html
多項式時間での素数判定の解説サイト！

遅ればせながら、こんなサイトを見つけたので興味があったら行ってみ
てください。

http://www.h4.dion.ne.jp/~a00/basic_jp.html

>>482 >>483
ブラクラ。閲覧注意。

>>484
　　　　　　　　　　　　　　　　





　　　　　　　　　　　　　　　　´_ゝ`

ブラクラだ^＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾

数論的代数幾何ってどんなことやるの？

http://elife.fam.cx/a008/

（＾＾）

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

int lucas(int p)
{
char *l, *m;
char *lp, *mp1, *mp2;
int i, j, k;
int ca, x;
int ret = 1;
if (p <= 0) return 0;
if (p <= 2) return 1;
if ((l = (char *)malloc(p)) == NULL) return -1;
if ((m = (char *)malloc(p)) == NULL) {
free(l);
return -1;
}

for (lp = l + p; lp != l; ) *--lp = 0;
*(l+2) = 1; /* L(1) = 4 */
for (i = 2; i < p; i++) {
for (lp = l + p, mp1 = m + p; lp != l; ) {
*--mp1 = *--lp;
*lp = 1; /* 2^p -1 mod 2^p -1 = 0 */
}
*(l+1) = 0; /* L(i) = L(i) - 2 */
for (mp1 = m, j = 0; j < p; j++) {
if (*mp1++) { /* this bit is 1 */
ca = 0;
k = j;
for (mp2 = m; mp2 != m + p; ) { /* L(i) * L(i) */
x = *mp2++ + *(l+k) + ca;
*(l+k) = x & 1;
ca = x >> 1;
if (++k == p) k = 0;
}
if (ca) {
while (*(l+k)) {
*(l+k) = 0;
if (++k == p) k = 0;
}
*(l+k) = 1;
}
}
}
}

x = *l;
for (lp = l + p; lp != l; ) /* L(p-1) == all 0 or 1 ? */
if (*--lp != x) {
ret = 0;
break;
}
free(m);
free(l);
return ret;
}

Ｃ言語は俺に聞けスレから来ました。
えー、上のプログラムはメルセンヌ素数のルカステストを行う関数なのですが
これが早いのか遅いのか私には判断がつきません。
ルカステストというのは、最速のアルゴリズムだとして、（まぁ普通のパソコンでＣＰＵ１Ｇ）
ぐらいのパソコンでどのくらいかかるのでしょか？
ちなみに自宅のパソコンで（ＣＰＵ５００Ｍぐらい）、2^3217のチェックが５分ほどかかりました。
誰か見てますかー？

>>493
500MHz から 1GHz になれば倍くらいの速度にはなるんじゃね？
恐らくCPUの世代も変わってるだろうからさらに早くなってるかもしれないし
コンパイラが違えば速度も変わるだろ？
で、何が知りたいの？

>>494
ＧＩＭＰＳのアプリケーションで2^11213-1のチェックでどのくらいかかるんでしょうか？

>>495
追加、要するに、パソコンの速さは気にせずに、上のコードが
早いのか遅いのか知りたいわけです。
ＦＦＴとか、あと、割り算をしなくていい方法とかあるようですが、
そういうの積んでいないもので、ちゃんとしたプログラムはどれく
らい早いのかなぁと思いまして

#0:　 　　　　　　　　1
1:　　　　　　　　　1　 1
2:　　　　　　　　1　 2　 1
3:　　　　　　　1　 3　 3　 1
4:　　　　　　1　 4　 6　 4　 1
5:　　　　　1　 5　10　10　5　1
6:　　　　1　 6　15　20　15 6　1
7:　　　1　 7　21　35　35 21 7　1

nは奇数とする。
1次項から(n-1)/2次項までの係数を評価すればよし
第m次項の係数は(1≦m≦(n-1)/2)　n C m =n(n-1)(n-2)(n-3)…(n-m)/1*2*3*…m
あぁ、自分なりに考えてみたけど。計算量が膨大すぎ。

↑に書いたピラミッドはあんまり意味ない(途中で気が変わったため不使用
暇なんで↑の方法使ったプログラム組んでみるわ（アホ

Qi Cheng,
``Primality Proving via One Round in ECPP and One Iteration in AKS,'' Crypto 2003
で少し高速化されたらしいです．age

しっかしここの>>1はよほどのアホだな。
「素数判定が多項式時間で可能！」なんて記事をちょっと学があるやつが見たら
「ぉ！鍵生成が楽になるな」って思うのが普通だろ…

まかに間違っても
「暗号総崩れ」などという奇天烈な発想にはつながらんはずだが…

ああ2年程前よくそんなレスを見たよ。