5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

素数判定は「決定的」多項式時間で可能

1 :132人目の素数さん:02/08/08 22:24
素数判定は「決定的」多項式時間で可能

だそうである。拡張リーマン予想とかの仮定なしに。
識者のチェックキボンヌ。

http://www.cse.iitk.ac.in/users/manindra/index.html

このページの上のほうの、"PRIMES in P"

2 :132人目の素数さん:02/08/08 22:26
ふ〜ん

3 :132人目の素数さん:02/08/08 23:13
それほど時間かからないってこった。

4 :132人目の素数さん:02/08/09 07:16
因数分解もそうなってくれたらいいのにね。

5 :132人目の素数さん:02/08/09 14:12
なんでこのスレは4つしかレスがないの?
これ、すごいことではないですか?
(数学専門ではないのですが、(コンピュータ専門)
すごい騒ぎになってるのでは?と思ってはじめて
この板に来たのですが)

6 :132人目の素数さん:02/08/09 14:13
だって意味和漢ねーン唾問、俺馬鹿だから。

7 :132人目の素数さん:02/08/09 14:16
いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね?(つい最近習った)

すごいんじゃないのかなぁ。。。
すいません。俺も詳細は全然わからんが。

Bell Labの研究者もこのインド人の先生のoutputを
検証してみたけど、問題なかったと言ってたらしい。

8 :132人目の素数さん:02/08/09 14:17
うちのパソコンじゃ見れません。・゚・(ノД`)・゚・。


9 :132人目の素数さん:02/08/09 14:21
っていうかアメリカはいま大騒ぎです。(Stanfordより)

10 :132人目の素数さん:02/08/09 14:21
英語が読めません
ばばーい(・∀・)

11 : :02/08/09 14:23
>>4
数学的にはいいんだろうけど、
それ出来てしまうと、コンピュータで使われている暗号が
使えなくなっちゃうよ。

12 :132人目の素数さん:02/08/09 14:24
ごめん。いまNYTimesか、Washington postの最新記事を
探してるんだけど、どうしても出てこない・・。

今日8日(もう昨日か)の朝は、大学はこの話題でもちきり
でした。>>11 そうなんですよね・・・。

13 :132人目の素数さん:02/08/09 14:31
ありました。NYTimes, 8日付です。
http://www.nytimes.com/2002/08/08/science/08MATH.html

14 :132人目の素数さん:02/08/09 14:47
スレタイ見た瞬間「渋い所をついたネタスレだなぁ」と思ってしまった。
マジなのかよ。

15 :132人目の素数さん:02/08/09 14:49
マジです。

16 :132人目の素数さん:02/08/09 14:50
っていうか「渋いところ」っていうより、かなり根幹でしょ。


17 :132人目の素数さん:02/08/09 14:52
>>16
正直、人による。

18 :gf:02/08/09 14:54
-------風俗の総合商社・MTTどこでも-------

〇デリバリーヘルス〇デートクラブ〇女性専用ホストクラブ〇
〇ハードSM奴隷クラブ〇レズビアン倶楽部〇ホモ・オカマ倶楽部
〇変態痴女と遊ぶ会〇痴漢・覗き趣味の会〇変態同好会・各種!
●楽しく遊べます! 090-8002-8356番
-----------美男・美女会員など多数在籍中-----------
  http://www.mttdocomo.jp/
-----女性アルバイト随時募集・高収入(日払い)月100万円可能住み込みも可
-----レズビアン・スタッフ●ホモスタッフ●女性専用ホストスタッフ同募-----
http://www.mttdocomo.jp/
------------------------------------------------

19 :132人目の素数さん:02/08/09 14:55
>>16
いや、明から様に冗談って感じじゃなくて、計算量理論とか知らないと
「フーン」ですまされそうな所を突いたネタスレだなぁと思ったんよ。

そう思ってスレ開いたらとんでもない事になってた。

20 :132人目の素数さん:02/08/09 15:03
http://dempa.2ch.net/misc/R3_temp.swf?inputStr=SEX%82%B5%82%BD%82%A2

21 :132人目の素数さん:02/08/09 15:04
2からn-1までで順次割ってみればいいんだから、多項式オーダって
あたりまえじゃん、とか思ったが、入力の「桁数」をサイズとして
多項式オーダということだったのですね

22 :132人目の素数さん:02/08/09 15:09
いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね?(つい最近習った)
っていうかアメリカはいま大騒ぎです。(Stanfordより)

おまえうざすぎ。
人と話せよ、アフォが。

23 :132人目の素数さん:02/08/09 15:12
>>22
スレの内容が理解できないからって八つ当たりするなよ。

24 :132人目の素数さん:02/08/09 15:15
>>21
順次割っていくにしても貧 以下の数で割れば十分なわけだが。

25 :132人目の素数さん:02/08/09 16:11
>>1のリンク先にあるその論文に雑誌名がないのが気になるが…。

まさか「論理的」多項式時間じゃないだろうね?(w

26 :132人目の素数さん:02/08/09 16:16
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/l50

説明求む

27 :132人目の素数さん:02/08/09 16:20
論文のURL(英語: 数学者の写真あり): http://www.cse.iitk.ac.in/news/primality.html
ココにpdfファイルとpsファイルがあるから、取りあえず嫁!


28 :132人目の素数さん:02/08/09 16:33
なんでこんなに静かなんだ・・・

29 :132人目の素数さん:02/08/09 16:45
>>28
このスレの住人が数学オンチだらけだからじゃねーの。
そうじゃなかったら祭りがはじまるはずだよ。

30 :132人目の素数さん:02/08/09 16:49
素因数分解が短時間でできるようになるわけじゃないのか・・・

31 :132人目の素数さん:02/08/09 16:59
相互リンク プログラム板

暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/


32 :132人目の素数さん:02/08/09 17:02
わかりやすく、何かに置き換えてこのすごさを表現してください。
あ、でもこの板の住人達ってそんなにレベル高くなかったんだね。
ゴメンゴメン

33 :132人目の素数さん:02/08/09 17:06
試してみたいんだけど
1 if ( n is of the form a b , b > 1 )

12 if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
の ,n の意味が判りません

誰か教えて

34 :132人目の素数さん:02/08/09 17:08
1は「もし nが a^b の形で表現可能なら 素数ではない」 という事だと思うんだけど



35 :132人目の素数さん:02/08/09 17:17
大発見には違いないんだが、「これでRSA崩壊だ!」って
騒いでる奴は一体何なんだ?

36 :132人目の素数さん:02/08/09 17:19
>>29
論文を読んでるからだと思いたい。

37 :132人目の素数さん:02/08/09 17:26
>>33
nは変数。
nが素数かどうかってことでしょ?

38 :132人目の素数さん:02/08/09 17:27
これMATLABだろ?誰かコンパイルしてくれ

39 :ヽ(´Д`)ノ:02/08/09 17:31
このスレがネタスレかどうかの判定法を教えてくださいです。。。

40 :132人目の素数さん:02/08/09 17:46
>>33
> 12 if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
> の ,n の意味が判りません

(mod x^r - 1), (mod n) の両方の場合でって意味じゃ。

41 :132人目の素数さん:02/08/09 17:57
>>28-29
>>36
数学屋にとっては、自分の専門分野以外の大発見なんて
対岸の火事でしかないからだろ。
暗号理論やってるヤツなんてオレの同期には一人だけだし…


42 :132人目の素数さん:02/08/09 18:08
このアルゴリズムが素因数分解に応用できるか
(または与える影響を)検証した人居る?

43 :132人目の素数さん:02/08/09 18:14
>>42
そんな事が簡単に検証できるならとっくにRSA破ってます。

44 :132人目の素数さん:02/08/09 18:15
ランダウ記号でO((log n)^12)と書いているのだが> http://www.cse.iitk.ac.in/news/primality.pdf

“多項式時間”とは何を指しているのだろう。

45 :132人目の素数さん:02/08/09 18:21
>>44
n の桁数はO(log n)。多項式時間で解けるつーのは、入力の桁数を
変数とする多項式で実行時間が抑えられるという事。

46 :44:02/08/09 18:23
>>45
どうもありがとうございました。

47 :132人目の素数さん:02/08/09 18:33
みんな論文読んでるの? それとも放置?

48 :132人目の素数さん:02/08/09 18:39
>>47
論文読んでとりあえずコード化してみんなでワイワイやってます。
これは面白い…

49 :41:02/08/09 18:40
>>47
専門外だけど、取りあえず読んでます。


50 :44:02/08/09 18:43
>>47
読んでいます。
多くの数学科関係者がチェックしているはず。


51 :132人目の素数さん:02/08/09 18:44
いままでも確率的な方法で素数判定ができたんだから
そんなに意味ないとおもうんだけど、なにに使えるの?
素因数分解もできる?

52 :132人目の素数さん:02/08/09 18:46
>いままでも確率的な方法で素数判定ができたんだから
>そんなに意味ないとおもうんだけど、なにに使えるの?

現時点ではその程度の物って認識で合ってると思う。
後は今後の研究次第かと。

53 :132人目の素数さん:02/08/09 18:48
>>51
応用に関しては、この板よりも他板のほうが詳しいんじゃないかな?


54 :132人目の素数さん:02/08/09 18:52
関連スレ

プログラム
暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/

ニュース速報+
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/

補完よろ。


55 :132人目の素数さん:02/08/09 19:03
ニュー速はかなり もりあがってるね

56 :132人目の素数さん:02/08/09 19:57
8頁目真ん中の「予想」が気になります。

57 :132人目の素数さん:02/08/09 21:07
素因数分解より素数判定の方が簡単っていうのが信じられない。
馬鹿が理解できるよう、サイモンのように教えて下さい。

58 :132人目の素数さん:02/08/09 21:21
RSAは死んだか?本格的に楕円の時代到来かな

