(X + a)^{n} \equiv X^{n} + a (mod X^{r} - 1, n)

AKS素数判定法

AKS primality test

8月6日付の9ページの原稿は、ガウスの言葉で始まっていた。

(X + a)ⁿとXⁿ + aを、Xʳ − 1とnで割った余りで比べる。乱数にも未証明の予想にも頼らず、桁数の多項式の手間で、素数かどうかを確実に決める。

年代: 2002年
習う: 大2・数論・合同式と素数判定
レベル: 大学(例題 5 問)
人物: マニンドラ・アグラワル、ニーラジ・カヤル、ニティン・サクセナ、カール・フリードリヒ・ガウス、ピエール・ド・フェルマー、ロバート・カーマイケル、ヘンドリック・レンストラ、カール・ポメランス
作成日: 2026-11-02
更新日: 2026-11-02
執筆・監修: 佐々木航

数学情報科学哲学

逸話

1801年の言葉で始まる原稿

561は素数だろうか。3で割れば187になり、すぐに合成数だと分かる。ところが、2を560回掛けた数を561で割ると、余りは1になる。2でない素数 $p$ なら $2^{p - 1}$ を $p$ で割った余りは必ず1、というフェルマーの小定理の結論と、見分けがつかない。

素数かどうかを確実に決めたいなら、小さい数から順に割っていけばよい。ただ、100桁の素数を確かめるには、割る数を素数に限っても $1 0^{47}$ 回を超える割り算が要る。桁数の多項式の手間で済む判定は長いあいだ、乱数か、証明されていない予想のどちらかに頼ってきた。

2002年8月、インド工科大学（IIT）カーンプル校の3人が、その両方を手放した9ページの原稿を出した。題は「PRIMES is in P」、日付は8月6日。本文の前には、ガウスが1801年の『整数論の研究』に書いた一節が置かれている。

「素数と合成数を見分け、合成数を素因数に分ける問題は、算術で最も重要で有用なものの一つとして知られている」。ガウスは、見分ける問題と分ける問題を一続きに挙げた。3人が原稿で解いたのは、その前の半分である。¹

カール・フリードリヒ・ガウスの肖像(Carl Friedrich Gauss) — カール・フリードリヒ・ガウス1777–1855数論・天文学・測量・地磁気に業績を残し、素数の分布を予想した出典: Wikimedia Commons・Gottlieb Biermann / After Christian Albrecht Jensen・Public domain

要旨は1文しかない。入力された数 $n$ が素数か合成数かを決める、決定的な多項式時間のアルゴリズムを示す、というものだ。乱数を使わず、証明されていない予想にも頼らず、 $n$ の桁数の多項式で抑えられる手間で、必ず正しい答えを出す。

雨の筋が残る窓辺の机に、印刷した紙の束と、ブラウン管の古いモニターが置かれている(画像生成 AI で描いたイメージ) — 2002年8月、IITカーンプル校。9ページの原稿には8月6日の日付が入っていた画像生成AIで描いたイメージ

マニンドラ・アグラワルは、同校で計算量理論を研究する教授である。共著者のニーラジ・カヤルとニティン・サクセナは、この年からアグラワルのもとで博士課程に進んだ。サクセナの経歴書によると、サクセナは2002年に学部（B.Tech）を終えている。卒業研究の題は「決定的な多項式時間の素数判定に向けて」で、指導教員はアグラワルだった。原稿の参考文献には、ほぼ同じ題のカヤルとサクセナの連名の報告が載っている。2人はその報告で、前の年に同じ大学のラジャット・バッタチャルジーとプラシャント・パンデーの報告に載った予想を、 $r \leq 100$ 、 $n \leq 1 0^{10}$ の範囲で計算機にかけて確かめていた。

マニンドラ・アグラワル2人の学生とAKS素数判定法を示した、IITカーンプル校の教授

原稿は、外からの指摘を受けて書き直されていく。2002年8月のうちに、ヘンドリック・レンストラが群の大きさの見積もりを改め、素数の分布についての深い結果を使わなくても証明が通るようにした。補題の証明の誤りを知らせた人の中には、ドイツ・シューラーアカデミーの受講生たちもいたと、最終版の謝辞にある。最終版は2004年にAnnals of Mathematicsの第160巻2号に載り、手間の見積もりは、最初の原稿の $O ~ (lo g^{12} n)$ から、初等的な議論だけで $O ~ (lo g^{21/2} n)$ 、その深い結果も使えば $O ~ (lo g^{15/2} n)$ まで下がった。

