Sign inSign up

chotto2/prime-oasis

By chotto2

•Updated 8 months ago

素数砂漠でオアシスのような素数を見つける。

Image
Security
0

8.2K

chotto2/prime-oasis repository overview

Open in GitHub Codespaces

⁠Prime Oasis - 砂漠の中のオアシスのような素数

素数が連続して現れない区間（以下、素数砂漠と呼ぶ）には、1%前後の確率で素数（以下、オアシス素数と呼ぶ）が存在することがある。

⁠概要

これは、「みんなの嫌われ者の素数砂漠で素数を探そう」という、やや捻くれたプロジェクトである。 素数砂漠の99%は、オアシス素数を持たない。 では、なぜ素数砂漠に固執するかと言えば、素数砂漠は一定の間隔で存在し探索に適しているからだ。 例えるなら、狙撃用ライフルでスコープを覗いて素数を狙い撃つ感覚だ。 気になるのは、99%ハズレなのにどのくらいの時間感覚でヒットするかだ。 これを体感できるようにしたので、ぜひ試して欲しい。

⁠素数砂漠の位置と大きさ

LCM(1,2,3,...n)は、サイズが2n+1の最初の素数砂漠の中心点を示す。
LCM(1,2,3,...n)の整数倍の位置に同じ素数砂漠が無限に続く。

注：　LCM()は最小公倍数を示す。（以下同様）
最小公倍数は次の素数が現れるまで変化しない傾向があるため、サイズは若干大きくなることが多い。

⁠素数を判定する位置

LCM(1,2,3,...n)±1の２点

⁠用語の定義
素数砂漠の構造：

    ...大きなギャップ...     p-1   p   p+1     ...大きなギャップ...
                              ↓    ↓    ↓
                           [素数][?][素数]
                              ↑         ↑
                          oasis primes（p±1に存在する1～2個の素数）

                           <----------->
                           prime oasis（中心点pまたは素数砂漠全体）

ここで：
- p: 中心点（通常は偶数、p = LCM(1,2,3,...n)）
- p±1: oasis primesが存在しうる位置
- prime oasis: 中心点pまたは素数砂漠全体(2n+1)を指す
- oasis primes: p-1 および/または p+1 に存在する実際の素数
⁠対象とする素数砂漠

ここでは素数砂漠として、中心点がLCM(1,2,3,...701)で大きさが1403のものを対象とした。

便宜上、LCM(1,2,3,...n)をdnと記述する。（以下同様）
例．LCM(1,2,3,...701) -> d701

具体的な中心点の値は、下記の通りである。

2626719802592710061239991829174692172528343457131512513976281060940948726537757144360059535978552440933031373189919061646742591656110407680769241480651946904946211000952247368842571964792534944293239882868728171914661797572466549735970311937966946924655356399900939424721115438589874540587436119564591680000

この値を素因数分解して積算の形式で示すと下記の様になる。

2^9*3^5*5^4*7^3*11^2*13^2*17^2*19^2*23^2*29^1*31^1*37^1*...677^1*683^1*691^1*701^1

ここで積算式の末尾に注目して欲しい。
これは原点０からd701までには、d691の倍数を中心点とする素数砂漠が701個あることを示す。
同様に原点０からd691までには、d683の倍数を中心点とする素数砂漠が691個あることを示す。
同様に原点０からd683までには、d677の倍数を中心点とする素数砂漠が683個あることを示す。
同様に...（続く）

このように1つの素数砂漠を見れば、それ以下の素数砂漠がマトリョシカの様な階層構造になっていることが分かる。
マトリョシカは1つの人形を開けると少し小さい人形が1つ現れるだけだが、素数砂漠の場合は複数である。
これは原点０からd701までには、d683の倍数を中心点とする素数砂漠が701*691=484391個あることを示す。
同様に原点０からd701までには、d677の倍数を中心点とする素数砂漠が701*691*683=330839053個あることを示す。
大小の素数砂漠の中心点が一致する箇所は、重ね合わせの状態となり大きさが大きい方の素数砂漠のサイズとなる。 もっとも本方式では、素数砂漠の大きさはまったくもって問題としていない。

注：　LCM計算では中間の素因数の乗数が変化すると値が変わってくる場合があるため、da砂漠中のdb砂漠の数は da/db で求めた方が無難である。

⁠プログラム構成

