Orders and logs

How many points?

import { countPoints, defineCurve, listPoints } from "@agntn/curves";

const curve = defineCurve({ a: 2n, b: 2n, p: 17n });
countPoints(curve); // 19n
listPoints(curve, { limit: 3 }); // [{ x: 0n, y: 6n }, { x: 0n, y: 11n }, { x: 3n, y: 1n }]

countPoints counts infinity too, so it gives the group order. listPoints leaves infinity out and goes by x, then y. It walks every x once, which is why p has a ceiling.

Want only the points of one order? Pass order:

const f23 = defineCurve({ a: 1n, b: 1n, p: 23n });
listPoints(f23, { order: 7n }); // six points, (5, 4) to (17, 20)

An order that doesn't divide the group order gives an empty list without multiplying a single point.

The order of a point

import { pointOrder } from "@agntn/curves";

pointOrder(curve, { x: 5n, y: 1n }); // 19n

That's the smallest n with n times the point at infinity. Baby step giant step finds it inside the Hasse interval. The prime factors of that number trim it down. So it works far past what a walk could count:

const wide = defineCurve({ a: 2n, b: 3n, p: 1099511627563n });
pointOrder(wide, { x: 1n, y: 727918651225n }); // 1099513053442n

A 40 bit field, a few milliseconds.

Discrete logs

import { discreteLog } from "@agntn/curves";

discreteLog(curve, { x: 5n, y: 1n }, { x: 16n, y: 4n }); // 13n

You get the smallest k below the order of the base with k times base equal to the target. No such k? You get undefined, never a guess. In f23, the point (4, 0) has order 2, and no multiple of a point of order 7 ever lands on it.

Over MCP, log also names the order it searched in, so a model knows what "smallest" meant:

{"operation":"log","order":"19","scalar":"13"}

Limits

Each of these stops at a limit instead of running for ever. The numbers are exported, so you can check before you call.

Past one, the error says which:

Counting and listing points takes p up to 1048576
The base has order 1099513053442, above the 68719476736 a search takes

A log for a base of order near 2^36 takes under half a second. A real 256 bit curve? Nobody's search takes that, which is the whole point of elliptic curve cryptography.