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

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

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

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

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

ふ〜ん

それほど時間かからないってこった。

因数分解もそうなってくれたらいいのにね。

なんでこのスレは4つしかレスがないの？
これ、すごいことではないですか？
（数学専門ではないのですが、（コンピュータ専門）
すごい騒ぎになってるのでは？と思ってはじめて
この板に来たのですが）

だって意味和漢ねーン唾問、俺馬鹿だから。

いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね？（つい最近習った）

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

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

うちのパソコンじゃ見れません｡･ﾟ･(ﾉД`)･ﾟ･｡

っていうかアメリカはいま大騒ぎです。(Stanfordより)

英語が読めません
ばばーい(･∀･)

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

ごめん。いまNYTimesか、Washington postの最新記事を
探してるんだけど、どうしても出てこない・・。

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

ありました。NYTimes, 8日付です。
http://www.nytimes.com/2002/08/08/science/08MATH.html

スレタイ見た瞬間「渋い所をついたネタスレだなぁ」と思ってしまった。
マジなのかよ。

マジです。

っていうか「渋いところ」っていうより、かなり根幹でしょ。

>>16
正直、人による。

-------風俗の総合商社・ＭＴＴどこでも-------

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

>>16
いや、明から様に冗談って感じじゃなくて、計算量理論とか知らないと
「ﾌｰﾝ」ですまされそうな所を突いたネタスレだなぁと思ったんよ。

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

http://dempa.2ch.net/misc/R3_temp.swf?inputStr=SEX%82%B5%82%BD%82%A2

2からn-1までで順次割ってみればいいんだから、多項式オーダって
あたりまえじゃん、とか思ったが、入力の「桁数」をサイズとして
多項式オーダということだったのですね

いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね？（つい最近習った）
っていうかアメリカはいま大騒ぎです。(Stanfordより)

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

>>22
スレの内容が理解できないからって八つ当たりするなよ。

>>21
順次割っていくにしても√n 以下の数で割れば十分なわけだが。

>>1のリンク先にあるその論文に雑誌名がないのが気になるが…。

まさか｢論理的｣多項式時間じゃないだろうね？（ｗ

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

説明求む

論文のURL(英語: 数学者の写真あり): http://www.cse.iitk.ac.in/news/primality.html
ココにpdfファイルとpsファイルがあるから、取りあえず嫁！

なんでこんなに静かなんだ・・・

>>28
このスレの住人が数学オンチだらけだからじゃねーの。
そうじゃなかったら祭りがはじまるはずだよ。

素因数分解が短時間でできるようになるわけじゃないのか・・・

相互リンク　プログラム板

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

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

試してみたいんだけど
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 の意味が判りません

誰か教えて

1は「もし nが a^b の形で表現可能なら　素数ではない」　という事だと思うんだけど

大発見には違いないんだが、「これでRSA崩壊だ！」って
騒いでる奴は一体何なんだ？

>>29
論文を読んでるからだと思いたい。

>>33
ｎは変数。
nが素数かどうかってことでしょ？

これMATLABだろ？誰かコンパイルしてくれ

このスレがネタスレかどうかの判定法を教えてくださいです。。。

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

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

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

このアルゴリズムが素因数分解に応用できるか
（または与える影響を）検証した人居る？

>>42
そんな事が簡単に検証できるならとっくにRSA破ってます。

ランダウ記号でO((log n)^12)と書いているのだが＞ http://www.cse.iitk.ac.in/news/primality.pdf

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

>>44
n の桁数はO(log n)。多項式時間で解けるつーのは、入力の桁数を
変数とする多項式で実行時間が抑えられるという事。

>>45
どうもありがとうございました。

みんな論文読んでるの？　それとも放置？

>>47
論文読んでとりあえずコード化してみんなでワイワイやってます。
これは面白い…

>>47
専門外だけど、取りあえず読んでます。

>>47
読んでいます。
多くの数学科関係者がチェックしているはず。

いままでも確率的な方法で素数判定ができたんだから
そんなに意味ないとおもうんだけど、なにに使えるの？
素因数分解もできる？

＞いままでも確率的な方法で素数判定ができたんだから
＞そんなに意味ないとおもうんだけど、なにに使えるの？

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

>>51
応用に関しては、この板よりも他板のほうが詳しいんじゃないかな？

関連スレ

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

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

補完よろ。

ニュー速はかなり もりあがってるね

８頁目真ん中の「予想」が気になります。

素因数分解より素数判定の方が簡単っていうのが信じられない。
馬鹿が理解できるよう、サイモンのように教えて下さい。

RSAは死んだか？本格的に楕円の時代到来かな

ﾎﾟｶｰﾝ（ﾟДﾟ;;

あ、あのさ、これさ・・・・
((( ((（ﾟДﾟ;;)))))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ

>>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は素数ではない。

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

RSAは素因数分解できないと解読できないっしょ？

質問。

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

>>62
多項式時間で判定できない数があるとすれば、
素数判定が決定的多項式時間で可能であるとは
言えません。

下記のスレで議論が活発にされていますので、こちらに移動
しましょう。

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

>>61
素因数分解をしなくてRSAを解読する方法があるかどうか
はまだ分かっていません。

プログラム板
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個だけですむ。

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

>>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
にも説明してあるよ。

>>66
ニュー速+はこれでいいのでは。
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/858

桁数nの素数判定をO(n^12)で解くのだな

このアイディアって、他に応用可能な部分はあるの？

むちゃくちゃでかい数を多項式時間で素数か判定できるようになった
↓
俺がランダムなむちゃくちゃでかい数をつくって多項式時間で素数か判定する
↓
「あなたの数は素数です」
↓
記録更新
↓
馬

ＲＳＡてなに？

日本中央競馬会

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

スパコンでもうメルセンヌ素数を計算させてるやつもいるんだろうなぁ。

n is of the form a^b
ってどうすりゃい〜のさ。これだけで指数時間使ってしまう
教えてくれ〜〜

ＲＳＡ亡き後はＥＣＣが台頭か？

>>76
bを2からlog nまで動かして
nのb乗根を計算して整数になるか判定すれば
O(log^3 n)でできるのでは

亡くなってないっつの。

log nを整数精度で浮動小数点を使わないで求める方法キボンヌ

>>80
俺なら、範囲を絞った上で、マクローリン展開、かな。

あきらめた

>>80
２で割っていく。

完全数たくさん求めてくれ。

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



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

>>80
上位ビットから順に1を探す。

>>86
シフトして上位ビットをキャリーフラグに入れて条件分岐を繰り返す。
シフト回数からlog_2 nがわかる。

>>87
右シフトして(つまり２で割って)ゼロフラグがたつまで繰り返す。

すんません。
学のないドシロウトなんですが、
これで一番でっかい素数とかみつかるんですか？

>>89
ﾊﾞｯﾁﾘ見つかります！(o^-')b　

一番でっかい素数って･･････。

一番でっかい整数が見つけられれば、一番でっかい素数も見つかります。

プログラム板でコード化が進んでいるようです。
http://pc3.2ch.net/test/read.cgi/tech/1028877628/182

やっぱり軍とかじゃあ公然の秘密だったのかな。

ひょっとして2^65536-1が素数かどうかわかるんじゃないか？
たしかまだわかってなかったきがする

ああ、違った。
2^n+1
n=2^t
でtが5のとき2^n+1は素数になるが、t>5のとき素数になる場合があるかはわからない
そうです。

今まで、ネタスレだと思ってたよ（ｗ
すげーな。さすがインド人！年齢関係なんてなくフィールズ賞やって良いん
じゃないの？
暗号全部再構築か…。ネスケもＩＥも今後しばらくの間、怖くてネット通販
使えないかもね。

＞暗号全部再構築か…。

小一時間問い詰めるぞ。

なんだか、論文読んでも意外とあっさりしたもんだね。
これで証明できちゃうなんて、拍子抜けしちゃうよ。ハッハ〜。

証明のとこ、わかった？
あのアルゴリズムが有限回で終わるとこと、
素数なら素数と判定される、合成数なら合成数と判定されるというのは
いいんだけど、その後がわからん。

>>99
証明の間違いを見つければ神になるチャンス!!!

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

そこらへんのライターなんて、そんなもん。
サイエンスやコンピュータ関係の専門的な内容は、誤解釈ばっかし。

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

>>102 ニュー速にスレ立てて馬鹿にしてもｲｲ!!と思うの

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

>>102
掛け合わせて1足してるとか、そんなところだろ。

>>106
素数と素数を掛け合わせた数は奇数であり、1足すと偶数になるがなにか？

>>107
じゃあ、2を足してるとか。
掛け合わせてる以外の計算もあるならあの記事でも良いだろ。

>>108
ｱﾌｫか？
素数を求める関数が未だに発見されてないから「素数定理」が長く未解決なんだろ？
お前意味わかってますか？

>>106 >>108はどうせニュー速板から来たんだろ。

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

■アスキー２４が２ちゃんねるを「総会屋と同じ仕組みの掲示板サイト」と記述

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


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

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

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

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

>RSA uses two huge prime numbers and multiplies them
>together to produce an even bigger prime.

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

第十問題と言って混乱させてみるテスト

>>107
２は偶数。

>>112

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

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

>>115
2が巨大な素数なのか。君の頭の中では。

１、２、３、たくさん(ﾌﾟ

>>118
いや、３まで数えられたら２が巨大な数だとは思わないだろ（ｗ
>>115の頭の中は「１、・・・えーっと、たくさん！」くらいだと思われ。

logの底は何に？

>>120
>1の論文の中では底は2だが、
そのことを聞いてるの？

>>121
それそれ

これって、そこら中の暗号化されたデータが簡単に解読されるようになるってこと？

>123
違う。

プログラマ板みたいに、「暗号崩壊」とか書いてるわけじゃないのに、
なんでこんなにRSAが崩壊すると勘違いする奴が次から次へと
湧いて出てくるんだ・・・。

これって何屋さんの領域なの（数学で）
数論？

↑は、スレタイに暗号崩壊とか書いてないのにって事ね。

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

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

>>126
そだね。数論。

http://ntw.e-one.uec.ac.jp/ntw/number_theorists.html
見つからない罠

>>126, >>128
計算量理論、で今回は問題が数論的だった
ではいかが

>>127 :
>>1 のリンクで M. Agrawal のページに飛ぶと、
回路計算量とかで錚々たる仕事してるみたい
そっちのコミュニティーのページには載ってるかも

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

>>132
しねーよ。

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

>>134
未だに読んでないような奴が何を偉そうに言ってるわけ？
興味のある奴はとっくに読み終えてるんだけど。

むしろ、ＲＳＡ暗号がより使いやすくなるって事でファイナルアンサー？
巨大素数が確実に入手できるようになるわけだし。

Oはオーダーだけど、
Oの上に~が付いてるのはどういう意味なの？

>>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.

>>138
ありがとうございました。
見落としてた…。勝手記法だったのね。

>>109 素数定理って、ふつうは、

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

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

http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html

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

>>141
原理上多項式時間で素数判定ができるかどうかに興味があるんだよ。数論の人は。

>>141-142
話が噛み合ってなくないか,君たち?

数学板住人だったら「暗号崩壊！？」って誤解よりも
「P≠NP問題解決！？」って誤解をしそうな気がする。

気のせい？

けどさ、いくら桁数の多項式時間って言っても
パソコンでやった時に一桁10年かかるようなのだったら
実生活に役立たないよな。

たとえ145のような場合でも量子コンピュータのような奴が実用化されなくて、
さらにコンピュータがそれなりに進歩すれば実生活に役立つ。

>>145
むしろ、これから「役に立つか」「立たないか」を検証するんじゃないの？

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

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

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-
夜勤は夜金＝ウマ＝上場反対＝２ｃｈは金のなる木
http://jbbs.shitaraba.com/computer/2095/のニュースに多数の大手広告

>148

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

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

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

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

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

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

>>151
手近にある本を調べてもわからなかったので，すみません教えてください．
グラフ同型問題はNP困難かどうかわかってないんですよね？
それでもグラフ同型問題がin PだったらP=NPになっちゃうんですか？
逆にいうと，P=NPになったり多項式階層がつぶれるということは，
グラフ同型問題についてなんらかの意味での困難性が知られてるんでしょうか？

>152

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

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

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

さてグラフ理論と（主にPvsNPについての）計算量理論を
バランスよく学ぶための教科書ですが，次の２つをお勧めします．

続きです．

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

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

続き２です．

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

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

４）計算と複雑さ，岩波
うら覚えですが，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

>153
書きこんでいる間に新しいメッセージがあったようですね．
なんだか前の書きこみと違ってずいぶんご存知のようですが．


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

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

153です．どうもありがとうございます．
Garey&Johnson，研究室内で探したんですが見つかりませんでした．
きっとあるはずなので，後日じっくり探して読んでみたいと思います．

１００桁とか２００桁、あるいは５００桁程度の整数を素数かどうか
判定するプログラムのソースコードがどこかに落ちていませんか？

ZDNNの記事
http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html

>>160
テンション的に健全な記事。

>>159
UBASICは２７００桁まで扱えるそうだ。
http://www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm
どっかに素数判定のプログラムもあるだろう

　　　 ／￣￣￣￣￣￣￣￣
　　　 | 作るのは
　　　 ＼
　　　　￣∨￣￣￣￣￣￣
　　　　 ∧＿∧
　　　　（ ´Д｀）
　　　／⌒　　⌒ヽ
　　／_／|　　 へ ＼
　　（ぃ９ ./　　/　＼ ＼.∧＿∧ ／￣￣￣￣￣￣￣
　　　 /　 ./ 　　　　　ヽ （ ´Д｀ ）＜ 君だ！！
　　　（　　/　　　　　　　∪ ,　/　 ＼＿＿＿＿＿＿＿
　　　＼ .＼＼　　　　 (ぃ９　|
　　　 .＼ .＼＼　　　 /　 /　,、
　　　　　　　 > ） ）　./　 ∧_二∃
　　　　/ ／／　　./　　￣￣ ヽ
　　　 / / /　.＿/ /~￣￣/ ／
　　　/ / / )⌒ ＿ ノ　 / ./
　　　（ ヽ ヽ | /　　　（ ヽ、
　　　 ＼__つ).し　　　　＼__つ

>159
javaで書けば？

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

100以上のスレってすげーな。

age

神帝大天才山口人生超教授のおっしゃるところによればP=NPです。
だから素数判定がPなんか自明です。

ｲﾝﾄﾞ人もﾋﾞｯｸﾘ

>>151
グラフ同型問題が NP完全ならば階層が2段目まで潰れる、
という話なら知ってるけど、P に入っていても潰れると言う話は
あったっけ?

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

>170

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

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

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

>>171
このネタで続けるのもあれだけど、
ttp://eccc.uni-trier.de/eccc/ の TR02-037 見るよろし。
定義はそっからたどりましょう。
FOCS2002 のプログラムももう見られるね。

なるほどポキン、新機軸

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

具体的に素因数分解するのと、素因数の数だけ求めるのには
本質的な時間の違い現れますか？

「時間が本質的に違わない」の意味を、
素因数計数問題が易しければ、素因数分解問題も易しい
とするのであれば、本質的に違いはある、と思うに一票

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

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

>>178
逆だと考えたんだけど。素因数計数問題を解くためには
素因数分解する以外に効率的な手段はないのかなって思った。

>>179
例えば試し割りしていく場合、途中で素因数の最大個数は確定すしそうな気がする。

桁数の１２乗で、ある予想が成り立てば６乗だというのだけど、
どこまで下げられるのかな。３乗とか４乗ぐらいだとずいぶん
やさしい問題になるんだけど、６乗でも相当、１２乗ならむちゃくちゃ
計算量が必要で、これはつらいね。

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


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


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

>>182
マジレスすると、ニュー速＋に人が流れてたから。

マジレスすると、１が、一人で騒いでただけだから

>>184
確かに、このスレを盛り上げようとしてたのは>>1を含めても少数だな。
いっそマ板のように「暗号崩壊！？」というデタラメでセンセーショナルな
スレタイにすれば無駄に盛り上がったんだろうな。

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

そうだね

数学板で「盛り上がる」という行為をするネタは大抵電波出現だった気がするんだが。

さあ、もうFortranかCで判定プログラムをかけましたか？課題提出の期限は
せまっていますよ。

>>1
Ｐ＝ＮＰより確定的多項式時間アルゴリズムは存在します。
　　
　　　参考文献(近刊予定)：御神本　山口人生著

12乗がデカイと感じるのはしかたない。
しかしコンピュータの処理速度がいまの10^43倍くらいだったらどうだろう？
指数オーダーに対する12乗オーダーはものすごい脅威になっていたはず。

>>191
え？12乗って聞いてまず感じたのは「ちっちゃい」だったんだけど。
冷静に考えてみて初めて実用に向かない程度に大きい事を理解した。

人生ちゃんって日本数学会にも顔だしてんの？

>190
計算量の授業後に「だれも相手にしてない」と
先生が言っておりました。

P=NPあるいはその否定が証明できたら、まちがいなくチューリング賞もの
だし、ある程度若ければフィールズ賞ももらえることはほぼ確実だろう。
ノーベル賞は出ないのも間違いない。

ノーベルコンピュータ科学賞もあるべきだ。

nobelの時代にコンピュータなんてない

http://science.2ch.net/test/read.cgi/sky/1029291426/227

http://yahooo.s2.x-beat.com/

>>198
ここで止まった。
http://tv2.2ch.net/test/read.cgi/eva/1024726406/190

>>196
Turing Prizeもらえばいいじゃん。それともタナカさんみたいに
「今日も同じ服」なんていわれたいの？

次の大きなニュースもこのスレで出来るかな？

２＾２００３−１＝４００７×６５８８６２２７１４９４６６０９×．．．。

（＾＾）

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

（･∀･）ｹﾞﾊﾊﾊﾊ

誰かPとNPが真に違うということを証明しようとしている人はいないのか？

げーつがMS-BASICを作ったと思ってるんですか？

P=NPだとすればP(1-N)=0だからP=0またはN=1でなければならない。
すると、一般のPもしくはNについてP＝NPは成り立たない。

( ﾟДﾟ)＜ﾅﾅ､ﾅﾝﾄ

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

＞公開鍵暗号は使えなくなる。

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

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

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

＞２１７

　　　　
　　　偽　者　は　消　え　て　く　だ　さ　い　。

Manindraさんの講演聴いてきた人いませんかー？

２進でb桁の自然数を素因数分解（簡単の為に素因子が２個としてよい）
するために必要な計算量の現在知られている下限は、どのぐらい？

下限が strict に押さえられるならみんな苦労していないとおもうが?

既出かもしれんがこんなのがあった
http://www.cybernet.co.jp/maple/hiroba/aks/ask.html
Mapleでの実装。Octaveでも動くかな？

OctaveはMatlabモドキだった。フリーのMapleモドキってないのかな。

mupad

http://www.tcs.hut.fi/~helger/crypto/link/primality_tests/aks.html

みれば

C++
Pari/GP
Magma

の実装もあるよ。

思い出したが以前RIMSで木田先生だったかが公演でこのアルゴリズムの解説やってたな。
現状ではnon-polynomialのAPRのほうが速いそうだ。

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

>>221
それじゃあ、現在分かっている上界のうち最良のものは？

>>Quserman ◆KeLXNma5KE
本当に馬鹿だな。
なんで公開鍵が使えなくなるの？
暗号の本でも読め。

>>227
bの準指数時間

【超高速計算機】量子コンピューターを開発　NECと理化学研
http://news2.2ch.net/test/read.cgi/newsplus/1045706530/l50

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

準指数ということは、指数関数よりは増加が少ないということだね？
多項式よりも多いということなんかな？

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

☆やっと見つけた宝物☆
http://bbs.1oku.com/bbs/bbs.phtml?id=rantyan

>>231

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

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

233さんの一応補足しとくと
nが分解したい整数のビット長でbは[0,1]に値をとるパラメタね。

＞nが分解したい整数のビット長

ダウト

訂正ありがとうございます（恥）>235
記号bの使われ方のほうに気をとられてました〜

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

準指数だよ。

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

>>237
え？

＞n^(pq-1)はpqを法として、何と合同になるか？

どうなるの？

最近のレス意味不明。
素因数分解なんて２、３、５、・・で割っていくだけでいい。
これも立派なアルゴリズム。
これくらい気付けよ・・・。
パソコンだったらあっという間に出来ます。


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

釣り人は早起きですね。

電波は241一人だけでよろし。

>>239
ごめん、オレの勘違いです。

山口ジンセーたんのスレって、どこが間違っているのか、実は何にも分かって
いない香具師が、結構多く騒いでいるような気がするのは俺だけ？

彼らトンデモ達が一番間違っているのが「進むべき道」である事を
理解しているのなら別にいいんじゃないかと。

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

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

>>225
Magma で10進9桁の素数を投げて実験してみました。

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

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

>>248
１２乗オーダーのアルゴリズムなので、１０進７桁の数の２０倍かかる。

＞＞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を探してみてください。

>>251
それって無限個あるんだよね。

（＾＾）

数学板の名無しさんだ…
せっかくだからなんかネタでも書いていけばいいのに。

？

Manindraさんが講演したときのスライド資料が
どっかに落ちてたよ。

最近の研究

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.
（以下略

これってどうよ？

>>259
お、何か楽しそう。今から読んでみる。

もうちょっと勉強してせめて４乗ぐらいにまかりませんか？

（＾＾）

>>261
ﾋﾞﾀ1乗も負けらんねえ！！！

http://endou.kir.jp/betu/linkvp2/linkvp.html

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

定期age

ほっしゅ

定期age

楕円暗号って何？
解読不可能っていうのはホントなの？

>>269

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

解読不可能てことはない

もっと数学勉強しな

>>269

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

>>271

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

>>271

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

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

（　ﾟдﾟ）ﾎﾟｶｰﾝ

無教養な>>274を沙羅氏安芸。

今まで、ネタスレだと思ってたよ（ｗ
すげーな。さすがインド人！

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

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

素数判定と（素）因数分解とでは、また大きな隔たりがあるわけで…

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

（　ﾟдﾟ）ﾎﾟｶｰﾝ

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

（　ﾟдﾟ）ﾎﾟｶｰﾝ

２７０のキチガイ猿
楕円曲線法による、素因数分解と、
楕円暗号を混同している。
猿の証拠
ここはキチガイの集まりか

>>280
＞ここはキチガイの集まりか

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

>>280

猿はオマエじゃ

>>282
正しい方に絡むとは・・・
本当にアホだな。

age

再現性が皆無な暗号は解読不能だな

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

一つの平文に対応する暗号文が複数個存在して、暗号化の際に
それらのうちの一つをランダムに選んで返す暗号方式は
「再現性あり」なんですか？

再現性の定義は？

一ヶ月ほど前に新聞で取り上げられていた、
「素因数分解は多項式時間で可能！？」の真偽はどうなったのですか？

>>290

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

＞一ヶ月ほど前に新聞で取り上げられていた

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

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

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

まあ、究極の「楕円曲線暗号」があるから問題ないんだけど。

＞「素因数分解は確率的多項式時間で出来る」が今回の結果。

何乗オーダーですか？

６２乗だったと思う。

>>293
究極？どこが？

　　　　　　　 　‖　　　　　　　　
　　　　　　　　('A`)　←>>296
　　　　　　　　（　）　　　　　　　
　　　　　|　　　 | |
　　　　　|
　　　　／￣￣