2006年、3人の論文はゲーデル賞とファルカーソン賞を受けた。EATCSの記録によると、その年のゲーデル賞は、ヴェネツィアで開かれた国際会議ICALPで贈られている。

運河に面した古い建物の会議場を、聴衆の後ろから見る。遠くの演台に小さな人影がある(画像生成 AI で描いたイメージ) — 2006年のゲーデル賞は、ヴェネツィアで開かれた国際会議ICALPで贈られた画像生成AIで描いたイメージ

起源

561は素数のふりをする

フェルマーは1640年10月18日付のフレニクルへの手紙で、いまフェルマーの小定理と呼ぶ事実を書き送った。今の言葉に直せば、素数 $p$ と、 $p$ で割り切れない $a$ について、 $a^{p - 1} - 1$ が $p$ で割り切れる、というものだ。両辺に $a$ を掛ければ、すべての整数 $a$ で $a^{p} - a$ が $p$ で割り切れる、という形にもなる。

ピエール・ド・フェルマーの肖像(French: Portrait de Pierre de Fermat Portrait of Pierre de Fermattitle QS:P1476,fr:"Portr…) — ピエール・ド・フェルマー1601頃–1665法律家の仕事の合間に、数論と確率論の土台を築いた出典: Wikimedia Commons・Rolland Lefebvre・Public domain

判定に使うなら、この定理はとても速い。 $a^{n - 1}$ を $n$ で割った余りは、2乗をくり返せば、 $n$ の桁数に比例する回数の掛け算で求まる。余りが1でなければ、 $n$ は合成数だと確定する。困るのは逆向きで、余りが1でも素数とは限らない。 $341 = 11 \times 31$ は、 $2^{340}$ を341で割ると1余るが、底を3にすれば余りは56になり、正体が分かる。

では、 $n$ と互いに素などの底を選んでもだまされる合成数はあるのだろうか。

ある。1910年、ロバート・カーマイケルは、 $561 = 3 \times 11 \times 17$ がすべての整数 $a$ について $a^{561} - a$ を割り切ることを指摘した。その11年前に、コルセルトがこうした数の見分け方を書いていた。 $n$ が同じ素数を2度含まず、 $n$ を割るどの素数 $p$ でも $p - 1$ が $n - 1$ を割り切ること、である。561なら2、10、16が、どれも560を割り切る。

ロバート・カーマイケルの肖像(画像生成 AI で描いたイメージ) — ロバート・カーマイケル1879–1967フェルマーの判定をすり抜ける合成数561を1910年に指摘した画像生成AIで描いたイメージ

この性質をもつ合成数をカーマイケル数と呼び、小さい順に561、1105、1729、2465、2821と続く。無限にあるかどうかは長く分からなかったが、1994年にW・R・アルフォード、アンドリュー・グランヴィル、カール・ポメランスが決着をつけた。十分大きな $x$ では、 $x$ 以下のカーマイケル数は $x^{2/7}$ 個より多い。

だまされない判定は、代わりに何かを手放してきた。1976年のゲイリー・ミラーの判定は、乱数を使わずに速いが、拡張リーマン予想が正しいことを前提にする。1980年のマイケル・ラビンの判定は前提を外した代わりに底を乱数で選び、合成数を素数と答える確率がわずかに残る。1977年のロバート・ソロヴェイとフォルカー・シュトラッセンの判定も、乱数に頼っていた。1983年のレナード・アドルマン、ポメランス、ロバート・ルメリーの判定は乱数も予想も使わないものの、手間は $(lo g n)^{O (l o g l o g l o g n)}$ で、桁数のどんな多項式よりもわずかに速く増える。

AKSが土台にしたのは、フェルマーの小定理を多項式に広げた恒等式だった。1999年にアグラワルとソーメナト・ビスワスが、乱数を使う判定の土台にしたものと同じ式である。

(X + a)^{n} \equiv X^{n} + a (mod n)

$a$ と $n$ が互いに素なら、これが成り立つのは $n$ が素数のときだけだ。ただし左辺の係数は $n + 1$ 個あり、全部を調べる手間は試し割りより重い。3人は両辺を $X^{r} - 1$ でも割り、比べる係数を $r$ 個に減らした。合成数がこの縮めた式を通り抜けないように、 $r$ をどう選び、 $a$ をいくつ試せばよいか。論文の中身は、その問いへの答えである。

証明

係数がnで割り切れるとき

$n \geq 2$ と、 $n$ と互いに素な整数 $a$ について、 $n$ が素数であることと、多項式として $(X + a)^{n} \equiv X^{n} + a (mod n)$ が成り立つことは同じである（論文の補題2.1）。多項式の合同は、同じ次数の係数どうしが $n$ で割った余りで等しいことを言う。展開には二項定理を使う。素数 $p$ で $_{p} C_{i}$ が $p$ の倍数になることと、 $2^{p} - 2$ が $p$ の倍数になることは、二項定理の例題5でも手で確かめられる。

両辺の差を展開する
$(X + a)^{n} - (X^{n} + a) = i = 1 \sum n - 1 (i n) a^{n - i} X^{i} + (a^{n} - a)$
$n = p$ が素数なら、 $1 \leq i \leq p - 1$ では分子だけが $p$ を含む
$(i p) = \frac{p !}{i ! ( p - i )!} \equiv 0 (mod p)$
定数項もフェルマーの小定理で $p$ の倍数になり、差の係数はすべて $p$ で割り切れる
$a^{p} - a \equiv 0 (mod p)$
$n$ が合成数なら、 $n$ を割る素数 $q$ をとり、 $n$ がちょうど $q^{k}$ で割り切れるとする。 $X^{q}$ の係数を見る
$(q n) = \frac{n ( n - 1 ) \dots ( n - q + 1 )}{q !}$
分子で $q$ の倍数は $n$ だけで（ $1 \leq j \leq q - 1$ なら $n - j \equiv - j$ ）、 $q$ はちょうど $k$ 個ある。分母の $q!$ は $q$ を1個含むので、残る $q$ は $k - 1$ 個になる
$q^{k} ∤ (q n)$
n = 9 = 3²の行では、9Cᵢを9で割って余りが残るのはi = 3と6の84だけで、余りは3。3つ目の係数で式が崩れる。
$a$ は $q$ で割り切れないので、 $X^{q}$ の係数は $q^{k}$ で割り切れず、 $n$ でも割り切れない
$(q n) a^{n - q} \neq \equiv 0 (mod n)$

合成数なら、どこかの係数が必ず残る。561で $q = 3$ とすると $(3 561) = 29, 269, 240$ で、561で割った余りは187だ。係数を全部数えると、560個のうち114個が561で割り切れない。

フェルマーの判定がだまされたのは、この係数を見ていなかったからだ。両辺に $X = 1$ を入れると、左辺は $(1 + a)^{n}$ 、右辺は $1 + a$ になり、 $n + 1$ 個の係数は足し合わされて1つの数に潰れる。カーマイケル数が素数と区別できないのは、その和の上だけである。

証明

素数のべきしか通れない

最終版の手順は6つしかない。まず、 $n$ が $a^{b}$ （ $b > 1$ ）と書ければ合成数と答える。次に、 $n^{k}$ を $r$ で割った余りが1になる最小の $k$ 、つまり $r$ を法とする $n$ の位数 $o_{r} (n)$ が、 $lo g^{2} n$ を超える最小の $r$ を探す。 $lo g$ の底は2だ。 $r$ 以下の $a$ に、 $n$ と1でも $n$ でもない公約数をもつものがあれば合成数とし、 $n \leq r$ なら素数とする。残った $n$ では、 $a = 1$ から $⌊ φ (r) lo g n ⌋$ まで縮めた式を確かめ、1つでも崩れたら合成数、すべて通れば素数。 $φ (r)$ は、 $r$ 以下で $r$ と互いに素な数の個数を表す。

素数がすべての手順を通ることは、前の補題から分かる。難しいのは逆向きで、完全な証明は論文の第4節にある。筋道は次のとおりだ。 $o_{r} (n) > 1$ なので、 $n$ の素因数には $o_{r} (p) > 1$ となる $p$ がある。その $p$ を1つとる。手順3と4を通っているので、 $p > r$ である。

手順5の式は $p$ で割っても成り立ち、補題から $p$ も同じ形の式を満たす
$(X + a)^{n} \equiv X^{n} + a, (X + a)^{p} \equiv X^{p} + a (mod X^{r} - 1, p)$
$f (X)^{m} \equiv f (X^{m})$ となる $m$ を、 $f$ について内省的と呼ぶ。 $n / p$ と $p$ は、手順5で試したどの $X + a$ にも内省的で、内省的な数の積も内省的になる
$I = {(\frac{n}{p})^{i} p^{j} i, j \geq 0}$
$I$ の数を $r$ で割った余りは群 $G$ をつくる。 $G$ は $n$ を含むので、その大きさ $t$ は位数 $o_{r} (n)$ 以上になる
$t = ∣ G ∣ \geq o_{r} (n) > lo g^{2} n$
$X^{r} - 1$ を割る $r$ 番目の円分多項式から、 $p$ を法とする既約な因数 $h (X)$ をとる。 $h (X)$ で割ってできる有限体の中で、 $X + a$ （ $0 \leq a \leq ℓ$ ）の積がつくる群 $G$ は大きい
$∣ G ∣ \geq (t - 1 t + ℓ) > n^{t}$
$n$ が $p$ のべきでなければ、指数 $i, j$ を $⌊ t ⌋$ 以下に限っても $I$ には $(⌊ t ⌋ + 1)^{2} > t$ 個の数があり、 $r$ で割った余りが等しい2数 $m_{1} > m_{2}$ が見つかる。 $G$ の元はすべて $Y^{m_{1}} - Y^{m_{2}}$ の根になり、根の数は次数を超えない
$∣ G ∣ \leq m_{1} \leq n^{t}$
4と5の不等式は両立しないので、 $n$ は $p$ のべきである。 $p^{k}$ （ $k \geq 2$ ）は最初の手順で除いてある
$n = p$

矛盾を生んだのは、手順2の $r$ の選び方だ。 $t > lo g^{2} n$ なので $t > lo g n$ となり、 $ℓ = ⌊ φ (r) lo g n ⌋$ 個の $X + a$ だけで、群 $G$ を $n^{t}$ より大きくできる。論文は、そうした $r$ が $⌈ lo g^{5} n ⌉$ 以下に必ず見つかることも示していて（補題4.3）、手順5の手間は桁数の多項式に収まる。

途中の計算

r個の位置に折りたたむ

補題の式は、 $X^{r} - 1$ で割った余りに縮めても、素数なら成り立ったままだ。指数は $r$ で割った余りの位置に回り込む。

二項定理で展開する
$(X + a)^{n} = i = 0 \sum n (i n) a^{n - i} X^{i}$
$X^{r} \equiv 1$ なので、指数を $r$ で割った余りに替える
$X^{i} \equiv X^{i mod r} (mod X^{r} - 1)$
余りが同じ $j$ になる項をまとめる
$c_{j} = i \equiv j (mod r) \sum (i n) a^{n - i}$
(X + 1)⁶の7つの係数を、指数を3で割った余りごとに集めると22、21、21になる。6で割った余りは4、3、3で、右辺のX⁰ + 1 = 2と合わない。
左辺は係数が $r$ 個の多項式になる
$(X + a)^{n} \equiv j = 0 \sum r - 1 c_{j} X^{j} (mod X^{r} - 1)$
右辺の指数も同じように替える
$X^{n} + a \equiv X^{n mod r} + a (mod X^{r} - 1)$
係数を $n$ で割った余りで比べる
$(X + a)^{n} \equiv X^{n} + a (mod X^{r} - 1, n)$

$n = 6$ 、 $r = 3$ 、 $a = 1$ で手を動かしてみる。 $(X + 1)^{6}$ の係数は1、6、15、20、15、6、1で、指数を3で割った余りごとに足すと $c_{0} = 1 + 20 + 1 = 22$ 、 $c_{1} = 6 + 15 = 21$ 、 $c_{2} = 15 + 6 = 21$ になる。6で割ると4、3、3が残り、右辺の $X^{0} + 1 = 2$ とは合わない。

$r = 1$ にすると、すべての項が定数項に集まって $c_{0} = (1 + a)^{n}$ となる。比べるのは $(1 + a)^{n} \equiv 1 + a (mod n)$ で、 $b = 1 + a$ と書けば $b^{n} \equiv b$ 、つまりフェルマーの判定そのものだ。 $r$ を上げるほど、潰れていた係数の違いが見えてくる。

561で $r = 3$ にすると、左辺は $374 + 375 X + 375 X^{2}$ 、右辺は2で、一致しない。それでも係数の和は $1124 \equiv 2$ で、フェルマーの判定の答えと変わらない。 $a = 1$ で調べると、561が通り抜けるのは $r = 1, 2, 4$ だけで、 $r = 3$ と、5から60までのすべての $r$ で崩れる。

応用

鍵の素数は確率で選ぶ

2048ビットのRSAの鍵を作るときは、1024ビットの素数を2つ選ぶ。アメリカ国立標準技術研究所（NIST）が2023年2月3日に公開した電子署名の規格FIPS 186-5は、その判定にミラー・ラビン法を使うよう定めている。1024ビットの素数 $p$ 、 $q$ では、誤る確率を $2^{- 100}$ 以下にするなら4回、 $2^{- 112}$ 以下なら5回の判定が要る。ミラー・ラビン法のあとにリュカの判定を1回足してもよく、規格には「この2つを組み合わせた判定を通る合成数は知られていない」とある。リュカの判定の中身はフィボナッチ数列、候補を選び直す回数の見積もりは素数定理で読める。

では、同じ大きさの数にAKSを使うと、どうなるか。1024ビットの $n$ では $lo g n$ が1023を超えるので、手順2の $r$ は $102 3^{2} + 1 = 1, 046, 530$ より大きくなり、多項式の係数は100万個を超える。試す $a$ も $⌊ φ (r) lo g n ⌋ \geq ⌊ lo g^{2} n ⌋$ から104万通りを超え、その1つごとに、100万個の係数をもつ多項式の2乗を約1000回くり返す。ミラー・ラビン法の1回は、1024ビットの数の2乗を約1000回すれば済む。実務の判定にAKSが使われないのは、この差のためである。

AKSの値打ちは速さではなく、乱数も予想も使わずに「多項式時間で決まる」と証明した点にある。もう一つ、素数かどうかを決める問題と、素因数を見つける問題は別物だ。AKSが合成数と答えても、崩れた $a$ からは約数が何も分からない。素因数を見つける問題には、古典的な計算機で多項式時間の方法が今も知られておらず、RSA暗号の安全性はこの差の上に立っている。量子計算機でこの差を詰めるのがショアのアルゴリズムで、小さな数を素数の積に分ける手順は素因数分解で確かめられる。

例題と解説

係数と位数を手で数える

例題 1基本5と6の行の係数

$(X + 1)^{5} - (X^{5} + 1)$ と $(X + 1)^{6} - (X^{6} + 1)$ を展開し、係数がそれぞれ5、6で割り切れるかを調べよ。

解説を見る

二項係数を並べる。

(X + 1)^{5} - (X^{5} + 1) = 5 X^{4} + 10 X^{3} + 10 X^{2} + 5 X

係数の5、10、10、5は、どれも5で割り切れる。

(X + 1)^{6} - (X^{6} + 1) = 6 X^{5} + 15 X^{4} + 20 X^{3} + 15 X^{2} + 6 X

15と20は6で割り切れない。証明の手順4〜6で $q = 2$ とすると $(2 6) = 15$ が奇数になり、 $q = 3$ とすると $(3 6) = 20$ が3で割り切れない。どちらの素因数からも、崩れる係数が見つかる。

例題 2基本561がだます理由

$a$ が561と互いに素なとき、 $a^{560} \equiv 1 (mod 561)$ を示せ。 $561 = 3 \times 11 \times 17$ を使ってよい。

解説を見る

560は2でも10でも16でも割り切れる。

560 = 2 \times 280 = 10 \times 56 = 16 \times 35

$a$ は3、11、17のどれでも割り切れないので、フェルマーの小定理から

a^{2} \equiv 1 (mod 3), a^{10} \equiv 1 (mod 11), a^{16} \equiv 1 (mod 17)

が成り立つ。それぞれを280乗、56乗、35乗すると、どの法でも $a^{560} \equiv 1$ になる。3、11、17はどの2つも互いに素なので、積の561を法としても次が成り立つ。

a^{560} \equiv 1 (mod 561)

コルセルトの見分け方は、この計算を一般の $n$ に広げたものである。

例題 3入試rを探す

$n = 31$ について、31の $r$ を法とする位数が $(lo g_{2} 31)^{2}$ を超える最小の $r$ を求めよ。 $lo g_{2} 31 = 4.954 \dots$ を使ってよい。

解説を見る

$(lo g_{2} 31)^{2} = 24.54 \dots$ なので、位数は25以上でなければならない。位数は $r - 1$ 以下なので、 $r = 26$ から調べる。

$r = 26$ では $31 \equiv 5$ で、 $5^{2} = 25 \equiv - 1$ から位数は4。

5^{4} \equiv 1 (mod 26)

$r = 27$ では $31 \equiv 4$ で、 $4^{3} = 64 \equiv 10$ は1でなく、 $4^{9} \equiv 1 0^{3} = 1000 = 27 \times 37 + 1$ から位数は9。

4^{9} \equiv 1 (mod 27)

$r = 28$ では $31 \equiv 3$ で、 $3^{3} = 27 \equiv - 1$ から位数は6。

3^{6} \equiv 1 (mod 28)

$r = 29$ では $31 \equiv 2$ で、 $2^{4} = 16$ 、 $2^{7} = 128 \equiv 12$ 、 $2^{14} \equiv 144 \equiv - 1$ はどれも1でないので、位数は28。

2^{28} \equiv 1 (mod 29)

28は24.54を超えるので、 $r = 29$ である。試す $a$ の個数は $⌊ 28 \times 4.954 \dots ⌋ = ⌊ 26.2 \dots ⌋ = 26$ になる。

例題 4難関素数のべきの二項係数

素数 $p$ と $k \geq 1$ について、 $(p p ^{k})$ は $p^{k - 1}$ で割り切れるが、 $p^{k}$ では割り切れないことを示せ。

解説を見る

分数の形に書く。

(p p ^{k}) = \frac{p ^{k} ( p ^{k} - 1 ) ( p ^{k} - 2 ) \dots ( p ^{k} - p + 1 )}{p !}

$1 \leq j \leq p - 1$ なら $p^{k} - j \equiv - j \neq \equiv 0 (mod p)$ なので、分子に含まれる $p$ はちょうど $k$ 個である。分母の $p! = p \cdot (p - 1)!$ に含まれる $p$ は1個なので、 $(p p ^{k})$ に残る $p$ は $k - 1$ 個になる。 $p = 3$ 、 $k = 2$ なら $(3 9) = 84 = 2^{2} \times 3 \times 7$ で、3はちょうど1個である。

例題 5大学r = 2の判定を通る合成数

$n$ を奇数のカーマイケル数とする。どの整数 $a$ についても、次が成り立つことを示せ。

(X + a)^{n} \equiv X^{n} + a (mod X^{2} - 1, n)

解説を見る

$X^{2} - 1$ で割った余りは $u + v X$ の形をしていて、 $X = 1$ と $X = - 1$ を入れた値は $u + v$ と $u - v$ になる。 $n$ は奇数なので2は $n$ を法として逆数をもち、2つの余りが等しいことは、 $X = 1$ と $X = - 1$ での値が $n$ を法として等しいことと同じである。

左辺の値は $(1 + a)^{n}$ と $(a - 1)^{n}$ 、右辺の値は $1 + a$ と $(- 1)^{n} + a = a - 1$ 。カーマイケル数ではすべての整数 $b$ で $b^{n} \equiv b (mod n)$ なので

(1 + a)^{n} \equiv 1 + a, (a - 1)^{n} \equiv a - 1 (mod n)

となり、両辺は一致する。 $r = 2$ の判定は、 $X = 1$ と $X = - 1$ の2か所でフェルマーの判定をするのと同じで、カーマイケル数を見抜けない。561が $r = 1$ と $r = 2$ の判定を、どの $a$ でも通り抜けるのはこのためである。

図示

乱数と予想と時間の条件

乱数を使わない、未証明の予想を使わない、桁数の多項式時間で終わる。試し割り、ミラー、ラビン、APR、AKSのうち、3つがそろうのは2002年のAKSが初めてである。

フェルマーの判定は、カーマイケル数で答えを誤るので、この比べ方の外にある。ソロヴェイとシュトラッセンの判定は、ラビンの判定と同じ並びの○と×になる。

シミュレーション

nを選び、3つの判定にかける

例の数を押すか、つまみで奇数 $n$ を選ぶと、上からフェルマーの判定、 $(X + 1)^{n}$ の $n - 1$ 個の係数、論文の $r$ で縮めた式が並ぶ。561、1105、1729のようなカーマイケル数では、上の段で $n$ と互いに素な底がすべて余り1を返すのに、中の段には $n$ で割り切れない係数の位置に縦の筋が現れ、下の段は $a = 1$ で崩れる。5から3001までの奇数では、合成数はどれも $a = 1$ で崩れ、素数はすべての $a$ で式が成り立つ。ただし、この大きさの合成数なら、論文どおりの手順は手順1の累乗の判定か手順3の公約数で止まる。下の段は、その2つを飛ばして式だけを当てた結果で、論文どおりの結論は下の読み出しに出る。

広がる学問

決定的な判定が届く先

数学有限体の上の多項式を調べるとき、 $p$ 乗が係数ごとの $p$ 乗になる $f (X)^{p} \equiv f (X^{p}) (mod p)$ を使う。AKSの証明では、この形が成り立つ指数を数え上げて、 $n$ を素数のべきに追い込む。 $X^{r} - 1$ の代わりに別の多項式で割る判定も、同じ考えで組み立てられる。
情報科学 問題を計算量で分類するとき、素数の集合PRIMESが多項式時間のクラスPに入る例として挙がる。合成数には約数という短い証拠があり、プラットが1975年の論文で示したように素数にも短い証拠があるが、証拠を渡されなくても多項式時間で決められると示したのはAKSだった。 $(X + a)^{n}$ と $X^{n} + a$ が等しいかを確かめる問題は、2つの多項式が等しいかを判定する多項式恒等式判定の一例でもあり、サクセナはのちにこの問題の総説を書いている。
哲学「実際に計算できる」とは何かを数学の基礎から問うとき、有界算術と呼ばれる弱い公理の体系で、どこまで証明できるかを調べる。素数判定が多項式時間で済むという定理も、その体系の中で証明できるかが問われてきた。

いまの研究と事業

速さの証明と、巨大な素数の証明書

2019年ヘンドリック・レンストラ（ライデン大学）とカール・ポメランス（ダートマス大学）: AKSの手順を変え、手間を $(lo g n)^{6} (2 + lo g lo g n)^{c}$ 以下に抑えた。論文は『Journal of the European Mathematical Society』に載った。 $X^{r} - 1$ の代わりに、ガウスが正多角形の作図の証明で使ったガウス周期から作る次数 $d > lo g^{2} n$ の多項式 $f (X)$ で割り、 $(X + a)^{n} \equiv X^{n} + a (mod f (X), n)$ を確かめる。ポメランスは講演で、ガウスの代表的な結果を使って、素数と合成数を見分けよというガウスの呼びかけに前進できたのは喜ばしい、と語っている。（出典: Lenstra, Pomerance「Primality testing with Gaussian periods」、J. Eur. Math. Soc. 21 (2019), 1229-1269・Pomerance「Primality testing: then and now」）
2021年ロバート・ベイリー、アンドリュー・フィオリ（レスブリッジ大学）、サミュエル・ワグスタッフ（パデュー大学）: ベイリー・PSW判定を、計算の手間をほとんど増やさずに強める方法を示し、『Mathematics of Computation』に発表した。この判定は、フェルマー型の判定とリュカ型の判定を組み合わせる。フェルマー型の部分は、AKSの式で $r = 1$ にした $b^{n} \equiv b$ を強めた判定である。論文によると、パラメーターを適切に選べば、この組み合わせを通る奇数の合成数は報告されていない。数値計算のライブラリGMPの素数判定も、試し割りのあとにこの判定を使う。（出典: Baillie, Fiori, Wagstaff「Strengthening the Baillie-PSW primality test」arXiv:2006.14425、Math. Comp. 90, no. 330, 2021・GNU MP 6.3.0 Manual「Number Theoretic Functions」）
2025年アンドレアス・エンゲとポール・アンダーウッド: 1が109,297個並ぶ数 $R_{109297} = (1 0^{109297} - 1) /9$ が素数であることの証明書を、楕円曲線を使う方法で完成させた。素数の記録を集めるPrime Pagesの一覧では、この方法で証明された素数の1位にある。もっともPrime Pagesは、楕円曲線法の証明書までは自ら確かめていないと断っている。同じ数にAKSを使うと、 $lo g^{2} n \approx 1.3 \times 1 0^{11}$ を超える $r$ が要り、係数1個が約45キロバイトなので、多項式を1つ書き留めるだけで約6ペタバイトになる（当サイトの見積もり）。（出典: The Prime Pages「Elliptic Curve Primality Proof」・「R(109297)」）
2026年ラヘレ・ジャラリ（バース大学）とオンドジェイ・イェジル（カレル大学）: AKSの正しさを、有界算術の体系 $T_{2}^{count}$ の中で証明し、『Forum of Mathematics, Sigma』に発表した。途中では、フェルマーの小定理を多項式に広げた形を公理として置き、のちにそれが体系の中で証明できることを示している。 $r$ の大きさを抑えるのに使う最小公倍数の評価 $lcm (1, \dots, 2 n) \geq 2^{n}$ も、さらに弱い体系 $S_{2}^{1}$ で証明した。（出典: Jalali, Ježil「Feasibility of Primality in Bounded Arithmetic」arXiv:2504.17041、Forum Math. Sigma 14 (2026), e49）

561は今も、互いに素などの底で試しても、フェルマーの判定に素数と答えさせる。それでも $(X + 1)^{561}$ を $X^{3} - 1$ で割れば、374という係数が残る。

参考文献

M. Agrawal, N. Kayal, N. Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, 781-793. 原稿は2002年8月6日付の版と最終版。
W. R. Alford, A. Granville, C. Pomerance, "There are infinitely many Carmichael numbers", Annals of Mathematics 139 (1994), 703-722. R. D. Carmichael, "Note on a new number theory function", Bulletin of the AMS 16 (1910), 232-238. A. Korselt, "Problème chinois", L'Intermédiaire des mathématiciens 6 (1899), 142-143.（フェルマーの1640年の手紙は2の序文、コルセルトの書誌は2の文献表による）
G. L. Miller, J. Comput. System Sci. 13 (1976), 300-317. M. O. Rabin, J. Number Theory 12 (1980), 128-138. R. Solovay, V. Strassen, SIAM J. Comput. 6 (1977), 84-86. L. M. Adleman, C. Pomerance, R. S. Rumely, Annals of Mathematics 117 (1983), 173-206.（書誌は1の文献表による）
H. W. Lenstra Jr., C. Pomerance, "Primality testing with Gaussian periods", J. Eur. Math. Soc. 21 (2019), 1229-1269. C. Pomerance, "Primality testing: then and now"（2018年の講演資料）.
NIST, FIPS 186-5 Digital Signature Standard（DSS）（2023年2月3日）, Appendix B.3, Table B.1.
N. Saxena, Résumé. M. Agrawal, Awards & Fellowships・Students. EATCS, Gödel Prize.
R. Baillie, A. Fiori, S. S. Wagstaff Jr., Math. Comp. 90 (2021), no. 330. R. Jalali, O. Ježil, Forum of Mathematics, Sigma 14 (2026), e49. The Prime Pages, R(109297)（2025年5月26日登録）.

注

英文は、クヌース『The Art of Computer Programming』第2巻の訳を、2002年8月6日付の原稿が引いたもの。和訳は当サイトによる。原文は1801年の『整数論の研究（Disquisitiones Arithmeticae）』にある。 ↩

AKS素数判定法

1801年の言葉で始まる原稿

561は素数のふりをする

係数がnで割り切れるとき

素数のべきしか通れない

r個の位置に折りたたむ

鍵の素数は確率で選ぶ

係数と位数を手で数える

例題 1基本5と6の行の係数

例題 2基本561がだます理由

例題 3入試rを探す

例題 4難関素数のべきの二項係数

例題 5大学r = 2の判定を通る合成数

乱数と予想と時間の条件

nを選び、3つの判定にかける

決定的な判定が届く先

速さの証明と、巨大な素数の証明書

参考文献

注

タグ

同じタグを持つ公式

姉妹サイト