## Square roots mod p in ARIBAS

Since version 1.44 ARIBAS has a builtin function
```    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.
Example:
```    ==> p := next_prime(10**9).
-: 1000000007

==> a := 6.
-: 6

==> jacobi(a,p).
-: 1

==> x := gfp_sqrt(p,a).
-: 959647287

==> x**2 mod p.
-: 6
```
As an application, we can write a function that constructs a point on an elliptic curve
```    Y**2 = X**3 + a*X + b
```
over 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_findpoint
```
With the same prime `p = 1000000007` as above and parameters
```    ==> a := 1.
-: 1

==> b := random(p).
-: 435846878
```
we 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)
```

Homepage of ARIBAS

Otto Forster 2004-08-16