p-adic Fields
Here is a $p$-adic field $\mathbf{Q}_5$.
{{{id=10|
Q5 = pAdicField(5,10); Q5
///
}}}
As with real numbers, computations in $p$-adic fields must be done with finite precision.
{{{id=11|
Q5(1)
///
}}}
The $O(5^{10})$ means that the result is correct mod $5^{10}$.
The $p$-adic representation of a positive integer is its base $p$ representation.
{{{id=12|
Q5(37)
///
}}}
The same holds for rational numbers with only powers of $p$ in the denominator.
{{{id=13|
Q5(6/5)
///
}}}
Other rational numbers are represented $p$-adically by computing their representations mod $p^d$ for each $d$.
For example, $-1$ is equal to 4 mod 5; 24 mod 25; 124 mod 125; etc.
{{{id=14|
Q5(-1)
///
}}}
Similarly, 3 is an inverse of 2 mod 5; 13 is an inverse of 2 mod 25; etc.
{{{id=15|
Q5(1/2)
///
}}}
Hensel's lemma says that if an algebraic equation has a solution mod $p$ with multiplicity 1, then it has a $p$-adic solution.
Here the equation $x^2+1 = 0$ has a solution mod 5, so there is a solution in $\mathbf{Q}_5$.
{{{id=16|
sqrt(Q5(-1))
///
}}}
Attacking anomalous curves
Here's an elliptic curve over $\mathbf{F}_p$.
{{{id=2|
p = 919;
E = EllipticCurve(GF(p),[0,15])
///
}}}
This curve is anomalous:
{{{id=5|
E.order() == p
///
}}}
Pick two random points $P,Q \in E(\mathbb{F}_p)$. We'll try to compute the discrete log of $Q$ to the base $P$.
{{{id=6|
P,Q = E.random_element(),E.random_element();
P; Q;
///
}}}
First define the relevant $p$-adic field. We only need to work with small precision.
{{{id=7|
Qp = pAdicField(p,5)
///
}}}
Define a lift of $E/\mathbb{F}_p$ to $\tilde E/\mathbf{Q}_p$. We add "random" multiples of $p$ to the curve coefficients in order to remove the special structure of the $j=0$ curve.
{{{id=8|
EE = EllipticCurve(Qp,[7*p, 15 + 12*p]); EE
///
}}}
Lift $P \in E(\mathbb{F}_p)$ to a point $\tilde P \in E(\mathbf{Q}_p)$, and similarly with $Q$.
{{{id=9|
PP = EE.lift_x(ZZ(P[0])); PP
///
}}}
{{{id=17|
QQ = EE.lift_x(ZZ(Q[0])); QQ
///
}}}
{{{id=24|
2*PP
///
}}}
Multiplying by $p$ moves the point into $\tilde E_1$, the kernel of reduction mod $p$.
{{{id=18|
PP1 = p*PP; PP1
///
}}}
{{{id=19|
QQ1 = p*QQ; QQ1
///
}}}
Taking the "elliptic logarithm" $\lambda(x,y) = x/y \bmod{p}$ gives an isomorphism to the additive group $\mathbb{Z} \bmod{p}$.
{{{id=20|
m1 = p*(PP1)[0]/(PP1)[1]
m2 = p*(QQ1)[0]/(QQ1)[1]
///
}}}
In $\mathbf{Z} \bmod{p}$, we have $\lambda(\tilde Q) = k \cdot \lambda(\tilde P)$, so discrete logarithm is just division:
{{{id=21|
m2/m1
///
}}}
The discrete logarithm is $m_2/m_1 \bmod{p}$.
{{{id=22|
Q == 373*P
///
}}}
{{{id=23|
///
}}}