README

Companion SageMath Code Implementation of the manuscript Improved Subfield Curve Search For Specific Field Characteristics.

In particular, this repository includes the following implemented algorithms:

• Searcher2 and SuperSearcher2
• Searcher4 and SuperSearcher4
• Searcher12 and SuperSearcher12

Requirements

The shared scripts require the following libraries/packages:

• SageMath
• numpy
• multiprocessing
• argparse

Additional (optional) requirements:

• Magma

Usage

% sage -python main.py --help       
usage: main.py [-h] [-a [EXPONENT]] [-f [COFACTOR]] [-r [RUNS]] [-s] [-v] [-e]

Parses command.

options:
  -h, --help            show this help message and exit
  -a, --exponent [EXPONENT]
                        Integer a in p = dᵃf - 1 with d=2 or d=12
  -f, --cofactor [COFACTOR]
                        Integer f in p = dᵃf - 1 with d=2 or d=12
  -r, --runs [RUNS]     Number of experiments (runs) for benchmarking
  -s, --super           Optimized subfield curve detection
  -v, --verbose         Verbose mode
  -e, --early_stopping  For measuring inspected nodes per 10^8 field operations

See below for an example of a single run in verbose mode.

% cd supersearcher2
% sage -python main.py -a 31 -f 1 -v

Field characteristic,	p: 2^31 × 1 - 1
Initial Elliptic Curve,	E: y² = x³ + (139307940*i + 108206703)x² + x with j(E) = 815383771*i + 2119073318
Basis generator,	xP: [444899703*i + 2094693529, 1]
Basis generator,	xQ: [1454178250*i + 457643027, 1]
Difference point,	xR: [242187899*i + 1451874201, 1]

Early Stopping:	No

SuperSearcher:	Deactivated
Height, h:	15
Path,   b:	000010111001111
Running time:
	#(Point doublings):	1500
	#(Point additions):	3844
	#(2-Isogeny eval.):	2988
	#(2-isogeny curve):	4500
	#(Subfield checks):	2982
	#(Inspected nodes):	2982
	#(Basefield muls.):	199168
	#(Basefield muls.)/2ʰ:	3.0390625

Final Elliptic Curve,	F: y² = x³ + (139307940*i + 108206703)x² + (29992370*i + 1169538893)x + 1810838916*i + 1970723751 with j(F) = 2024743763
which is a Subfield Curve

Remarks

• Implementation concerning SuperSearche12 assumes primes of the form p = 12ᵃf - 1 for some positive integers a and f.

• You can find in the script_experiments.sh the full list of parameters we used in the experiments.

• Running script_experiments.sh takes a considerable time due to the long list of experiments.

• There are few files coded in Magma language used for generate tables, plots, and calculate the constant \gamma.

• By default, benchmark flag -r runs ten parallel processors. Each processor is trying to solve a random instance. This can be modified at each main.py file by modifying the variable cores.

• Some Tables and Plots presented in the manuscript can be replicated (in LaTeX format) as below.

  # Using sage
  cd miscellaneous
  sage -python3 generate_table_experiments.py
  sage -python3 generate_plot_experiments.py
  sage -python3 generate_table_concluding_remarks.py

• The file script_comparison.sh allows to replicate the number of inspect nodes per 10^8 field multiplications over GF(p) for SuperSearcher4. In particular, the numbers from Table 4 corrrespond to dividing these number of inspected curves by 10^8 and taking reciprocals, leading to a "multiplications per visited curve" metric.

• The file experiments/SuperSolverLogs.txt includes the number of inspect nodes per 10^8 field multiplications over GF(p) for SuperSolver. That file concerns experiments for the SuperSolver implementation from https://github.com/microsoft/SuperSolver, and employs the provided files experiments/ExperimentAlgo0.sage and experiments/ExtFieldSearch.sage. The file experiments/ExperimentAlgo0.sage perform the experiments for the same set of primes as in script_comparison.sh, while experiments/ExtFieldSearch.sage includes the stop condition for the 10^8 field operations. To replicate the content in experiments/SuperSolverLogs.txt one should use these two provided files whe running SuperSolver implementation from https://github.com/microsoft/SuperSolver.