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

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

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

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

452 ：デフォルトの名無しさん：03/01/11 13:59

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

453 ：デフォルトの名無しさん：03/01/11 15:39

コリア困った

454 ：デフォルトの名無しさん：03/01/11 16:48

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

455 ：デフォルトの名無しさん：03/01/11 16:55

(^^)

456 ：デフォルトの名無しさん：03/01/11 23:42

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

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

457 ：デフォルトの名無しさん：03/01/11 23:52

600,000,088

458 ：デフォルトの名無しさん：03/01/12 02:31

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

459 ：デフォルトの名無しさん：03/01/12 02:37

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

460 ：デフォルトの名無しさん：03/01/12 10:04

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

461 ：デフォルトの名無しさん：03/01/12 10:06

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

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

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

462 ：デフォルトの名無しさん：03/01/12 20:52

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

463 ：デフォルトの名無しさん：03/01/12 20:55

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

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

464 ：デフォルトの名無しさん：03/01/12 21:04

くすぐり攻撃。

まぁ　火曜日までには、

465 ：qwert：03/01/12 23:29

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言語で書いて下さい。

466 ：デフォルトの名無しさん：03/01/13 00:42

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

467 ：山崎渉：03/01/13 18:27

（＾＾）

468 ：デフォルトの名無しさん：03/01/13 22:15

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

469 ：山崎渉：03/01/15 17:52

（＾＾）

470 ：山崎渉：03/01/23 22:23

（＾＾）

471 ：デフォルトの名無しさん：03/02/18 17:22

結局どうなった？

472 ：デフォルトの名無しさん：03/03/27 04:58

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

473 ：デフォルトの名無しさん：03/03/27 18:20

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

474 ：デフォルトの名無しさん：03/03/27 19:44

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

475 ：デフォルトの名無しさん：03/03/30 18:24

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

476 ：デフォルトの名無しさん：03/03/31 00:50

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

477 ：山崎渉：03/04/17 15:49

（＾＾）

478 ：山崎渉：03/05/28 13:23

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

479 ：デフォルトの名無しさん：03/06/21 21:50

…実は?

480 ：山崎渉：03/07/15 10:40

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

481 ：山崎渉：03/07/15 14:07

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

482 ：age：03/07/26 13:40

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

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

483 ：デフォルトの名無しさん：03/07/26 14:07

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

484 ：デフォルトの名無しさん：03/07/26 15:13

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

485 ：デフォルトの名無しさん：03/07/26 18:22

>>484
　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　´_ゝ`

486 ：デフォルトの名無しさん：03/07/26 19:02

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

487 ：デフォルトの名無しさん：03/07/26 19:43

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

488 ：コヨーテ：03/07/26 20:54

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

489 ：山崎渉：03/08/02 02:17

（＾＾）

490 ：山崎渉：03/08/15 16:26

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

491 ：age：03/08/21 21:11

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;
}

492 ：age：03/08/21 21:12

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;
}
}
}
}

493 ：age：03/08/21 21:16

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のチェックが５分ほどかかりました。
誰か見てますかー？

494 ：デフォルトの名無しさん：03/08/23 03:20

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

495 ：age：03/08/23 16:22

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

496 ：age：03/08/23 16:24

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

497 ：デフォルトの名無しさん：03/09/26 22:12

#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
あぁ、自分なりに考えてみたけど。計算量が膨大すぎ。

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

498 ：デフォルトの名無しさん：04/02/12 19:35

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

499 ：デフォルトの名無しさん：04/05/28 11:42

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

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

500 ：デフォルトの名無しさん：04/06/30 00:29

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