カニンガムプロジェクト

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

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

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

初等代数学から、

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

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

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

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

実際には、

${\displaystyle b^{n}-1=\prod _{d\mid n}\Phi _{d}(b)}$

そして

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

詳細については、このページをご覧ください。

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

b = s ²  ×  kとし、 kを平方根 として、条件の 1 つが成立する場合は、オーリフィーユ因数分解が行われます 。${\displaystyle \Phi_{n}(b)}$

（i）および${\displaystyle k\equiv 1\mod 4}$${\displaystyle n\equiv k{\pmod {2k}};}$

（ii）そして${\displaystyle k\equiv 2,3{\pmod {4}}}$${\displaystyle n\equiv 2k{\pmod {4k}}.}$

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

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

• カニンガム数
• ECMNETとNFS@Home、カニンガム プロジェクトのために働く 2 つの共同作業

• カニンガムプロジェクトのホームページ
• bn±1、b = 2、3、5、6、7、10、11、12 の因数分解、第 2 版、高べき乗まで
• bn±1、b = 2、3、5、6、7、10、11、12 の因数分解、第 3 版
• 機械可読なカニンガム表
• カニンガムプロジェクト
• ブレント・モンゴメリ・テ・リーレ表（高次の基数（基数 13 ≤ b ≤ 99、完全累乗は除く。b nの累乗は b の累乗でもあるため^）に対するカニンガム表）
• オンライン要素収集
• プライムウィキのカニンガムプロジェクト
• PrimePagesの Cunningham プロジェクト