数理解析研究所講究録
第 1572 巻 2007 年 1-10

1Grantham’s problem
篠原直行

NAOYUKI SHINOHARA*

CREST JST/立教大学
CREST JST/RIKKYO UNIV.

Abstract
現在, 任意に与えられた自然数
案されているが, 計算量評価がが素数であるか否かを効率よく判定するアルゴリズムがいくっか提より小さく, かつ, 合成数を必ず「合成数である」 と判定できるアルゴリズムは知られていない. したがって, 計算量評価が小さく判定結果も常に正しいアルゴリズム$n$$\mathcal{O}((\log n)^{5})$を構築することがこの分野において最終的な課題とされる.
本稿では, この課題の達成に重要な意味を持つ Grantham の問題に関するいくつかの結果を紹介する.
本稿は, この最終躁題を達成する上で必要となるであろう, 既存のアルゴリズムの長所と短所, 著者の研究の方向付け, 現在までの成果に関する概説である.

1

序論

1.1

素数判定アルゴリズム

素数判定アルゴリズムとは, 任意に与えられた自然数が素数であるか否かを判定するアルゴリズムであり,その結果は確率的である. つまり, まれに合成数を合成数と判定できない場合が存在する. それは, この種のアルゴリズムが$r_{n}$

が素数であるならば,$n$に関する計算可能な条件が成り立っ」 という定理の対偶を用いるからである.

例えば, Fermat test は下にあげる Fermat の小定理に基づいた素数判定アルゴリズムである.
定理 1.1. $n$ は素数とし,$a$は $gcd(a,n)=1$なる整数であるとする. このとき次の式が成り立っ.

$a^{n-1}\equiv 1$$(mod n)$.

従って, Fermat test は定理 1.1 の対偶を利用する, つまり与えられた自然数
に選んだ

$a$

(1)

$n$

と $gcd(a, n)=1$ なる適当に対して (1) が成り立っかを見るわけである. もし (1) が成り立たなければ $n$ は合成数である

ことがただちにわかる. ただ, ここで注意しなければならないのは, (1) が $n$ に対して成り立ったとしても$n$が必ずしも素数であるとは限らない点である.
例えば $2^{S41-1}\equiv 1(mod 341)$ であるが $341=11\cdot 31$ より素数ではない. このように合成数でありながら素数判定アルゴリズム $T$ で合成数と判定されないものを $T$-擬素数と呼ぶ. さらに, Fermat test のように, 与えられたパラメータ $P$ によって結果が異なる場合, それは $P$ に対する T 擬素数と呼ばれる. (上の例の場合は, 341 は 2 に対する Fermat 擬素数であるという. )素数判定アルゴリズムには, Strong Fermat test (Miller-Rabin test) [1], Quadratic IFtobenius test [1] な
ど, 計算量評価が $O((\log n)^{3})$ と小さいものが多いことがその特徴の一つにあげられる.
’hnhr@tv8 rikkyo. ne.jp

2
12

素数証明アルゴリズム

素数性を判定するもう一つの種のアルゴリズムに素数証明アルゴリズムがある. 先に述べた素数判定アル

ゴリズムとの違いは, 判定された結果が常に正しい, つまり素数証明アルゴリズムをパスしたものは必ず素数であるという点である. この意味で素数証明アルゴリズムは素数判定アルゴリズムより上位であるといえる. しかしながら, 計算量の点では素数判定アルゴリズムの方が素数証明アルゴリズムより優れているといえる. その理由を少し説明しよう.

Eratosthenes の鯖 (試し割) は非常にシンプルな索数証明アルゴリズムである. このアルゴリズムでは,与えられた自然数
が而以下の全ての素数に対して割り切れるかどうかをみるため, $O(\sqrt{n}/\log n)$ 回の割り算を必要とする. (この評価は素数定理より得られる. ) 従って, bit 演算の評価は $O(\sqrt{n}\log n)$ とな$n$り, 実用的であるとは言えない.

(素数性を判定するアルゴリズムの計算量は $O((1ogn)^{6})$ 以下であることが望まれる. )また, 同じく素数証明アルゴリズムである $n-1$ 法は, 判定対象を としたときに $n-1$ が二つ以上の大きな素因子を持てば, の素因数分解と同等の計算を必要とすることになるため, 当然ながらその計算量評
価も素因数分解を考えた場合のものと等しくなり log 多項式時間とはならない.
$n$

$n$

$n$

に対して計算量評価が log 多項式
近年, 注目を浴びた AKS 法 [2] は, 任意に与えられた判定対象
時間であらわされる現在唯一の素数証明アルゴリズムである. しかし, このアルゴリズムも計算量評価が$O((\log n)^{5})$ 以下ではないため実用的なアルゴリズムとは言い難いものである.
他にも, 楕円曲線法 $[3],[4]$ , Jacobi sums test [5] など, 数値実験により計算量が $O((\log n)^{5})$ を下回ると予想されるものも存在するが, どれも未解決問題を抱え論理的に証明を与えられているものは知られていない.
$n$