プログラムは下記の7本で構成している。

  • oasis_layer1: 第1層のフルスペック版
  • oasis_layer2: 第2層のフルスペック版
  • oasis_layer3: 第3層のマイナーチェンジ版（Codespaceで11分程度で終了するように調整済み）
  • oasis_divs: LCM(1,2,3,...n)形式の素因数分解の情報を2から順次表示
  • prime_oasis: コマンドライン引数でstart/end/stepを指定可能な汎用版（v1.5.0で追加）
    • 引数の数と値をチェックし、不正な場合はUSAGEを表示
    • 2つまたは3つの引数を受け付ける
    • 引数は全てnの値（LCM(1,2,3,...n)のn）で指定
  • prime_oases: コマンドライン引数でdesert/no/numを指定可能な汎用版（v1.6.0で追加）
  • test_runner: 統合テストプログラム（v1.7.0で追加）
⁠プログラムの進化

  • Layer 1-3: 固定パラメータ版（体験用）

    • start/end/step は固定
    • ユーザーによる変更不可

  • prime_oasis: 第1世代汎用版（v1.5.0）

    • コマンドライン引数で start/end/step を指定可能
    • 全て LCM(1,2,3,...n) 形式で指定
    • 制約: end=start*2 の指定ができないため使い勝手に課題

  • prime_oases: 第2世代汎用版（v1.6.0）

    • 素数砂漠(desert)と個数(num)で直感的に指定
    • d701 のような簡潔な記法をサポート
    • start/end 境界での特殊処理を撤廃し、論理を単純化
    • 統計情報にコマンドとパラメータを追加
    • 途中から検索できる(no)機能を追加(v1.6.1)

  • test_runner: 統合テストプログラム（v1.7.0）

    • 上記６つのコマンドの出力結果について検査
    • 複数行の出力結果については、先頭・中間点・末尾を検査
    • 統計情報を出力するものは、その内容を含めて検査
    • 引数があるコマンドの場合は、同一結果となるように引数を設定
    • 被テスト対象コマンドにトレース以外の変更を加えない（自己診断機能等）

⁠特徴

  • 🎯 非消去法アプローチ - 消去ではなく積極的に素数候補の領域を絞り込む
  • 🔢 LCM法 - 最小公倍数を利用した革新的アルゴリズム
  • 🏜️ 素数砂漠内の探索 - 大きな素数砂漠内の素数を効率的に発見
  • 🐳 Docker対応 - 再現可能なビルド環境
  • 📊 約1024ビット - 教育・研究目的に適したサイズ

⁠必要環境

  • Docker Desktop
  • Git

⁠ビルドと実行

# リポジトリのクローン
git clone https://github.com/chotto2/prime-oasis.git
cd prime-oasis

# Dockerイメージのビルド
docker build -t prime-oasis .

# 各レイヤーの実行
docker run -it prime-oasis /app/build/oasis_layer1
docker run -it prime-oasis /app/build/oasis_layer2
docker run -it prime-oasis /app/build/oasis_layer3
docker run -it prime-oasis /app/build/oasis_divs

# prime_oasisコマンドの実行
# 使用方法: prime_oasis <start> [<end>] <step>
#   - 2引数の場合: prime_oasis <start> <step>（endはstart*2と同じ値になる）
#   - 3引数の場合: prime_oasis <start> <end> <step>

# 例1: oasis_layer2と同等（start=701, end=701*2, step=683）
docker run -it prime-oasis /app/build/prime_oasis 701 683

# 例2: start/end/stepを明示的に指定
docker run -it prime-oasis /app/build/prime_oasis 701 709 683

# 例3: USAGEメッセージの表示（不正な引数の場合）
docker run -it prime-oasis /app/build/prime_oasis

# prime_oasesコマンドの実行
# 使用方法: prime_oases d<n> [x<no>] [<num>]
#   - 1引数の場合: prime_oases d<n> （no, numとも１となる）
#   - 2引数の場合: prime_oases d<n> <num>（noは１となる）
#                : prime_oases d<n> x<no>（numは１となる）
#   - 3引数の場合: prime_oases d<n> x<no> <num>
#   d<n>: d<番号>形式で素数砂漠を指定（例: d701, d683, d677など）
#   x<no> : d<n>*<no>から検索開始（例：x701など）
#   num: チェックする個数

# 例1: d691*1から701個チェック
docker run -it prime-oasis /app/build/prime_oases d691 701

# 例2: d691*701から701個チェック
docker run -it prime-oasis /app/build/prime_oases d691 x701 701         // oasis_layer1相当

