2
$\begingroup$

I am reading the book Pairing for beginners (PDF) to understand pairing.

In the following example for page 52 of the book, I could not understand how the author depict the 4 cyclic subgroups and how he found different points in different cyclic subgroups. I attached the picture of the example.

enter image description here

Can you help me understand how the author found the points which are depicted in different cyclic subgroups like $(8, i), (8, 10i), …$?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

With a very small field (here, $q = 11$, i.e. there are only eleven elements in the base field), the number of points on the curve is small enough to enumerate them all, even by hand.

Elements in $\mathbb{F}_q$ are integers from $0$ to $10$. The field extension $\mathbb{F}_{q^2}$ is defined by using a formal extra element $i$ such that $i^2 = -1 = 10 \bmod q$ (there is no such element in $\mathbb{F}_q$, so $i$ is really a "new element"). All elements of $\mathbb{F}_{q^2}$ are then written as $a+ib$ for two values $a,b \in \mathbb{F}_q$. This is basically the same way that complex numbers ($\mathbb{C}$) are defined with regards to real numbers ($\mathbb{R}$). There are $q^2 = 121$ elements in $\mathbb{F}_{q^2}$.

The C program below just enumerates all points $(x,y)$ such that $x$ and $y$ are elements of $\mathbb{F}_{q^2}$; there are $121^2 = 14641$ such points. Out of these, $143$ match the curve equation ($y^2 = x^3 + 4$) (total curve order is $144$ since there is also the "point at infinity", which has no $x$ and $y$ coordinates). For each such point, we apply the point addition law repeatedly to work out the point order (for a point $P$, we add $P$ repeatedly until we reach the "point at infinity"). For points of order $3$, we print out the points $P$ and $P+P$. Here is the code:

#include <stdio.h>

typedef struct {
        unsigned re, im;
} mq2;

static mq2
mq2_sub(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (11 + x.re - y.re) % 11;
        z.im = (11 + x.im - y.im) % 11;
        return z;
}

static mq2
mq2_mul(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (121 + x.re * y.re - x.im * y.im) % 11;
        z.im = (x.re * y.im + x.im * y.re) % 11;
        return z;
}

static mq2
mq2_mul_int(mq2 x, unsigned f)
{
        mq2 z;

        z.re = (x.re * f) % 11;
        z.im = (x.im * f) % 11;
        return z;
}

static mq2
mq2_inv(mq2 x)
{
        unsigned d, d0;
        mq2 z;

        d0 = (x.re * x.re + x.im * x.im) % 11;
        d = (d0 * d0 * d0 * d0) % 11;
        d = (d * d * d0) % 11;
        z.re = (x.re * d) % 11;
        z.im = (121 - x.im * d) % 11;
        return z;
}

static mq2
mq2_div(mq2 x, mq2 y)
{
        return mq2_mul(x, mq2_inv(y));
}

static int
mq2_eq(mq2 x, mq2 y)
{
        return x.re == y.re && x.im == y.im;
}

static int
mq2_eq0(mq2 x)
{
        return x.re == 0 && x.im == 0;
}

static void
mq2_print(mq2 x)
{
        if (x.im == 0) {
                printf("%u", x.re);
        } else if (x.im == 1) {
                if (x.re == 0) {
                        printf("i");
                } else {
                        printf("i+%u", x.re);
                }
        } else {
                if (x.re == 0) {
                        printf("%ui", x.im);
                } else {
                        printf("%ui+%u", x.im, x.re);
                }
        }
}

typedef struct {
        mq2 x, y;
        int zero;
} point;

static const point Z = { { 0, 0 }, { 0, 0 }, 1 };

static int
point_is_on_curve(point P)
{
        mq2 x, y;

        x = mq2_mul(P.x, mq2_mul(P.x, P.x));
        x.re = (x.re + 4) % 11;
        y = mq2_mul(P.y, P.y);
        return mq2_eq(x, y);
}

static void
point_print(point P)
{
        if (P.zero) {
                printf("inf");
        } else {
                printf("(");
                mq2_print(P.x);
                printf(",");
                mq2_print(P.y);
                printf(")");
        }
}

