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