# 例3: d683*484391から484391個チェック(484391 = 701 * 691)
docker run -it prime-oasis /app/build/prime_oases d683 x484391 484391   // oasis_layer2相当

# 例4: d683*1から100個チェック
docker run -it prime-oasis /app/build/prime_oases d683 100

# 例5: d701*1から50個チェック
docker run -it prime-oasis /app/build/prime_oases d701 50

# 例6: USAGEメッセージの表示（不正な引数の場合）
docker run -it prime-oasis /app/build/prime_oases

# 統合テストの実行
docker run -it prime-oasis /app/build/test_runner

⁠パフォーマンス

oasis_layer1: (try=1402, hit=20, twin=0)
real    0m0.933s
user    0m0.016s
sys     0m0.012s

oasis_layer2: (try=968782, hit=16093, twin=143)
real    5m54.973s
user    0m0.217s
sys     0m0.619s

oasis_layer3: (try=1928792, hit=32000, twin=282)
real    11m45.549s
user    0m0.488s
sys     0m1.140s

oasis_divs: lcm(1,2,3,...n) // n=2-1429
real    0m7.564s
user    0m0.017s
sys     0m0.037s

prime_oasis 701 683: (try=968782, hit=16093, twin=143)   // same as oasis_layer2
real    5m54.112s
user    0m0.222s
sys     0m0.605s

prime_oases d683 x484391 484391: (try=968782, hit=16093) // same as oasis_layer2
real    5m54.098s
user    0m0.215s
sys     0m0.606s

test_runner: oasis_layer1/2/3, oasis_divs, prime_oasis, prime_oases
real    27m22.726s
user    0m0.063s
sys     0m0.015s

※Codespace:2-Core
※出力のリダイレクトなし

⁠出力例1

oasis_layer2の出力結果を示す。

Prime Oasis Layer 2 - Press 'q', ESC, or Ctrl+C to interrupt
=============================================================

oasis prime  = 2627072279800520541108487733245775976709705914990377662819691566645970417005220318148142724703856185033686932519587335291395440838811257152578688808732448765114590478925747900600954691097754312058906587230259388083365289208029989861267516201208765727131254172910746710700018581925544158406797303706682880001
oasis prime  = 2627164466147178666612555892772059433187908403968850086363352775830360705281326071292718327908935625798473771113500576090766186009671479322128851956076580020850935880857278808906993250285273223628388648370967552312103125481946581894037554239287395260086488975082542462417577865567180827682630228789999039999
...
oasis prime  = 2628943120365053088102812147161528475826168191318200375911639635388008620255601779023353495630468365260243362807826633866860563423915765887567293857775112484469835400477404569164678392256226340968983710379925073901868437119866710526306523444569188601811019275808954613203427573476405976063406665691628479999
oasis primes = 2628943120365053088102812147161528475826168191318200375911639635388008620255601779023353495630468365260243362807826633866860563423915765887567293857775112484469835400477404569164678392256226340968983710379925073901868437119866710526306523444569188601811019275808954613203427573476405976063406665691628480001
...
oasis prime  = 5253325727933665967445546520111034192936554427877853210633921804654121214616795417188584503292006749156620181057945296423674262807040540916800046132231731670453407093636133027424743356471075939000648984328346258605588620924212603431459988652424998543895422750060248803202892938563609666187078625790969279999
oasis prime  = 5253336573386213982210731009467067540757519426581202907521411358675814189708101976382063986022016095128948044421935089458894350474200567054394182973095747112304741846804548428401924363434313458008823344462547219103087189897614555435315287245140131430125450373845165950463782266050861039043058969918418239999
(try=968782, hit=16093, twin=143)

最初の行は、oasis_layer2が実行中で'q'かESCかCtrl+Cの押下で処理を中断できることを示している。

セパレータに続きヒットしたオアシス素数が表示される。

先頭のブロックと末尾のブロックは、１つの素数砂漠で１つだけ発見されたオアシス素数のリストを表示している。

真ん中のブロックは双子素数がヒットしたことを示している。
双子素数の２つめの素数はoasis primesというキーワードで表示される。
双子素数の１つめの素数はoasis primeというキーワードで直前に表示される。

最後の行は、統計情報を括弧でくくって表示する。
tryは、素数かどうか調べた回数を示す。
hitは、素数を見つけた回数を示す。
twinは、双子素数を見つけた回数を示す。

⁠出力例2

