ポックリントンのアルゴリズム

ポックリントンのアルゴリズムは、次の形式の 合同式を解く手法です

${\displaystyle x^{2}\equiv a{\pmod {p}},}$

ここで、xとaは整数であり、aは平方剰余です。

このアルゴリズムは、このような合同式を解く最初の効率的な方法の一つであり、1917年にHCポックリントンによって記述されました。 ^[1]

アルゴリズム

（注：特に明記されていない限り、すべては…を意味します。） ${\displaystyle \equiv}$ ${\displaystyle {\pmod {p}}}$

入力：

• p、奇数の素数
• a 、平方剰余となる整数${\displaystyle {\pmod {p}}}$

出力：

• x、を満たす整数。x が解の場合、- x も解であり、p が奇数なので、であることに注意してください。したがって、 1つの解が見つかった場合は、常に2番目の解が存在します${\displaystyle x^{2}\equiv a}$ ${\displaystyle x\neq -x}$

解法

ポックリントンはpについて 3つの異なるケースを分類します

最初のケース、 の場合、 のとき、解は です。 ${\displaystyle p=4m+3}$ ${\displaystyle m\in \mathbb{N} }$ ${\displaystyle x\equiv \pm a^{m+1}}$

2番目のケース、つまり、および ${\displaystyle p=8m+5}$ ${\displaystyle m\in \mathbb{N} }$

1. ${\displaystyle a^{2m+1}\equiv 1}$ 、解決策は です。${\displaystyle x\equiv \pm a^{m+1}}$
2. ${\displaystyle a^{2m+1}\equiv -1}$ , 2 は（二次）非剰余なので となる。これはとなることを意味し、は の解となる。したがって、または、yが奇数の場合は となる。${\displaystyle 4^{2m+1}\equiv -1}$ ${\displaystyle (4a)^{2m+1}\equiv 1}$ ${\displaystyle y\equiv \pm (4a)^{m+1}}$ ${\displaystyle y^{2}\equiv 4a}$ ${\displaystyle x\equiv \pm y/2}$ ${\displaystyle x\equiv \pm (p+y)/2}$

3番目のケースでは、 ならば と置くので、解くべき方程式は となります。試行錯誤で と を求め、が2次の非留数となる ようにします。さらに、 とします。${\displaystyle p=8m+1}$ ${\displaystyle D\equiv -a}$ ${\displaystyle x^{2}+D\equiv 0}$ ${\displaystyle t_{1}}$ ${\displaystyle u_{1}}$ ${\displaystyle N=t_{1}^{2}-Du_{1}^{2}}$

${\displaystyle t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}$ 。

以下の等式が成り立ちます。

${\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}$ 。

pが の形であると仮定すると（ pが の形であれば真）、D は平方剰余であり、 です。ここで、方程式は ${\displaystyle 4m+1}$ ${\displaystyle 8m+1}$ ${\displaystyle t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}}$

${\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}\quad {\mbox{and}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}$

解決策を提示します。 ${\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}$

とします。次に とします。これは、または がpで割り切れることを意味します。もし であれば、 と置き、 についても同様に進めます。すべてのがpで割り切れるわけではありません。なぜなら は割り切れないからです。mが奇数の場合は不可能です。なぜならが成り立ち、これはが平方剰余と合同であることを意味し、これは矛盾です。したがって、このループは特定のlについて のときに停止します。これにより が得られ、 は平方剰余なので、l は偶数でなければなりません。 と置きます。次に です。したがって、 の解は線形合同を解くことで得られます。 ${\displaystyle p-1=2r}$ ${\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}$ ${\displaystyle t_{r}}$ ${\displaystyle u_{r}}$ ${\displaystyle u_{r}}$ ${\displaystyle r=2s}$ ${\displaystyle 0\equiv 2t_{s}u_{s}}$ ${\displaystyle u_{i}}$ ${\displaystyle u_{1}}$ ${\displaystyle u_{m}\equiv 0}$ ${\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}$ ${\displaystyle t_{m}^{2}}$ ${\displaystyle t_{l}\equiv 0}$ ${\displaystyle -Du_{l}^{2}\equiv N^{l}}$ ${\displaystyle -D}$ ${\displaystyle l=2k}$ ${\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}$ ${\displaystyle x^{2}+D\equiv 0}$ ${\displaystyle u_{k}x\equiv \pm t_{k}}$

例

以下は、ポックリントンのpの3つの異なるケースに対応する4つの例です。いずれも例の 法に従って計算されます。${\displaystyle \equiv }$

例0

${\displaystyle x^{2}\equiv 43{\pmod {47}}.}$

これはアルゴリズムによれば最初のケースです が、43ではないので、アルゴリズムをまったく適用すべきではありません。アルゴリズムを適用できない理由は、a=43がp=47に対して平方非剰余であるためです ${\displaystyle x\equiv 43^{(47+1)/2}=43^{12}\equiv 2}$ ${\displaystyle x^{2}=2^{2}=4}$

例1

合同式を解け

${\displaystyle x^{2}\equiv 18{\pmod {23}}.}$

法は23です。これはなので、 です。 解は となるはずで、これは確かに真です${\displaystyle 23=4\cdot 5+3}$ ${\displaystyle m=5}$ ${\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}}$ ${\displaystyle (\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}}$

例2

合同式を解け

${\displaystyle x^{2}\equiv 10{\pmod {13}}.}$

法は13です。これはなので、 です。ここで を検証します。したがって、解は です。 これは確かに真です${\displaystyle 13=8\cdot 1+5}$ ${\displaystyle m=1}$ ${\displaystyle 10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}}$ ${\displaystyle x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}}$ ${\displaystyle (\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}}$

例3

合同式を解きなさい。これは と書きます。まず、 と が2乗非剰余となるような を求めます。例えばを取ります。次にを計算して を 求めます${\displaystyle x^{2}\equiv 13{\pmod {17}}}$ ${\displaystyle x^{2}-13=0}$ ${\displaystyle t_{1}}$ ${\displaystyle u_{1}}$ ${\displaystyle t_{1}^{2}+13u_{1}^{2}}$ ${\displaystyle t_{1}=3,u_{1}=1}$ ${\displaystyle t_{8}}$ ${\displaystyle u_{8}}$

${\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}$

${\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}$

そして同様に${\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}}$ ${\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}$

なので、方程式 を解く方程式が得られます。この方程式には解があります。確かに、 です。 ${\displaystyle t_{8}=0}$ ${\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}$ ${\displaystyle 3x\equiv \pm 7{\pmod {17}}}$ ${\displaystyle x\equiv \pm 8{\pmod {17}}}$ ${\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}}$

参考文献

• レナード・ユージン・ディクソン著『数論の歴史』第1巻222ページ、チェルシー出版、1952年

1. HCポックリントン『ケンブリッジ哲学協会紀要』第19巻、57～58ページ