カニンガムプロジェクト
Mathematical project in integer factorization

カニンガム・プロジェクトは、1925年に開始された共同研究であり、b = 2, 3, 5, 6, 7, 10, 11, 12およびnが大きい場合のb n ± 1の形式の数を 因数分解することを目的としています。このプロジェクトは、ハーバート・J・ウッドオールと共に最初の因数分解表を発表したアラン・ジョセフ・チャンプニーズ・カニンガムにちなんで名付けられました。[1]この表には3つの印刷版があり、最新のものは2002年に出版されました。 [2]また、サミュエル・ワグスタッフによるオンライン版もあります。[3]

指数の現在の制限は次のとおりです。

ベース 2 3 5 6 7 10 11 12
制限 1500 900 600 550 500 450 400 400
オーリフィーユ（LM）極限 3000 1800 1200 1100 1000 900 800 800

カニンガム数の因数

カニンガム数からは、因数分解アルゴリズムを使用せずに 2 種類の因数を導き出すことができます。指数に依存する二項数の代数 因数(例: 2 つの平方の差と2 つの立方の合計) と、底と指数の両方に依存する オーリフィーユ因数です。

代数的因子

初等代数学から、

( b k n − 1 ) = ( b n − 1 ) ∑ r = 0 k − 1 b r n {\displaystyle (b^{kn}-1)=(b^{n}-1)\sum _{r=0}^{k-1}b^{rn}}

すべてのkに対して、そして

( b k n + 1 ) = ( b n + 1 ) ∑ r = 0 k − 1 ( − 1 ) r ⋅ b r n {\displaystyle (b^{kn}+1)=(b^{n}+1)\sum _{r=0}^{k-1}(-1)^{r}\cdot b^{rn}}

kが奇数 の場合。さらに、 b 2 n − 1 = ( b n − 1)( b n + 1)。したがって、mでn を割るとき、nをmで割った商が偶数であれば、 b m − 1とb m + 1はb n − 1の因数です。商が奇数の場合は、最初の数だけが因数です。m でnを割って商が奇数の 場合、b m + 1はb n − 1の因数です。

実際には、

b n − 1 = ∏ d ∣ n Φ d ( b ) {\displaystyle b^{n}-1=\prod _{d\mid n}\Phi _{d}(b)}

そして

b n + 1 = ∏ d ∣ 2 n , d ∤ n Φ d ( b ) {\displaystyle b^{n}+1=\prod _{d\mid 2n,\,d\nmid n}\Phi _{d}(b)}

詳細については、このページを参照してください。

オーリフイユ因子

数が特定の形式（正確な表現は基数によって異なる）である場合、2つまたは3つの数の積を与えるオーリフィーユ因数分解が用いられることがある。以下の式は、カニンガム計画基数のオーリフィーユ因数をF、L、Mの積として与える。[4]

b = s 2  ×  kとし、平方 kの場合、条件の1つが成立すれば、オーリフィーユ因数分解が行われます。 Φ n ( b ) {\displaystyle \Phi _{n}(b)}

(i)および k ≡ 1 ( mod 4 ) {\displaystyle k\equiv 1{\pmod {4}}} n ≡ k ( mod 2 k ) ; {\displaystyle n\equiv k{\pmod {2k}};}
（ii）そして k ≡ 2 , 3 ( mod 4 ) {\displaystyle k\equiv 2,3{\pmod {4}}} n ≡ 2 k ( mod 4 k ) . {\displaystyle n\equiv 2k{\pmod {4k}}.}
b 番号 F L M その他の定義
2 2 4 k +2 + 1 1 2 2 k +1 − 2 k +1 + 1 2 2 k +1 + 2 k +1 + 1
3 3 6 k +3 + 1 3 2 k +1 + 1 3 2 k +1 − 3 k +1 + 1 3 2 k +1 + 3 k +1 + 1
5 5 10 k +5 − 1 5 2 k +1 − 1 T 2 − 5 k +1 T + 5 2 k +1 T 2 + 5 k +1 T + 5 2 k +1 T = 5 2 k +1 + 1
6 6 12 k +6 + 1 6 4 k +2 + 1 T 2 − 6 k +1 T + 6 2 k +1 T 2 + 6 k +1 T + 6 2 k +1 T = 6 2 k +1 + 1
7 7 14 k +7 + 1 7 2 k +1 + 1 A − B A + B A = 7 6 k +3 + 3(7 4 k +2 ) + 3(7 2 k +1 ) + 1
B = 7 5 k +3 + 7 3 k +2 + 7 k +1
10 10 20 k +10 + 1 10 4 k +2 + 1 A − B A + B A = 10 8 k +4 + 5(10 6 k +3 ) + 7(10 4 k +2 ) + 5(10 2 k +1 ) + 1
B = 10 7 k +4 + 2(10 5 k +3 ) + 2(10 3 k +2 ) + 10 k +1
11 11 22 k +11 + 1 11 2 k +1 + 1 A − B A + B A = 11 10 k +5 + 5(11 8 k +4 ) − 11 6 k +3 − 11 4 k +2 + 5(11 2 k +1 ) + 1
B = 11 9 k +5 + 11 7 k +4 − 11 5 k +3 + 11 3 k +2 + 11 k +1
12 12 6 k +3 + 1 12 2 k +1 + 1 12 2 k +1 − 6(12 k ) + 1 12 2 k +1 + 6(12 k ) + 1