static point
point_add(point P, point Q)
{
        mq2 lambda;
        point R;

        if (P.zero) {
                return Q;
        }
        if (Q.zero) {
                return P;
        }
        if (mq2_eq(P.x, Q.x)) {
                if (mq2_eq(P.y, Q.y)) {
                        if (mq2_eq0(P.y)) {
                                return Z;
                        }
                        lambda = mq2_div(
                                mq2_mul_int(mq2_mul(P.x, P.x), 3),
                                mq2_mul_int(P.y, 2));
                } else {
                        return Z;
                }
        } else {
                lambda = mq2_div(mq2_sub(Q.y, P.y), mq2_sub(Q.x, P.x));
        }

        R.x = mq2_sub(mq2_sub(mq2_mul(lambda, lambda), P.x), Q.x);
        R.y = mq2_sub(mq2_mul(lambda, mq2_sub(P.x, R.x)), P.y);
        R.zero = 0;
        return R;
}

static unsigned
point_order(point P)
{
        point Q;
        unsigned order;

        order = 1;
        Q = P;
        while (!Q.zero) {
                Q = point_add(Q, P);
                order ++;
        }
        return order;
}

int
main(void)
{
        int i, j;
        unsigned num;

        num = 1;
        for (i = 0; i < 121; i ++) {
                for (j = 0; j < 121; j ++) {
                        point P, Q;

                        P.x.re = i % 11;
                        P.x.im = i / 11;
                        P.y.re = j % 11;
                        P.y.im = j / 11;
                        P.zero = 0;
                        if (!point_is_on_curve(P)) {
                                continue;
                        }
                        num ++;
                        if (point_order(P) == 3) {
                                point_print(P);
                                Q = P;
                                while (!Q.zero) {
                                        Q = point_add(Q, P);
                                        printf(" -> ");
                                        point_print(Q);
                                }
                                printf("\n");
                        }
                }
        }
        printf("curve order: %u\n", num);
        return 0;
}

This code is gloriously inefficient, with all its integer divisions and use of affine coordinates; it still completes in less than a hundredth of a second on my laptop computer.

When run, it shows the points of order $3$, as expected:

(0,2) -> (0,9) -> inf
(0,9) -> (0,2) -> inf
(8,i) -> (8,10i) -> inf
(8,10i) -> (8,i) -> inf
(2i+7,i) -> (2i+7,10i) -> inf
(2i+7,10i) -> (2i+7,i) -> inf
(9i+7,i) -> (9i+7,10i) -> inf
(9i+7,10i) -> (9i+7,i) -> inf
curve order: 144

Note that this includes the point $(2i+7,10i)$ which is missing on the screenshot in your question (but it is present on page 52 of the PDF).

Notes:

  • I wrote that code just for that answer; it's not an extract from anything else.

  • The mq2 structure represents an element of $\mathbb{F}_{q^2}$. The two fields re and im are named by analogy with complex numbers ("real part" and "imaginary part").

  • The mq2_inv() function computes the inverse of an element. In $\mathbb{F}_{q^2}$, the inverse of $a+ib$ is: $$ (a+ib)^{-1} = \frac{a-ib}{a^2+b^2} $$ To compute the inverse of $d = (a^2+b^2)$, Fermat's little theorem is used: $d^{-1} = d^{q-2} \bmod q$. Note that the inverse will silently return $0$ if asked to invert $0$ (which is nominally not defined).

  • A curve point is a pair of coordinates $(x,y)$ in $\mathbb{F}_{q^2}$, or the special "point at infinity" (which is not in the plane). The point structure contains the coordinates $x$ and $y$, and a flag (zero) for the point at infinity. The point addition function must filter out the special cases:

    • When one of the operands is the point at infinity, then the sum is the other operand (this also handles the case of adding the point at infinity to itself).

    • When both operands have the same coordinate $x$, then this is either a doubling (operands are equal); or the operands are opposite to each other, and their sum is the point at infinity. There is a special-special case when we double a point whose coordinate $y = 0$, in which case the result is the point at infinity.

    • In all other cases, this is a normal point addition, which we compute with the group law formulas.

I cannot prove that the book author (Craig Costello) computed the points with a crude program such as this one, but it is certainly a possibility, and it's not that hard. It's a matter of one hour of work at most, and the code does not need to be efficient since there are so few elements to check.

When studying elliptic curves, and especially pairings, it is very useful to write some customary implementation like that one, that allows fiddling with values and check examples.

$\endgroup$
1
  • $\begingroup$ Thank you so much for your clear and informative explanation. I really appreciate your help. $\endgroup$
    – tesoke
    Mar 4, 2018 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.