Elliptic curves cryptography

[Andy]

I am searching curve domain parameters using Sage. I search curve with prime order.

First I find prime with minimal number of zeros (especially minimal hex digits != 0xf) :

def find_prime(nbits):

  diglist = ['e', 'd', 'b', '7', 'c', '9', '3', '8', '1', '0']

  mask = 2 ^ nbits - 1

  if is_prime(mask):

    return mask

  hexmask = list(hex(mask))

  first = min((len(hexmask)-2)//2, 8)+2

  for i in range(len(diglist)):

    for j in range(len(hexmask) - 1, first - 1, -1):

      candhex = copy(hexmask)

      candhex[j] = diglist[i]

      c = int("".join(candhex), 16)

      if is_prime(c):

        return c

  return 0

from sage.all import *

def slightly_less(n, p, bits):

   minimal = p - 2 ^ (bits//2)

   return n >= minimal and n < p

def define_curve(bits):

  set_random_seed(1234)

  p = find_prime(bits)

  K = GF(p)

  cnt = 0

  while True:

    a = K(-3)

    b = K(randint(1, p-1))

   print(cnt, b)

   try:

      E = EllipticCurve(GF(p), [a, b])

   except: #singular

       continue

    n = E.order()

    if not slightly_less(n, p, bits):

      continue

    cnt += 1

    if is_prime(n):

      break

  print(bits, p, n)

  return cnt

Is possible do this in C with flint library? How compute order of Ellipse ?, is implemented Schoof-Atkin-Elkies algorithm?

[Albin Ahlbäck]

On 4/13/24 2:37 PM, Andy wrote:
> Is possible do this in C with flint library? How compute order of
> Ellipse ?, is implemented Schoof-Atkin-Elkies algorithm?

We do have a lot of utilities for elliptic curves, and I do not think
the Schoof-Atkin-Elies algorithm is implemented in FLINT. But it appears
to be in PARI/GP [1].

Best,
Albin

[1]:
https://pari.math.u-bordeaux.fr/dochtml/html/Elliptic_curves.html#se:ellap

[Albin Ahlbäck]

Meant to say "We do not have[...]"