$n$

1.3

素数判定アルゴリズムから素数証明アルゴリズムへの改良

素数判定アルゴリズムを改良することにより, 素数証明アルゴリズムを構築することは非常に興味深く有効な手法である. その一つに extended Riemann hypothesis と strong Fermat test を組み合わせたもの [6]がある. ただ, 残念なことに extended Riemann hypothesis は未解決であるため, この手法は素数証明アル

ゴリズムとしては認められていない.
定理 1.2. extended Riemann hypothesis が成り立っと仮定する. このとき $n$ が奇合成数であるならば,が区間
strong Femat test で $n$ を合成数と判定できる $gcd(a,n)=1$ なるパラメータ$a\in \mathbb{Z}$$[2, 2(\ln n)^{2}]$内に必ず存在する.

この定理 12 により, パラメータの変換は高々 $2(\ln n)^{2}$ 回であるため, 計算量評価は $O(2(\log n)^{2}\cdot(\log n)^{3})=$$O((\log n)^{5})$ となる.
このようにパラメータの選び方に条件を付け加えることで, quadratic IFlirobenius test から素数証明アル
ゴリズムを構築することを試みるのは興味深いことである. Quadratic Firobenius test とは, J. Grantham
によって提案された素数判定アルゴリズムで, 次の定理によるものである.
定理 1.3 $a,$る.

$b$

は $\Delta=a^{2}-4b\neq 0$ を満たす整数とする. また素数 $n$ は $gcd(n, 2b\Delta)=1$ を満たすものとす

このとき次の合同式が成り立っ.