prime_oasesの出力結果を示す。

Prime Oases - Press 'q', ESC, or Ctrl+C to interrupt
====================================================

d683*484456+1 = 2627072279800520541108487733245775976709705914990377662819691566645970417005220318148142724703856185033686932519587335291395440838811257152578688808732448765114590478925747900600954691097754312058906587230259388083365289208029989861267516201208765727131254172910746710700018581925544158406797303706682880001
d683*484473-1 = 2627164466147178666612555892772059433187908403968850086363352775830360705281326071292718327908935625798473771113500576090766186009671479322128851956076580020850935880857278808906993250285273223628388648370967552312103125481946581894037554239287395260086488975082542462417577865567180827682630228789999039999
...
d683*968761-1 = 5253325727933665967445546520111034192936554427877853210633921804654121214616795417188584503292006749156620181057945296423674262807040540916800046132231731670453407093636133027424743356471075939000648984328346258605588620924212603431459988652424998543895422750060248803202892938563609666187078625790969279999
d683*968763-1 = 5253336573386213982210731009467067540757519426581202907521411358675814189708101976382063986022016095128948044421935089458894350474200567054394182973095747112304741846804548428401924363434313458008823344462547219103087189897614555435315287245140131430125450373845165950463782266050861039043058969918418239999
{ prime_oases d683 x484391 484391: try=968782, hit=16093(1.7%) }

最初の行は、prime_oasesが実行中で'q'かESCかCtrl+Cの押下で処理を中断できることを示している。

セパレータに続きヒットしたオアシス素数が表示される。

d683*484456+1 = 262707...は、「d683素数砂漠の484456個目は中心点+1がオアシス素数で262707...である」ことを示す。
d683*484473-1 = 262716...は、「d683素数砂漠の484473個目は中心点-1がオアシス素数で262716...である」ことを示す。
d683*968761-1 = 525332...は、「d683素数砂漠の968761個目は中心点-1がオアシス素数で525332...である」ことを示す。
d683*968763-1 = 525333...は、「d683素数砂漠の968763個目は中心点-1がオアシス素数で525333...である」ことを示す。

最後の行は、統計情報を中括弧でくくって表示する。
prime_oases d683 x484391 484391は、実行したコマンドとパラメタを示す。
tryは、素数かどうか調べた回数を示す。
hitは、素数を見つけた回数を示す。
(1.7%)はヒット率でhit/try*100.0の値を示す。

⁠出力例3

test_runnerの出力結果を示す。

====< 0001 oasis_layer1:top-mid-bot-sta
====< 0002 oasis_layer2:top-mid-bot-sta
====< 0003 oasis_layer3:top-mid-bot-sta
====< 0004 oasis_divs:top-mid-bot
====< 0005 prime_oasis:top-mid-bot-sta
====< 0006 prime_oases:top-mid-bot-sta

'====< 'で始まる行は、テストごとに表示されるタイトル行である。
また、それに続く文字列は下記のような意味を持っている。
先頭の数字はテスト番号を示す。
次にテスト対象のコマンド名称を示す。
次にテスト内容を示す。
topは、複数結果の先頭行を検査することを示す。
midは、複数結果の中間点の行を検査することを示す。
botは、複数結果の末尾行を検査することを示す。
staは、統計情報を検査することを示す。

特にエラーがなければ、タイトル行以外は表示しない。

エラー発生時には、原因となった情報を表示して統合テストを中断する。

test_runnerは、30分程度かかるので時間の余裕があるときに実施すること。
中断したいときは、キー割り込み（'q',ESC,Ctrl+C押下）で抜けることができる。

⁠技術詳細

  • 言語: C
  • ライブラリ: GMP (GNU Multiple Precision Arithmetic Library)
  • ビルドシステム: CMake
  • LCM範囲: 1..701 (約1020ビット)

⁠注意事項

⚠️ 重要: このバージョンは教育・研究目的の実装です。約1024ビットの素数を扱うため、現代の暗号システム（RSA-4096など）には影響しません。

⁠今後の予定

  • 📝 arXivへの論文投稿予定
  • 📚 アルゴリズムの詳細な理論的背景

⁠ライセンス

MIT License

⁠著者

N.Arai

⁠引用

論文準備中。公開後、適切な引用方法を記載します。

⁠関連リンク

Tag summary

Content type

Image

Digest

sha256:0bd1da263…

Size

196.5 MB

Last updated

8 months ago

docker pull chotto2/prime-oasis