gfp_sqrt(p,a: integer): integer;which calculates the square root of an integer
a
modulo
a prime number p
. The number a
must
be a quadratic residue modulo p
, i.e. its
Legendre (Jacobi) symbol mod p
must be 1 or 0.
==> p := next_prime(10**9). -: 1000000007 ==> a := 6. -: 6 ==> jacobi(a,p). -: 1 ==> x := gfp_sqrt(p,a). -: 959647287 ==> x**2 mod p. -: 6As an application, we can write a function that constructs a point on an elliptic curve
Y**2 = X**3 + a*X + bover the finite field
GF(p) = Z/p
.
This function chooses
first an x-coordinate and tests whether
x**3 + a*x + b
is a square mod p
.
If this is the case, the y-coordinate is determined
by calculating the square root.
The last argument x0
of the function
serves as a start value for the x-coordinate
of the point. If this argument is < 0, or is not given,
a random value is used instead.
==> function ecp_findpoint(p,a,b: integer; x0 := -1): array[2]; var x, y, y2: integer; begin if x0 < 0 then x := random(p); else x := x0; end; while true do y2 := (x**3 + a*x + b) mod p; if jacobi(y2,p) = -1 then inc(x); else y := gfp_sqrt(p,y2); break; end; end; if x >= p then x := x mod p; end; return (x,y); end. -: ecp_findpointWith the same prime
p = 1000000007
as above and
parameters
==> a := 1. -: 1 ==> b := random(p). -: 435846878we get for example
==> ecp_findpoint(p,a,b,0). -: (0, 353710864) ==> ecp_findpoint(p,a,b,4). -: (6, 605147815) ==> ecp_findpoint(p,a,b). -: (918115695, 463220581)