$x^{n}\equiv\{\begin{array}{ll}a-x (mod (x^{2}-ax+b, n)), ( (\frac{\Delta}{n})=-1 \text{のとき}),x (m d (x^{2}-ax+b,n)), ( (\frac{A}{n})=1 \text{のとき})\end{array}$(2)

3
この定理からわかるように quadratic Robenius test は Robenius autmorphism の性質を用いたものであ

さらに, 多項式剰余環 $(\mathbb{Z}/n\mathbb{Z})[x]/(x^{2}-ax+b)$ 上での計算を行うことからわかるように, 整数の組 $(a, b)$

る.

は Frobenius test におけるパラメータである.

最終的に我々が知りたいのは, 任意に与えられた合成数 が回以下のパラメータ変換で必ず(2) が成り立たないようなパラメータ $(a, b)$ を得る方法である. そのためには, まず合成数 が Frobenius
擬素数となるときのパラメータ $(a, b)$ との関係を知ることが重要である. [7] では, Robenius 擬素数を$\mathcal{O}((\log n)^{2})$

$n$

$n$

$n$

五つの場合に分類し, それぞれに対する同値条件, つまり $n,$の関係を明らかにした.
また, Grantham の問題 [1] は, 一組のパラメータ $(-5,5)$ で $n\equiv\pm 2(mod 5)$ なる全ての自然数
$a,$

$b$

$n$

に対

して quadratic Frobenius test は素数証明アルゴリズムになる可能性があることを示唆している.

本稿では 2 つの相異なる奇素数の積の場合について Grantham の問題を検証して得られた結果について
紹介する.

2

Quadratic Frobenius 擬素数
この章では, Quadratic Frobenius test に関するいくつかの性質などを紹介する.

2.1

Quadratic Robenius test

Quadratic IFbobenius test は, J. Grantham [1] によって提案された, 定理 13 に基づく素数判定アルゴリ
ズムである. ここで, $n$ が $gcd(n, 2b\Delta)=1$ でありながら式 (2) を満たすものが存在し, それを $(a, b)$ に対する quadratic Frobenius 擬素数と呼ぶ. 以後, 簡単のため単に $(a, b)$ に対する Robenius 擬素数とよび,

fpsp $(a, b)$ とかく.
[1] の定義では $\Delta=a^{2}-4b$ は平方数でないとしているが,が平方数であるときは, Frobenius test がFermat test と常に同等となるだけである. また,の任意の素因子が平方数でなくても, 判定対象
を法としてが平方剰余であれば, Robenius test は Fermat test と同等になる. 従って, 本稿の定義ではとしているのは Robeniu8test でが平方数であるか否かを区別しないものを採用した. ただ,$gcd(n, 2b\Delta)=1$ という条件を使うからである.
以後は考えやすくするため次の補題 21 の条件 (3) に注目する.
$\Delta$$\Delta$$n$$P$$\Delta$$\Delta$$\Delta\neq 0$

補題 2.1.

$a,$$b$は $\Delta=a^{2}-4b\neq 0$ を満たす整数とする.

このとき $gcd(n, 2b\Delta)=1$ なる合成数 $n$ がfPsp $(a, b)$ であることと以下の合同式が成り立つことは同値である.

$x^{n-()} \bigwedge_{n}$$\equiv$$\{\begin{array}{ll}b (mod (x^{2}-ax+b,n)) ( (\frac{\Delta}{n})=-1 \text{のとき}),1 (mod (x^{2}-ax+b,n)) ( (\frac{\Delta}{\mathfrak{n}})=1 \text{のとき}).\end{array}$

(3)

2.2

Robenius 擬素数と円分多項式

先に述べたように, fPsp $(a, b)$ となる奇合成数とそのときの整数の組 $(a, b)$ との関係を知りたいわけであるが, 素幕環における円分多項式の “因子” の性質を考えることによりその関係が明らかになる. (ただ, 素4幕環$\mathbb{Z}/p^{e}\mathbb{Z}$は $e>1$ のときは整域ではないため, 素幕環での多項式の “既約性” や “因子” の取り扱いには一般には注意が必要である. しかし, 本稿で取り扱う内容においては通常の規約性や因子と同様に考えても問題はない. 従って以後は単に因子と書く. )Robenius test による の判定結果は $(\mathbb{Z}/n\mathbb{Z})[x]/(x^{2}-ax+b)$ における の位数に左右される. 当然
$x$

$n$

ながら $x$ は有限位数をもちそれを $M$ とし, 第 $m$ 円分多項式を $\Phi_{m}(x)$ と書くこととすれば,$x^{M}-1= \prod_{m|M}\Phi_{m}(x)---:0$

が $n$ の任意の素幕因子$p^{\epsilon}$$(mod (x^{2}-ax+b,p^{e}))$に対して成り立っ. っまり, $x^{2}-ax+b$ は$\mathbb{Z}/p^{e}\mathbb{Z}$において $x^{M}-1$ の因子であり, さらに $x^{M}-1$ が円分多項式の積でかけることに注目したわけである.
における第 $m$ 円分多項式 $\Phi_{m}(x)$ の因子は, Hensel の補題によって,結論から先に言うと,$\mathbb{Z}/p^{e}\mathbb{Z}$$F_{p}$

上の因子からリフトアップしたものである.

Frobenius 擬素数と円分多項式の関係に関する詳しい内容は [7] を参照していただきたい. ここでは, 本
稿で使われる定義や記号を紹介する.
何度も言うように, $e>1$ のとき$\mathbb{Z}/p^{\epsilon}\mathbb{Z}$は整域ではない. しかし, モニックな多項式については既約性などが以下のように自然に定義できる.

定義 2.2. $g(x)$ と $h(x)$ はモニックな整数係数多項式であるとする. $h(x)\equiv 0(mod (p^{e},g(x)))$ であると上で $h(x)$ をわりきる” といい, $g(x)|_{P}\cdot h(x)$ とかく.
はき,${}^{t}g(x)$$\mathbb{Z}/p^{e}\mathbb{Z}$

定義 23. $g(x)$ をモニックな整数係数多項式であるとする. このとき,$g(x)\equiv s(x)t(x)$$(mod p^{\epsilon})$なる整数係数多項式 $s(x),t(x)$ が存在しないとき,$x\in(\mathbb{Z}/p^{e}\mathbb{Z})[x]/(f(x))$

and $0<\deg s<\deg g$ .

$g(x)$は$\mathbb{Z}/p^{e}\mathbb{Z}$

上既約である “ という.

の位数は, $f(x)$ もしくはその一次因子がどの円分多項式割り切るかを決める重要な役割を持っ.
定義 24$\alpha\in(\mathbb{Z}/p^{e}\mathbb{Z})^{*}$の位数を$ord(p^{e}, \alpha)$と書く.

言い換えれば, $\alpha^{ord(p,\alpha)}=1$ かつ $1<\forall k\leq ord(p^{\epsilon}, \alpha)-1$ に対して
定義 25

$g(x)\in(\mathbb{Z}/p^{\epsilon}\mathbb{Z})[x]$はモニックで$(\mathbb{Z}/p^{e}\mathbb{Z})$$\alpha^{k}\neq 1$

である.

上で既約であるものとする. このとき,$\alpha\in((\mathbb{Z}/p^{e}\mathbb{Z})[x]/(g(x)))^{*}$の位数を$ord(p^{\epsilon},g(x),$$\alpha$).

とかく.

言い換えると, $\alpha^{ord(p,g(x),\alpha)}=1$ かつ $1<\forall k\leq ord(p^{\epsilon}, g(x),$ ) $-1$ に対して$\alpha$$\alpha^{k}\neq 1$

である.

5
2.3

IFhrobenius 擬素数と ICF

この節では Frobenius 擬素数の分類と, 与えられた $(a, b)$ に対して奇合成数$n$が各種の Frobenius 擬素数になるときの同値条件 (ICFl) から (ICF5) を紹介する.
$1\leq a,$ $b\leq 10$

かつ $\Delta=a^{2}-4b$ が平方数にならない組 $(a, b)$ それぞれに対して, 区間 $[50000, 10^{8} +50000]$

内のすべての奇合成数に対して Robenius test を行った. その結果, fPsp $(a, b)$ の個数が 1000 を超えるの特徴がわかった. それは, $b=1$ となる場合の $(a, b)$ か Lucas sequence が退化数列となる場合の$(a, b)$ である. 後者の原因は Lucas test の性質によるものである. さらに, $b=-1$ となる場合の同様の実験結果では, fPsp $(a, -1)$ の個数は 500 個を超えることがわかった. これらの $(a, b)$ に対する Robenius 擬素数の個数は, 他の $(a, b)$ に対して非常に大きなものである. またこれらの実験結果から,
かつ$(a, b)$$( \frac{\Delta}{n})=-1$$b\neq\pm 1$. なる $n=fpsp(a, b)$ は 291409 のみであることは興味深い事実である.

これらの結果から, $b=\pm 1$ との値に注意して, Robenius 擬素数を以下の五つに分類した. 各種のRobeniu8 擬素数は互いに背反である.
$( \frac{\Delta}{n})$定義 2.6 (Frobenius pseudoprime of the flrst type).

$n$は fPsp $(a, b)$ で, さら [こ $n$ の全ての素因子に対して $(_{p}^{A})=1$ が成り立っものとする. このとき, $n$ を $(a, b)$ に対する Frobeius pseu&
first tyPe とよび, さらに fPspl $(a, b)$ とかく.

$P$

定義 2.7 (libobenius pseudoprime of the second type).
1 つの素因子$p$に対して$( \frac{\Delta}{p})=-1$$n$が成り立っものとする.

$i\pi oe$of theは fPsp $(a, b)$ で, さらに $n$ の少なくとも

このとき, $n$ を $(a, b)$ に対する Frobeius

pseud 化 prime of the second tyPe とよび, さらに $fpsp2(a, b)$ とかく.

定藤 2.8 (Frobenius pseudoprime of the third type). $n$ は fPsp $(a, b)$ で, さらに $b\equiv 1(mod n)$ と$( \frac{\Delta}{n})=-1$が成り立っものとする. このとき,$n$を $(a, b)$ に対する Frobeius pseudoprime of the third typeとよび, さらに $fpsp3(a, b)$ とかく.

定義 2.9 (Frobenius $pseudopr\ddagger me$ of the fourth type).
が成り立つものとする. このとき,type とよび, さらに $fpsp4(a, b)$ とかく.と$( \frac{\Delta}{n})=-1$

$n$

$n$

は fpsp $(a, b)$ で, さらに $b\equiv-1(mod n)$

を $(a, b)$ に対する Frobeius pseudoprime

定義 2.10 (litobenius pseudoprime of the fifth type).

$n$of the fourthは fpsp $(a, b)$ で, さらに $b\neq\pm 1(mod n)$と $( \frac{\Delta}{n})=-1$ が成り立つものとする. このとき, $n$ を $(a, b)$ に\star ‘tt る Frobeius $pseud_{W}$ imeof the fifth typeとよび, さらに $fpsp5(a, b)$ とかく.
知りたいのは, 与えられた奇合成数 $n$ が fPsp $(a, b)$ となる $(n, a, b)$ の組の条件である. そのような条件を以下のように定義した.

定義 2.11 (Inefflcasious conditions of Frobenius test $(ICF)$ ). いくっかの条件を満たす全ての数がMben 伽擬素数となるものが存在し, それらの条件を哩 nefficacious Conditions of Robenius test $(ICF)’$とよぷ.

例えば, $(a, b)=(1,1)$ かつ合成数 が $gcd(n, 6)=1$ を満たすという条件は ICF である. なぜならば,その条件の下では が fPsp $(1,1)$ だからである.
ここでは, 各タイプの lobenius 擬素数の同値条件をそれぞれ, ICFl から ICF5 までで与える.
$n$

$n$

6
定義 2.12 (ICF of the first type (ICFl)). $a,$ は整数で $f(x)=x^{2}-ax+b$ とし, $n$ は奇合成数でそ: とあらわす. このとき $(n, a, b)$ に関する以下の条件一組を “ICFl” とよぶ.の素因数分解を$b$$n= \prod_{i=1}^{k}p_{i}^{e}$$(ICF1-1)$ 各 $i\in[1, k]$ に対して, $f(x)\equiv(x-c_{i,1})(x-q_{2})(mod p_{i}^{e_{t}})$ かっ果,1 $\neq c_{i,2}(mod p_{i}^{e:})$ で.
$x-$ 砺,1

をみたす自然数臓,$m_{i}’$が存在する.

$(ICF1-2)m=lcm(m_{1}, m_{1}’, \ldots, m_{k}, m_{k}’)$

奇合成数

$n$

$x-$ 砲,2 $|_{p};:\Phi_{m_{l}’}(x)$$|_{p^{\epsilon_{i}}}:\Phi_{m}.(x),$に対して $n\equiv 1(mod m)$ .

が $fpsp1(a, b)$ であることと, $(n, a, b)$ に対して ICFl が成り立つことは同値である.

定義 2.13 (ICF of the second type (ICF2)). $a,$

その素因数分解を$n= \prod_{i=1}^{k+\ell}p_{i}^{e}$$b$は整数で $f(x)=x^{2}-ax+b$ とし, $n$ は奇合成数で‘とあらわす. このとき $(n, a, b)$ に関する以下の条件一組を“ICF2” とよぶ.

(ICF2–1) 各 $i\in[1, k]$ に対して, $f(x)$ は(ICF2–2) $\sum_{i=1}^{k}e_{i}\equiv 0(mod 2)$ が成り立っ.

上既約で, $f(x)|_{p_{i}^{*}}:\Phi_{m}(x)$ なる$\mathbb{Z}/p_{\dot{v}}^{e\iota}\mathbb{Z}$(ICF2-3) 各 $i\in[k+1, k+\ell]$ に対して,$f(x)\equiv(x-q_{1})(x-c_{i,2})(mod p_{\dot{\iota}}^{c_{\mathfrak{i}}})$$m_{j}$が存在する.

かつ果,1 $\neq c_{t,2}(mod p_{i}^{e:})$で,$x-$ 傷,1 $|_{p}*:\Phi_{m}:(x),$ $x-c_{j,2}|_{p}::\Phi_{m’}.(x)$なる自然数$m_{i},$$m_{i}’$が存在する.

(ICF2-4) $m=lm(m_{1}, \ldots, m_{k}, m_{k+1}, m_{k+1}’, \ldots, m_{k}+\ell, m_{k+\ell}’)$ に対して $n\equiv 1(mod m)$ が成り立っ.
奇合成数 $n$ が $fpsp2(a, b)$ であることと, $(n, a, b)$ に対して ICF2 が成り立つことは同値である.
定義 2.14 (ICF of the third tyPe (ICF3)). $a,$の素因数分解を$b$は整数で $f(x)=x^{2}-ax+b$ とし, $n$ は奇合成数でそ‘とあらわす. このとき $(n, a, b)$ に関する以下の条件一組を$n= \prod_{i=1}^{k+t}p_{i}^{e}$(ICF3-1) 各 $i\in[1, k]$ に対して, $f(x)$ はなる自然数 $m_{i}>2$ が存在する.

$\mathbb{Z}/p_{i}^{\epsilon}$‘$\mathbb{Z}$上既約で, さらに $p_{i}\equiv-1(mod m\iota),$${}^{t}ICF3’’$とよぶ.

$f(x)|_{p_{i^{5}}}\cdot\Phi_{m:}(x)$(ICF3–2) $\sum_{i=1}^{k}e_{i}\equiv 1(mod 2)$ が成り立っ.
(ICF3-3) 各 $i\in[k+1, k+\ell]$ に対して, $f(x)\equiv(x-c_{1})(x-c_{i}^{-1})(mod p_{i}^{e:})$ で, さらに $x-c_{1}|_{p}::\Phi_{m:}(x)$なる自然数 $m:>2$ が存在する.
(ICF3-4) $m=lcm(m_{1}, \ldots,m_{k+\ell})$ に対して $n\equiv-1(mod m)$ が成り立っ.
奇合成数

$n$

が $fpsp3(a, b)$ であることと, $(n, a, b)$ に対して ICF3 が成り立つことは同値である.

定義 2.15 (ICF of the fourth (ICF4)). $a,$
因数分解を

$n= \prod_{|=1}^{k+\ell}p_{i^{:}}^{e}$は整数で $f(x)=x^{2}-ax+b$ とし, $n$ は奇合成数でその素とあらわす. このとき $(n, a, b)$ に関する以下の条件一組を(ICF4–1) 各 $i\in[1, k]$ に対して, $f(x)$ は$s_{i}\geq 2,$を満たす自然数$b$$m_{i}=2^{*}\cdot r_{i}$$\mathbb{Z}/p_{\dot{\iota}}^{G:}\mathbb{Z}$$p_{i}\equiv 2^{e:-1}r_{i}-1$が存在する. ただし$r_{i}$

“ICF4

$n$

とよぶ.

上既約で, $f(x)|_{p^{\epsilon}}.:\Phi_{m}:(x)$ と$(mod m)B_{1’}\supset m_{i}\neq 4$は奇数とする.

が成り立つ.
(ICF4–2)
各$i\in[k+1,k+\ell]$に対して, $f(x)\equiv(x-c_{i})(x+c_{i}^{-1})(mod p_{i}^{\epsilon:})$ で, さらに $x-c_{*}\cdot|_{p}::\Phi_{m}:(x)$(ICF4-3)が存在する.
なる自然数(ICF4-4) $m=lcm(m_{1}, \ldots, m_{k+\ell})$ に対して, $n\neq-1(mod m),$ $2(n+1)\equiv 0(mod m)$ 力\leq 成り立っ.
$\sum_{\mathfrak{i}=1}^{k}e_{1}\equiv 1(mod 2)$$m_{i}$

奇合成数 $n$ が $fpsp4(a, b)$ であることと, $(n, a, b)$ に対して ICF4 が成り立っことは同値である.

7
定義 2.16 (ICF of the fifth type (ICF5)). $a,$の素因数分解を$n= \prod_{i=1}^{k+\ell}p_{i}^{e_{i}}$$b$は整数で $f(x)=x^{2}-ax+b$ とし,$n$とあらわす. このとき $(n, a, b)$ に関する以下の条件一組をは奇合成数でそ${}^{t}ICF5$’ とよぶ.

$(ICF5-1)$ 各 $i\in[1, k]$ に対して, $m_{i}|gcd(p_{i}n-1,p_{i}^{2}-1),$が存在する.
\dag er $p_{i}-1$ なる自然数$(ICF5-2)$ 各 $i\in[1, k]$ に対して, $f(x)$ は
さらに
上既約で,
が成り立っ.
$m_{i}$$\mathbb{Z}/p_{i}^{e}\mathbb{Z}$$m_{i}$$f(x)|_{p^{\epsilon_{\mathfrak{i}}}}\dot{.}\Phi_{m_{i}}(x)$$(ICF 5-3)\sum_{i=1}^{k}e_{i}\equiv 1(mod 2)$ が成り立っ.

$(ICF5-4)$ 各 $i\in[k+1, k+t]$ に対して, $m_{i}|gcd$ ($n^{2}-1$ ,Pi–l), $m_{i}\{n-1$ をみたす自然数$m_{i}$が存在する.

$(ICF5-5)$ 各 $i\in[k+1, k+\ell]$ }こ対して, $f(x)\equiv(x-c_{i})(x-c_{i}^{n})(mod p_{i}^{e\iota})$ となり, さらに $f(x)|_{p}*:\Phi_{m:}(x)$なる整数傭が存在する.
$(ICF5-6)b\neq\pm 1(mod n)$ が成り立っ.

奇合成数

3

$n$

が $fpsp5(a, b)$ であることと, $(n, a, b)$ に対して ICF5 が成り立っことは同値である.

Grantham の問題と ICF5
Ftobenius test から素数証明アルゴリズムを構築する上で非常に興味深い以下のような問題がある.

問題 3.1 (Grantham の問題) $n\equiv\pm 2(mod 5)$ なる奇合成数 $n$ で $fpsp5(-5,5)$ となるものは存在す
るか.
と $n_{j}\equiv\pm 1(\bm{m}od 5)$ なる素数
Dirichlet の算術級数定理より, $n_{i}\equiv\pm 2(mod 5)$ なる素数の存在
比率は等しい. 従って, Grantham の問題の条件を満たすような合成数が存在しなければ, Robenius test は半分の素数に対する計算量 $O((\log n)^{3})$ の素数証明アルゴリズムに改良できることになる.
$n_{i}$

3.1$n$

ICF5 と$n_{j}$$( \frac{b}{n})=-1$

が $n\equiv\pm 2(mod 5)$ を満たすならば, $( \frac{5}{n})=-1$ が成り立っ. このとき, さらに $n$ が fPsp $(-5,5)$ である場合について考えることから, $\Delta=b=5$ より,$n$が $fpsp5(a, b)$ でかつ $( \frac{b}{n})=-1$ なる場合について考える必要がある. この節では後で必要となる二つの結果を紹介する.

補題 3.2 $n$ は $fpsp5(a, b)$ であるものとする. また$P$

は $n$ の素因子で$( \frac{\Delta}{p})=1$を満たすものとする.

このとき$( \frac{b}{p})=1$.

補題 33 $\Delta=a^{2}-4b\neq 0$ で $f(x)=x^{2}-ax+b$ とする. また, 奇素数$q$のとする. このとき, $x\in(\mathbb{Z}/q\mathbb{Z})[x]/(f(x))$ の乗法位数を $m$ とし, 自然数

くとき, $m$ は$2^{s}$は$s$$( \frac{\Delta}{q})=(\frac{\Delta}{q})=-1$

と奇数

$t$

を満たすも

で $q^{2}-1=2t$と書で割り切れる.

ここで, $q^{2}-1$ は必ず 8 で割り切れることから次の系を得る.

系 3.4 $\Delta=a^{2}-4b\neq 0$ で $f(x)=x^{2}-ax+b$ とする. また, 奇素数とする. このとき$f$$x\in(\mathbb{Z}/q\mathbb{Z})[x]/(f(x))$$q$は$( \frac{\Delta}{q})=(\frac{\Delta}{q})=-1$の乗法位数 $m$ は 8 で割り切れる.

を満たすもの

8
3.2$n=pq$ 型の Grantham の問題

Grantham の問題を, 最もシンプルと思われる, 二っの相異なる奇素数
Grantham の問題では $fpsp5(-5,5)$ なるものを考えている.
事実 3.5$n$がfPsP $(a, b)$ ならば$n$$p,$ $q$の積$n$にっいて考えてみる.

は fPsp $(-a, b)$ である.

著者が持っている数値実験のデータの都合により, Grantham の問題を $fpsp5(5,5)$ の場合に置き換えて議論を進めていく.

$f(x)=x^{2}-5x+5$ とし, $n=pq$ は $fpsp5(5,5)$ で奇素数 $p,$$q$はそれぞれ $( \frac{5}{p})=1,$$( \frac{5}{q})=-1$を満たすものとする. 従って,
$p\equiv\pm 1$$(mod 5)$

$q\equiv\pm 2$$(mod 5)$が成り立っている. また $\Delta=5$ であることから, $f(x)$ は

$P$

,

(4)
(5)

を法として可約であり,$q$を法としたときは既, c2 が存在して $f(x)\equiv(x-c_{1})(x-c_{2})(mod p)$ と書ける.
さて, ここから $n,$ $a,$ に対して ICF5 の条件を検証していく.
まず (ICF5–3) と (ICF5–6) は明らかに成り立っ.

約である. 従って, ある整数

$c_{1}$$b$

次に (ICF5–2) については, 先ほど述べたように $f(x)$ が

実は $m_{q}=ord(q, f(x),x)$ とすれば $f(x)$ は$q$を法として第$F_{q}$$m_{q}$

上既約であることは問題ない. さらに,
円分多項式を割り切る. 従って$\Phi_{m_{q}}(x)$(ICF5–1) において, このがが条件を満たしているかどうかが論点となる.
$m_{q}|q^{2}-1,$
二次の規約因子に因数分解されることと\dag er $q-1$ は同値であることから,$\Phi_{m_{q}}(x)$$m_{q}$$F_{q}$$m_{q}|$$m_{q}$

上で相異なるqn-l, っまり(6)

$m_{q}|p-1$が成り立たなければならない.
残るは (ICF5-4) と (ICF5-5) の確認である. (ICF5-5) よりとすると $f(x)$ は$P$を法として第$m_{p}$

円分多項式$c_{1}^{q}\equiv c_{2}$$\Phi_{m_{p}}(x)$$(mod p),$(mod P) で, $m_{p}=ord(p, c_{1})$を割り切る. これらの条件は, 実は$c_{2}^{q}\cong c_{1}$$c_{1}^{n}\equiv c_{2}$(7)$(mod p)$と同値である. (ICF5–4) から, $m_{p}|gcd(n^{2}-1,p-1)=gcd(q^{2}-1,p-1),$$m_{p}$\dag er $q-1$ が成り立たなければならないことになるが, この場合は必ず成り立つので問題ない. 理由は次に述べるとおりである.
$(x-c_{1})(x-c_{2})$が $P$ を法として $\Phi_{m_{p}}(x)$ を割り切るということは, $\Phi_{m_{p}}(x)$ が $P$ を法として相異なる一次多項式の積に因数分解されることを意味する. (であることから $c_{1}\not\equiv c_{2}(mod p)$ であることに注意) 従って, この場合,
は $p-1$ を割り切ることとなる.
\dag er $q-1$ については, 逆に $m_{p}|q-1$ と仮定すると $c_{2}\equiv c_{1}^{q}\equiv c_{1}(mod p)$ となり矛盾が生じる. そして $m_{p}|q^{2}-1$ については (7) が成り立てば明らかに成り立っ.
最後に\rangle
は 8 で割り切れなければならい. さらに $m_{q}|p-1$であることから, 系 3.4 より$( \frac{\Delta}{p})\neq 0$$m_{p}$$m_{p}$$( \frac{b}{n})=(\frac{5}{n})=1$$m_{q}$と $p\equiv\pm 1(mod 5)$ の条件から$p\equiv 1,9$を得る.

以上より次の定理を得る.

$(\bm{m}od 40)$(8)

9
定理 3.6 $n=pq$ は $fpsp5(5,5)$ であるとし,$( \frac{5}{p})=1$と$( \frac{5}{q})=-1$が成り立っものとする.

$f(x)=x^{2}-5x+5\equiv(x-c_{1})(x-c_{2})(mod p)$ とし, $m_{q}=ord(q, f(x),$ $x$ )$,$$m_{p}=ord(p, c_{1})$さらに,とおく. このとき以下の条件が成り立っ.

(I)$p\equiv 1,9$(II)

$m_{q}|p-1$ ,(III)$(mod 40),$$(mod p)$ and$c_{1}^{q}\equiv c_{2}$$(mod 5)$ ,$q\equiv 2,3$$(mod p)$ .

$c_{2}^{q}\equiv c_{1}$

この定理の条件を満たす素数の組 $(p, q)$ が存在すれば, $pq$ が Grantham 問題の条件を満たす Robenius
擬素数となるわけである.
では, そのようなそのような素数の組を探すことを考えよう.
定理 36 の (I), (III) より,$P$に関する条件がに $P$ の候補となりうる素数を探すのが望ましい.

として $f(x)=x^{2}-5x+5$ を因数分解する.
$(x-c_{1})(x-c_{2})$のように因数分解され, これはに関する条件より厳しいと考えられる. 従って, 最初を法を探し,
つまり, $P\equiv 1,9(mod 40)$ なる素数$q$$m_{p}$$(mod p),$を満たすような$t$が存在するか否かを$\neq$であることから, $f(x)$が $p-1$ を割り切ること意味する. ここでを満たすかどうかをチェックしなければならないのだが, この時点では$c_{1}^{t}\equiv c_{2}$

$P$

$P$

このとき, $P\equiv\pm 1(mod 5)$$c_{2}^{t}\equiv c_{1}$$q$$c_{1},$$c_{2}$

は必ずが (III)が未定であるため, 代わりに

(9)$(mod p)$

エックする. 存在しなければ, 最初のステップへもどり

$P$

を選びな

おすことから始める.

ここまでで, に関する エックはすべて終了である. 次は,探すことになる. (III) と (9) より$\neq$$P$$q\equiv t$$p$$(mod m_{p})$に対して (I) から (III) を満たす素数

$q$

を

,

が成り立たなければならない. また (I) より $q\equiv\pm 2(mod 5)$ も満たさなければならない. もしここまでの条件を満たす$q$が存在しなければ最初のステップヘ) 存在するならばもちろん満たされなければ最初のステップヘ戻り, 成り立てば $p,$
以上よりアルゴリズムは以下のようになる.

$q$$m_{q}$を求めて $m_{q}\{p-1$ の確認を行う.

を返し, $n=pq$ が $fpsp5(5,5)$ となる.

アルゴリズム 3.7

1, $p\equiv 1(mod 40)$ なる素数 を求める.
2, $x^{2}-5x+5$ を を法として因数分解し $(x-c_{1})(x-c_{2})$ をえる.
3,$(mod p)$(mod p),$P$$P$$c_{1}^{t}\equiv c_{2}$を満たす整数4,5,$c_{1}\in F_{p}$$t$を求める. 存在しなければ 1 へ.

の乗法位数

$m_{p}$

を計算する.

$q\equiv t$を満たす素数$q$$c_{2}^{t}\equiv c_{1}$$(mod m_{p}))q\equiv\pm 2$を求める. 存在しなければ 1 へ.

を計算する.
6, $x\in F_{q}[x]/(f(x))$ の乗法位数
7, $m_{q}|p-1$ を満たせば $pq$ を返し, 満たさなければ $1\sim$ .
$m_{q}$$(mod 5)$

(10)

10
(8) を満たす $[0,10^{9}]$ 内の全ての素数 p に対して数値実験を行ったところ, 候補となりうるのは 521, 221401の二つのみであった. つまり, これらの素数を
とすると,
$P$

$p\equiv 1,9$$\exists t\in \mathbb{Z},$が成り立つ. 従って, あとは
数

$q$

$P$

$(mod 40)$ ,$c_{1}^{t}\equiv c_{2}$

と組をなす

$q$

$(mod p),$$c_{2}^{t}\equiv c_{1}$$(mod p)$.

は何かということになるが, 実は 521 や 221401 と組をなす素が存在しないことがわかる.

各 $(p, t, m_{p})$ は (521, 181, 260) と (221401, 17549, 36900) である. ここで, どちらの場合も $t\equiv\pm 1(mod 5)$% であることに気付く. これは (10) を満たす
従って次の定理を得る.

かつ 5

$|$

定理 38 $n=pq$ で,$fpsp5(5,5)$

4

$P$

と

$q$

はそれぞれ $( \frac{5}{p})=1,$

であるならば $p>10^{9}$$q$が存在しないことを意味する.

$( \frac{5}{q})=-1$を満たすものとする. このとき, もし $n$ がである$\blacksquare$まとめ
本稿では $n=pq$ 型の場合の $fpsp5(5,5)$ についてふれたが, 実験によりとなりうる候補の存在を確認することができなかった. 仮に存在したとしてもそれは極めてまれであると推測される. 今後の研究課題は,より広範囲で$P$の候補を探すこととなるが,

$q$

$P$

に関して絞り込みができる条件について考えることも重要で

ある.
$q$

に関する条件の考察は $n=q_{1}q_{2}q_{3}$ で $( \frac{\Delta}{q})=-1(i=1,2,3)$ について考える上で重要となる. 当然のことながら, $n=pq$ 型以外の場合でも ICF5 によって, $fpsp5(5,5)$ の素因子が持つ条件がわかり, それをもとに素因子の候補を計算することができる.

参考文献[1] R. Crandall and C. Pomerance. Lucas pseudoprimes, Pime Numbers (2001),$13\propto 140$.

[2] M. Agrawal, N. Kayal and N. Saxena. PRIMES is in $P$ , (2002).
[3] A. O. L. Atkin and F. Morain. Elliptic curves and primality proving, (1993).
[4] F. Morain, INRIA Research Report 911, (1988).
[5] L. Adleman, C. Pomerance, and R. Rumely. On distinguishing prime numbers from composite numbers.
Ann. of Math., 117 (1983), 173-206.

[6] E. Bach. Analytic Methods in the Analysis and Design of Number Theoretic Algorithms. A 1984
ACM Distinguished Dissertation. The MIT Press, (1985).
[7] N. Shinohara. Frobenius pseudoprimes and cydotomic polynomials., Math. Comp. (投稿中)[8] J. Grantham. A probable prime test with high confidence, J. Number Thmry, 72 (1998), 32-47.