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

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

502:１３２人目の素数さん
06/09/21 09:47:19
保守

503:１３２人目の素数さん
06/10/03 01:20:35
544

504:１３２人目の素数さん
06/11/13 00:07:07
421

505:１３２人目の素数さん
06/12/27 10:30:49
976

506:１３２人目の素数さん
07/02/05 15:46:04
224

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

508:１３２人目の素数さん
07/03/11 14:12:52
409

509:１３２人目の素数さん
07/03/11 17:52:12
age

510:１３２人目の素数さん
07/05/02 13:02:47
>>507
2^512= 512bit
2^1024= 1024bit の鍵長です。

511:１３２人目の素数さん
07/05/20 20:22:17
素数は無限にあるんでつか？

512:１３２人目の素数さん
07/05/20 20:23:25
>>511
つ　｢素数は無限: 6つの証明｣

URLﾘﾝｸ(www.amazon.co.jp)
（頁をめくるには、右側のタブをクリック）

ｽﾚﾘﾝｸ(math板: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
----------------------------------------------

513:１３２人目の素数さん
07/05/24 12:57:53
>>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は合成数でも素数でも無い数となり、これは矛盾。

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

514:１３２人目の素数さん
07/06/06 20:45:28
背理法はピンと来ない

515:１３２人目の素数さん
07/06/11 01:04:13
VBで素数を求めるプログラムはありますかね

516:１３２人目の素数さん
07/06/11 15:36:09
作れよ。
VBは知らんけど、5～10行程度でできるだろう。

517:１３２人目の素数さん
07/06/13 01:34:16
【nビット】 Furer 乗算【n log n 2^O(log^* n)】
ｽﾚﾘﾝｸ(math板)

518:１３２人目の素数さん
07/06/25 14:14:13
233

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

520:１３２人目の素数さん
07/08/08 22:24:19
五年。

521:１３２人目の素数さん
07/08/31 18:41:23

522:１３２人目の素数さん
07/10/30 12:15:55
470