Cryptography Reference
In-Depth Information
> EllipticCurve := proc(a::{integer,string}, b::{integer,string}, p::{posint,string})
local q, A, B;
q := stringposint(p);
if not isprime(q) orq<5then
error "%1 is not a prime >3", q
end if;
A := stringposint(a) mod q;
B := stringposint(b) mod q;
if (4*Aˆ3+27*Bˆ2) mod q = 0 then
error "singular curve"
else
[A, B, q]
end if;
end proc:
The point at infinity of an elliptic curve will be represented by 0 and the remaining
points by a Maple list
[
x
,
y
]
, where
x
and
y
are the coordinates of the point. Observe
that the 0 representing
O
should not be confused with the element 0
∈ F
p
nor with
the point
(in case this point belongs to the elliptic curve) nor with any other
affine point for that matter. The next procedure takes as input either 0 (for the point
at infinity) or the coordinates
x
,
y
(in decimal or hexadecimal format), and outputs
the point given as either 0 or
(
0
,
0
)
, with decimal coordinates.
> EllipticPoint := proc(x::{integer, string}, y::{integer, string})
if _params['y'] = NULL then
0
else
stringposint
∼
([x, y])
end if
end proc:
The next function takes as input a point and an elliptic curve and checks whether
the point is on the curve, in which case it returns
true
, otherwise it returns
false
:
[
x
,
y
]
> IsEllipticPoint := proc(P, E)
evalb(P = 0 or (P[2]ˆ2-P[1]ˆ3-E[1]*P[1]-E[2]) mod E[3] = 0)
end proc:
The discriminant of the cubic polynomial defining an elliptic curve is computed
by:
> discr := proc(E)
(-4*E[1]ˆ3-27*E[2]ˆ2) mod E[3]
end proc:
Next we give a Maple function that computes the set of points of an elliptic curve
over
F
p
. It runs over the field elements
x
and computes
x
3
b
and its Legendre
symbol modulo
p
, extracting the square roots when it is a quadratic residue. The
input is an elliptic curve in the format output by
EllipticCurve
and the output
a list of the points on the curve.
+
ax
+
> EllipticPoints := proc(E::list(integer))
local a, b, p, EP, x, z, y;
a := E[1];
b := E[2];
p := E[3];
EP := [];
for x from 0 to p-1 do
z := (xˆ3+a*x+b) mod p;
if numtheory:-legendre(z, p) <> -1 then
