元祖ワシ的日記

3n+1型の素数には三乗根があります。それは原始根をeとすれば 1, w=e^(p-1)/3 および w^2と求まるのですが、求めるだけならば原始根は知らなくても問題ありません。フェルマーの小定理からFpの任意の元aについて

a^(p-1) = 1

なのですから a^(p-1)/3 はあと3乗すれば１になる数、すなわちそれは1かwかw^2のいずれかです。よって適当に数を選んで(p-1)/3乗してみれば2/3の確率で求まります。原始根を求めるのは大変なので大きな素数pに対してはこちらのほうが簡単でしょう。

同じ理論が 素数の羃乗根(たとえば4乗根とか)にも使えます。

4n+1型の素数は4乗根があります。さきほど同様原始根をeとすれば 1, w=(p-1)/4、w^2, w^3が4乗根です。しかしw^2は2乗根であり、それは-1で自明な根です。自明でない4乗根(すなわち原始4乗根はwと w^3になります)よって、ランダムに選んだ数を(p-1)/4乗してみれば、1/2の確率で原始4乗根が得られることになります。

例1)
F13を考えます。12 = 3 * 2^2ですからF13は4乗根をもちます。実際

2^3 = 8

で、8は2乗根ではないから(原始)4乗根です。

例2)
F97は 97-1 = 3 * 32ですから32 乗根を持ちます。

よって、F97の任意の元を選び3乗すれば32乗根のうちのどれかに属します。その数をrとします。
これくらい大きくなるとそれが原始的かどうか(つまり32乗して始めて1になるのか)チェックするのは結構大変に思えます。
普通に考えれば rが原始32乗根であるには

r≠1
r^2≠1
r^4≠1
r^8≠1
r^16≠1

であることを確認すればよいのですが。しかしよく注視してみると

r^16≠1

だけチェックすればよいことがわかります。なぜなら r^16≠1ならば r^8≠1 だからです。
よって

r^16 = (a^3)^16 = a^48 ≠ 1

だけのチェックをすればよく、このチェックを通過した数は F97における1の原始32乗根です。
なおこのチェックは2の羃に関しては平方剰余かどうかをチェックしているのと同じというのがまた味わい深いですね。

これで計算してみると

2^48=1
3^48=1
4^48=1
5^48=96

よって、5^3 = 28がF97の原始32乗根ということになります。

例3）
F433は

p-1 = 432 = 16 * 3^3

よって F433は 27乗根をもちます。よって任意にaを選び16乗すればそれは27乗根の1つです。
原始27乗根であるかどうかチェックするには

r≠1
r^3≠1
r^9≠1

をチェックすればよいのですが、同様の理論により
r^9≠1だけをチェックすればよいことがわかります。
実際計算してみると

(2^16)^9 = 1
(3^16)^9 = 198

であり、3^16 = 26が F433の 原始27乗根として求まります

確率的なアルゴリズムではありますが「あたり」を引く確率は高いので、総じて計算は早いといえましょう。