anomalous
system:sage


<h2>p-adic Fields</h2>

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}$.

<p>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$.  

<p>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.  

<p>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))
///
}}}

<h2>Attacking anomalous curves</h2>
<!--

{{{id=1|
y = 2^5+1
p = 4
while not is_prime(p):
    p = (1+3*y^2)//4
    y += 2
///
}}}

-->

Here's an elliptic curve over $\mathbf{F}_p$.

{{{id=2|
p = 919;
E = EllipticCurve(GF(p),[0,15])
///
}}}

<!--

{{{id=3|
a = 0
n = 4
while n != p:
    a += 1
    E = EllipticCurve(GF(p),[0,a])
    n = E.order()
///
}}}

-->

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|

///
}}}