その他の要因

代数因数とオーリフィーユ因数を除去すると、b n ± 1の他の因数は常に2 kn + 1の形式になります。これは、 b n − 1の因数がすべて の因数であり、 b n + 1の因数がすべて の因数であるためです。nが素数の場合、自明な因数 ( b n − 1の場合はb − 1、b n + 1の場合はb + 1 )を除き、代数因数とオーリフィーユ因数はどちらも不可能です。メルセンヌ数の場合、自明な因数は素数nには不可能であるため、すべての因数は2 kn + 1の形式になります。 一般に、( b n − 1) /( b − 1)のすべての因数は2 kn + 1の形式になります( b ≥ 2かつnは素数)。ただし、n がb − 1を割り切る場合は除き、その場合は( b n − 1) /( b − 1)はn自身で割り切れます。 Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ 2 n ( b ) {\displaystyle \Phi _{2n}(b)}

b n − 1の形式のカニンガム数は、b = 2 かつnが素数（ n ≥ 2と仮定）の場合にのみ素数となります。これらはメルセンヌ数です。 b n + 1の形式の数は、bが偶数かつnが2 のべき乗（ n ≥ 2と仮定）の場合にのみ素数となります。これらは一般化フェルマー数（b = 2の場合のフェルマー数）です。フェルマー数2 2 n + 1の因数はいずれもk ·2 n +2 + 1の形式となります。

表記

b n − 1 はb , n − と表記される。同様に、b n  + 1 はb , n + と表記される。オーリフィーユ因数分解に必要な形式の数を扱う場合、上記の積のL と M を表すためにb , n L とb , n M が使用される。[5] b , n − およびb , n +への参照は、すべての代数的因数とオーリフィーユ因数が除去された数を指す。例えば、メルセンヌ数は 2, n − の形式であり、フェルマー数は 2,2 n +の形式である。1871 年にオーリフィーユが因数分解した数は2,58L と 2,58M の積であった。

参照

参考文献

  1. ^ Cunningham, Allan JC; Woodall, HJ (1925). y n ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, n の高べき乗までの因数分解. Hodgson.
  2. ^ ブリルハート, ジョン;レーマー,デリック H.;セルフリッジ, ジョン L.;タッカーマン, ブライアント;ワグスタッフ, サミュエル S. (2002). b n ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 の高べき乗までの因数分解. Contemporary Mathematics. Vol. 22. AMS. doi :10.1090/conm/022. ISBN 9780821850787。
  3. ^ 「カニンガム・プロジェクト」 。 2023年11月23日閲覧。
  4. ^ 「Main Cunningham Tables」 . 2025年1月15日閲覧。表 2LM、3+、5-、6+、7+、10+、11+、および 12+ の最後には、オーリフィーユ因数分解の詳細を示す公式があります。
  5. ^ 「ページ上の表記の説明」 。 2023年11月23日閲覧。
  • カニンガムプロジェクトのホームページ
  • bn±1, b = 2, 3, 5, 6, 7, 10, 11, 12 の因数分解（高べき乗まで）、第 2 版
  • bn±1, b = 2, 3, 5, 6, 7, 10, 11, 12 の因数分解（高べき乗まで）、第3版
  • カニンガムプロジェクトのメインテーブル
  • カニンガムプロジェクトの古いメインテーブル
  • カニンガム本第3版のメインテーブル
  • 機械可読なカニンガム表
  • カニンガム・プロジェクト
  • ブレント・モンゴメリ・テ・リーレ表（高次の基数（基数 13 ≤ b ≤ 99、完全累乗は除く。b nの累乗は b の累乗でもあるため）のカニンガム表）
  • オンライン要素収集
  • プライムウィキのカニンガムプロジェクト
  • PrimePagesのCunninghamプロジェクト
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cunningham_Project&oldid=1308449698"