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

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