テストスレ [無断転載禁止]©2ch.net (762ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
613: 2023/11/12(日)11:59 ID:yQVh9yuF(1/12) AAS
2017年現在では、5≤n≤32 に対して Fn が合成数であることが分かっている。 F20,F24 は合成数だが素因子は一つも見つかっていない。
外部ﾘﾝｸ[html]:www.math.kyoto-u.ac.jp
F(20)はPépinの判定法で素数と判定されなかったので合成数と判定されている模様。
F(20)を素数テーブルで割った余りが0になるループチェックが必要？
まぁF(20)の素因数は発見したら新発見なんだろうが誰かやるのか？
615: 2023/11/12(日)12:45 ID:yQVh9yuF(2/12) AAS
test
616: 2023/11/12(日)13:06 ID:yQVh9yuF(3/12) AAS
早速pythonのsympyでF20の素数判定と素因数抽出プログラムを作って流してみたが、実行時間がかかっている。
618: 2023/11/12(日)14:55 ID:yQVh9yuF(4/12) AAS
以下の素数判定プログラムをcolabで流したところでは1時間程度では処理が終わらなかった。同時に流している素因数抽出プログラムはもっと時間がかかるだろうな。
```
import datetime
dt_now1 = datetime.datetime.now()
print(dt_now1)
from sympy import isprime
print(isprime((65536**65536)+1))
dt_now2 = datetime.datetime.now()
print(dt_now2)
print(dt_now2 - dt_now1)
省3
619: 2023/11/12(日)15:26 ID:yQVh9yuF(5/12) AAS
```
import datetime
dt_now1 = datetime.datetime.now()
print(dt_now1)
from sympy import isprime
print(isprime((65536**512)+1))
dt_now2 = datetime.datetime.now()
print(dt_now2)
print(dt_now2 - dt_now1)
```
省26
620: 2023/11/12(日)15:56 ID:yQVh9yuF(6/12) AAS
ローカルにsympyを入れて実行したところcolabより8～64倍速く実行できた。
しかし4096で1分以上かかるので、65536では21～24時間程度かかることになる。
どうせfalseで合成数だろうし、素数ではなく合成数だと分かったところで素因数が分からないと意味がない。
もっと工夫しないといけない。
621: 2023/11/12(日)16:23 ID:yQVh9yuF(7/12) AAS
F(0)=3:true
F(1)=5:true
F(2)=17:true
F(3)=257:true
F(4)=65537:true
F(5)=4294967297=(65536^2)+1:false
F(6)=18446744073709551617=(65536^4)+1:false
F(7)=340282366920938463463374607431768211457=(65536^8)+1:false
F(8)=115792089237316195423570985008687907853269984665640564039457584007913129639937=(65536^16)+1:false
F(9)=(65536^32)+1:false
省11
622: 2023/11/12(日)17:00 ID:yQVh9yuF(8/12) AAS
F(0)=3:true
F(1)=5:true
F(2)=17:true
F(3)=257:true
F(4)=65537:true
F(5)=4294967297=(65536^2)+1:false:{641: 1, 6700417: 1}
F(6)=18446744073709551617=(65536^4)+1:false:{274177: 1, 67280421310721: 1}
F(7)=340282366920938463463374607431768211457=(65536^8)+1:false:{59649589127497217: 1, 5704689200685129054721: 1}
F(8)=115792089237316195423570985008687907853269984665640564039457584007913129639937=(65536^16)+1:false:{1238926361552897: 1, 93461639715357977769163558199606896584051237541638188580280321: 1}
F(9)から素因数抽出も時間がかかる。
省1
624: 2023/11/12(日)22:09 ID:yQVh9yuF(9/12) AAS
ペピンの素数判定法によるF(20)の素数判定
3^( (((65536^65536)+1)-1) / 2 ) ≡ -1 (mod ((65536^65536)+1))
外部ﾘﾝｸ:ja.wolframalpha.com
偽
625: 2023/11/12(日)22:12 ID:yQVh9yuF(10/12) AAS
ペピンの素数判定法によるF(1048596)の素数判定
3^( (((65536^65536)^(65536^65536)+1)-1) / 2 ) ≡ -1 (mod ((65536^65536)^(65536^65536)+1))
外部ﾘﾝｸ:ja.wolframalpha.com
偽
626: 2023/11/12(日)22:13 ID:yQVh9yuF(11/12) AAS
F(5)以降のフェルマー数は全部合成数なんじゃね？
つまりフェルマー素数は5個しか無いんじゃね？
627(1): 2023/11/12(日)22:16 ID:yQVh9yuF(12/12) AAS
ペピンの素数判定法とは？
ペピンの素数判定法は、フェルマー数が素数であるかどうかを判定するための方法です³。具体的には、nが1以上のとき、次の等式が成り立つことがフェルマー数F(n)が素数であるための必要十分条件となります³:
3^( (F(n)-1) / 2 ) ≡ -1 (mod F(n))³
この判定法は、フェルマー数に対する有効な素数判定法の一つです¹²。ただし、フェルマー数以外の数に対しては、この方法は適用できません¹²。
ソース: Bing との会話 2023/11/12
(1) 素数の判定（ペパン判定法） - 単なるリンクのメニュー. 外部ﾘﾝｸ:bing.com
(2) 安全素数 - Wikipedia. 外部ﾘﾝｸ:ja.wikipedia.org
(3) フェルマー数 - Wikipedia. 外部ﾘﾝｸ:ja.wikipedia.org
(4) 素数とその探求 - 南山大学 理工学部・理工学研究科・理工学 .... 外部ﾘﾝｸ:www.st.nanzan-u.ac.jp
(5) 素数判定の試し割り法 エラトステネスの篩とは | 趣味の大学数学. 外部ﾘﾝｸ:math-fun.net
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.025s