　　　　　　　 　‖　　　　　　　　
　　　　　　　　('A`)　←数時間後のワイルズ
　　　　　　　　（　）　　　　　　　
　　　　　|　　　 | |
　　　　　|
　　　　／￣￣

age

楕円曲線の種類によっては，未知の攻撃法が存在する可能性があるので
「究極の暗号」とはいえないです＞楕円曲線暗号
そういや，情報理論的に安全な暗号が「究極の暗号」などと見出しを付けて
報道されたことがありましたね．

>>300
知らないで聴くのもなんだけど、量子暗号とか言わないよね？
情報理論的に安全な暗号なんて、バーナム暗号しか知らないけど。

　　　　　　　 　‖　　　　　　　　
　　　　　　　　('A`)　←>>301
　　　　　　　　（　）　　　　　　　
　　　　　|　　　 | |
　　　　　|
　　　　／￣￣

計算量的安全性ではなく、情報量的安全性に基づく暗号のことです。



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

スマン、ちょっと言い過ぎた。流してくれ。

>>300 >>303
暗号の安全性は以下の理解で正しい？（２）がうろおぼえで悪いんだけど？
（１）計算量的安全性：確率ＴＭが多項式時間で解読できない
（２）情報量的安全性：多項式領域で解読できない
（３）情報理論的安全：領域量、時間にかかわらず解読できない

ゼロ知識対話証明には「はっきり」安全性の段階があった・・・ような気が
（１）計算量的ゼロ知識：確率ＴＭが多項式時間で解読できない
（２）情報量的ゼロ知識：いっさいの情報が漏洩しない

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

すいません、実は私もうろおぼえで
今教科書をあさっているところですm(__)m

2,3,5,7,11・・・・と素数がありますが、
ある素数Pが、2から数えて奇数番目の素数か偶数番目の素数かどうか判定する方法はありますか？

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

あげ

携帯ゲーム機"プレイステーションポータブル(PSP)

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

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

宣伝ったらageろ！

age

π（ｘ）に関するリーマンの明示公式を用いれば原理的には
条件をかけるが、それは非自明なリーマンゼーター零点を
すべて必要なだけ持ってこなければならないので、もちろん
簡単ではないな。

逆に判定する方法があったとすると
数論のどんな問題が解けるのかな？

The PRIMES is in P little FAQ
http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html

age

リーマン
　　　　　　　　≡≡
　　　　　　　 （‘台‘）
　　　　( ( (　l⌒ Ｙ⌒l
　　　 　 　 　|_| ：|　|_|
　　　　　　 　Uレへ|U┓
　　　　( ( (　　|　|　|￣］
　.　　　　　　　|　|　|￣
　　　　　　　　(二)二)

定期あげ厨がいるな。

>>317
今ごろ気づくなよ、ヴァカ！

空気を読めよ

くうき？（ちがうの？）












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

age

ほしゅ

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

AKS?

素数スレ4

数論，計算量，量子計算，暗号 ハァハァな香具師向け
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. *

まだこのスレ生きてたのかよ、しぶといな（ｗ

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

>>326
ナイス情報。特攻ｹﾃｰｲ

あげ

　

age

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

Coates さんってどなた？有名人？

>>333
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Coates.html
http://www.dpmms.cam.ac.uk/site2000/Staff/coates01.html

>>334
フェルマーに多大な貢献をした人。
シルバーマンと共著で、数論幾何の本を書いている。

素数判定って、小さい数から順に割っていくだけだろ？
そんなもんの早さを競ってどうするんだ？

>>337
>>1にある論文読め。短いんだから。
読めないんであればお前勉強辞めた方がいいぞ。

>>338
論文なんて読めるはずねえだろ！！
まだM2だぞ。

M2で論文読めない．．．(　ﾟдﾟ) ﾎﾟｶｰﾝ

>>340
はぁ？普通だろ！
オレの大学はMで基礎知識をつける。
そして面接に合格してDに進学する。
それから論文を読み出して博士論文を書く。
いわゆる修士論文なるものは無い。

ちなみにDQN大学じゃねえぞ！
MARCHの中位。

>>342
俺のうんこやるから、煎じて飲め。
去年B4だったときに読んだから。

>>342
普通に読めるぞ，学部生でも．

挑戦してみる＞Primes is in P

英語か・・。

何が書いてあるか説明しろ！！！！！！！

本当に院生なのか？

お前らなんで荒らしにマジレスしてんの？

>>348
本当だ。
きちんと面接試験（自分の自己紹介を英語でおこなう、群論)に合格したぞ！！

と、話についていけないDQNな>>349が申しております。

My name is Which Fuicchi.
I want play Gunron for Daigakuin!
OK?

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

だから相手すんなって・・・。

代数専攻でWeilしらんのか･･･

>>352
英語はもう少し詳しく言えば合格ライン。
群論は数学的なことが聞かれる。ただし日本語で。
オレはシローの定理を述べるように言われた。

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

>>346 日本語による解説はこちらをどうぞ
http://www.h4.dion.ne.jp/~a00/ms_project_jp.html

11

12

６

昔は大学側が受験生を撰べたが、今や立場が逆転して、
学生側が大学を撰ぶ時代になってきた。

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

(´-`).｡ｏＯ(選択定理って何だろう？)

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

ﾋﾞﾝﾋﾞﾝﾏｯﾁｮﾃﾞ(ﾟдﾟ)ｵｰｴｰｵｰｴｰ

8

194

Ａ

ほしゅったらageろ！

282

96

最新の岩波の雑誌「数学」に解説が出ているから，それを読め．

これでRSA暗号の鍵つくるさいにカーマイケル数引かなくて済むようになるぜ。

桁数の12乗に比例する計算量というものは、ちょっときついぜ。
せめて6乗、出来れば4乗ぐらいに、まからないものですかな。

GRHを認めれば6乗だよ。4乗は無理ぽ。

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

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

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

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

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

H.Cohen, A Course in Computational Algebraic Number Theory
によると，Adleman-Rumely法は
O( (ln N)^{C ln ln ln N} )

あと，
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/

アルゴリズムがいくつもあるんじゃなくて、計算量の上限を
評価する方法がいくつかあるって事でしょ？アルゴリズム自体も
改良は加えられてるみたいだけど。

12

959

そろそろ、多項式アルゴリズムの指数の下界が発表されないものだろうか?

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

シローの定理の説明できると大学院いけるんだ・・・

796

とりあえず、一の位が
0,2,4,5,6,8
だったら素数じゃないね。

↑二桁以上

169

論文のLemma 4.2の証明で q|ο_r(n) が導かれるところがわかりません。お前らどうぞ教えてください

http://www.h4.dion.ne.jp/~a00/proofs.html
というの見つけますた

>>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)で割り切れる。

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)が成り立つことがわかる。

結局RSAを短時間で解読できるようになるには
量子コンピュータの実用化を待ってグローバーのアルゴリズム
を適用するしかないの？

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

516

>>392
それを言うならShorのアルゴリズムだろ．
まだRSAの解読が決定的に（あるいは確率的に高い正解率で）多項式時間で出来ないということは
証明されてないから量子コンピュータ抜きでもRSAを破る可能性がないこともない．限りなく低いだろうけども．

つーか一部の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.

確かこれかな．

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.

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

761

>>398
暗号の専門家に聞いたところ，(1)と(2)の難しさは同値ではないという予想らしい．
もちろんギャップがあることを直接証明するのは相当難しいことなんだろうけども．

>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

>>401
RSAと素因数分解のギャップは経験的なところでの議論と思っていたら，
実は理論的な結果が知られてたんですね．面白い結果ですね．知りませんでした．

693

243

関連スレ
暗号数学について語ろう
http://science3.2ch.net/test/read.cgi/math/1088146349/l50

332

908

二年。

255

582

586

713

877

861

879

まったく読んでないんだがＲＳＡ駄目ぽ、と理解してよろしいか？

>>416
素因数分解がPTIMEだと示されたわけじゃないよ。

892

因数分解をせずにRSAを攻撃して解読する手法が発見されれば、
副産物として、因数分解の効率的な方法のヒントが得られるような気もする。

>>416
素因数分解とは関係ないだろ

>>419
GQ1だかGQ2だかのプロトコルでも同じような話があるみたい

685

213

あぼーん

Re:>424 お前何考えてんだよ？

397

442

232

566

あぼーん

564

953

425

368

計算量クラスがまだわかっていない有名（無名でも可）な問題って何がある？

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

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

>>436
意味不明。
分かるように書いてくれ。

もとい訂正します(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}
となるような数列の算出です。

所謂差集合ですか?　だとしたら、
http://science3.2ch.net/test/read.cgi/math/1078820583/225
で紹介された本にあります。

差集合も知らんのか
この馬鹿や労

差集合は関係ないと思うが・・それほど単純な問題では無いと思うが

all-intはベンチマークに使われる類らしい。

602

117

525

633

802

日本語解説サイトの人がWikipediaにも書いてくれてたのね

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

722

990

886

615

951

746

数体ふるい法ってよくわからないです。
解りやすく教えてください。

>>447
スレ違いだから↓で聞いたほうがよさそう

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

age

549

>>438
これは本当に4000個くらいしか解がないの？

128

536

test

age

三年二分。

age

まだ生きてたのかここw

素因数分解なんて簡単でよ。

7

age

結局どうなの？

>>470
何が。

age

506

738

sage

ラッセルの(2^(2^n)+1)でおｋ

705

283

いくら Cn^a でも C =2^(2^10000000000000)　だったらなぁ

●素数判別法発見●暗号無効、世界パニック●
現代の暗号の基礎となっている、ハッシュ関数の逆関数を
現実時間で解を求める方法を、アメリカのＤ．Ｒ．シース博士が
発見。これにより、現在ほとんどすべての暗号が数ヶ月以内に
解読可能になる恐れが出てきた。
この発見をしたＤ．Ｒシース博士は、アメリカのＣＩＡによって
既に超法規的に拘束（一説には既に殺害されている）が、
一部の解法を記したメモが既にイスラエルに流出しているという。

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

タイトルと内容が全然違うじゃねーか
もちっと勉強せい

317

318

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

157

724

素数判定をしたい19728桁の自然数があるのだが、フリーソフトを利用して
判定することは可能だろうか？

訂正:19728桁→19729桁

自己解決。
素数ではなかった・・・。

というか2の倍数でした・・・。

やっぱりＲＳＡはガセだったのか・・・みんなエシュロンに読まれっぱなし

>>492
warota
とでも言ってほしいのかばかやろう

素数の一般式の発見者はもう埋葬されてしまっている・・・

そうなの？あれは誰だったっけ？

WillansかMinác．Sierpinskiは反則気味だし。

素数多項式は誰だっけ？

四年五時間。

269

このアルゴリズムは例えば1万桁だとどのぐらいかかるの？

保守

544

421

976

224

なぁ、素数っていうのは具体的に、何にどのようにどのくらい使われているんだ？
なんか暗号で使われているそうだけど、その桁数ってどのくらいあるんだ？
プログラム初心者で、課題から
素数を導き出すプログラムつくって、
ついでに判定プログラムもつくってみたけど、
どういう効能があるんだろうと疑問に思った。

409

age

>>507
2^512= 512bit
2^1024= 1024bit の鍵長です。

素数は無限にあるんでつか？

>>511
つ　 ｢素数は無限: 6つの証明｣

http://www.amazon.co.jp/gp/reader/443170986X
（頁をめくるには、右側のタブをクリック）

http://science6.2ch.net/test/read.cgi/math/1166904000/619 ,592
東大入試作問者スレ８

----------------------------------------------
M.アイグナー(著), G.M.ツィーグラー(著), 蟹江幸博(翻訳)
「天書の証明」
出版社: ｼｭﾌﾟﾘﾝｶﾞｰ･ﾌｪｱﾗｰｸ東京
価格: \3675
単行本: 313p.
出版年月: 2002/12/
ISBN-10: 443170986X
ISBN-13: 978-4431709862
寸法: 21.2 x 18.6 x 2.8 cm
----------------------------------------------

>>511
素数が有限個しか存在しないとして背理法使えばすぐ出る。

素数が有限個しか存在しないと仮定。個数をQとする。
第n番目の素数をP(n)とする。
P(1)からP(Q)までの全ての数をかけた数をMとする。
M+1はP(1)からP(Q)の全ての素数の内、いかなる素数でも割り切れない。
これは最小の素数P(1)から最大の素数P(Q)の全ての数で割り切れない数であり、「合成数」の定義からM+1は合成数では無い数である事が分かる。
また、M+1は少なくともP(Q)よりは大きい。なぜならP(1)は2であり、P(Q)は2以上であるため。
そして、素数表P(n)に存在しない数は素数ではない事は自明。
この時、数M+1は合成数でも素数でも無い数となり、これは矛盾。

よって、素数は無限に存在する。

背理法はピンと来ない

VBで素数を求めるプログラムはありますかね

作れよ。
VBは知らんけど、5〜10行程度でできるだろう。

【nビット】 Furer 乗算【n log n 2^O(log^* n)】
http://science6.2ch.net/test/read.cgi/math/1181643550/

233

背理法以外の方法…か
Nから素数の集合Pへの単射写像fは…簡単に作れるか
f(0),..,f(n-1)が与えられてるならf(n)はf(0)*f(1)*...*f(n-1)+1の素因数として帰納的に義すればいいし
任意の自然数が素因数分解出来る事を示すのに素数が無限個存在するのを示す必要は無いはずよね

五年。

470