p^n を見かけたら - crypto-writeup-public

p-adic number を考える。sageには Zp が用意されていて、例えば $\mod p^{100}$ みたいな拡大体の上での演算を扱いたいときはGF(p^100)よりも、Zp(p, prec=100) とするのが良い。

https://doc.sagemath.org/html/en/reference/padics/index.html

例えば、 $x^2 + ax + b \equiv r \mod p^2$ みたいな式が合った時に、GF(p^2) を使って計算してしまうと $\mod p$ の解が出てくる。これでもHensel's Liftを使って持ち上げればうまく行くかもしれないが、うまく行かなかったりもするので（というか今うまくできていない）Zpを使いたい（Zpでも計算結果を lift で持ち上げている

p = random_prime(1<<64)

x = randint(1, p^2-1)  # secret
a = randint(1, p^2-1)
b = randint(1, p^2-1)

print(x)

# ---

F = Zp(p, prec=2)
PR.<z> = PolynomialRing(F)

f = z^2 + a*z + b - r
g = z^2 + p*z + b - s

print("===")
for root in f.roots():
    print(root[0].lift())
print("---")
for root in g.roots():
    print(root[0].lift())