n冪剰余に関する検討
実験結果として, 「mod pにおいて7/34のn冪剰余 (n-th power residue) が存在する場合, pを割り切るSNNN数を単純に見つけることは不可能」という結果が出ている. 少なくともこれは100000以下の素数については確定しているものの「 mod pにおいて7/34のn冪剰余が存在しない ⇒ pを約数にもつSNNN数は存在しない」については未証明である (あくまで必要条件であって, 十分条件にはならないのではと踏んでいる).
n冪剰余は一般の数体に関する定義を有理数体直に取ることで$ \left(\frac{a}{p}\right)_n := a^{(p-1)/\gcd(n, p-1)}と定義している.
code: search.sage
p = 19
l = []
while p < 100000:
g = primitive_root(p)
a = Mod(10, p).log(g)
b = Mod(7 / 34, p).log(g)
assert Mod(g, p) ^ a == 10
assert Mod(g, p) ^ b == Mod(7 / 34, p)
d = gcd(p - 1, a)
if Mod(7 / 34, p) ^ ((p - 1) / d) == 1:
try:
n = Mod(7 / 34, p).log(Mod(10, p))
except ValueError:
l.append(p)
else:
try:
n = Mod(7 / 34, p).log(Mod(10, p))
except ValueError as e:
continue
p = next_prime(p)
print(l)
↑ []とだけ出力される. これは結局「n冪剰余をもたない場合にはまず離散対数自体が存在しない」「nべき剰余をもつ場合, 必ず計算に成功する」ということを意味している
$ pを素数, $ p\nmid a,とする. 方程式 $ x^n\equiv a\ (p)が解$ x\in\mathbb{Z}をもつための必要十分条件は$ a^f\equiv 1\ (p)なることである. ただし $ p - 1 = ef, $ e = (n, p - 1). また解があるときは解の数$ (\mathrm{mod}\ p)は$ eである.
方程式の解が存在する ⇒ 10の離散対数があるまで直接言える? 反例はない?