59 :ネット屋:02/08/09 21:24
ポカーン(゚Д゚;;

あ、あのさ、これさ・・・・
((( (((゚Д゚;;)))))ガクガクブルブル

60 :132人目の素数さん:02/08/09 21:35
>>57
素因数分解できれば素数かどうか判定はできるから
素数判定は素因数分解より難しくはない。

素数ならばある性質を満たすとわかっていたら、
その性質を満たすかどうか調べるだけで素数でないと判定できる。
だから素数判定の方が素因数分解と同程度の難しさかまたは簡単なはず。

例 nが素数ならば(x-1)^nの1次からn-1次の係数はすべてnで割り切れる。
n=4のとき(x-1)^4=x^4-4x^3+6x^2-4x+1で2次の係数が6で4で割りきれないから
4は素数ではない。

素数でないと判定できても素因数分解する方法はわからないから
まぁ素因数分解の方が難しいのだろう。

61 :132人目の素数さん:02/08/09 21:35
RSAは素因数分解できないと解読できないっしょ?

62 :132人目の素数さん:02/08/09 21:37
質問。

判定できる素数に何か条件はありますか?
どんな数でも、多項式時間で判定できるの?

63 :132人目の素数さん:02/08/09 21:50
>>62
多項式時間で判定できない数があるとすれば、
素数判定が決定的多項式時間で可能であるとは
言えません。


64 :132人目の素数さん:02/08/09 21:55
下記のスレで議論が活発にされていますので、こちらに移動
しましょう。

http://news2.2ch.net/test/read.cgi/newsplus/1028876818/


65 :132人目の素数さん:02/08/09 22:16
>>61
素因数分解をしなくてRSAを解読する方法があるかどうか
はまだ分かっていません。


66 :132人目の素数さん:02/08/09 23:00
プログラム板
http://pc3.2ch.net/test/read.cgi/tech/1028877628/78

>r=3として例をあげると
>x^3は1にしてx^4はxにしてx^5はx^2にしてx^6は1にする。
>x^5 +3x^4 +2x^3 +4x^2 +2x +3
>x^2 +3x +2 +4x^2 +2x +3 = 5x^2+5x+5 (mod x^3-1)
>これならどんな多項式も2次以下の多項式になる。
>だからいつもr次以下の多項式計算だけですむ。
>係数の無限長整数変数はr個だけですむ。

これが本質?合ってるのかな
ニュー速読みにくいなぁ…

67 :132人目の素数さん:02/08/09 23:09
>>66

2ページIdentityのProofの次の段落にある
Therefore, to make it feasible we will evaluate both side of (1) modulo a polynomial
of the form x^r-1.
のことでしょう。
暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/114
にも説明してあるよ。


68 :132人目の素数さん:02/08/09 23:32
>>66
ニュー速+はこれでいいのでは。
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/858


69 :132人目の素数さん:02/08/09 23:39
桁数nの素数判定をO(n^12)で解くのだな

70 :132人目の素数さん:02/08/10 00:16
このアイディアって、他に応用可能な部分はあるの?

71 :132人目の素数さん:02/08/10 00:26
むちゃくちゃでかい数を多項式時間で素数か判定できるようになった

俺がランダムなむちゃくちゃでかい数をつくって多項式時間で素数か判定する

「あなたの数は素数です」

記録更新



72 :132人目の素数さん:02/08/10 00:27
RSAてなに?

73 :132人目の素数さん:02/08/10 00:30
日本中央競馬会

74 :132人目の素数さん:02/08/10 00:47
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/
1000レス逝ったのか

75 :132人目の素数さん:02/08/10 00:49
スパコンでもうメルセンヌ素数を計算させてるやつもいるんだろうなぁ。

76 :132人目の素数さん:02/08/10 00:55
n is of the form a^b
ってどうすりゃい〜のさ。これだけで指数時間使ってしまう
教えてくれ〜〜

77 :132人目の素数さん:02/08/10 00:56
RSA亡き後はECCが台頭か?

78 :132人目の素数さん:02/08/10 00:59
>>76
bを2からlog nまで動かして
nのb乗根を計算して整数になるか判定すれば
O(log^3 n)でできるのでは

79 :132人目の素数さん:02/08/10 00:59
亡くなってないっつの。

80 :132人目の素数さん:02/08/10 01:04
log nを整数精度で浮動小数点を使わないで求める方法キボンヌ

81 :132人目の素数さん:02/08/10 01:07
>>80
俺なら、範囲を絞った上で、マクローリン展開、かな。

82 :132人目の素数さん:02/08/10 01:13
あきらめた

83 : ◆Math2chk :02/08/10 01:20
>>80
2で割っていく。


84 :132人目の素数さん:02/08/10 01:20
完全数たくさん求めてくれ。

85 :132人目の素数さん:02/08/10 01:44
>>80
/* 値は切り捨て、底は整数限定の手抜き版 */
int log_junk(int n, int base)
{
int a ,i;

if (n < 1 || base <= 1) {
exit(-1);
}

for (i = 0, a = 1; a < n; i++, a *= base) {
;
}
return i;
}



と、糞プログラムを書いて手の運動をするテスト

86 :132人目の素数さん:02/08/10 02:13
>>80
上位ビットから順に1を探す。


87 :132人目の素数さん:02/08/10 02:16
>>86
シフトして上位ビットをキャリーフラグに入れて条件分岐を繰り返す。
シフト回数からlog_2 nがわかる。

88 :132人目の素数さん:02/08/10 02:20
>>87
右シフトして(つまり2で割って)ゼロフラグがたつまで繰り返す。

89 :132人目の素数さん:02/08/10 03:21
すんません。
学のないドシロウトなんですが、
これで一番でっかい素数とかみつかるんですか?

90 :(o^-')b:02/08/10 03:36
>>89
バッチリ見つかります!(o^-')b 

91 :132人目の素数さん:02/08/10 03:39
一番でっかい素数って・・・・・・。

92 :132人目の素数さん:02/08/10 04:07
一番でっかい整数が見つけられれば、一番でっかい素数も見つかります。

93 :132人目の素数さん:02/08/10 08:16
プログラム板でコード化が進んでいるようです。
http://pc3.2ch.net/test/read.cgi/tech/1028877628/182

94 :132人目の素数さん:02/08/10 10:30
やっぱり軍とかじゃあ公然の秘密だったのかな。

95 :132人目の素数さん:02/08/10 13:05
ひょっとして2^65536-1が素数かどうかわかるんじゃないか?
たしかまだわかってなかったきがする

96 :132人目の素数さん:02/08/10 13:11
ああ、違った。
2^n+1
n=2^t
でtが5のとき2^n+1は素数になるが、t>5のとき素数になる場合があるかはわからない
そうです。

97 :132人目の素数さん:02/08/10 15:21
今まで、ネタスレだと思ってたよ(w
すげーな。さすがインド人!年齢関係なんてなくフィールズ賞やって良いん
じゃないの?
暗号全部再構築か…。ネスケもIEも今後しばらくの間、怖くてネット通販
使えないかもね。

98 :132人目の素数さん:02/08/10 15:27
>暗号全部再構築か…。

小一時間問い詰めるぞ。

99 :132人目の素数さん:02/08/10 16:21
なんだか、論文読んでも意外とあっさりしたもんだね。
これで証明できちゃうなんて、拍子抜けしちゃうよ。ハッハ〜。

100 :132人目の素数さん:02/08/10 18:57
証明のとこ、わかった?
あのアルゴリズムが有限回で終わるとこと、
素数なら素数と判定される、合成数なら合成数と判定されるというのは
いいんだけど、その後がわからん。

101 : :02/08/10 18:59
>>99
証明の間違いを見つければ神になるチャンス!!!

102 :132人目の素数さん:02/08/10 19:19
http://headlines.yahoo.co.jp/hl?a=20020810-00000008-zdn-sci
>2つの巨大な素数を掛け合わせ、より大きな素数を生み出している
って素数掛け合わせた時点で素数じゃないと思うんだが・・・?

103 :132人目の素数さん:02/08/10 20:17
そこらへんのライターなんて、そんなもん。
サイエンスやコンピュータ関係の専門的な内容は、誤解釈ばっかし。

自分で分かってないのによく書けるな。さすがモノカキのプロだ。

104 :132人目の素数さん:02/08/10 21:10
>>102 ニュー速にスレ立てて馬鹿にしてもイイ!!と思うの

105 :132人目の素数さん:02/08/10 21:41
>>102
それの日本語の元記事
ZDNN:暗号技術研究者が素数の問題を克服
http://www.zdnet.co.jp/news/0208/10/nebt_08.html
で原文の記事
News: Crypto scientists crack prime problem
http://zdnet.com.com/2100-1104-949170.html

106 :132人目の素数さん:02/08/10 21:49
>>102
掛け合わせて1足してるとか、そんなところだろ。

107 :名無しゲノムのクローンさん:02/08/10 21:51
>>106
素数と素数を掛け合わせた数は奇数であり、1足すと偶数になるがなにか?

108 :132人目の素数さん:02/08/10 21:54
>>107
じゃあ、2を足してるとか。
掛け合わせてる以外の計算もあるならあの記事でも良いだろ。

109 :名無しゲノムのクローンさん:02/08/10 21:56
>>108
アフォか?
素数を求める関数が未だに発見されてないから「素数定理」が長く未解決なんだろ?
お前意味わかってますか?

110 :132人目の素数さん:02/08/10 22:03
>>106 >>108はどうせニュー速板から来たんだろ。

111 :132人目の素数さん:02/08/10 22:05
>>106=>>108
おいおい。記事を読んだ上でそんな事を言ってるのか?
RSAの話だぞ。巨大素数を2つ掛け合わせて巨大な
合成数を作るのがRSAの準備段階だろうが。素数判定を
行うってのは掛け合わせる前の2つの素数を選ぶ段階で
使うって意味だ。個の記事書いたライターの方が、1足すだの
2足すだのとトンチンカンな事を言い出さない分お前よりRSAを
理解してんじゃないの?

112 :132発目の誤爆さん:02/08/10 22:05
■アスキー24が2ちゃんねるを「総会屋と同じ仕組みの掲示板サイト」と記述

アスキーの記事、削除されちゃいました…


・世論ではなく総会屋? に踊らされた

2ちゃんねるに近いあるインターネット関連会社の社長は、2ちゃんねるの幹部か
ら得た話として証言する。「2ちゃんねるは、運営者や幹部などがそれぞれ別々に会
社を作りカネの流れを見え難くしているが、実際の資金源は複数の大手通信会社系
からの調査費名目のカネ。月額で計約700万円と言い、年間にすれば1億円近く。額
はともあれ、これは通信会社系的には、ぼう大なトラフィックを調査すると言う表
向きの理由が一応は立つ。自社系に都合の悪い書き込みがされた時に優先的に削除
してもらうことも期待している」と前置きし「通信会社系の削除の期待も含めて、2
ちゃんねるは総会屋と同じになっている」と言うのだ。

その具体的な理由として社長は、こう話す。 「2ちゃんねるはボランティアの削
除人が書き込みをチェックして、好ましくない書き込みを一所懸命削除している、
ということになっているが、あれはウソ。削除人には給料が支払われ、その給料の
原資となっているのが、まずいことを書き込まれた企業が削除要求とともに渡す裏
金。これはまさに、総会屋の構図そのものだ。これまで裁判になっているのは金額
で折り合えなかったり、裏金を出さない強い態度の企業とだけだ」

もしこの社長の証言が事実だとすれば、警察や検察は、総会屋と同じ仕組みの掲
示板サイトに動かされて摘発したり、異例の動物愛護法による逮捕・起訴や、書類
送検で処理した容疑者を異例の逮捕・起訴に持ち込んだことになる。「社会への影
響」と検察が言う“社会”が、実は総会屋に等しいものだった、とは、警察、検察
にとって何とも情けない話である。

113 :132人目の素数さん:02/08/10 22:07
>RSA uses two huge prime numbers and multiplies them
>together to produce an even bigger prime.

元記事からして間違ってんのな。

114 :132人目の素数さん:02/08/10 22:08
第十問題と言って混乱させてみるテスト

115 :132人目の素数さん:02/08/10 22:12
>>107
2は偶数。

116 :132人目の素数さん:02/08/10 22:20
>>112

http://news2.2ch.net/test/read.cgi/newsplus/1028955206/
http://ascii24.com/news/reading/causebooks/2002/08/09/print/637825.html

真偽のほどは定かでない・・・

117 :132人目の素数さん:02/08/10 22:22
>>115
2が巨大な素数なのか。君の頭の中では。

118 :132人目の素数さん:02/08/10 22:30
1、2、3、たくさん(プ

119 :132人目の素数さん:02/08/10 22:46
>>118
いや、3まで数えられたら2が巨大な数だとは思わないだろ(w
>>115の頭の中は「1、・・・えーっと、たくさん!」くらいだと思われ。

120 :132人目の素数さん:02/08/10 23:16
logの底は何に?

121 :132人目の素数さん:02/08/10 23:17
>>120
>1の論文の中では底は2だが、
そのことを聞いてるの?


122 :132人目の素数さん:02/08/10 23:24
>>121
それそれ

123 :132人目の素数さん:02/08/10 23:59
これって、そこら中の暗号化されたデータが簡単に解読されるようになるってこと?

124 :132人目の素数さん:02/08/11 00:25
>123
違う。

125 :132人目の素数さん:02/08/11 01:55
プログラマ板みたいに、「暗号崩壊」とか書いてるわけじゃないのに、
なんでこんなにRSAが崩壊すると勘違いする奴が次から次へと
湧いて出てくるんだ・・・。

126 :132人目の素数さん:02/08/11 01:55
これって何屋さんの領域なの(数学で)
数論?

127 :132人目の素数さん:02/08/11 01:57
↑は、スレタイに暗号崩壊とか書いてないのにって事ね。

プログラマ板
暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/

こういうスレタイなら、勘違いする奴が出てくるのもわかるんだが。

128 :132人目の素数さん:02/08/11 01:57
>>126
そだね。数論。

129 :132人目の素数さん:02/08/11 02:05
http://ntw.e-one.uec.ac.jp/ntw/number_theorists.html
見つからない罠

130 :132人目の素数さん:02/08/11 07:32
>>126, >>128
計算量理論、で今回は問題が数論的だった
ではいかが

131 :132人目の素数さん:02/08/11 07:37
>>127 :
>>1 のリンクで M. Agrawal のページに飛ぶと、
回路計算量とかで錚々たる仕事してるみたい
そっちのコミュニティーのページには載ってるかも

132 ::02/08/11 08:02
別に素数判定ができるだけで、多項式時間でn=pqが因数分解されるわけでないのに
なんでRSAが崩壊するんかわからん。
確率的手法でも十分だと思うんだけど。

133 :132人目の素数さん:02/08/11 08:13
>>132
しねーよ。

134 :132人目の素数さん:02/08/11 08:16
諸君!!!
暗号の問題と関係なく、素数の判定は歴史的にも興味をもたれてきた問題だから
この結果はとても重要であることはいうまでもない。
まず9ページをプリントして、パソコン、携帯電話から離れ、論文を読もうでは
ないか。
我輩もこの書き込みをしたら Shutdown するぞ!

135 :132人目の素数さん:02/08/11 08:37
>>134
未だに読んでないような奴が何を偉そうに言ってるわけ?
興味のある奴はとっくに読み終えてるんだけど。

136 :132人目の素数さん:02/08/11 11:33
むしろ、RSA暗号がより使いやすくなるって事でファイナルアンサー?
巨大素数が確実に入手できるようになるわけだし。


137 :132人目の素数さん:02/08/11 14:30
Oはオーダーだけど、
Oの上に~が付いてるのはどういう意味なの?

138 :132人目の素数さん:02/08/11 15:02
>>137
> We will use the symbol O~(t(n)) for O(t(n)poly(log t(n))), where t(n) is some function of n.

139 :132人目の素数さん:02/08/11 15:27
>>138
ありがとうございました。
見落としてた…。勝手記法だったのね。

140 :132人目の素数さん:02/08/11 16:12
>>109 素数定理って、ふつうは、

π(x)
lim ――――― = 1
n→∞ x /log x 

だろ?こりはみかいけつだったですか?


141 :132人目の素数さん:02/08/13 10:35
http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html

正確だけど遅いってさ。
数論な人にとっては証明が正しければそれでOKなのかな?
それとも高速化にも興味あるの?

142 :132人目の素数さん:02/08/13 13:34
>>141
原理上多項式時間で素数判定ができるかどうかに興味があるんだよ。数論の人は。

143 :132人目の素数さん:02/08/13 15:12
>>141-142
話が噛み合ってなくないか,君たち?

144 :132人目の素数さん:02/08/13 18:57
数学板住人だったら「暗号崩壊!?」って誤解よりも
「P≠NP問題解決!?」って誤解をしそうな気がする。

気のせい?

145 :132人目の素数さん:02/08/13 19:04
けどさ、いくら桁数の多項式時間って言っても
パソコンでやった時に一桁10年かかるようなのだったら
実生活に役立たないよな。

146 :132人目の素数さん:02/08/13 19:13
たとえ145のような場合でも量子コンピュータのような奴が実用化されなくて、
さらにコンピュータがそれなりに進歩すれば実生活に役立つ。

147 :132人目の素数さん:02/08/13 23:42
>>145
むしろ、これから「役に立つか」「立たないか」を検証するんじゃないの?

148 :132人目の素数さん:02/08/14 00:00
他にPなアルゴリズムを持つかどうか未だにわかっていない問題もたくさんありますが、
その中でこの素数判定というものはどれくらいの難易度にあったのでしょうか。

149 : :02/08/14 02:35
うーん。このことから「拡張されたリーマン予想が真である」
ということは導けないのが残念だね。

150 : :02/08/14 03:04

928 :nanashi :02/08/13 00:36 ID:*********
http://news.2ch.net/test/read.cgi/news/1028881473/l50
『2chは総会屋? 』のやばスレのため、ニュー速板は板ごと夜勤および夜勤の
会社のリーマン削除人により
削除されます。要スレ保存。

929 :********** :02/08/13 00:39 ID:********

まーここは夏厨とプロ市民専用らしいから
どんな電波スレ立ててもいいんじゃねーの?

930 :nanashi :02/08/13 00:52 ID:********
http://qb.2ch.net/test/read.cgi/accuse/1028877735/175-
夜勤は夜金=ウマ=上場反対=2chは金のなる木
http://jbbs.shitaraba.com/computer/2095/のニュースに多数の大手広告

151 :132人目の素数さん:02/08/14 06:22
>148

マイケル・ラビンなど,この分野の天才たちが挑戦してきた
歴史的に有名な問題です.もっとも,NP∩co-NPに含まれることは
自明なので,NP-hardではなかろうと信じられてきました.

ラビンらのアルゴリズムはこれをさらに小さなRPというクラスに
押し下げるものでしたが,リーマン予想云々という条件が
出てきた時点でこれ以上の結果はそう簡単にはでないだろうと
思ってましたので,このニュースには本当にびっくりしました.

いまだにNP-hardnessが未解決な問題として残されているのは
グラフに関する問題が多いです.一番有名なのはグラフ同型問題です.
これなどは,Pに含まれることは絶対にないだろうと思われています.
なぜかというと,もしそれが真ならば,P=NPはおろか
無限の多項式階層が有限個につぶれてしまうからです.
NPというクラスはこの階層のもっとも下に位置します.

かれらの論文はまだ未発表ですが,それはおそらく
次のACM STOCに投稿するつもりだからではないでしょうか.
チューリング賞を授与するこの世界で最も権威のある会議ですから.
〆切は12月ぐらいだったと思います.

こんなニュースを聞くと,未解決問題に挑戦したくなりますが
私にはリスクが大きすぎます.人生は有限なので(w

152 : :02/08/14 16:02
グラフ同型問題の良い参考書があったら、おしえてください。
N=NP?に関連する解説が載っていたらなお歓迎です。

153 :132人目の素数さん:02/08/14 20:43
>>151
手近にある本を調べてもわからなかったので,すみません教えてください.
グラフ同型問題はNP困難かどうかわかってないんですよね?
それでもグラフ同型問題がin PだったらP=NPになっちゃうんですか?
逆にいうと,P=NPになったり多項式階層がつぶれるということは,
グラフ同型問題についてなんらかの意味での困難性が知られてるんでしょうか?

154 :151:02/08/14 21:03
>152

学生さんですか? 質問の内容から,これから勉強する人だと思って
答えますね.

グラフに関する研究は,グラフの代数的構造を研究する人と
グラフ問題を解くためのコストを見積もる人に分かれます.
例えばなしをすると,グラフG=(E,V)が与えられたとして,
Gが平面グラフであることの必要十分条件を調べるのが前者で,
Gの平面性を効率的に判定するアルゴリズムを構築するのが後者です.
あなたはPvsNPに興味があるように見受けられましたので,後者の
ための教科書という意味だと受け取りました.

ちなみにグラフの平面性を判定する多項式時間アルゴリズムは
ロバート E.タージャンらによって発見され,かれはこの研究によって
チューリング賞を受賞しました.

さてグラフ理論と(主にPvsNPについての)計算量理論を
バランスよく学ぶための教科書ですが,次の2つをお勧めします.



155 :151:02/08/14 21:08
続きです.

1)Computers & Intractability, Michael R. Garey and D. S. Johnson,
W.H. Freeman & Company:
最も有名な教科書です.この本は前半と後半があって,前半は普通の
計算量の教科書です.計算量(PとNP)の基本的な概念はこれでOKです.
この本の真価は後半部です.後半はそれまでに知られている膨大な量の
NP-completeな問題のリストと初出の文献リストからなっています.
これらのリストは,いままで見たことのないアルゴリズム上の問題に
突き当たったときにこのリストをながめて似た問題を探すという使い方をします.

2)計算とアルゴリズム,新コンピュータサイエンス講座,浅野孝夫・今井浩,オーム社:
最近出たとてもよい日本語の教科書です.1)で定義を厳密に学んだ後に
よむとよいです.グラフ問題に関係があるのは1章のアルゴリズムの基礎,
7章のグラフアルゴリズム,8章の近似アルゴリズムです.


156 :151:02/08/14 21:09
続き2です.

教科書はこの2つで十分です.この2つで訓練すれば
例外的なものを除けばほとんどの論文を自分一人で
読んで,証明の内容をチェックできるようになります.
なおこれ以上の知識をお望みなら,次の2つを参照してください.

3)Computational Complexity, Christos H. Papadimitriou,
Addison Wesley Publishing Company:
様々なクラスの計算量が扱ってあります.ただ書き方が少し特殊なので
まじめに読むとはまります.結果だけ参照すればよいと思います.

4)計算と複雑さ,岩波
うら覚えですが,Algorithms and Complexity Volume A,Elsevier:
という本の和訳だったと思います.2冊組です.古今東西の計算量理論の結果が網羅されてます.
誰も知らないようなことまで載っているので面白いのですが,
とても高いので必要なら研究室で買ってもらってください.

最後に,グラフ同型問題の最新の結果が以下の会議で発表されてます.
Graph Isomorphism is in SPP,
by V. Arvind and Piyush P Kurur,
The 43rd Annual IEEE Symposium on Foundations of Computer Science


157 :151:02/08/14 22:04
>153
書きこんでいる間に新しいメッセージがあったようですね.
なんだか前の書きこみと違ってずいぶんご存知のようですが.


え〜とすみません.
>P=NPはおろか
これは筆がすべりました.これは下の条件に包含されない可能性がありますね.
>無限の多項式階層が有限個につぶれてしまうからです.
これは本当です.1)のGarey and Johnsonのリストの最後にある
Open problemの節を見てください.Graph Isomorphismという問題が
出ているはずです.そこのコメントを見てみてください.
参照すべき論文がかいてあるはずです.

それからSamuel R.Buss,Bounded Arithmeticという本に
多項式階層とPvsNPの関係がのってます.






158 :132人目の素数さん:02/08/14 22:24
153です.どうもありがとうございます.
Garey&Johnson,研究室内で探したんですが見つかりませんでした.
きっとあるはずなので,後日じっくり探して読んでみたいと思います.

159 : :02/08/16 20:52
100桁とか200桁、あるいは500桁程度の整数を素数かどうか
判定するプログラムのソースコードがどこかに落ちていませんか?

160 :132人目の素数さん:02/08/16 23:57
ZDNNの記事
http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html

161 :132人目の素数さん:02/08/17 03:32
>>160
テンション的に健全な記事。

162 :132人目の素数さん:02/08/17 05:37
>>159
UBASICは2700桁まで扱えるそうだ。
http://www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm
どっかに素数判定のプログラムもあるだろう

163 :132人目の素数さん:02/08/17 06:58
    / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
    | 作るのは
    \
     ̄∨ ̄ ̄ ̄ ̄ ̄ ̄
     ∧_∧
    ( ´Д`)
   /⌒  ⌒ヽ
  /_/|   へ \
  (ぃ9 ./  / \ \.∧_∧ / ̄ ̄ ̄ ̄ ̄ ̄ ̄
    /  ./      ヽ ( ´Д` )< 君だ!!
   (  /        , /  \_______
   \ .\\     (ぃ9 |
    .\ .\\    /  / ,、
        > ) ) ./  ∧_二∃
    / //  ./   ̄ ̄ ヽ
    / / / ._/ /~ ̄ ̄/ /
   / / / )⌒ _ ノ  / ./
   ( ヽ ヽ | /   ( ヽ、
    \__つ).し    \__つ

164 :132人目の素数さん:02/08/17 10:04
>159
javaで書けば?

165 ::02/08/17 10:05
注意して下さい!!
 毎日100以上のスレで大量の荒らし行為を行っている悪質な
 人間が書き込みを行っています。徹底して無視してください。
 皆さん 力を合わせ 一刻も早く2chから追放いたしましょう。
                    2chを守る会

166 :132人目の素数さん:02/08/17 10:10
100以上のスレってすげーな。

167 :132人目の素数さん:02/08/26 21:27
age

168 :132人目の素数さん:02/08/27 03:43
神帝大天才山口人生超教授のおっしゃるところによればP=NPです。
だから素数判定がPなんか自明です。

169 :132人目の素数さん:02/08/27 07:27
インド人もビックリ

170 :132人目の素数さん:02/08/27 21:40
>>151
グラフ同型問題が NP完全ならば階層が2段目まで潰れる、
という話なら知ってるけど、P に入っていても潰れると言う話は
あったっけ?

それにしても `Graph Isomorphism is in SPP' は同型問題の
論文例としてはマニアック過ぎると思うのだけど :)


171 :151:02/08/28 18:43
>170

>P に入っていても潰れると言う話
これは失礼.NP-completeではなさそうだという予想を
勝手に,多項式では解けなさそうだと脳内変換していたようです.
私データマイニングなんぞやってる似非理論屋なもので.

>それにしても `Graph Isomorphism is in SPP' は
FOCSの会員じゃないので,実はこれ読んでません.
知り合いの専門家にタイトルを教えて意見を聞いたところ
SPP???という反応でした.

SPPってはじめて聞いたんですけどどんなクラスなんですかね.





172 :132人目の素数さん:02/08/31 18:05
>>171
このネタで続けるのもあれだけど、
ttp://eccc.uni-trier.de/eccc/ の TR02-037 見るよろし。
定義はそっからたどりましょう。
FOCS2002 のプログラムももう見られるね。

173 :132人目の素数さん:02/08/31 19:14
なるほどポキン、新機軸

174 : :02/09/03 22:12
しまった、素数判定に引き込まれて、公募書類と学会発表の申し込みを
出すのを忘れていた。

175 :132人目の素数さん:02/09/04 10:05


176 :132人目の素数さん:02/09/05 08:45


177 :132人目の素数さん:02/09/05 16:10
具体的に素因数分解するのと、素因数の数だけ求めるのには
本質的な時間の違い現れますか?

178 :132人目の素数さん:02/09/05 22:26
「時間が本質的に違わない」の意味を、
素因数計数問題が易しければ、素因数分解問題も易しい
とするのであれば、本質的に違いはある、と思うに一票

素因数の個数を教えてもらっても、そんなに素因数分解
問題が易しくなった気がしない。
たとえば、RSA とかで使われている
n = p q (p, q: 素数)
は、はじめから素因数の個数が2個とわかっているけど、
効率的に素因数分解せよ、と言われればどうして良いか
わからん。

もちろん、素因数分解問題がそもそも易しいのであれば、
(そうじゃないだろと思ってるが...)両者の時間は
本質的に同じ、ということになるが。

179 :132人目の素数さん:02/09/05 22:40
>>178
逆だと考えたんだけど。素因数計数問題を解くためには
素因数分解する以外に効率的な手段はないのかなって思った。

180 :132人目の素数さん:02/09/06 19:45
>>179
例えば試し割りしていく場合、途中で素因数の最大個数は確定すしそうな気がする。

181 : :02/09/08 14:25
桁数の12乗で、ある予想が成り立てば6乗だというのだけど、
どこまで下げられるのかな。3乗とか4乗ぐらいだとずいぶん
やさしい問題になるんだけど、6乗でも相当、12乗ならむちゃくちゃ
計算量が必要で、これはつらいね。

182 :132人目の素数さん:02/09/08 22:12
5 :132人目の素数さん :02/08/09 14:12
なんでこのスレは4つしかレスがないの?
これ、すごいことではないですか?
(数学専門ではないのですが、(コンピュータ専門)
すごい騒ぎになってるのでは?と思ってはじめて
この板に来たのですが)


6 :132人目の素数さん :02/08/09 14:13
だって意味和漢ねーン唾問、俺馬鹿だから。
28 :132人目の素数さん :02/08/09 16:33
なんでこんなに静かなんだ・・・


29 :132人目の素数さん :02/08/09 16:45
>>28
このスレの住人が数学オンチだらけだからじゃねーの。
そうじゃなかったら祭りがはじまるはずだよ。

183 :132人目の素数さん:02/09/08 23:07
>>182
マジレスすると、ニュー速+に人が流れてたから。

184 :132人目の素数さん:02/09/08 23:43
マジレスすると、1が、一人で騒いでただけだから

185 :132人目の素数さん:02/09/08 23:53
>>184
確かに、このスレを盛り上げようとしてたのは>>1を含めても少数だな。
いっそマ板のように「暗号崩壊!?」というデタラメでセンセーショナルな
スレタイにすれば無駄に盛り上がったんだろうな。

186 :132人目の素数さん:02/09/09 00:11
マジレスすると、自分が分かっちゃうとそれ以上語り合うことないっしょ
数学って
教えるという形以外ではさ
自分の分野に関係していて、進めていけるならともかく、所詮、他ジャンル
という人が多いのだろ

187 :132人目の素数さん:02/09/09 14:25
そうだね

188 :132人目の素数さん:02/09/17 10:15
数学板で「盛り上がる」という行為をするネタは大抵電波出現だった気がするんだが。

189 :132人目の素数さん:02/09/22 06:33
さあ、もうFortranかCで判定プログラムをかけましたか?課題提出の期限は
せまっていますよ。

190 :132人目の素数さん:02/09/22 09:49
>>1
P=NPより確定的多項式時間アルゴリズムは存在します。
  
   参考文献(近刊予定):御神本 山口人生著

191 :132人目の素数さん:02/09/24 01:35
12乗がデカイと感じるのはしかたない。
しかしコンピュータの処理速度がいまの10^43倍くらいだったらどうだろう?
指数オーダーに対する12乗オーダーはものすごい脅威になっていたはず。

192 :132人目の素数さん:02/09/24 05:46
>>191
え?12乗って聞いてまず感じたのは「ちっちゃい」だったんだけど。
冷静に考えてみて初めて実用に向かない程度に大きい事を理解した。

193 :132人目の素数さん:02/10/08 02:36
人生ちゃんって日本数学会にも顔だしてんの?

194 :132人目の素数さん:02/10/11 13:19
>190
計算量の授業後に「だれも相手にしてない」と
先生が言っておりました。

195 :132人目の素数さん:02/10/14 03:09
P=NPあるいはその否定が証明できたら、まちがいなくチューリング賞もの
だし、ある程度若ければフィールズ賞ももらえることはほぼ確実だろう。
ノーベル賞は出ないのも間違いない。

196 :132人目の素数さん:02/10/14 13:54
ノーベルコンピュータ科学賞もあるべきだ。

197 :132人目の素数さん:02/10/14 15:02
nobelの時代にコンピュータなんてない

198 :132人目の素数さん:02/10/14 15:24
http://science.2ch.net/test/read.cgi/sky/1029291426/227

199 :132人目の素数さん:02/10/14 15:28
http://yahooo.s2.x-beat.com/

200 :132人目の素数さん:02/10/14 15:33
>>198
ここで止まった。
http://tv2.2ch.net/test/read.cgi/eva/1024726406/190

201 :132人目の素数さん:02/10/24 03:04
>>196
Turing Prizeもらえばいいじゃん。それともタナカさんみたいに
「今日も同じ服」なんていわれたいの?

202 :132人目の素数さん:02/10/30 19:22


203 :132人目の素数さん:02/10/31 14:49
次の大きなニュースもこのスレで出来るかな?

204 :132人目の素数さん:02/11/23 04:34


205 :132人目の素数さん:02/12/12 04:19


206 : ◆BhMath2chk :03/01/10 07:00
2^2003−1=4007×6588622714946609×...。


207 :山崎渉:03/01/11 12:43
(^^)

208 :132人目の素数さん:03/01/17 04:03
ゲーツあたりがノーベル賞委員会に多額の寄付をすれば、ノーベル計算機賞が
できて、多分第一回目の受賞者は、MS-BASICを作った功績でゲーツが貰う
ことになろうか。

209 :132人目の素数さん:03/01/23 17:56
(・∀・)ゲハハハハ

210 :132人目の素数さん:03/02/01 01:42
誰かPとNPが真に違うということを証明しようとしている人はいないのか?

211 :132人目の素数さん:03/02/01 05:36
げーつがMS-BASICを作ったと思ってるんですか?

212 :132人目の素数さん:03/02/08 18:21


213 :132人目の素数さん:03/02/16 00:31
P=NPだとすればP(1-N)=0だからP=0またはN=1でなければならない。
すると、一般のPもしくはNについてP=NPは成り立たない。

214 :132人目の素数さん:03/02/16 00:35
( ゚Д゚)<ナナ、ナント

215 :Quserman ◆KeLXNma5KE :03/02/17 18:56
素数判定が多項式時間で可能だとしても、我々が生きている間に素数判定が終わることの保証がされたわけではない。
それでも、最近の素数判定はめざましい進歩を遂げたと思う。
2^(2^n)+1の形の数は、フェルマーは素数だと思っていたようだが、
オイラーによって、4294967297が素数でないことが示された。
それより大きい数をどうやって素因数分解するのかはよく知らないが、
とにかくコンピュータが無いと殆ど不可能だろう。
その意味では、素数判定が早いとは言えない。
だが、もし素数判定にかかる計算量が、桁数の対数のオーダーになったならどうしよう?
まぁ、私はそんなことはないと信じているが、そんなことになってしまったら、
公開鍵暗号は使えなくなる。
素数関連の問題が人類の運命を左右すると言っても決して過言ではないだろう…。

216 :132人目の素数さん:03/02/17 19:05
>公開鍵暗号は使えなくなる。

そうなの?
そもそも公開鍵暗号ってどんな仕組みなの?

217 :級数王:03/02/17 20:53
>Quserman
お前は公開鍵暗号のこと全然わかってないね
素数判定が高速で行えれば、暗号の強化にはなるが
暗号を破れるわけじゃない

破るのは素因数分解せんといけんだろ、、、、

218 :級数王 ◆Tqj41pFNVk :03/02/17 20:59
>217

    
   偽 者 は 消 え て く だ さ い 。


219 :132人目の素数さん:03/02/17 23:06
Manindraさんの講演聴いてきた人いませんかー?

220 :132人目の素数さん:03/02/19 00:24
2進でb桁の自然数を素因数分解(簡単の為に素因子が2個としてよい)
するために必要な計算量の現在知られている下限は、どのぐらい?

221 :132人目の素数さん:03/02/19 00:30
下限が strict に押さえられるならみんな苦労していないとおもうが?


222 :132人目の素数さん:03/02/19 01:53
既出かもしれんがこんなのがあった
http://www.cybernet.co.jp/maple/hiroba/aks/ask.html
Mapleでの実装。Octaveでも動くかな?

223 :222:03/02/19 02:03
OctaveはMatlabモドキだった。フリーのMapleモドキってないのかな。

224 :132人目の素数さん:03/02/19 02:44
mupad


225 :132人目の素数さん:03/02/19 02:48
http://www.tcs.hut.fi/~helger/crypto/link/primality_tests/aks.html

みれば

C++
Pari/GP
Magma

の実装もあるよ。


226 :132人目の素数さん:03/02/19 14:19
思い出したが以前RIMSで木田先生だったかが公演でこのアルゴリズムの解説やってたな。
現状ではnon-polynomialのAPRのほうが速いそうだ。

特別の数については高速アルゴリズムが確立してるから、俺的にはそれで十分だが。

227 :132人目の素数さん:03/02/20 06:03
>>221
それじゃあ、現在分かっている上界のうち最良のものは?

228 :132人目の素数さん:03/02/20 14:58
>>Quserman ◆KeLXNma5KE
本当に馬鹿だな。
なんで公開鍵が使えなくなるの?
暗号の本でも読め。

229 :132人目の素数さん:03/02/20 15:07
>>227
bの準指数時間

230 :132人目の素数さん:03/02/21 03:30
【超高速計算機】量子コンピューターを開発 NECと理化学研
http://news2.2ch.net/test/read.cgi/newsplus/1045706530/l50

関連ちょとぐらいはあるのでリンク

231 :132人目の素数さん:03/02/21 13:52
準指数ということは、指数関数よりは増加が少ないということだね?
多項式よりも多いということなんかな?

 exp(sqrt(n))
みたいなの?


232 :132人目の素数さん:03/02/21 13:52
☆やっと見つけた宝物☆
http://bbs.1oku.com/bbs/bbs.phtml?id=rantyan

233 :132人目の素数さん:03/02/22 20:14
>>231

 O( exp ( c (log n) ^ b (log log n) ^ (1-b) ) )
らすぃ

exp(sqrt(n)) は指数やね。


234 :132人目の素数さん:03/02/22 22:58
233さんの一応補足しとくと
nが分解したい整数のビット長でbは[0,1]に値をとるパラメタね。

235 :132人目の素数さん:03/02/23 05:31
>nが分解したい整数のビット長

ダウト

236 :229=234:03/02/24 09:18
訂正ありがとうございます(恥)>235
記号bの使われ方のほうに気をとられてました〜

237 :132人目の素数さん :03/02/24 19:37
>exp(sqrt(n)) は指数やね。

準指数だよ。

238 :Quserman ◆KeLXNma5KE :03/02/24 19:44
>>217>>228
そのとおりであった。
素数判定よりも、素因数分解の方がずっと難しいことに気がついていなかった。
異なる素数p,qについて、pqと素である正整数nに対して、
n^(pq-1)はpqを法として、何と合同になるか?
(これは難しいか。)
それじゃあ、n^((p-1)(q-1))にしよう。

239 :132人目の素数さん:03/02/24 20:44
>>237
え?

240 :132人目の素数さん :03/02/24 21:38
>n^(pq-1)はpqを法として、何と合同になるか?

どうなるの?

241 :132人目の素数さん :03/02/25 08:28
最近のレス意味不明。
素因数分解なんて2、3、5、・・で割っていくだけでいい。
これも立派なアルゴリズム。
これくらい気付けよ・・・。
パソコンだったらあっという間に出来ます。


こ の ス レ は 電 波 さ ん だ ら け の よ う で す ね 。





242 :132人目の素数さん:03/02/25 08:31
釣り人は早起きですね。

243 :132人目の素数さん:03/02/25 09:18
電波は241一人だけでよろし。

244 :237:03/02/25 10:14
>>239
ごめん、オレの勘違いです。

245 :132人目の素数さん :03/02/25 13:05
山口ジンセーたんのスレって、どこが間違っているのか、実は何にも分かって
いない香具師が、結構多く騒いでいるような気がするのは俺だけ?

246 :132人目の素数さん:03/02/25 13:51
彼らトンデモ達が一番間違っているのが「進むべき道」である事を
理解しているのなら別にいいんじゃないかと。

まぁ、ある程度の知識を持っていればより楽しめるのだろうけど、
彼らの主張について真面目に考えるのはあんまりお薦めはしない。
如何に無駄な時間を過ごしたのかと後悔するだけだし。

247 :132人目の素数さん :03/02/25 14:31
>>246
そうかね?Cook, Levin, Karp のリダクションとかも分かっていない奴が
人生痰をバカにする資格あるのかなと思うけどね。そんな奴らもしょせん
神帝レベルだろ。
物理板とかで「アインシュタインは間違っている」っていうデンパを
しったかして攻撃してる奴に限って、相対論をまるで理解できていない
香具師ばっかなのと同じだよ。
まあ、人生をからかうために奴の「世界観」を理解する必要なんて
まるでない、ってことには大いに同意するが。激しくスレ違いスマソ

248 :132人目の素数さん:03/02/25 14:32
>>225
Magma で10進9桁の素数を投げて実験してみました。

6時間経つけどまだ返って来ない。
どこに時間食ってるんだろう?

249 :246:03/02/25 14:42
>>247
個人的には「バカにしてる」という行為をする人は多くは無く、そしてそういう人達は
246前半には該当せず、トンデモスレの深みに嵌ってしまっている気がする。

250 :132人目の素数さん :03/02/25 14:49
>>248
12乗オーダーのアルゴリズムなので、10進7桁の数の20倍かかる。

251 :Quserman ◆KeLXNma5KE :03/02/25 19:52
>>240
これは、p,q,nの値によるので、n^(pq-1)=n^(pq-p-q+1+p+q-2)≡n^(p+q-2)としか言えないけれど、
gcd(n,m)=1⇒n^(m-1)≡1(mod m)となるような合成数mを探してみてください。

252 :132人目の素数さん :03/02/25 19:54
>>251
それって無限個あるんだよね。

253 :山崎渉:03/03/13 13:27
(^^)

254 :132人目の素数さん:03/03/16 08:33


255 :●゜、⊃゜) ◆13ThomasYo :03/03/19 09:26
数学板の名無しさんだ…
せっかくだからなんかネタでも書いていけばいいのに。

256 :132人目の素数さん:03/03/19 22:23


257 :132人目の素数さん:03/03/26 17:43




258 :132人目の素数さん:03/03/29 05:00
Manindraさんが講演したときのスライド資料が
どっかに落ちてたよ。

259 :132人目の素数さん:03/03/29 11:40
最近の研究

http://www.arxiv.org/abs/math?0211334
Sharpening "Primes is in P" for a large family of numbers

Authors: Pedro Berrizbeitia
Subj-class: Number Theory
MSC-class: 11A51

We give Deterministic Primality tests for large families of numbers.
(以下略

これってどうよ?

260 :132人目の素数さん:03/03/29 17:58
>>259
お、何か楽しそう。今から読んでみる。

261 :132人目の素数さん:03/03/30 01:48
もうちょっと勉強してせめて4乗ぐらいにまかりませんか?

262 :山崎渉:03/04/17 09:54
(^^)

263 :132人目の素数さん:03/04/17 14:14
>>261
ビタ1乗も負けらんねえ!!!

264 :132人目の素数さん:03/04/17 14:18
http://endou.kir.jp/betu/linkvp2/linkvp.html

265 :山崎渉:03/04/20 04:07
   ∧_∧
  (  ^^ )< ぬるぽ(^^)

266 :132人目の素数さん:03/04/27 21:52
定期age

267 :132人目の素数さん:03/05/05 21:28
ほっしゅ

268 :132人目の素数さん:03/05/11 21:55
定期age

269 :132人目の素数さん:03/05/12 09:28
楕円暗号って何?
解読不可能っていうのはホントなの?

270 :132人目の素数さん:03/05/12 09:30
>>269

楕円曲線を使った素因数分解による
暗号化のことたタコ

解読不可能てことはない

もっと数学勉強しな

271 :タコ:03/05/12 09:38
>>269

どうも。一から出直してきます。

272 :132人目の素数さん:03/05/12 09:43
>>271

おまえは九九からやり直せ!タコ

273 :132人目の素数さん:03/05/12 09:51
>>271

タコだから誤解しそうだけど,
「楕円曲線」ていうのは楕円じゃないよ(w

274 :132人目の素数さん:03/05/13 17:56
>楕円曲線を使った素因数分解による
>暗号化のことたタコ

( ゚д゚)ポカーン

275 :132人目の素数さん:03/05/16 22:41
無教養な>>274を沙羅氏安芸。

276 :132人目の素数さん:03/05/16 22:44
今まで、ネタスレだと思ってたよ(w
すげーな。さすがインド人!

暗号全部再構築か…。ネスケもIEも今後しばらくの間、怖くてネット通販
使えないかもね。

277 :132人目の素数さん:03/05/16 23:01
/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
| 素数判定は多項式時間でできますよ。

   ̄ ̄ ̄|/ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 γ~三ヽ
 (三彡0ミ)        / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
  ( ・∀・)  ∧ ∧ < えっえっ!!
 (  ⊃ )  (゚Д゚;)  \____________
 ̄ ̄ ̄ ̄ ̄ (つ_つ__
 ̄ ̄ ̄日∇ ̄\| BIBLO |\
        ̄   =======  \
----

278 :132人目の素数さん:03/05/16 23:05
素数判定と(素)因数分解とでは、また大きな隔たりがあるわけで…

279 :132人目の素数さん:03/05/17 05:46
>楕円曲線を使った素因数分解による
>暗号化のことたタコ

( ゚д゚)ポカーン

>暗号全部再構築か…。ネスケもIEも今後しばらくの間、怖くてネット通販
>使えないかもね。

( ゚д゚)ポカーン

280 :132人目の素数さん:03/05/17 13:41
270のキチガイ猿
楕円曲線法による、素因数分解と、
楕円暗号を混同している。
猿の証拠
ここはキチガイの集まりか


281 :132人目の素数さん:03/05/17 15:59
>>280
>ここはキチガイの集まりか

まともなツッコミを入れた人間に謝れ

282 :翔太@中3:03/05/17 21:15
>>280

猿はオマエじゃ

283 :132人目の素数さん:03/05/17 21:40
>>282
正しい方に絡むとは・・・
本当にアホだな。

284 :132人目の素数さん:03/05/17 21:42
age

285 :132人目の素数さん:03/05/20 20:25
再現性が皆無な暗号は解読不能だな

286 :山崎渉:03/05/21 22:00
━―━―━―━―━―━―━―━―━[JR山崎駅(^^)]━―━―━―━―━―━―━―━―━―

287 :山崎渉:03/05/22 00:07
━―━―━―━―━―━―━―━―━[JR山崎駅(^^)]━―━―━―━―━―━―━―━―━―

288 :132人目の素数さん:03/05/22 05:25
一つの平文に対応する暗号文が複数個存在して、暗号化の際に
それらのうちの一つをランダムに選んで返す暗号方式は
「再現性あり」なんですか?

289 :132人目の素数さん:03/05/22 15:47
再現性の定義は?

290 :132人目の素数さん:03/05/22 21:30
一ヶ月ほど前に新聞で取り上げられていた、
「素因数分解は多項式時間で可能!?」の真偽はどうなったのですか?

291 :132人目の素数さん:03/05/22 21:41
>>290

その後間違いが発覚した
しかし確率的にはうまく作動するらしい
RSAから有限体の乗法群暗号への総移行を
急ピッチで進めているのが現状

292 :次世代のワイルズ :03/05/22 21:54
>一ヶ月ほど前に新聞で取り上げられていた

ぷぷっ。
もう2ヶ月以上前の話だ。

>その後間違いが発覚した

証明自体は間違っていなかった。
「確率的」であるのに著者が「決定的」であると勘違いしていただけ。
「素因数分解は確率的多項式時間で出来る」が今回の結果。
世紀の大発見みたいだな。


293 :次世代のワイルズ:03/05/22 21:56
まあ、究極の「楕円曲線暗号」があるから問題ないんだけど。

294 :132人目の素数さん:03/05/22 22:01
>「素因数分解は確率的多項式時間で出来る」が今回の結果。

何乗オーダーですか?

295 :次世代のワイルズ :03/05/22 22:03
62乗だったと思う。

296 :132人目の素数さん:03/05/22 22:10
>>293
究極?どこが?

297 :次世代のワイルズ:03/05/22 22:12
         ‖        
        ('A`) ←>>296
        ( )       
     |    | |
     |
    / ̄ ̄



298 :132人目の素数さん:03/05/22 22:13
         ‖        
        ('A`) ←数時間後のワイルズ
        ( )       
     |    | |
     |
    / ̄ ̄

299 :132人目の素数さん:03/05/22 22:31
age

300 :132人目の素数さん:03/05/23 21:39
楕円曲線の種類によっては,未知の攻撃法が存在する可能性があるので
「究極の暗号」とはいえないです>楕円曲線暗号
そういや,情報理論的に安全な暗号が「究極の暗号」などと見出しを付けて
報道されたことがありましたね.

301 :132人目の素数さん:03/05/24 23:15
>>300
知らないで聴くのもなんだけど、量子暗号とか言わないよね?
情報理論的に安全な暗号なんて、バーナム暗号しか知らないけど。


302 :次世代のワイルズ :03/05/24 23:25
         ‖        
        ('A`) ←>>301
        ( )       
     |    | |
     |
    / ̄ ̄

303 :300:03/05/25 01:39
計算量的安全性ではなく、情報量的安全性に基づく暗号のことです。



>>302
キミ、ほんと専門板には不必要な存在だよ。とっとと名無しに戻ってろよ。
>>300にはツッコミいれられなかったんですね。ワラ


304 :300:03/05/25 05:04
スマン、ちょっと言い過ぎた。流してくれ。

305 :301:03/05/25 14:14
>>300 >>303
暗号の安全性は以下の理解で正しい?(2)がうろおぼえで悪いんだけど?
(1)計算量的安全性:確率TMが多項式時間で解読できない
(2)情報量的安全性:多項式領域で解読できない
(3)情報理論的安全:領域量、時間にかかわらず解読できない

ゼロ知識対話証明には「はっきり」安全性の段階があった・・・ような気が
(1)計算量的ゼロ知識:確率TMが多項式時間で解読できない
(2)情報量的ゼロ知識:いっさいの情報が漏洩しない

引越しのドサクサで昔の教科書が出てこない(;_;)


306 :300:03/05/25 14:29
すいません、実は私もうろおぼえで
今教科書をあさっているところですm(__)m

307 :132人目の素数さん:03/05/28 19:43
2,3,5,7,11・・・・と素数がありますが、
ある素数Pが、2から数えて奇数番目の素数か偶数番目の素数かどうか判定する方法はありますか?

どの素数も6±1なので、これを使えないかどうかでやってみましたがだめでした・・・・。
どなたか知ってたら教えていただけませんか?
よろしくお願いします。

308 :132人目の素数さん:03/06/06 02:05
あげ

309 :t-akiyama:03/06/09 20:55
携帯ゲーム機"プレイステーションポータブル(PSP)

 このPSPは、新規格UMD(ユニバーサルメディアディスク)というディスクを利用しており、そのサイズは直径6cmととても小さい(CDの半分程度)。 容量は1.8GBとなっている。
画面は4.5インチのTFT液晶で、480px x 272px(16:9)。MPEG4の再生やポリゴンも表示可能。外部端子として、USB2.0とメモリースティックコネクタが用意されているという。

この際、スク・エニもGBAからPSPに乗り換えたらどうでしょう。スク・エニの場合、PSPの方が実力を出しやすいような気がするんですが。
任天堂が携帯ゲーム機で圧倒的なシェアをもってるなら、スク・エニがそれを崩してみるのもおもしろいですし。かつて、PS人気の引き金となったFF7のように。

310 :132人目の素数さん:03/06/09 23:27
宣伝ったらageろ!

311 :132人目の素数さん:03/06/20 15:29
age

312 :132人目の素数さん:03/06/24 02:43
π(x)に関するリーマンの明示公式を用いれば原理的には
条件をかけるが、それは非自明なリーマンゼーター零点を
すべて必要なだけ持ってこなければならないので、もちろん
簡単ではないな。

313 :132人目の素数さん:03/06/24 04:14
逆に判定する方法があったとすると
数論のどんな問題が解けるのかな?

314 :132人目の素数さん:03/06/25 01:02
The PRIMES is in P little FAQ
http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html



315 :132人目の素数さん:03/07/13 22:34
age

316 :132人目の素数さん:03/07/20 23:06
リーマン
        ≡≡
        (‘台‘)
    ( ( ( l⌒ Y⌒l
         |_| :| |_|
        Uレへ|U┓
    ( ( (  | | | ̄]
 .       | | | ̄
        (二)二)

317 :132人目の素数さん:03/07/20 23:13
定期あげ厨がいるな。

318 :132人目の素数さん:03/07/20 23:54
>>317
今ごろ気づくなよ、ヴァカ!

319 :132人目の素数さん:03/07/21 00:02
空気を読めよ

320 :132人目の素数さん:03/07/21 02:29
くうき?(ちがうの?)












ってゆうネタは逝ってよしでつか。(つーか逝ってきます。)

321 :132人目の素数さん:03/07/21 10:42
age

322 :132人目の素数さん:03/08/05 20:37
ほしゅ

323 :132人目の素数さん:03/08/05 20:38
http://www.eonet.ne.jp/~nohohon/osaka-band.htm
http://diary4.cgiboy.com/vote/vote.cgi?i=dave&s=7
http://chat.mimora.com/common/chat.mpl?roomnum=481485

324 :132人目の素数さん:03/08/05 21:29
AKS?

325 :132人目の素数さん:03/08/12 20:12
素数スレ4

326 :132人目の素数さん:03/08/13 09:36
数論,計算量,量子計算,暗号 ハァハァな香具師向け
2003 Workshop on Cryptography an Related Mathematics
Tuesday 9 --- Thursday 11, September 2003
Organized by 21st Century COE Security Program and
Research and Development Initiative, Chuo University

ttp://www.21coe.chuo-u.ac.jp/security/ngcm2003-2/200309.htm

* Anyone can attend this workshop without any registration. *

327 :132人目の素数さん:03/08/13 09:37
まだこのスレ生きてたのかよ、しぶといな(w

328 :山崎 渉:03/08/15 18:26
    (⌒V⌒)
   │ ^ ^ │<これからも僕を応援して下さいね(^^)。
  ⊂|    |つ
   (_)(_)                      山崎パン

329 :132人目の素数さん:03/08/18 03:36
>>326
ナイス情報。特攻ケテーイ

330 :132人目の素数さん:03/08/29 14:04
あげ

331 :132人目の素数さん:03/09/07 08:57
 

332 :132人目の素数さん:03/09/18 11:44
age

333 :132人目の素数さん:03/09/29 23:39
第5回「代数学と計算」研究集会(AC2003)
2003年10月6日(月) -- 10日(金) 東京都立大学 国際交流会館
http://tnt.math.metro-u.ac.jp/ac/2003/program2003.html
なにげに,Coates さん,話すらしい.

334 :132人目の素数さん:03/09/30 00:52
Coates さんってどなた?有名人?

335 :132人目の素数さん:03/09/30 20:49
>>333
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Coates.html
http://www.dpmms.cam.ac.uk/site2000/Staff/coates01.html


336 :132人目の素数さん:03/10/01 08:25
>>334
フェルマーに多大な貢献をした人。
シルバーマンと共著で、数論幾何の本を書いている。

337 :Which不一致 ◆v.V7zKGUME :03/10/16 17:57
素数判定って、小さい数から順に割っていくだけだろ?
そんなもんの早さを競ってどうするんだ?

338 :132人目の素数さん:03/10/16 18:22
>>337
>>1にある論文読め。短いんだから。
読めないんであればお前勉強辞めた方がいいぞ。

339 :Which不一致 ◆v.V7zKGUME :03/10/16 18:31
>>338
論文なんて読めるはずねえだろ!!
まだM2だぞ。

340 :132人目の素数さん:03/10/16 18:48
M2で論文読めない...( ゚д゚) ポカーン

341 :Which不一致 ◆v.V7zKGUME :03/10/16 18:50
>>340
はぁ?普通だろ!
オレの大学はMで基礎知識をつける。
そして面接に合格してDに進学する。
それから論文を読み出して博士論文を書く。
いわゆる修士論文なるものは無い。

342 :Which不一致 ◆v.V7zKGUME :03/10/16 18:51
ちなみにDQN大学じゃねえぞ!
MARCHの中位。

343 :132人目の素数さん:03/10/16 18:53
>>342
俺のうんこやるから、煎じて飲め。
去年B4だったときに読んだから。

344 :132人目の素数さん:03/10/16 18:54
>>342
普通に読めるぞ,学部生でも.

345 :Which不一致 ◆v.V7zKGUME :03/10/16 18:57
挑戦してみる>Primes is in P

346 :Which不一致 ◆v.V7zKGUME :03/10/16 19:00
英語か・・。

347 :Which不一致 ◆v.V7zKGUME :03/10/16 19:00
何が書いてあるか説明しろ!!!!!!!

348 :132人目の素数さん:03/10/16 19:01
本当に院生なのか?

349 :132人目の素数さん:03/10/16 19:02
お前らなんで荒らしにマジレスしてんの?

350 :Which不一致 ◆v.V7zKGUME :03/10/16 19:03
>>348
本当だ。
きちんと面接試験(自分の自己紹介を英語でおこなう、群論)に合格したぞ!!

351 :Which不一致 ◆v.V7zKGUME :03/10/16 19:04
と、話についていけないDQNな>>349が申しております。

352 :132人目の素数さん:03/10/16 19:49
My name is Which Fuicchi.
I want play Gunron for Daigakuin!
OK?

これくらいで合格できる?

353 :132人目の素数さん:03/10/16 19:54
だから相手すんなって・・・。

354 :132人目の素数さん:03/10/16 20:40
代数専攻でWeilしらんのか・・・

355 :Which不一致 ◆v.V7zKGUME :03/10/16 21:07
>>352
英語はもう少し詳しく言えば合格ライン。
群論は数学的なことが聞かれる。ただし日本語で。
オレはシローの定理を述べるように言われた。

>>354
文句あっか?
そんかわり、ヒルベルト・ネタ−・ガロア・ニュートンなどは知っている。
こんだけ知っていれば十分だろ!!

356 :132人目の素数さん:03/10/22 02:15
>>346 日本語による解説はこちらをどうぞ
http://www.h4.dion.ne.jp/~a00/ms_project_jp.html

357 :132人目の素数さん:03/11/07 02:34
11

358 :◆exZOdLT/no :03/11/08 03:03
12

359 :132人目の素数さん:03/11/29 17:46



360 :132人目の素数さん:03/12/02 01:15
昔は大学側が受験生を撰べたが、今や立場が逆転して、
学生側が大学を撰ぶ時代になってきた。

撰択定理が分からなくても、大学側は撰択して貰いたがっているよ。
馬鹿でも入って定員を満たしてくれれば、大事なお客さまだから。
教員の意識もかわってきている。接客業だということを理解しはじめた
んだよ。

361 :132人目の素数さん:03/12/02 23:16
(´-`).。oO(選択定理って何だろう?)

362 :132人目の素数さん:03/12/03 01:20
>>361
http://www.google.co.jp/search?q=cache:6bJcCN_a5ckJ:www.medianetjapan.ne.jp/three/tv_radio/tako/ss/simi-1.htm+%22%E9%81%B8%E6%8A%9E%E5%AE%9A%E7%90%86%22&hl=ja&ie=UTF-8

363 :132人目の素数さん:03/12/12 17:22
ビンビンマッチョデ(゚д゚)オーエーオーエー

364 :132人目の素数さん:03/12/22 04:38
8

365 :132人目の素数さん:04/01/08 21:05
194

366 :132人目の素数さん:04/01/13 17:38


367 :132人目の素数さん:04/01/13 18:37
ほしゅったらageろ!

368 :132人目の素数さん:04/01/29 04:59
282

369 :132人目の素数さん:04/02/01 06:41
96

370 :132人目の素数さん:04/02/14 00:26
最新の岩波の雑誌「数学」に解説が出ているから,それを読め.

371 :132人目の素数さん:04/02/28 20:36
これでRSA暗号の鍵つくるさいにカーマイケル数引かなくて済むようになるぜ。

372 :132人目の素数さん:04/03/02 07:45
桁数の12乗に比例する計算量というものは、ちょっときついぜ。
せめて6乗、出来れば4乗ぐらいに、まからないものですかな。

373 :132人目の素数さん:04/03/02 17:20
GRHを認めれば6乗だよ。4乗は無理ぽ。

374 :132人目の素数さん:04/03/03 10:13
GRHが証明されていない以上。GRHを認めればという前提で素数判定をしても、
意味がない。GRHが誤っている可能性はまだ現時点では0ではないからだ。
それなら、確率的素数判定で、たくさんの(本当は独立ではないといわれて
きたが)試行を繰り返して、誤判定の確率を試行回数に関して指数関数的に
減少できる方法の方が圧倒的に早く判定できる。(但し結論が誤っている
確率はいくらでも小さくなるが0ではない。しかしその確率とGRHの
誤っている確率と、どっちが小さいだろうか?ということになる)

375 :132人目の素数さん:04/03/03 18:37
ノンノン。
アルゴリズムが素数性を正しく判定できるというのはGRHによらず証明されてる。
ただ、そのアルゴリズムがいつ終わるかを評価するとき、GRHを認めれば上界は6乗で
認めなければ7.5乗。ふるい理論を使わずに初歩的な代数で証明できるのは10.5乗。
FFTを使わなければ12乗。
「7.5乗で抑えられるのは保証できるけど、たぶん6乗で終わるんじゃない?」
ということ。

どっちみち、実用上は確率的素数判定だべ。
上界が3乗まで落ちないと実用はむりぽと工学部のえろい人が言ってた。

376 :132人目の素数さん:04/03/04 01:35
ええ-?
もうこんなに短期間の間に多項式アルゴリズムが
6乗、7.5乗、10.5乗、12乗などと、いろんなバリエ-ションが出てきたの?
参考文献を教えてちょうだいな。

それにしても7.5乗でも12乗に比べたら、えらく良いですよ。
アンドレルメリイテストという方法が昔あったけど、あれは何乗(たぶん
多項式ではないのだろうね?)

377 :132人目の素数さん:04/03/04 17:07
H.Cohen, A Course in Computational Algebraic Number Theory
によると,Adleman-Rumely法は
O( (ln N)^{C ln ln ln N} )

378 :132人目の素数さん:04/03/04 17:18
あと,
Qi Cheng, ``Primality Proving via One Round in ECPP and One Iteration in AKS,''
Proc.Crypto'2003, pp.338-348, Vol.2729, LNCS

http://www.cs.ou.edu/~qcheng/

379 :132人目の素数さん:04/03/05 17:02
アルゴリズムがいくつもあるんじゃなくて、計算量の上限を
評価する方法がいくつかあるって事でしょ?アルゴリズム自体も
改良は加えられてるみたいだけど。

380 :132人目の素数さん:04/03/09 01:14
12

381 :132人目の素数さん:04/04/02 09:25
959

382 :132人目の素数さん:04/04/03 17:20
そろそろ、多項式アルゴリズムの指数の下界が発表されないものだろうか?

(行列同士の積の計算量の指数の真の下限すら、
いまだに求まらないという現実もあるけど。)

383 :132人目の素数さん:04/04/03 19:00
シローの定理の説明できると大学院いけるんだ・・・

384 :132人目の素数さん:04/04/25 19:00
796

385 :不登校の厨房:04/04/28 07:43
とりあえず、一の位が
0,2,4,5,6,8
だったら素数じゃないね。


386 :不登校の厨房:04/04/28 07:56
↑二桁以上

387 :132人目の素数さん:04/05/05 23:58
169

388 :132人目の素数さん:04/05/08 01:38
論文のLemma 4.2の証明で q|ο_r(n) が導かれるところがわかりません。お前らどうぞ教えてください

389 :388:04/05/08 06:21
http://www.h4.dion.ne.jp/~a00/proofs.html
というの見つけますた

390 :132人目の素数さん:04/05/11 01:43
>>388
q≧√r*log_2(n),q|ο_r(n)とq≧√r*log_2(n),n^{(r-1)/q}!≡1 (mod r)
が同値であることでいいのかな。

証明
q≧√r*log_2(n),n^{(r-1)/q}!≡1 (mod r)⇒q≧√r*log_2(n),q|ο_r(n)

qがο_r(n)を割り切らないと仮定するとqは素数だからqとο_r(n)は互いに素

フェルマーの小定理よりn^(r-1)≡1 (mod r)
位数の性質よりο_r(n)|r-1=q*{(r-1)/q}
qとο_r(n)は互いに素だから、(r-1)/qはο_r(n)で割り切れる
ο_r(n)h=(r-1)/qと書ける。

ο_r(n)の定義よりn^{ο_r(n)}≡1 (mod r)
よってn^{ο_r(n)*h}≡n^{(r-1)/q}≡1

これは仮定のn^{(r-1)/q}!≡1 (mod r)に反する。

よってqはο_r(n)で割り切れる。



391 :132人目の素数さん:04/05/11 01:50
q≧√r*log_2(n),q|ο_r(n)⇒q≧√r*log_2(n),n^{(r-1)/q}!≡1 (mod r)

証明
n^{(r-1)/q}≡1 (mod r)となると仮定する・
位数の性質よりο_r(n)は(r-1)/qを割り切る。

qはο_r(n)を割り切るので、(r-1)/qはqで割り切れる。
qk=(r-1)/q、
よって
q^2≦q^2*k=r-1<rとなる。

ところがq≧√rlog_2(n)≧√rより
q^2≧rとなる。
これは不合理

r-1はq^2で割り切れることがわかる。

よって、n^{(r-1)/q}≡1 (mod r)となると言う仮定は誤りで
q≧√r*log_2(n),n^{(r-1)/q}!≡1 (mod r)が成り立つことがわかる。

392 :132人目の素数さん:04/05/11 05:24
結局RSAを短時間で解読できるようになるには
量子コンピュータの実用化を待ってグローバーのアルゴリズム
を適用するしかないの?

393 :132人目の素数さん:04/05/11 17:25
>>390
>よってqはο_r(n)で割り切れる。

よってο_r(n)はqで割り切れる。
の誤り




394 :132人目の素数さん:04/05/28 23:05
516

395 :132人目の素数さん:04/05/29 04:10
>>392
それを言うならShorのアルゴリズムだろ.
まだRSAの解読が決定的に(あるいは確率的に高い正解率で)多項式時間で出来ないということは
証明されてないから量子コンピュータ抜きでもRSAを破る可能性がないこともない.限りなく低いだろうけども.

396 :395:04/05/29 04:14
つーか一部のRSAって破れたんじゃなかったっけ.PKCS#1とか.

D. Bleichenbacher, "Chosen Ciphertext Attacks against Protocols Based on RSA Encryption Standard PKCS #1" in Advances in Cryptology -- CRYPTO'98, LNCS vol. 1462, pages: 1--12, 1998.

確かこれかな.

397 :prime twins:04/05/29 22:58
http://arXiv.org/abs/math.NT/0405509

There Are Infinitely Many Prime Twins

Authors: R. F. Arenstorf
Comments: 38 pages
Subj-class: Number Theory
MSC-class: 11A41; 11N05

A proof of the twin-prime conjecture is presented using methods from classical analytic number theory.



398 :一応:04/06/05 18:27
(1)大きな数を素因数分解する

(2)RSA関数の一方向性を破る

(3)RSA関数を用いたある種の暗号方式を破る
はそれぞれ微妙に違う話だぞい。
(1)と(2)が完全に同値かどうかはまだ知られてない。

399 :132人目の素数さん:04/06/12 01:05
761

400 :132人目の素数さん:04/06/12 02:35
>>398
暗号の専門家に聞いたところ,(1)と(2)の難しさは同値ではないという予想らしい.
もちろんギャップがあることを直接証明するのは相当難しいことなんだろうけども.

401 :132人目の素数さん:04/06/15 18:30
>400
これとかかな?

"Breaking RSA may not be equivalent to factoring," D. Boneh, R. Venkatesan,
In Proceedings of Eurocrypt '98, Lecture Note in Computer Science, Vol. 1233, pp. 59-71, 1998.
ttp://crypto.stanford.edu/~dabo/abstracts/no_rsa_red.html

402 :400:04/06/17 22:44
>>401
RSAと素因数分解のギャップは経験的なところでの議論と思っていたら,
実は理論的な結果が知られてたんですね.面白い結果ですね.知りませんでした.

403 :132人目の素数さん:04/06/27 09:28
693

404 :132人目の素数さん:04/07/06 16:02
243

405 :132人目の素数さん:04/07/08 03:54
関連スレ
暗号数学について語ろう
http://science3.2ch.net/test/read.cgi/math/1088146349/l50

406 :132人目の素数さん:04/07/27 11:59
332

407 :132人目の素数さん:04/08/06 13:43
908

408 :132人目の素数さん:04/08/08 22:24
二年。


409 :132人目の素数さん:04/08/15 06:23
255

410 :132人目の素数さん:04/08/22 06:03
582

411 :132人目の素数さん:04/08/22 21:02
586

412 :132人目の素数さん:04/08/30 08:53
713

413 :132人目の素数さん:04/09/06 00:05
877

414 :132人目の素数さん:04/09/10 21:46:29
861

415 :132人目の素数さん:04/09/16 15:01:22
879

416 :132人目の素数さん:04/09/16 18:19:58
まったく読んでないんだがRSA駄目ぽ、と理解してよろしいか?

417 :132人目の素数さん:04/09/19 01:58:10
>>416
素因数分解がPTIMEだと示されたわけじゃないよ。


418 :132人目の素数さん:04/09/24 11:16:07
892

419 :132人目の素数さん:04/09/27 00:38:56
因数分解をせずにRSAを攻撃して解読する手法が発見されれば、
副産物として、因数分解の効率的な方法のヒントが得られるような気もする。

420 :132人目の素数さん:04/09/27 00:48:07
>>416
素因数分解とは関係ないだろ

421 :132人目の素数さん:04/10/01 18:26:42
>>419
GQ1だかGQ2だかのプロトコルでも同じような話があるみたい

422 :132人目の素数さん:04/10/06 09:31:42
685

423 :132人目の素数さん:04/10/11 16:44:42
213

424 :あぼーん:あぼーん
あぼーん

425 :LettersOfLiberty ◆rCz1Zr6hLw :04/10/11 22:25:44
Re:>424 お前何考えてんだよ?

426 :132人目の素数さん:04/10/17 02:43:51
397

427 :132人目の素数さん:04/10/22 17:09:16
442

428 :132人目の素数さん:04/10/27 07:28:34
232

429 :132人目の素数さん:04/11/02 00:08:03
566

430 :あぼーん:あぼーん
あぼーん

431 :132人目の素数さん:04/11/08 10:28:08
564

432 :132人目の素数さん:04/11/14 20:11:40
953

433 :132人目の素数さん:04/11/19 11:36:02
425

434 :132人目の素数さん:04/11/25 14:37:29
368

435 :132人目の素数さん:04/11/26 01:36:14
計算量クラスがまだわかっていない有名(無名でも可)な問題って何がある?

436 :132人目の素数さん:04/11/27 12:34:43
かつて質問スレッドで”総音程問題(all-interval)”の解法を問うたが、結局解らなかった。
問題集のページ探せば出てる有名?解決済み問題なんだけど何やら難しいとこばかりで、、
総音程問題:
重複/欠損の無いn個{0,1,2...n}の要素を、その間隔(interval)に於いても重複/欠損無く全てのinterval{1〜n-1}で並べる、全ての可能性の算出。
同じintarval列をもつものは一つとみなす。

一つだけ見つける単純な方法と、原始根を使ったヤツは思いついたがそれでは
4000弱ある可能性の中のほんの5個に過ぎない。。
数列の素を求めるということで素数関係に強い人たちのスレで尋ねてみました。


437 :132人目の素数さん:04/11/27 12:38:17
>>436
意味不明。
分かるように書いてくれ。

438 :132人目の素数さん:04/11/27 13:07:05
もとい訂正します(0はややこしいので1〜nとします)

n=12の場合:
{1,3,12,11,9,4,8,2,5,10,6,7}
↑の各数字間の差(modulo-12で)
{2,9,11,10,7,4,6,3,5,8,1}
となるような数列の算出です。

439 :132人目の素数さん:04/11/27 15:11:15
所謂差集合ですか? だとしたら、
http://science3.2ch.net/test/read.cgi/math/1078820583/225
で紹介された本にあります。

440 :伊丹公理:04/11/27 15:59:48
差集合も知らんのか
この馬鹿や労

441 :132人目の素数さん:04/11/28 00:35:23
差集合は関係ないと思うが・・それほど単純な問題では無いと思うが

442 :132人目の素数さん:04/12/02 03:57:25
all-intはベンチマークに使われる類らしい。

443 :132人目の素数さん:04/12/09 06:54:54
602

444 :132人目の素数さん:04/12/16 16:42:01
117

445 :132人目の素数さん:04/12/23 09:51:00
525

446 :132人目の素数さん:04/12/27 18:04:48
633

447 :132人目の素数さん:04/12/30 19:11:43
802

448 :132人目の素数さん:05/02/02 18:07:50
日本語解説サイトの人がWikipediaにも書いてくれてたのね

AKS素数判定法
http://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

449 :132人目の素数さん:05/02/16 13:16:00
722

450 :132人目の素数さん:05/02/25 11:49:03
990

451 :132人目の素数さん:05/03/07 12:43:20
886

452 :132人目の素数さん:05/03/17 17:54:15
615

453 :132人目の素数さん:2005/03/29(火) 14:33:47
951

454 :132人目の素数さん:2005/04/13(水) 19:51:01
746

455 :132人目の素数さん:2005/04/24(日) 12:07:04
数体ふるい法ってよくわからないです。
解りやすく教えてください。

456 :132人目の素数さん:2005/04/30(土) 06:27:04
>>447
スレ違いだから↓で聞いたほうがよさそう

素因数分解、素イデアル分解、一意分解整域。
http://science3.2ch.net/test/read.cgi/math/1082199793/

457 :132人目の素数さん:2005/05/03(火) 02:00:02
age

458 :132人目の素数さん:2005/05/19(木) 15:00:13
549

459 :132人目の素数さん:2005/05/25(水) 23:29:37
>>438
これは本当に4000個くらいしか解がないの?

460 :132人目の素数さん:2005/06/22(水) 04:54:33
128

461 :132人目の素数さん:2005/07/24(日) 02:15:16
536

462 :132人目の素数さん:2005/07/28(木) 23:36:08
test

463 :132人目の素数さん:2005/07/29(金) 15:23:01
age

464 :132人目の素数さん:2005/08/08(月) 22:26:30
三年二分。


465 :132人目の素数さん:2005/08/10(水) 23:07:49
age

466 :132人目の素数さん:2005/08/15(月) 21:25:00
まだ生きてたのかここw

467 :132人目の素数さん:2005/08/20(土) 21:51:13
素因数分解なんて簡単でよ。



468 :132人目の素数さん:2005/10/03(月) 02:10:51
7

469 :132人目の素数さん:2005/10/03(月) 15:46:53
age

470 :132人目の素数さん:2005/11/04(金) 02:17:34
結局どうなの?

471 :132人目の素数さん:2005/11/16(水) 23:24:20
>>470
何が。

472 :132人目の素数さん:2005/11/18(金) 05:35:20
age

473 :132人目の素数さん:2005/12/12(月) 18:44:30
506

474 :132人目の素数さん:2006/01/02(月) 01:56:50
738

475 :132人目の素数さん:2006/01/29(日) 20:32:47
sage

476 :132人目の素数さん:2006/01/31(火) 15:49:35
ラッセルの(2^(2^n)+1)でおk


477 :132人目の素数さん:2006/02/05(日) 08:30:34
705

478 :132人目の素数さん:2006/03/02(木) 17:20:54
283

479 :132人目の素数さん:2006/03/26(日) 13:39:43


480 :132人目の素数さん:2006/03/32(土) 01:46:24
いくら Cn^a でも C =2^(2^10000000000000) だったらなぁ

481 :132人目の素数さん:2006/04/15(土) 21:26:40


482 :132人目の素数さん:2006/04/27(木) 08:18:54
●素数判別法発見●暗号無効、世界パニック●
現代の暗号の基礎となっている、ハッシュ関数の逆関数を
現実時間で解を求める方法を、アメリカのD.R.シース博士が
発見。これにより、現在ほとんどすべての暗号が数ヶ月以内に
解読可能になる恐れが出てきた。
この発見をしたD.Rシース博士は、アメリカのCIAによって
既に超法規的に拘束(一説には既に殺害されている)が、
一部の解法を記したメモが既にイスラエルに流出しているという。

現在米軍は不測の事態にそなえ、準戦争体制をとり、
既に偶発核戦争防止のための協議に入っているという。
博士の殺害について各国から非難の声が上がっているが、
政府は、「世界平和上、真にやむをえない、極めて特殊な超法規的措置である」
という声明を出している。
流出したメモは解法の一部だけしかなかったが、これを
スタンフォード大学の数理学者が米軍の厳重な監視下で分析作業
をしたところ、現時点では学者としての直感的ではあるが、
博士は真に解法を発見しただろうと予想しているという。
博士は既に殺害されているが、周辺メモなどから、実際に
逆関数が導出可能であることが示されれば、世界中の数理学者の
補足研究により、数ヶ月以内に世界中で解法が発見されるだろうと
いうことです。





483 :132人目の素数さん:2006/04/27(木) 16:17:27
タイトルと内容が全然違うじゃねーか
もちっと勉強せい

484 :132人目の素数さん:2006/05/13(土) 21:20:45
317

485 :博士:2006/05/17(水) 01:39:16
318

486 :132人目の素数さん:2006/05/23(火) 13:21:49
実は長大整数の効率的な素因数分解の方法もとっくに発見されているが
発見者達は地下の別荘で隔離監視されながら、これまでどおり研究する
ことだけを許されているらしい。外部との交信は常に検閲され、他人と
の面会も出来ないそうだ。

487 :132人目の素数さん:2006/06/15(木) 23:56:42
157

488 :132人目の素数さん:2006/07/28(金) 15:26:27
724

489 :素数番目の素数:2006/08/01(火) 19:13:45
素数判定をしたい19728桁の自然数があるのだが、フリーソフトを利用して
判定することは可能だろうか?

490 :素数番目の素数:2006/08/02(水) 11:38:34
訂正:19728桁→19729桁

491 :素数番目の素数:2006/08/02(水) 17:36:47
自己解決。
素数ではなかった・・・。

492 :132人目の素数さん:2006/08/02(水) 19:04:07
というか2の倍数でした・・・。

493 :132人目の素数さん:2006/08/02(水) 21:53:18
やっぱりRSAはガセだったのか・・・みんなエシュロンに読まれっぱなし

494 :132人目の素数さん:2006/08/02(水) 22:50:07
>>492
warota
とでも言ってほしいのかばかやろう


495 :132人目の素数さん:2006/08/02(水) 22:58:22
素数の一般式の発見者はもう埋葬されてしまっている・・・

496 :132人目の素数さん:2006/08/02(水) 23:07:58
そうなの?あれは誰だったっけ?

497 :132人目の素数さん:2006/08/03(木) 00:22:27
WillansかMinác.Sierpinskiは反則気味だし。

498 :132人目の素数さん:2006/08/03(木) 23:54:12
素数多項式は誰だっけ?

499 :132人目の素数さん:2006/08/09(水) 03:24:30
四年五時間。


500 :132人目の素数さん:2006/08/30(水) 16:44:40
269

501 :132人目の素数さん:2006/09/05(火) 08:57:52
このアルゴリズムは例えば1万桁だとどのぐらいかかるの?

502 :132人目の素数さん:2006/09/21(木) 09:47:19
保守

503 :132人目の素数さん:2006/10/03(火) 01:20:35
544

504 :132人目の素数さん:2006/11/13(月) 00:07:07
421

505 :132人目の素数さん:2006/12/27(水) 10:30:49
976

506 :132人目の素数さん:2007/02/05(月) 15:46:04
224

507 :132人目の素数さん:2007/02/07(水) 19:06:20
なぁ、素数っていうのは具体的に、何にどのようにどのくらい使われているんだ?
なんか暗号で使われているそうだけど、その桁数ってどのくらいあるんだ?
プログラム初心者で、課題から
素数を導き出すプログラムつくって、
ついでに判定プログラムもつくってみたけど、
どういう効能があるんだろうと疑問に思った。

90 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)