# Curve25519 Base Points calculation

I ran the following Sage script from A.3. Base Points Section of rfc7748 for Curve25519

def findBasepoint(prime, A):
F = GF(prime)
E = EllipticCurve(F, [0, A, 0, 1, 0])

for uInt in range(1, 1e3):
u = F(uInt)
v2 = u^3 + A*u^2 + u
if not v2.is_square():
continue
v = v2.sqrt()
point = E(u, v)
pointOrder = point.order()
if pointOrder > 8 and pointOrder.is_prime():
Q=u^3 + A*u^2 + u
return u, Q, sqrt(Q), point

res=findBasepoint(2^255 - 19, 486662)
res

(9, 39420360, 14781619447589544791020593568409986887264606134616475288964881837755586237401, (9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1))


and got the expected result (from 4.1. Curve25519):

The base point is u = 9, v = 1478161944758954479102059356840998688726 4606134616475288964881837755586237401.

But now I can't understand how sqrt(39420360) can be such an enormous value. Seems sqrt() is not math.sqrt() here. How did Sage calculate it?

• -1 for yet another question by someone trying to do elliptic curves when they don't know basic modular arithmetic. – fkraiem May 3 '17 at 12:35

It computed the squareroot modulo $2^{255} - 19$
A normal (that is, computed in the field of the reals) squareroot of 39420360 would be that value $Q$ such that $Q^2 = 39420360$, where the squaring operation is done as multiplication within $\mathbb{R}$
What Sage did is the equivalent operation within the field $GF(2^{255}-19)$. That is, it found a value $Q$ such that $Q^2 = 39420360$ when computed in that field, or equivalently, $Q^2 \equiv 39420360 \pmod{2^{255}-19}$.
Because such a $Q$ is an integer between 0 and $2^{255}-19$ (all elements of $GF(2^{255}-19)$ are), it's not surprising it's a large value.
• $Q^2=486662$ or $Q^2=39420360$? – Meysam Ghahramani May 3 '17 at 13:44