Elliptic curve search (Montgomery form)

What is this?

A PARI/GP script I wrote in early November of 2025 while taking a break from fighting with the Web Workers and the WASM during my work on SendCipher. What the script does is it searches for elliptic curves of the Montgomery form that can be interesting from the cryptographic point of view.

But why?

Because implementing some of the criteria listed on safecurves.cr.yp.to was fun. The hunt for elliptic curves over finite fields with properties that make them suitable for public-key cryptography is fascinating.

How to use it?

Once you have the installation of PARI/GP done, load the script e.g.

$ gp
? \r ecs.gp

Then call the function ec_search(p, a0, a1) which does the search by examining curves of the form y^2 = x^3 + Ax^2+x where integer A goes through range [a0, a1]:

$ gp
# ...snip...
? ec_search(2^320-197, 3, 12501)
Searching range [3, 12501], log file: `ecsearch.log'
? \q
$ head -5 ecsearch.log
a0=3, a1=12501
y^2 = x^3+149*x^2+x is not super-singular and has order = 2^2*q (q prime) ** FAIL: N_twist/4 is not a prime **
y^2 = x^3+295*x^2+x is not super-singular and has order = 2^7*q (q prime) ** FAIL: N_twist/8 is not a prime **
y^2 = x^3+1177*x^2+x is not super-singular and has order = 2^4*q (q prime) ** FAIL: N_twist/8 is not a prime **
y^2 = x^3+1236*x^2+x is not super-singular and has order = 2^3*q (q prime) ** EPIC WIN!!! N_twist/16 is a prime! **

Since the problem is embarassingly parallel, I wrote a parallel version of the function which can be used if the PARI/GP installation is MPI enabled. For example:

$ mpiexec -n 9 ~/pari-2.17.2-install/bin/gp -s 256MB -D parisizemax=8GB -D parisize=512MB -D threadsize=512MB -D threadsizemax=4GB -f ecs.gp
                  GP/PARI CALCULATOR Version 2.17.2 (released)
          amd64 running linux (x86-64/GMP-6.3.0 kernel) 64-bit version
compiled: Nov 10 2025, mpicc for MPICH version 4.2.1,gcc version 14.2.0 (Debian 14.2.0-19)
                      threading engine: mpi, nbthreads = 8
               (readline not compiled in, extended help enabled)

                     Copyright (C) 2000-2024 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.

parisizemax = 8589934592, primelimit = 1048576, factorlimit = 1048576
? ec_parallel_search(8, 2^320-197, 3, 1000)
{3} searching range [252, 375], log file: `ecsearch_0003.log'
{8} searching range [875, 999], log file: `ecsearch_0008.log'
{6} searching range [626, 749], log file: `ecsearch_0006.log'
{7} searching range [750, 874], log file: `ecsearch_0007.log'
{4} searching range [376, 500], log file: `ecsearch_0004.log'
{5} searching range [501, 625], log file: `ecsearch_0005.log'
{1} searching range [3, 126], log file: `ecsearch_0001.log'
{2} searching range [127, 251], log file: `ecsearch_0002.log'
%1 = [0, 0, 0, 0, 0, 0, 0, 0]

Output

The log files indicate the searched ranges and an output line for each curve worthy of interest. A win, indicated by "EPIC WIN!!!", is a curve for which the cardinal and the twist have only small factors, such curves get a special treatment: the function ec_trial is called on them and the resulting output can be found in the log e.g.

# Output of ec_trial(2^320-197, 38460)
y^2 = x^3+38460*x^2+x is not super-singular and has order = 2^2*q (q prime) ** EPIC WIN!!! N_twist/4 is a prime! **
================================================================================
Trial for Y^2 = X^3 + 38460*X^2 + X (mod 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936379)
--------------------------------------------------------------------------------
* Is supersingular: 0
* Checking cardinal and twist cardinal
  N = #E(F_p) = 2135987035920910082395021706169552114602704522355303495046887549005588444185520338169035467730476
    = 2^2 * 533996758980227520598755426542388028650676130588825873761721887251397111046380084542258866932619
  N/(2^2) is a prime
  N_twist = 2135987035920910082395021706169552114602704522358002044847195666638851007375760761876888706142284
    = 2^2 * 533996758980227520598755426542388028650676130589500511211798916659712751843940190469222176535571
  N_twist/(2^2) is a prime
* Trial factoring Dp = |t^2 - 4p| = 6723405387497894940747771083441048937427371732550494162315448271614982995969722287117688799288300 to 2^35...
  square part of Dp: 2^2*5^2 (probability of a remaining non-squarefree factor is ~ 1.1996557677372254026786995328246783277 E-12)
  Discriminant D = 268936215499915797629910843337641957497094869302019766492617930864599319838788891484707551971532
  Discriminant is OK with probability ~ 99.999999999880034423226277459732130047%
The curve passed the CM field discriminant test, continuing...
* Searching for a generator point
  A = 38460
  h = 4
  r = 533996758980227520598755426542388028650676130588825873761721887251397111046380084542258866932619
  Attempting X = 8
Generator found: [835411467044968411874579108943540396713208499461081879546382596576469989063606884651372681607379,
579567910653627540637191719493403013493340260719689958163544668771590440310699645919293166455862]
================================================================================

Results

The results of the various searches I ran can be found in the results subfolder of this repository. In the following section I listed the best curves I have found.

Best curves

P	A	h	h'	embedding order	twist embedding order
2^400-593	122929	4	4	r-1	(s-1)/2
2^318-2^160-1	190327	4	4	r-1	s-1