summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.clang-format90
-rw-r--r--CMakeLists.txt23
-rw-r--r--Makefile52
-rw-r--r--README.md46
-rw-r--r--ecgen.c76
-rw-r--r--gp.c357
-rw-r--r--gp.gp3
-rw-r--r--gp.h33
-rw-r--r--points.gp56
-rw-r--r--sea.gp100
-rw-r--r--src/Makefile72
-rw-r--r--src/cli.c97
-rw-r--r--src/cli.h36
-rw-r--r--src/curve.c35
-rw-r--r--src/curve.h12
-rw-r--r--src/ecgen.c150
-rw-r--r--src/field.c69
-rw-r--r--src/field.h39
-rw-r--r--src/gp.c207
-rw-r--r--src/gp.h28
-rw-r--r--src/gp/equation.gp28
-rw-r--r--src/gp/field.gp33
-rw-r--r--src/gp/gp.gp7
-rw-r--r--src/gp/invalid.gp59
-rw-r--r--src/gp/utils.gp52
-rw-r--r--src/input.c135
-rw-r--r--src/input.h51
-rw-r--r--src/output.c42
-rw-r--r--src/output.h12
-rw-r--r--src/poly.c540
-rw-r--r--src/poly.h48
-rw-r--r--utils.gp11
32 files changed, 1895 insertions, 704 deletions
diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..4956b9f
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,90 @@
+---
+Language: Cpp
+# BasedOnStyle: Google
+AccessModifierOffset: -1
+AlignAfterOpenBracket: Align
+AlignConsecutiveAssignments: false
+AlignConsecutiveDeclarations: false
+AlignEscapedNewlinesLeft: true
+AlignOperands: true
+AlignTrailingComments: true
+AllowAllParametersOfDeclarationOnNextLine: true
+AllowShortBlocksOnASingleLine: false
+AllowShortCaseLabelsOnASingleLine: false
+AllowShortFunctionsOnASingleLine: All
+AllowShortIfStatementsOnASingleLine: true
+AllowShortLoopsOnASingleLine: true
+AlwaysBreakAfterDefinitionReturnType: None
+AlwaysBreakAfterReturnType: None
+AlwaysBreakBeforeMultilineStrings: true
+AlwaysBreakTemplateDeclarations: true
+BinPackArguments: true
+BinPackParameters: true
+BraceWrapping:
+ AfterClass: false
+ AfterControlStatement: false
+ AfterEnum: false
+ AfterFunction: false
+ AfterNamespace: false
+ AfterObjCDeclaration: false
+ AfterStruct: false
+ AfterUnion: false
+ BeforeCatch: false
+ BeforeElse: false
+ IndentBraces: false
+BreakBeforeBinaryOperators: None
+BreakBeforeBraces: Attach
+BreakBeforeTernaryOperators: true
+BreakConstructorInitializersBeforeComma: false
+ColumnLimit: 80
+CommentPragmas: '^ IWYU pragma:'
+ConstructorInitializerAllOnOneLineOrOnePerLine: true
+ConstructorInitializerIndentWidth: 4
+ContinuationIndentWidth: 4
+Cpp11BracedListStyle: true
+DerivePointerAlignment: true
+DisableFormat: false
+ExperimentalAutoDetectBinPacking: false
+ForEachMacros: [ foreach, Q_FOREACH, BOOST_FOREACH ]
+IncludeCategories:
+ - Regex: '^<.*\.h>'
+ Priority: 1
+ - Regex: '^<.*'
+ Priority: 2
+ - Regex: '.*'
+ Priority: 3
+IndentCaseLabels: true
+IndentWidth: 4
+IndentWrappedFunctionNames: false
+KeepEmptyLinesAtTheStartOfBlocks: false
+MacroBlockBegin: ''
+MacroBlockEnd: ''
+MaxEmptyLinesToKeep: 1
+NamespaceIndentation: None
+ObjCBlockIndentWidth: 2
+ObjCSpaceAfterProperty: false
+ObjCSpaceBeforeProtocolList: false
+PenaltyBreakBeforeFirstCallParameter: 1
+PenaltyBreakComment: 300
+PenaltyBreakFirstLessLess: 120
+PenaltyBreakString: 1000
+PenaltyExcessCharacter: 1000000
+PenaltyReturnTypeOnItsOwnLine: 200
+PointerAlignment: Left
+ReflowComments: true
+SortIncludes: true
+SpaceAfterCStyleCast: false
+SpaceBeforeAssignmentOperators: true
+SpaceBeforeParens: ControlStatements
+SpaceInEmptyParentheses: false
+SpacesBeforeTrailingComments: 2
+SpacesInAngles: false
+SpacesInContainerLiterals: true
+SpacesInCStyleCastParentheses: false
+SpacesInParentheses: false
+SpacesInSquareBrackets: false
+Standard: Auto
+TabWidth: 4
+UseTab: ForIndentation
+...
+
diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..b0c5410
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,23 @@
+cmake_minimum_required(VERSION 2.8.11)
+project(ecgen)
+
+SET(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -Wall")
+
+add_custom_command(
+ OUTPUT gp.c gp.h
+ COMMAND gp2c -g -i4 gp/gp.gp | clang-format | awk "BEGIN{print \"#ifndef GP_H\" > \"gp.h\"; print \"#define GP_H\" >> \"gp.h\";} { if\(found\) print >> \"gp.c\"; else print >> \"gp.h\"} /End of prototype/{found=1; print \"\#include \\\"gp.h\\\"\" > \"gp.c\"; print \"#endif //GP_H\" >> \"gp.h\"}"
+ WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/src"
+ COMMENT "gp2c gp.gp"
+ VERBATIM
+)
+
+add_custom_target(gp2c ALL DEPENDS gp.c gp.h)
+
+include_directories(src)
+
+file(GLOB SOURCES "src/*.c")
+
+add_executable(ecgen ${SOURCES})
+add_dependencies(ecgen gp2c)
+
+target_link_libraries(ecgen pari) \ No newline at end of file
diff --git a/Makefile b/Makefile
index a32a853..80cad13 100644
--- a/Makefile
+++ b/Makefile
@@ -1,45 +1,13 @@
+#
+# ecgen, tool for generating Elliptic curve domain parameters
+# Copyright (C) 2017 J08nY
+#
-CC=gcc
-GP2C=gp2c
+# Default target first
+all:
+ +$(MAKE) -C src all
-INCLUDES=-I.
+# Just pass all targets to a Makefile in src
+$(MAKECMDGOALS):
+ +$(MAKE) -C src $@
-CFLAGS=$(INCLUDES) -g -O3 -Wall
-GP_CFLAGS=$(INCLUDES) -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC
-GPFLAGS=-g
-
-LIBS=-lpari -lreadline -ltermcap
-
-GP = gp
-GPC = $(addsuffix .c, $(GP))
-GPO = $(addsuffix .o, $(GP))
-GPH = $(addsuffix .h, $(GP))
-
-all: ecgen
-
-ecgen: ecgen.o $(GPO)
- $(CC) $(CFLAGS) -o $@ $^ $(LIBS)
-
-gp2c: $(GPC) $(GPH)
-
-$(GPO): $(GPC) $(GPH)
- $(CC) $(GP_CFLAGS) -c -o $@ $< $(LIBS)
-
-%.o: %.c $(GPH)
- $(CC) $(CFLAGS) -c -o $@ $< $(LIBS)
-
-%.h %.c: %.gp
- $(GP2C) $*.gp $(GPFLAGS) 2>/dev/null | { sed -u '/\/\*End of prototype\*\//q' >"$*.h"; echo '#include "$*.h"' >"$*.c"; cat >>"$*.c"; }
-
-.PHONY: clean-all clean clean-gp
-
-clean-all: clean clean-gp
-
-clean:
- rm -f ecgen
- rm -f *.o
-
-clean-gp:
- rm -f $(GPH)
- rm -f $(GPC)
- rm -f $(GPO)
diff --git a/README.md b/README.md
index 28108b4..560b3cc 100644
--- a/README.md
+++ b/README.md
@@ -2,35 +2,19 @@
Tool for generating Elliptic curve domain parameters.
-Currently only supports curves over prime fields.
-
### Usage
#### ecgen
The main binary of the tool, does the hard work.
```
-ecgen [-l|-s|-p]
- -l for point with the largest prime order on the curve
- -s for point with the smallest prime order on the curve
- -p for a generator of the whole curve as well as a smallest prime order point(pubkey)
-```
-ecgen then reads three lines of input:
-* `p` - a prime number, in hex, without hex prefix
-* `a` - a random number, in hex, without hex prefix
-* `b` - a random number, in hex, without hex prefix
-the curve is then specified as `E(Fp): y^2 = x^3 + a x + b mod p`
-
-#### gen.sh
-Utility script, uses OpenSSL to generate the *p*, *a*, *b* parameters
-required for ecgen.
-```
-gen.sh [-l|-s|-p] [num_curves] [prime_size] [timeout]
+ecgen --fp/--f2m -r BITS
```
-This script will generate `num_curves` curves with random `prime_size` bit size parameters.
-It requires a timeout value, as the curve order computation can get really
-slow for some unfortunate curve parameters, it is therefore more effective
-to skip those after some timeout.
-The `-l -s -p` options correspond to ecgen options.
+ - `--fp`/`--f2m` specifies the field type(prime/binary).
+ - `-r` requests a random curve to be generated, currently only supported feature.
+ - `-o/--output FILE` writes output to `FILE`.
+ - `-i/--input FILE` reads input from `FILE`.
+ - `-a/--append` appends to output file(doesn't overwrite it).
+ - `-d/--datadir DIR` specifies the PARI/GP datadir containing the `seadata` and `elldata` packages.
### Build
```
@@ -43,9 +27,19 @@ make
ecgen uses the [PARI/GP](http://pari.math.u-bordeaux.fr/) library for elliptic
curve arithmetic and it's SEA point counting algorithm implementation.
-gen.sh script uses [OpenSSL](https://www.openssl.org/) to generate the random domain parameters,
-although any library/language can be used here, ecgen does not require OpenSSL.
-
+### License
+```
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <http://www.gnu.org/licenses/>.
+```
*© Eastern Seaboard Phishing Authority*
diff --git a/ecgen.c b/ecgen.c
deleted file mode 100644
index bc7d190..0000000
--- a/ecgen.c
+++ /dev/null
@@ -1,76 +0,0 @@
-/**
- * @author J08nY
- * @license GPL v2.0
- * @version 0.1
- */
-
-#include "gp.h"
-
-#include <pari/pari.h>
-
-#include <readline/readline.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <unistd.h>
-
-/**
- *
- *
- */
-char *readHex(const char* prompt) {
- char *r = readline(prompt);
- size_t len = strlen(r);
- if (len > 2 && r[0] == '0' && (r[1] == 'x' || r[1] == 'X')){
- return r;
- }
-
- char *result = realloc(r, len + 3);
- memmove(result + 2, result, len + 1);
- result[0] = '0';
- result[1] = 'x';
- return result;
-}
-
-/**
- *
- *
- *
- */
-int main(int argc, char * argv[]) {
- GEN (*todo)(GEN,GEN,GEN,long) = &largest_prime;
- void (*print)(GEN) = &print_params;
-
- if (argc > 1) {
- if (!strcmp(argv[1], "-l")) {
- todo = &largest_prime;
- print = &print_params;
- } else if (!strcmp(argv[1], "-s")) {
- todo = &smallest_prime;
- print = &print_params;
- } else if (!strcmp(argv[1], "-p")) {
- todo = &small_pubkey;
- print = &print_params_pub;
- }
- }
-
- init_gp();
- pari_init( 1e9, 1e8 );
-
- //default0("datadir","./data");
-
- char *sp = readHex("p:");
- char *sa = readHex("a:");
- char *sb = readHex("b:");
-
- GEN p = strtoi(sp);
- GEN a = strtoi(sa);
- GEN b = strtoi(sb);
- free(sp);
- free(sa);
- free(sb);
-
- GEN result = (*todo)(p, a, b, 0);
- (*print)(result);
- pari_close();
- return 0;
-}
diff --git a/gp.c b/gp.c
deleted file mode 100644
index fa70fe7..0000000
--- a/gp.c
+++ /dev/null
@@ -1,357 +0,0 @@
-#include "gp.h"
-
-void
-init_gp(void) /* void */
-{
- pari_sp ltop = avma;
- avma = ltop;
- return;
-}
-
-void
-print_params(GEN curve) /* void */
-{
- pari_sp ltop = avma;
- printf0("%x,%x,%x,%x,%x,%x,%x\n", mkvecn(7, gel(curve, 1), gel(curve, 2), gel(curve, 3), gel(curve, 4), gel(curve, 5), gel(curve, 6), gel(curve, 7)));
- avma = ltop;
- return;
-}
-
-void
-print_params_pub(GEN curve) /* void */
-{
- pari_sp ltop = avma;
- printf0("%x,%x,%x,%x,%x,%x,%x,%x,%x,%x\n", mkvecn(10, gel(curve, 1), gel(curve, 2), gel(curve, 3), gel(curve, 4), gel(curve, 5), gel(curve, 6), gel(curve, 7), gel(curve, 8), gel(curve, 9), gel(curve, 10)));
- avma = ltop;
- return;
-}
-
-GEN
-pack_params(GEN p, GEN a, GEN b, GEN G) /* vec */
-{
- pari_sp ltop = avma;
- GEN p1 = gen_0; /* vec */
- p1 = cgetg(8, t_VEC);
- gel(p1, 1) = gcopy(p);
- gel(p1, 2) = gcopy(a);
- gel(p1, 3) = gcopy(b);
- gel(p1, 4) = lift(gel(gel(G, 1), 1));
- gel(p1, 5) = lift(gel(gel(G, 1), 2));
- gel(p1, 6) = gcopy(gel(G, 2));
- gel(p1, 7) = gcopy(gel(G, 3));
- p1 = gerepilecopy(ltop, p1);
- return p1;
-}
-
-/**
-* Finds random point of order n on curve e of order o.
-* @returns [[P.x, P.y], n, h]
-* @param e curve
-* @param o curve order
-* @param n desired point order
-*/
-GEN
-find_point(GEN e, GEN o, GEN n) /* vec */
-{
- pari_sp ltop = avma;
- GEN h = gen_0, P = gen_0;
- GEN p1 = gen_0; /* vec */
- h = gdivent(o, n);
- {
- pari_sp btop = avma;
- do
- {
- P = genrand(e);
- if (gc_needed(btop, 1))
- P = gerepilecopy(btop, P);
- } while(gequal0(ellmul(e, P, n)));
- }
- p1 = cgetg(4, t_VEC);
- gel(p1, 1) = gcopy(P);
- gel(p1, 2) = gcopy(n);
- gel(p1, 3) = gcopy(h);
- p1 = gerepilecopy(ltop, p1);
- return p1;
-}
-
-/**
-* Finds random points of orders given by vector p.
-* @returns vector of points in format [[P.x, P.y], n, h]
-* @param e curve
-* @param o curve order
-* @param p vector of point orders
-*/
-GEN
-find_points(GEN e, GEN o, GEN p) /* vec */
-{
- pari_sp ltop = avma;
- long l1;
- GEN p2 = gen_0; /* vec */
- l1 = glength(p);
- {
- long X;
- p2 = cgetg(l1+1, t_VEC);
- for (X = 1; X <= l1; ++X)
- gel(p2, X) = find_point(e, o, gel(p, X));
- }
- p2 = gerepilecopy(ltop, p2);
- return p2;
-}
-
-/*####################################################################*/
-
-GEN
-maxprime_order(GEN e, GEN o)
-{
- pari_sp ltop = avma;
- if (!gequal0(gisprime(o, 0)))
- {
- o = gerepilecopy(ltop, o);
- return o;
- }
- else
- {
- GEN p1 = gen_0;
- p1 = vecmax(factor(o));
- p1 = gerepilecopy(ltop, p1);
- return p1;
- }
- avma = ltop;
- return gen_0;
-}
-
-GEN
-minprime_order(GEN e, GEN o)
-{
- pari_sp ltop = avma;
- if (!gequal0(gisprime(o, 0)))
- {
- o = gerepilecopy(ltop, o);
- return o;
- }
- else
- {
- GEN p1 = gen_0;
- p1 = gcopy(gcoeff(factor(o), 1, 1));
- p1 = gerepilecopy(ltop, p1);
- return p1;
- }
- avma = ltop;
- return gen_0;
-}
-
-/*####################################################################*/
-
-GEN
-prime_orders(GEN e, GEN o)
-{
- pari_sp ltop = avma;
- GEN f = gen_0;
- if (!gequal0(gisprime(o, 0)))
- {
- GEN p1 = gen_0; /* vec */
- p1 = cgetg(2, t_VEC);
- gel(p1, 1) = gcopy(o);
- p1 = gerepilecopy(ltop, p1);
- return p1;
- }
- else
- {
- long l2;
- GEN p3 = gen_0; /* vec */
- f = factor(o);
- l2 = glength(f);
- {
- long X;
- p3 = cgetg(l2+1, t_VEC);
- for (X = 1; X <= l2; ++X)
- gel(p3, X) = gcopy(gcoeff(f, X, 1));
- }
- p3 = gerepilecopy(ltop, p3);
- return p3;
- }
- avma = ltop;
- return gen_0;
-}
-
-/**
-* E(Fp): y^2 = x^3 + ax + b mod p
-* @returns [p, a, b, G.x, G.y, n, h], G has the largest prime order possible
-* @param p
-* @param a
-* @param b
-*/
-GEN
-largest_prime(GEN p, GEN a, GEN b, long prec)
-{
- pari_sp ltop = avma;
- GEN e = gen_0, o = gen_0, G = gen_0;
- GEN p1 = gen_0, p2 = gen_0; /* vec */
- p1 = cgetg(3, t_VEC);
- gel(p1, 1) = gcopy(a);
- gel(p1, 2) = gcopy(b);
- e = ellinit(p1, p, prec);
- o = ellsea(e, 0);
- if (gequal0(o))
- {
- avma = ltop;
- return gen_0;
- }
- G = find_point(e, o, maxprime_order(o, gen_0));
- p2 = pack_params(p, a, b, G);
- p2 = gerepilecopy(ltop, p2);
- return p2;
-}
-
-/**
-* E(Fp): y^2 = x^3 + ax + b mod p
-* @returns [p, a, b, G.x, G.y, n, h], G has the smallest prime order possible
-* @param p
-* @param a
-* @param b
-*/
-GEN
-smallest_prime(GEN p, GEN a, GEN b, long prec)
-{
- pari_sp ltop = avma;
- GEN e = gen_0, o = gen_0, G = gen_0;
- GEN p1 = gen_0, p2 = gen_0; /* vec */
- p1 = cgetg(3, t_VEC);
- gel(p1, 1) = gcopy(a);
- gel(p1, 2) = gcopy(b);
- e = ellinit(p1, p, prec);
- o = ellsea(e, 0);
- if (gequal0(o))
- {
- avma = ltop;
- return gen_0;
- }
- G = find_point(e, o, minprime_order(o, gen_0));
- p2 = pack_params(p, a, b, G);
- p2 = gerepilecopy(ltop, p2);
- return p2;
-}
-
-/**
-* E(Fp): y^2 = x^3 + ax + b mod p
-* @returns [p, a, b, G.x, G.y, n, h=1], G is generator of E(Fp)
-* @param p
-* @param a
-* @param b
-*/
-GEN
-generator(GEN p, GEN a, GEN b, long prec)
-{
- pari_sp ltop = avma;
- GEN e = gen_0, o = gen_0, G = gen_0;
- GEN p1 = gen_0, p2 = gen_0; /* vec */
- p1 = cgetg(3, t_VEC);
- gel(p1, 1) = gcopy(a);
- gel(p1, 2) = gcopy(b);
- e = ellinit(p1, p, prec);
- o = ellsea(e, 0);
- if (gequal0(o))
- {
- avma = ltop;
- return gen_0;
- }
- G = find_point(e, o, o);
- p2 = pack_params(p, a, b, G);
- p2 = gerepilecopy(ltop, p2);
- return p2;
-}
-
-/**
-* E(Fp): y^2 = x^3 + ax + b mod p
-* @returns vector of domain parameters [p, a, b, G, n, h] points of all prime orders
-* @param p
-* @param a
-* @param b
-*/
-GEN
-all_prime(GEN p, GEN a, GEN b, long prec)
-{
- pari_sp ltop = avma;
- GEN e = gen_0, o = gen_0, G = gen_0;
- GEN p1 = gen_0; /* vec */
- long l2;
- GEN p3 = gen_0; /* vec */
- p1 = cgetg(3, t_VEC);
- gel(p1, 1) = gcopy(a);
- gel(p1, 2) = gcopy(b);
- e = ellinit(p1, p, prec);
- o = ellsea(e, 0);
- if (gequal0(o))
- {
- avma = ltop;
- return gen_0;
- }
- G = find_points(e, o, prime_orders(o, gen_0));
- l2 = glength(G);
- {
- long X;
- p3 = cgetg(l2+1, t_VEC);
- for (X = 1; X <= l2; ++X)
- gel(p3, X) = pack_params(p, a, b, gel(G, X));
- }
- p3 = gerepilecopy(ltop, p3);
- return p3;
-}
-
-/*####################################################################*/
-
-/**
-* E(Fp): y^2 = x^3 + ax + b mod p
-* @returns [p, a, b, G.x, G.y, r, k, P.x, P.y, n], G is generator of E(Fp), P has the smallest prime order
-*/
-GEN
-small_pubkey(GEN p, GEN a, GEN b, long prec)
-{
- pari_sp ltop = avma;
- GEN e = gen_0, o = gen_0, G = gen_0, f = gen_0, n = gen_0, r = gen_0, P = gen_0;
- GEN p1 = gen_0, p2 = gen_0; /* vec */
- p1 = cgetg(3, t_VEC);
- gel(p1, 1) = gcopy(a);
- gel(p1, 2) = gcopy(b);
- e = ellinit(p1, p, prec);
- o = ellsea(e, 0);
- if (gequal0(o))
- {
- avma = ltop;
- return gen_0;
- }
- if (!gequal0(gisprime(o, 0)))
- {
- G = genrand(e);
- n = o;
- r = o;
- P = genrand(e);
- }
- else
- {
- G = find_point(e, o, o);
- f = factor(o);
- n = gcopy(gcoeff(f, 1, 1));
- /*
- until(r % n == 0,
- G = random(e);
- r = ellorder(e, G);
- );
- */
- P = ellmul(e, G, gdivent(o, n));
- }
- p2 = cgetg(11, t_VEC);
- gel(p2, 1) = gcopy(p);
- gel(p2, 2) = gcopy(a);
- gel(p2, 3) = gcopy(b);
- gel(p2, 4) = lift(gel(G, 1));
- gel(p2, 5) = lift(gel(G, 2));
- gel(p2, 6) = gcopy(r);
- gel(p2, 7) = gdivent(o, r);
- gel(p2, 8) = lift(gel(P, 1));
- gel(p2, 9) = lift(gel(P, 2));
- gel(p2, 10) = gcopy(n);
- p2 = gerepilecopy(ltop, p2);
- return p2;
-}
-
diff --git a/gp.gp b/gp.gp
deleted file mode 100644
index 9d85a3f..0000000
--- a/gp.gp
+++ /dev/null
@@ -1,3 +0,0 @@
-\r utils
-\r points
-\r sea
diff --git a/gp.h b/gp.h
deleted file mode 100644
index 254173c..0000000
--- a/gp.h
+++ /dev/null
@@ -1,33 +0,0 @@
-/*-*- compile-command: "cc -c -o gp.gp.o -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -I"/usr/include/x86_64-linux-gnu" gp.gp.c && cc -o gp.gp.so -shared -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC -Wl,-shared -Wl,-z,relro gp.gp.o -lc -lm -L/usr/lib/x86_64-linux-gnu -lpari"; -*-*/
-#include <pari/pari.h>
-/*
-GP;install("init_gp","v","init_gp","./gp.gp.so");
-GP;install("print_params","vD0,G,","print_params","./gp.gp.so");
-GP;install("print_params_pub","vD0,G,","print_params_pub","./gp.gp.so");
-GP;install("pack_params","D0,G,D0,G,D0,G,D0,G,","pack_params","./gp.gp.so");
-GP;install("find_point","D0,G,D0,G,D0,G,","find_point","./gp.gp.so");
-GP;install("find_points","D0,G,D0,G,D0,G,","find_points","./gp.gp.so");
-GP;install("maxprime_order","D0,G,D0,G,","maxprime_order","./gp.gp.so");
-GP;install("minprime_order","D0,G,D0,G,","minprime_order","./gp.gp.so");
-GP;install("prime_orders","D0,G,D0,G,","prime_orders","./gp.gp.so");
-GP;install("largest_prime","D0,G,D0,G,D0,G,p","largest_prime","./gp.gp.so");
-GP;install("smallest_prime","D0,G,D0,G,D0,G,p","smallest_prime","./gp.gp.so");
-GP;install("generator","D0,G,D0,G,D0,G,p","generator","./gp.gp.so");
-GP;install("all_prime","D0,G,D0,G,D0,G,p","all_prime","./gp.gp.so");
-GP;install("small_pubkey","D0,G,D0,G,D0,G,p","small_pubkey","./gp.gp.so");
-*/
-void init_gp(void);
-void print_params(GEN curve);
-void print_params_pub(GEN curve);
-GEN pack_params(GEN p, GEN a, GEN b, GEN G);
-GEN find_point(GEN e, GEN o, GEN n);
-GEN find_points(GEN e, GEN o, GEN p);
-GEN maxprime_order(GEN e, GEN o);
-GEN minprime_order(GEN e, GEN o);
-GEN prime_orders(GEN e, GEN o);
-GEN largest_prime(GEN p, GEN a, GEN b, long prec);
-GEN smallest_prime(GEN p, GEN a, GEN b, long prec);
-GEN generator(GEN p, GEN a, GEN b, long prec);
-GEN all_prime(GEN p, GEN a, GEN b, long prec);
-GEN small_pubkey(GEN p, GEN a, GEN b, long prec);
-/*End of prototype*/
diff --git a/points.gp b/points.gp
deleted file mode 100644
index 428704e..0000000
--- a/points.gp
+++ /dev/null
@@ -1,56 +0,0 @@
-/**
- * Finds random point of order n on curve e of order o.
- * @returns [[P.x, P.y], n, h]
- * @param e curve
- * @param o curve order
- * @param n desired point order
- */
-find_point(e, o, n) = {
- local(h, P);
- h = o\n;
- until(ellmul(e, P, n),
- P = random(e);
- );
- return([P, n, h]);
-}
-
-/**
- * Finds random points of orders given by vector p.
- * @returns vector of points in format [[P.x, P.y], n, h]
- * @param e curve
- * @param o curve order
- * @param p vector of point orders
- */
-find_points(e, o, p) = {
- return(vector(length(p),X,find_point(e, o, p[X])));
-}
-
-/*####################################################################*/
-
-maxprime_order(e, o) = {
- if(isprime(o),
- return(o);
- ,
- return(vecmax(factor(o)));
- );
-}
-
-minprime_order(e, o) = {
- if(isprime(o),
- return(o);
- ,
- return(factor(o)[1,1]);
- );
-}
-
-/*####################################################################*/
-
-prime_orders(e, o) = {
- local(f);
- if(isprime(o),
- return([o]);
- ,
- f = factor(o);
- return(vector(length(f),X,f[X,1]));
- );
-}
diff --git a/sea.gp b/sea.gp
deleted file mode 100644
index a24ee2b..0000000
--- a/sea.gp
+++ /dev/null
@@ -1,100 +0,0 @@
-/**
- * E(Fp): y^2 = x^3 + ax + b mod p
- * @returns [p, a, b, G.x, G.y, n, h], G has the largest prime order possible
- * @param p
- * @param a
- * @param b
- */
-largest_prime(p, a, b) = {
- local(e, o, G);
- e = ellinit([a, b], p);
- o = ellsea(e);
- if(!o, return);
-
- G = find_point(e, o, maxprime_order(o));
- return(pack_params(p, a, b, G));
-}
-
-/**
- * E(Fp): y^2 = x^3 + ax + b mod p
- * @returns [p, a, b, G.x, G.y, n, h], G has the smallest prime order possible
- * @param p
- * @param a
- * @param b
- */
-smallest_prime(p, a, b) = {
- local(e, o, G);
- e = ellinit([a, b], p);
- o = ellsea(e);
- if(!o, return);
-
- G = find_point(e, o, minprime_order(o));
- return(pack_params(p, a, b, G));
-}
-
-/**
- * E(Fp): y^2 = x^3 + ax + b mod p
- * @returns [p, a, b, G.x, G.y, n, h=1], G is generator of E(Fp)
- * @param p
- * @param a
- * @param b
- */
-generator(p, a, b) = {
- local(e, o, G);
- e = ellinit([a, b], p);
- o = ellsea(e);
- if(!o, return);
-
- G = find_point(e, o, o);
- return(pack_params(p, a, b, G));
-}
-
-/**
- * E(Fp): y^2 = x^3 + ax + b mod p
- * @returns vector of domain parameters [p, a, b, G, n, h] points of all prime orders
- * @param p
- * @param a
- * @param b
- */
-all_prime(p, a, b) = {
- local(e, o, G);
- e = ellinit([a, b], p);
- o = ellsea(e);
- if(!o, return);
-
- G = find_points(e, o, prime_orders(o));
- return(vector(length(G),X,pack_params(p, a, b, G[X])));
-}
-
-/*####################################################################*/
-
-/**
- * E(Fp): y^2 = x^3 + ax + b mod p
- * @returns [p, a, b, G.x, G.y, r, k, P.x, P.y, n], G is generator of E(Fp), P has the smallest prime order
- */
-small_pubkey(p, a, b) = {
- local(e, o, G, f, n, r, P);
- e = ellinit([a, b], p);
- o = ellsea(e);
- if(!o, return);
-
- if(isprime(o),
- G = random(e);
- n = o;
- r = o;
- P = random(e);
- ,
- G = find_point(e, o, o);
- f = factor(o);
- n = f[1,1];
- /*
- until(r % n == 0,
- G = random(e);
- r = ellorder(e, G);
- );
- */
- P = ellmul(e, G, o\n);
- );
-
- return([p, a, b, lift(G[1]), lift(G[2]), r, o\r, lift(P[1]), lift(P[2]), n]);
-}
diff --git a/src/Makefile b/src/Makefile
new file mode 100644
index 0000000..6e4726a
--- /dev/null
+++ b/src/Makefile
@@ -0,0 +1,72 @@
+####
+#
+# ecgen, tool for generating Elliptic curve domain parameters
+# Copyright (C) 2017 J08nY
+#
+####
+
+CC=gcc
+GP2C=gp2c
+
+CFLAGS=-O3 -Wall
+LDFLAGS=
+
+GP_CFLAGS=-O3 -Wall -fomit-frame-pointer -fno-strict-aliasing -fPIC
+GPFLAGS=-g -i4
+
+INCLUDES=-I.
+LIBS=-lpari
+
+####
+
+GP = gp
+GPC = $(addsuffix .c, $(GP))
+GPO = $(addsuffix .o, $(GP))
+GPH = $(addsuffix .h, $(GP))
+
+SRC = cli input
+OBJ = $(addsuffix .o, $(SRC))
+HDR = $(addsuffix .h, $(SRC))
+
+####
+
+all: ecgen
+
+ecgen: ecgen.o $(GPO) $(OBJ)
+ $(CC) $(CFLAGS) $(INCLUDES) -o $@ $^ $(LDFLAGS) $(LIBS)
+
+gp2c: $(GPC) $(GPH)
+
+$(GPO): $(GPC) $(GPH)
+ $(CC) $(GP_CFLAGS) $(INCLUDES) -c -o $@ $< $(LDFLAGS) $(LIBS)
+
+%.o: %.c $(GPH)
+ $(CC) $(CFLAGS) $(INCLUDES) -c -o $@ $< $(LDFLAGS) $(LIBS)
+
+%.h %.c: %.gp
+ $(GP2C) $(GPFLAGS) gp/$*.gp 2>/dev/null | clang-format | awk 'BEGIN{print "#ifndef GP_H" > "gp.h"; print "#define GP_H" >> "gp.h";} { if(found) print >> "gp.c"; else print >> "gp.h"} /End of prototype/{found=1; print "#include \"gp.h\"" > "gp.c"; print "#endif //GP_H" >> "gp.h"}'
+
+####
+
+.PHONY: all gp2c clean-all clean clean-gp help
+
+clean-all: clean clean-gp
+
+clean:
+ rm -f ecgen
+ rm -f *.o
+
+clean-gp:
+ rm -f $(GPH)
+ rm -f $(GPC)
+
+help:
+ @echo "ecgen, tool for generating Elliptic curve domain parameters"
+ @echo
+ @echo "Available targets:"
+ @echo " - all : builds all"
+ @echo " - ecgen : builds the main binary"
+ @echo " - gp2c : generates the .c and .h files from gp code"
+ @echo " - clean : cleans up after a build"
+ @echo " - clean-gp : cleans up after gp2c generation"
+ @echo " - clean-all : cleans all"
diff --git a/src/cli.c b/src/cli.c
new file mode 100644
index 0000000..cdc2af4
--- /dev/null
+++ b/src/cli.c
@@ -0,0 +1,97 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "cli.h"
+
+char doc[] = "ecgen, tool for generating Elliptic curve domain parameters.\v(C) 2017 Eastern Seaboard Phishing Authority";
+char args_doc[] = "bits";
+
+enum opt_keys {
+ OPT_DATADIR = 'd',
+ OPT_APPEND = 'a',
+ OPT_PRIME = 'p',
+ OPT_OUTPUT = 'o',
+ OPT_INPUT = 'i',
+ OPT_RANDOM = 'r',
+ OPT_FP = 1,
+ OPT_F2M = 2,
+};
+
+struct argp_option options[] = {
+ // Field specification
+ {"fp", OPT_FP, 0, 0, "Prime field."},
+ {"f2m", OPT_F2M, 0, 0, "Binary field."},
+ // Curve specification
+ {"random", OPT_RANDOM, 0, 0, "Generate a random curve."},
+ {"prime", OPT_PRIME, 0, 0, "Generate a curve with prime order."},
+ // Other
+ {"data-dir", OPT_DATADIR, "DIR", 0,
+ "PARI/GP data directory (containing seadata and elldata)."},
+ {"input", OPT_INPUT, "FILE", 0, "Input from file."},
+ {"output", OPT_OUTPUT, "FILE", 0, "Output into file. Overwrites any existing file!"},
+ {"append", OPT_APPEND, 0, 0, "Append to output file(don't overwrite)."},
+ {0}};
+
+error_t parse_opt(int key, char *arg, struct argp_state *state) {
+ struct arguments *args = state->input;
+
+ switch (key) {
+ case OPT_DATADIR:
+ args->datadir = arg;
+ break;
+ case OPT_INPUT:
+ args->input = arg;
+ break;
+ case OPT_OUTPUT:
+ args->output = arg;
+ break;
+ case OPT_APPEND:
+ args->append = true;
+ break;
+ case OPT_RANDOM:
+ args->random = true;
+ break;
+ case OPT_PRIME:
+ args->prime = true;
+ break;
+ case OPT_FP:
+ if (args->binary_field) {
+ argp_failure(
+ state, 1, 0,
+ "Either specify prime field or binary field, not both.");
+ }
+ args->field = FIELD_PRIME;
+ args->prime_field = true;
+ break;
+ case OPT_F2M:
+ if (args->prime_field) {
+ argp_failure(
+ state, 1, 0,
+ "Either specify binary field or prime field, not both.");
+ }
+ args->field = FIELD_BINARY;
+ args->binary_field = true;
+ break;
+ case ARGP_KEY_ARG:
+ if (state->arg_num >= 1) {
+ argp_usage(state);
+ }
+
+ args->bits = strtol(arg, NULL, 10);
+ break;
+ case ARGP_KEY_END:
+ if (!args->prime_field && !args->binary_field) {
+ argp_failure(
+ state, 1, 0,
+ "Specify field type, prime or binary, with --fp / --f2m.");
+ }
+ break;
+ case ARGP_KEY_NO_ARGS:
+ argp_usage(state);
+ break;
+ default:
+ return ARGP_ERR_UNKNOWN;
+ }
+ return 0;
+}
diff --git a/src/cli.h b/src/cli.h
new file mode 100644
index 0000000..e9b832b
--- /dev/null
+++ b/src/cli.h
@@ -0,0 +1,36 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_CLI_H
+#define ECGEN_CLI_H
+
+#include <argp.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+extern char doc[];
+extern char args_doc[];
+extern struct argp_option options[];
+
+typedef enum {
+ FIELD_PRIME,
+ FIELD_BINARY
+} field_t;
+
+struct arguments {
+ field_t field;
+ bool binary_field;
+ bool prime_field;
+ bool random;
+ bool prime;
+ char *datadir;
+ char *output;
+ char *input;
+ bool append;
+ long bits;
+};
+
+error_t parse_opt(int key, char *arg, struct argp_state *state);
+
+#endif // ECGEN_CLI_H
diff --git a/src/curve.c b/src/curve.c
new file mode 100644
index 0000000..0d15ccf
--- /dev/null
+++ b/src/curve.c
@@ -0,0 +1,35 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "curve.h"
+
+GEN curve_random(GEN field) {
+ pari_sp ltop = avma;
+
+ GEN curve;
+ do {
+ GEN a = genrand(field);
+ GEN b = genrand(field);
+
+ GEN v = gen_0;
+ switch (typ(field)) {
+ case t_INT:
+ v = gtovec0(gen_0, 2);
+ gel(v, 1) = a;
+ gel(v, 2) = b;
+ break;
+ case t_FFELT:
+ v = gtovec0(gen_0, 5);
+ gel(v, 1) = gen_1;
+ gel(v, 4) = a;
+ gel(v, 5) = b;
+ break;
+ default:
+ pari_err_TYPE("curve_random", field);
+ }
+ curve = ellinit(v, field, -1);
+ } while (gequal0(ell_get_disc(curve)));
+
+ return gerepilecopy(ltop, curve);
+}
diff --git a/src/curve.h b/src/curve.h
new file mode 100644
index 0000000..106bf5e
--- /dev/null
+++ b/src/curve.h
@@ -0,0 +1,12 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_CURVE_H
+#define ECGEN_CURVE_H
+
+#include "gp.h"
+
+GEN curve_random(GEN field);
+
+#endif //ECGEN_CURVE_H
diff --git a/src/ecgen.c b/src/ecgen.c
new file mode 100644
index 0000000..4459805
--- /dev/null
+++ b/src/ecgen.c
@@ -0,0 +1,150 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+/**
+ * @author J08nY <johny@neuromancer.sk>
+ * @license GPL v2.0
+ * @version 0.2
+ */
+
+#include <time.h>
+#include "cli.h"
+#include "field.h"
+#include "curve.h"
+#include "output.h"
+
+const char *argp_program_version = "ecgen 0.2\n"
+ "Copyright (C) 2017 J08nY\n"
+ "License GPLv2: GNU GPL version 2 (or later) <http://gnu.org/licenses/gpl.html>\n"
+ "This is free software: you are free to change and redistribute it.\n"
+ "There is NO WARRANTY, to the extent permitted by law.";
+const char *argp_program_bug_address = "<johny@neuromancer.sk>";
+
+static struct argp argp = {options, parse_opt, args_doc, doc};
+static struct arguments args;
+static FILE *in;
+static FILE *out;
+
+bool init() {
+ // Init PARI, 1GB stack, 1M primes
+ pari_init(1000000000, 1000000);
+ init_gp();
+
+
+ // Init PARI PRNG
+ pari_ulong seed = 0;
+ // Try urandom first
+ FILE *rand = fopen("/dev/urandom", "rb");
+ if (rand) {
+ fread(&seed, sizeof(char), sizeof(pari_ulong), rand);
+ fclose(rand);
+ }
+ // Try worse methods later
+ if (seed == 0) {
+ struct timespec t;
+ if (!clock_gettime(CLOCK_REALTIME, &t)) {
+ seed = (pari_ulong) t.tv_nsec;
+ } else {
+ seed = (pari_ulong) time(NULL);
+ }
+ }
+
+ pari_sp ltop = avma;
+ setrand(utoi(seed));
+ avma = ltop;
+
+ //set datadir if specified
+ if (args.datadir) {
+ default0("datadir", args.datadir);
+ }
+
+ //open outfile
+ out = stdout;
+ if (args.output) {
+ out = fopen(args.output, args.append ? "a" : "w");
+ if (!out) {
+ //fallback to stdout and output err
+ out = stdout;
+ perror("Failed to open output file.");
+ }
+ }
+
+ //open infile
+ in = stdin;
+ if (args.input) {
+ in = fopen(args.input, "r");
+ if (!in) {
+ //fallback to stdin or quit?
+ in = stdin;
+ perror("Failed to open input file.");
+ }
+ }
+
+ return true;
+}
+
+int quit(int status) {
+ pari_close();
+
+ if (out != NULL && out != stdout) {
+ fclose(out);
+ }
+
+ if (in != NULL && in != stdout) {
+ fclose(in);
+ }
+
+ return status;
+}
+
+int main(int argc, char *argv[]) {
+ // Parse cli args
+ memset(&args, 0, sizeof(args));
+ argp_parse(&argp, argc, argv, 0, 0, &args);
+
+
+ if (!init()) {
+ return quit(1);
+ }
+
+ if (args.random) {
+ GEN field = gen_0;
+ switch (args.field) {
+ case FIELD_PRIME:
+ field = field_primer(args.bits);
+ break;
+ case FIELD_BINARY:
+ field = field_binaryr(args.bits);
+ break;
+ }
+ GEN curve = curve_random(field);
+ GEN ord = ellcard(curve, NULL);
+
+ GEN f = field_params(field);
+ GEN a = gtovec(field_elementi(ell_get_a4(curve)));
+ GEN b = gtovec(field_elementi(ell_get_a6(curve)));
+
+ GEN o = gconcat(gconcat(gconcat(f, a), b), gtovec(ord));
+
+ output_csv(out, ',', 'x', o);
+ } else {
+ fprintf(stderr, "Currently unsupported.");
+ }
+
+ return quit(0);
+}
diff --git a/src/field.c b/src/field.c
new file mode 100644
index 0000000..016f095
--- /dev/null
+++ b/src/field.c
@@ -0,0 +1,69 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "field.h"
+
+
+GEN field_primer(long bits) {
+ return random_prime(bits);
+}
+
+
+GEN field_binaryr(long bits) {
+ if (poly_exists(bits)) {
+ return poly_find_gen(bits);
+ } else {
+ fprintf(stderr, "Unable to find a suitable binary field. Use an explicit one.");
+ exit(1);
+ }
+}
+
+GEN field_params(GEN field) {
+ pari_sp ltop = avma;
+
+ long l2;
+ if (typ(field) == t_INT) {
+ GEN p3 = cgetg(2, t_VEC);
+ gel(p3, 1) = gcopy(field);
+ p3 = gerepilecopy(ltop, p3);
+ return p3;
+ }
+
+ GEN out = gtovec0(gen_0, 3);
+
+ long j = 1;
+ l2 = glength(member_mod(field)) - 2;
+ {
+ pari_sp btop = avma;
+ for (GEN i = gen_1; gcmpgs(i, l2) <= 0; i = gaddgs(i, 1)) {
+ GEN c = polcoeff0(member_mod(field), gtos(i), -1);
+ if (cmpis(c, 0) != 0) {
+ gel(out, j) = gcopy(i);
+ j++;
+ }
+ if (gc_needed(btop, 1)) gerepileall(btop, 4, &out, &c, &i);
+ }
+ }
+ out = gerepilecopy(ltop, out);
+ return out;
+}
+
+GEN field_elementi(GEN element) {
+ switch (typ(element)) {
+ case t_INT:
+ return element;
+ case t_INTMOD:
+ return lift(element);
+ case t_FFELT: {
+ pari_sp ltop = avma;
+ GEN coeffs = FF_to_FpXQ(element);
+ GEN vec = gtovec(coeffs);
+ GEN n = fromdigits(vec, stoi(2));
+ return gerepilecopy(ltop, n);
+ }
+ default:
+ pari_err_TYPE("field_elementi", element);
+ return NULL; /* NOT REACHABLE */
+ }
+} \ No newline at end of file
diff --git a/src/field.h b/src/field.h
new file mode 100644
index 0000000..55d6bf9
--- /dev/null
+++ b/src/field.h
@@ -0,0 +1,39 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_FIELD_H
+#define ECGEN_FIELD_H
+
+#include "poly.h"
+#include "gp.h"
+
+/**
+ *
+ * @param bits
+ * @return
+ */
+GEN field_primer(long bits);
+
+/**
+ *
+ * @param bits
+ * @return
+ */
+GEN field_binaryr(long bits);
+
+/**
+ * Extract a field representation from a field.
+ * - char(field) == 2:
+ * returns the vector of powers of middle coefficients of the reduction polynomial.
+ * - char(field) != 2:
+ * returns the field characteristic(p).-
+ *
+ * @param field
+ * @return field representation
+ */
+GEN field_params(GEN field);
+
+GEN field_elementi(GEN element);
+
+#endif //ECGEN_FIELD_H
diff --git a/src/gp.c b/src/gp.c
new file mode 100644
index 0000000..d15e117
--- /dev/null
+++ b/src/gp.c
@@ -0,0 +1,207 @@
+#include "gp.h"
+
+void init_gp(void) /* void */
+{
+ pari_sp ltop = avma;
+ avma = ltop;
+ return;
+}
+
+/*
+* ecgen, tool for generating Elliptic curve domain parameters
+* Copyright (C) 2017 J08nY
+*/
+
+/*
+* ecgen, tool for generating Elliptic curve domain parameters
+* Copyright (C) 2017 J08nY
+*/
+
+GEN random_primer(GEN range) /* int */
+{
+ pari_sp ltop = avma;
+ GEN p = gen_0; /* int */
+ if (!is_matvec_t(typ(range))) pari_err_TYPE("random_primer", range);
+ {
+ pari_sp btop = avma;
+ do {
+ p = randomprime(range);
+ if (gc_needed(btop, 1)) p = gerepilecopy(btop, p);
+ } while (!isprime(p));
+ }
+ p = gerepilecopy(ltop, p);
+ return p;
+}
+
+/**
+* Calculates a random prime of bit size bits.
+*
+* @param bits bit size of the requested prime
+* @return random prime between 2^(bits - 1) and 2^bits
+*/
+GEN random_prime(long bits) /* int */
+{
+ pari_sp ltop = avma;
+ GEN p1 = gen_0; /* vec */
+ GEN p2 = gen_0; /* int */
+ p1 = cgetg(3, t_VEC);
+ gel(p1, 1) = powis(gen_2, bits - 1);
+ gel(p1, 2) = powis(gen_2, bits);
+ p2 = random_primer(p1);
+ p2 = gerepilecopy(ltop, p2);
+ return p2;
+}
+
+GEN random_intr(GEN range) {
+ pari_sp ltop = avma;
+ GEN p1 = gen_0;
+ if (!is_matvec_t(typ(range))) pari_err_TYPE("random_intr", range);
+ p1 = genrand(range);
+ p1 = gerepilecopy(ltop, p1);
+ return p1;
+}
+
+/**
+* Generates a random integer with bit size bits.
+*
+* @param bits bit size of the requested integer
+* @return random int between 2^(bits - 1) and 2^bits
+*/
+GEN random_int(long bits) {
+ pari_sp ltop = avma;
+ GEN p1 = gen_0; /* vec */
+ GEN p2 = gen_0;
+ p1 = cgetg(3, t_VEC);
+ gel(p1, 1) = powis(gen_2, bits - 1);
+ gel(p1, 2) = powis(gen_2, bits);
+ p2 = random_intr(p1);
+ p2 = gerepilecopy(ltop, p2);
+ return p2;
+}
+
+/**
+* Converts a list to a vector.
+*
+* @param l list to convert
+* @return a vector of the lists values
+*/
+GEN list_to_vec(GEN l) /* vec */
+{
+ pari_sp ltop = avma;
+ GEN v = gen_0; /* vec */
+ GEN n = gen_0; /* int */
+ GEN p1 = gen_0; /* vec */
+ n = stoi(glength(l));
+ {
+ long l2;
+ p1 = cgetg(itos(n) + 1, t_VEC);
+ for (l2 = 1; cmpsi(l2, n) <= 0; ++l2) gel(p1, l2) = gen_0;
+ }
+ v = p1;
+ {
+ pari_sp btop = avma;
+ GEN i = gen_0;
+ for (i = gen_1; gcmp(i, n) <= 0; i = gaddgs(i, 1)) {
+ gel(v, gtos(i)) = gcopy(gel(list_data(l), gtos(i)));
+ if (gc_needed(btop, 1)) gerepileall(btop, 2, &v, &i);
+ }
+ }
+ v = gerepilecopy(ltop, v);
+ return v;
+}
+
+/*
+* ecgen, tool for generating Elliptic curve domain parameters
+* Copyright (C) 2017 J08nY
+*/
+
+/**
+* Computes primes upto some upper bound.
+*
+* @param bound an upper bound on primes
+* @return a vector of primes up to bound^2
+*/
+GEN prime_upto(GEN bound) /* vec */
+{
+ pari_sp ltop = avma;
+ GEN p = gen_0; /* list */
+ GEN product = gen_0, last = gen_0; /* int */
+ GEN result = gen_0; /* vec */
+ if (typ(bound) != t_INT) pari_err_TYPE("prime_upto", bound);
+ p = mklist();
+ bound = sqri(bound);
+ listput0(p, gen_2, 0);
+ product = gen_2;
+ last = gen_2;
+ {
+ pari_sp btop = avma;
+ while (cmpii(product, bound) < 0) {
+ last = nextprime(addis(last, 1));
+ listput0(p, last, 0);
+ product = mulii(product, last);
+ if (gc_needed(btop, 1)) gerepileall(btop, 3, &p, &product, &last);
+ }
+ }
+ result = list_to_vec(p);
+ listkill(p);
+ result = gerepilecopy(ltop, result);
+ return result;
+}
+
+/**
+*
+*/
+GEN invalid(GEN coeffs, GEN field, GEN primes, GEN bits, long prec) /* vec */
+{
+ pari_sp ltop = avma;
+ GEN bs = gen_0, cs = gen_0, eq = gen_0; /* vec */
+ GEN e = gen_0; /* ell */
+ GEN b = gen_0, n = gen_0, c = gen_0, o = gen_0; /* int */
+ GEN p1 = gen_0; /* vec */
+ if (!is_matvec_t(typ(coeffs))) pari_err_TYPE("invalid", coeffs);
+ if (typ(field) != t_POL) pari_err_TYPE("invalid", field);
+ if (!is_matvec_t(typ(primes))) pari_err_TYPE("invalid", primes);
+ if (typ(bits) != t_INT) pari_err_TYPE("invalid", bits);
+ n = stoi(lg(primes) - 1);
+ {
+ long l2;
+ p1 = cgetg(itos(n) + 1, t_VEC);
+ for (l2 = 1; cmpsi(l2, n) <= 0; ++l2) gel(p1, l2) = gen_0;
+ }
+ bs = p1;
+ eq = gcopy(coeffs);
+ c = gen_0;
+ {
+ pari_sp btop = avma;
+ while (cmpii(c, n) < 0) {
+ b = random_int(itos(bits));
+ gel(eq, 4) = icopy(b);
+ /* Times field? */
+
+ pari_CATCH(CATCH_ALL) {
+ GEN E = pari_err_last(); /* error */
+ continue;
+ }
+ pari_TRY { e = ellinit(eq, field, prec); }
+ pari_ENDCATCH o = ellsea(e, 0);
+ {
+ pari_sp btop = avma;
+ GEN i = gen_0;
+ for (i = gen_1; gcmp(i, n) <= 0; i = gaddgs(i, 1)) {
+ if (gequal0(gmod(o, gel(primes, gtos(i)))) &&
+ gequal0(gel(bs, gtos(i)))) {
+ gel(bs, gtos(i)) = icopy(b);
+ gel(cs, gtos(i)) = gcopy(e);
+ c = addis(c, 1);
+ }
+ if (gc_needed(btop, 1))
+ gerepileall(btop, 4, &bs, &cs, &c, &i);
+ }
+ }
+ if (gc_needed(btop, 1))
+ gerepileall(btop, 7, &bs, &cs, &eq, &e, &b, &c, &o);
+ }
+ }
+ cs = gerepilecopy(ltop, cs);
+ return cs;
+}
diff --git a/src/gp.h b/src/gp.h
new file mode 100644
index 0000000..c81c4c1
--- /dev/null
+++ b/src/gp.h
@@ -0,0 +1,28 @@
+#ifndef GP_H
+#define GP_H
+/*-*- compile-command: "cc -c -o gp/gp.gp.o -g -O3 -Wall -fomit-frame-pointer
+ * -fno-strict-aliasing -fPIC -I"/usr/include/x86_64-linux-gnu" gp/gp.gp.c && cc
+ * -o gp/gp.gp.so -shared -g -O3 -Wall -fomit-frame-pointer -fno-strict-aliasing
+ * -fPIC -Wl,-shared -Wl,-z,relro gp/gp.gp.o -lc -lm -L/usr/lib/x86_64-linux-gnu
+ * -lpari"; -*-*/
+#include <pari/pari.h>
+/*
+GP;install("init_gp","v","init_gp","./gp/gp.gp.so");
+GP;install("random_primer","G","random_primer","./gp/gp.gp.so");
+GP;install("random_prime","L","random_prime","./gp/gp.gp.so");
+GP;install("random_intr","G","random_intr","./gp/gp.gp.so");
+GP;install("random_int","L","random_int","./gp/gp.gp.so");
+GP;install("list_to_vec","G","list_to_vec","./gp/gp.gp.so");
+GP;install("prime_upto","G","prime_upto","./gp/gp.gp.so");
+GP;install("invalid","GGGGp","invalid","./gp/gp.gp.so");
+*/
+void init_gp(void);
+GEN random_primer(GEN range);
+GEN random_prime(long bits);
+GEN random_intr(GEN range);
+GEN random_int(long bits);
+GEN list_to_vec(GEN l);
+GEN prime_upto(GEN bound);
+GEN invalid(GEN coeffs, GEN field, GEN primes, GEN bits, long prec);
+/*End of prototype*/
+#endif //GP_H
diff --git a/src/gp/equation.gp b/src/gp/equation.gp
new file mode 100644
index 0000000..c1483e4
--- /dev/null
+++ b/src/gp/equation.gp
@@ -0,0 +1,28 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+/**
+ * Constructs an elliptic curve in the form E:
+ * y^2 = x^3 + ax + b, over a prime field
+ * @param a
+ * @param b
+ * @param p
+ * @returns elliptic curve
+ */
+prime_weierstrass(a:int, b:int, field:gen) = {
+ return(ellinit([a,b], field));
+}
+
+/**
+ * Constructs an elliptic curve in the form E:
+ * y^2 + xy = x^3 + ax + b, over a binary field.
+ * @param a
+ * @param b
+ * @param field
+ * @returns elliptic curve
+ */
+binary_weierstrass(a:int, b:int, field:gen) = {
+ return(ellinit([1,0,0,a,b], field));
+}
diff --git a/src/gp/field.gp b/src/gp/field.gp
new file mode 100644
index 0000000..c428abd
--- /dev/null
+++ b/src/gp/field.gp
@@ -0,0 +1,33 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+/**
+ * Extract a field representation from a field.
+ * - char(field) == 2:
+ * returns the vector of powers of middle coefficients of the reduction polynomial.
+ * - char(field) != 2:
+ * returns the field characteristic(p).
+ *
+ * @return field representation
+ */
+field_params(field:gen) = {
+ if(type(field) == "t_INT",
+ return([field]);
+ );
+
+ local(out:vec, j:int, c:int);
+ out = vector(3);
+
+ j = 1;
+ for(i=2, length(field.mod) - 2,
+ c = polcoeff(field.mod, i):int;
+ if(c != 0,
+ out[j] = i;
+ j++;
+ );
+ );
+
+ return(out);
+} \ No newline at end of file
diff --git a/src/gp/gp.gp b/src/gp/gp.gp
new file mode 100644
index 0000000..0124958
--- /dev/null
+++ b/src/gp/gp.gp
@@ -0,0 +1,7 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+\r gp/utils
+\r gp/invalid \ No newline at end of file
diff --git a/src/gp/invalid.gp b/src/gp/invalid.gp
new file mode 100644
index 0000000..4970014
--- /dev/null
+++ b/src/gp/invalid.gp
@@ -0,0 +1,59 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+/**
+ * Computes primes upto some upper bound.
+ *
+ * @param bound an upper bound on primes
+ * @return a vector of primes up to bound^2
+ */
+prime_upto(bound:int) = {
+ local(p:list, product:int, last:int, result:vec);
+ p = List();
+
+ bound = bound^2;
+ listput(p, 2);
+ product = 2;
+ last = 2;
+
+ while(product < bound,
+ last = nextprime(last + 1);
+ listput(p, last);
+ product = product * last;
+ );
+
+ result = list_to_vec(p);
+ listkill(p);
+ return(result);
+}
+
+/**
+ *
+ */
+invalid(coeffs:vec, field:pol, primes:vec, bits:int) = {
+ local(bs:vec, cs:vec, eq:vec, e:ell, b, n, c, o):int;
+ n = length(primes);
+ bs = vector(n);
+ eq = coeffs;
+ c = 0;
+
+ while(c < n,
+ b = random_int(bits):int;
+ eq[4] = b; /* Times field? */
+
+ iferr(e = ellinit(eq,field):ell, E, next());
+
+ o = ellsea(e):int;
+ for(i=1,n,
+ if((o % primes[i]) == 0 && bs[i] == 0,
+ bs[i] = b;
+ cs[i] = e;
+ c = c + 1;
+ );
+ );
+ );
+
+ return(cs);
+} \ No newline at end of file
diff --git a/src/gp/utils.gp b/src/gp/utils.gp
new file mode 100644
index 0000000..932a44a
--- /dev/null
+++ b/src/gp/utils.gp
@@ -0,0 +1,52 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+ random_primer(range:vec) = {
+ local(p:int);
+ until(isprime(p),
+ p = randomprime(range):int;
+ );
+ return(p);
+ }
+
+/**
+ * Calculates a random prime of bit size bits.
+ *
+ * @param bits bit size of the requested prime
+ * @return random prime between 2^(bits - 1) and 2^bits
+ */
+random_prime(bits:small) = {
+ return(random_primer([2^(bits-1), 2^bits]));
+}
+
+random_intr(range:vec) = {
+ return(random(range));
+}
+
+/**
+ * Generates a random integer with bit size bits.
+ *
+ * @param bits bit size of the requested integer
+ * @return random int between 2^(bits - 1) and 2^bits
+ */
+random_int(bits:small) = {
+ return(random_intr([2^(bits-1), 2^bits]));
+}
+
+/**
+ * Converts a list to a vector.
+ *
+ * @param l list to convert
+ * @return a vector of the lists values
+ */
+list_to_vec(l:list) = {
+ local(v:vec, n:int);
+ n = length(l);
+ v = vector(n);
+ for(i=1, n,
+ v[i] = l[i];
+ );
+ return(v);
+} \ No newline at end of file
diff --git a/src/input.c b/src/input.c
new file mode 100644
index 0000000..441fd47
--- /dev/null
+++ b/src/input.c
@@ -0,0 +1,135 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "input.h"
+
+/*
+ *
+ *char *prime_prompts[] = {"p:", "a:", "b:"};
+ param_t prime_params[] = {PARAM_PRIME, PARAM_INT, PARAM_INT};
+
+ char *binary_prompts[] = {"e1:", "e2:", "e3:", "a:", "b:"};
+ param_t binary_params[] = {PARAM_SHORT, PARAM_SHORT, PARAM_SHORT, PARAM_INT, PARAM_INT};
+
+ char **prompts;
+ param_t *params;
+ size_t length;
+ if (args.prime_field) {
+ prompts = prime_prompts;
+ params = prime_params;
+ length = 3;
+ } else {
+ prompts = binary_prompts;
+ params = binary_params;
+ length = 5;
+ }
+ GEN field;
+ GEN domain[length];
+
+ if (args.random) {
+ //random domain, might not define a curve... check disc
+ if (args.prime_field) {
+ field = ifield_prime(args.bits);
+ } else {
+ field = ifield_binary(args.bits);
+ }
+ } else {
+ for (size_t i = 0; i < length; ++i) {
+ domain[i] = fread_param(params[i], in, prompts[i], args.bits, in == stdin ? '\n' : ',');
+ if (equalii(domain[i], gen_m1)) {
+ fprintf(stderr, "Whoops?");
+ return quit(1);
+ }
+ }
+ if (args.prime_field) {
+ field = field_prime(domain[0]);
+ } else {
+ field = field_binary(args.bits, domain[0], domain[1], domain[2]);
+ }
+ }
+ pari_fprintf(out, "%Ps", field_params(field));
+
+ if (args.prime_field) {
+ GEN field = prime_field(p);
+ GEN curve = prime_weierstrass(a, b, field, 0);
+ } else if (args.binary_field) {
+ GEN e[3];
+ for (size_t i = 0; i < 3; ++i) {
+ char prompt[] = {'e', (char) ('1' + i), ':', 0};
+ e[i] = read_short(prompt, '\n');
+ }
+ GEN a = read_int("a:", args.bits, '\n');
+
+ GEN field = binary_field(args.bits, e[0], e[1], e[2]);
+ }
+*/
+
+
+GEN fread_i(FILE *stream, const char *prompt, long bits, int delim,
+ GEN (*rand_func)(long)) {
+ printf("%s ", prompt);
+ char *line = NULL;
+ size_t n = 0;
+
+ ssize_t len = getdelim(&line, &n, delim, stream);
+ if (len == 1) {
+ free(line);
+ if (rand_func) {
+ return rand_func(bits);
+ } else {
+ return gen_0;
+ }
+ }
+ pari_sp ltop = avma;
+ GEN in = strtoi(line);
+ free(line);
+
+ // check bitsize here
+ GEN size = int2n(bits);
+ if (cmpii(in, size)) {
+ return gerepileupto(ltop, in);
+ } else {
+ fprintf(stderr, "Number too big(> %ld bits).\n", bits);
+ return gen_m1;
+ }
+}
+
+GEN fread_prime(FILE *stream, const char *prompt, long bits, int delim) {
+ GEN read = fread_i(stream, prompt, bits, delim, &random_prime);
+ if (equalii(read, gen_m1)) {
+ return read;
+ } else {
+ if (isprime(read)) {
+ return read;
+ } else {
+ fprintf(stderr, "Number is not prime. Prime required.\n");
+ return gen_m1;
+ }
+ }
+}
+
+GEN fread_int(FILE *stream, const char *prompt, long bits, int delim) {
+ return fread_i(stream, prompt, bits, delim, &random_int);
+}
+
+GEN fread_short(FILE *stream, const char *prompt, int delim) {
+ return fread_i(stream, prompt, 16, delim, NULL);
+}
+
+GEN fread_param(param_t param, FILE *stream, const char *prompt, long bits, int delim) {
+ switch (param) {
+ case PARAM_PRIME:
+ return fread_prime(stream, prompt, bits, delim);
+ case PARAM_INT:
+ return fread_int(stream, prompt, bits, delim);
+ case PARAM_SHORT:
+ return fread_short(stream, prompt, delim);
+ }
+ return gen_m1;
+}
+
+GEN read_param(param_t param, const char *prompt, long bits, int delim) {
+ return fread_param(param, stdin, prompt, bits, delim);
+}
+
diff --git a/src/input.h b/src/input.h
new file mode 100644
index 0000000..b0ab421
--- /dev/null
+++ b/src/input.h
@@ -0,0 +1,51 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_INPUT_H
+#define ECGEN_INPUT_H
+
+#include "gp.h"
+
+typedef enum PARAM {
+ PARAM_PRIME,
+ PARAM_INT,
+ PARAM_SHORT
+} param_t;
+
+/**
+ *
+ * @param stream
+ * @param prompt
+ * @param bits
+ * @param delim
+ * @return
+ */
+GEN fread_prime(FILE *stream, const char *prompt, long bits, int delim);
+
+/**
+ *
+ * @param stream
+ * @param prompt
+ * @param bits
+ * @param delim
+ * @return
+ */
+GEN fread_int(FILE *stream, const char *prompt, long bits, int delim);
+
+/**
+ *
+ * @param stream
+ * @param prompt
+ * @param delim
+ * @return
+ */
+GEN fread_short(FILE *stream, const char *prompt, int delim);
+
+
+GEN fread_param(param_t param, FILE *stream, const char *prompt, long bits, int delim);
+
+GEN read_param(param_t param, const char *prompt, long bits, int delim);
+
+
+#endif //ECGEN_INPUT_H
diff --git a/src/output.c b/src/output.c
new file mode 100644
index 0000000..26f4f89
--- /dev/null
+++ b/src/output.c
@@ -0,0 +1,42 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "output.h"
+
+void output_csv(FILE *out, char delim, char format, GEN vector) {
+ char fmt[] = {'%', 'P', format, 0};
+
+ long len = lg(vector) - 1;
+ char *params[len];
+ size_t lengths[len];
+ size_t total = 0;
+ for (long i = 0; i < len; ++i) {
+ params[i] = pari_sprintf(fmt, gel(vector, i + 1));
+ lengths[i] = strlen(params[i]);
+ total += lengths[i];
+ }
+
+ char *result = malloc(total + len);
+ if (!result) {
+ perror("Couldn't malloc.");
+ exit(1);
+ }
+
+ size_t offset = 0;
+ for (long i = 0; i < len; ++i) {
+ memcpy(result + offset, params[i], lengths[i]);
+ free(params[i]);
+
+ offset += lengths[i];
+ if (i != len - 1) {
+ result[offset] = delim;
+ offset++;
+ }
+ }
+ result[offset] = 0;
+
+ fprintf(out, "%s", result);
+ free(result);
+}
+
diff --git a/src/output.h b/src/output.h
new file mode 100644
index 0000000..f3632a1
--- /dev/null
+++ b/src/output.h
@@ -0,0 +1,12 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_OUTPUT_H
+#define ECGEN_OUTPUT_H
+
+#include "gp.h"
+
+void output_csv(FILE *out, char delim, char format, GEN vector);
+
+#endif //ECGEN_OUTPUT_H
diff --git a/src/poly.c b/src/poly.c
new file mode 100644
index 0000000..89e2c74
--- /dev/null
+++ b/src/poly.c
@@ -0,0 +1,540 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "poly.h"
+#include <stdlib.h>
+
+polynomial_t ansi_trinomials[] = {
+ {161, 18}, {162, 27}, {166, 37}, {167, 6}, {169, 34},
+ {170, 11}, {172, 1}, {174, 13}, {175, 6}, {177, 8},
+ {178, 31}, {180, 3}, {182, 81}, {183, 56}, {185, 24},
+ {186, 11}, {191, 9}, {193, 15}, {194, 87}, {196, 3},
+ {198, 9}, {199, 34}, {201, 14}, {202, 55}, {204, 27},
+ {207, 43}, {209, 6}, {210, 7}, {212, 105}, {214, 73},
+ {215, 23}, {217, 45}, {218, 11}, {220, 7}, {223, 33},
+ {225, 32}, {228, 113}, {231, 26}, {233, 74}, {234, 31},
+ {236, 5}, {238, 73}, {239, 36}, {241, 70}, {242, 95},
+ {244, 111}, {247, 82}, {249, 35}, {250, 103}, {252, 15},
+ {253, 46}, {255, 52}, {257, 12}, {258, 71}, {260, 15},
+ {263, 93}, {265, 42}, {266, 47}, {268, 25}, {270, 53},
+ {271, 58}, {273, 23}, {274, 67}, {276, 63}, {278, 5},
+ {279, 5}, {281, 93}, {282, 35}, {284, 53}, {286, 69},
+ {287, 71}, {289, 21}, {292, 37}, {294, 33}, {295, 48},
+ {297, 5}, {300, 5}, {302, 41}, {303, 1}, {305, 102},
+ {308, 15}, {310, 93}, {313, 79}, {314, 15}, {316, 63},
+ {318, 45}, {319, 36}, {321, 31}, {322, 67}, {324, 51},
+ {327, 34}, {329, 50}, {330, 99}, {332, 89}, {333, 2},
+ {337, 55}, {340, 45}, {342, 125}, {343, 75}, {345, 22},
+ {346, 63}, {348, 103}, {350, 53}, {351, 34}, {353, 69},
+ {354, 99}, {358, 57}, {359, 68}, {362, 63}, {364, 9},
+ {366, 29}, {367, 21}, {369, 91}, {370, 139}, {372, 111},
+ {375, 16}, {377, 41}, {378, 43}, {380, 47}, {382, 81},
+ {383, 90}, {385, 6}, {386, 83}, {388, 159}, {390, 9},
+ {391, 28}, {393, 7}, {394, 135}, {396, 25}, {399, 26},
+ {401, 152}, {402, 171}, {404, 65}, {406, 141}, {407, 71},
+ {409, 87}, {412, 147}, {414, 13}, {415, 102}, {417, 107},
+ {418, 199}, {420, 7}, {422, 149}, {423, 25}, {425, 12},
+ {426, 63}, {428, 105}, {431, 120}, {433, 33}, {436, 165},
+ {438, 65}, {439, 49}, {441, 7}, {444, 81}, {446, 105},
+ {447, 73}, {449, 134}, {450, 47}, {455, 38}, {457, 16},
+ {458, 203}, {460, 19}, {462, 73}, {463, 93}, {465, 31},
+ {468, 27}, {470, 9}, {471, 1}, {473, 200}, {474, 191},
+ {476, 9}, {478, 121}, {479, 104}, {481, 138}, {484, 105},
+ {486, 81}, {487, 94}, {489, 83}, {490, 219}, {492, 7},
+ {494, 17}, {495, 76}, {497, 78}, {498, 155}, {500, 27},
+ {503, 3}, {505, 156}, {506, 23}, {508, 9}, {510, 69},
+ {511, 10}, {513, 26}, {514, 67}, {516, 21}, {518, 33},
+ {519, 79}, {521, 32}, {522, 39}, {524, 167}, {526, 97},
+ {527, 47}, {529, 42}, {532, 1}, {534, 161}, {537, 94},
+ {538, 195}, {540, 9}, {543, 16}, {545, 122}, {550, 193},
+ {551, 135}, {553, 39}, {556, 153}, {558, 73}, {559, 34},
+ {561, 71}, {564, 163}, {566, 153}, {567, 28}, {569, 77},
+ {570, 67}, {574, 13}, {575, 146}, {577, 25}, {580, 237},
+ {582, 85}, {583, 130}, {585, 88}, {588, 35}, {590, 93},
+ {593, 86}, {594, 19}, {596, 273}, {599, 30}, {601, 201},
+ {602, 215}, {604, 105}, {606, 165}, {607, 105}, {609, 31},
+ {610, 127}, {612, 81}, {614, 45}, {615, 211}, {617, 200},
+ {618, 295}, {620, 9}, {622, 297}, {623, 68}, {625, 133},
+ {626, 251}, {628, 223}, {631, 307}, {633, 101}, {634, 39},
+ {636, 217}, {639, 16}, {641, 11}, {642, 119}, {646, 249},
+ {647, 5}, {649, 37}, {650, 3}, {651, 14}, {652, 93},
+ {654, 33}, {655, 88}, {657, 38}, {658, 55}, {660, 11},
+ {662, 21}, {663, 107}, {665, 33}, {668, 147}, {670, 153},
+ {671, 15}, {673, 28}, {676, 31}, {679, 66}, {682, 171},
+ {684, 209}, {686, 197}, {687, 13}, {689, 14}, {690, 79},
+ {692, 299}, {694, 169}, {695, 177}, {697, 267}, {698, 215},
+ {700, 75}, {702, 37}, {705, 17}, {708, 15}, {711, 92},
+ {713, 41}, {714, 23}, {716, 183}, {718, 165}, {719, 150},
+ {721, 9}, {722, 231}, {724, 207}, {726, 5}, {727, 180},
+ {729, 58}, {730, 147}, {732, 343}, {735, 44}, {737, 5},
+ {738, 347}, {740, 135}, {742, 85}, {743, 90}, {745, 258},
+ {746, 351}, {748, 19}, {750, 309}, {751, 18}, {753, 158},
+ {754, 19}, {756, 45}, {758, 233}, {759, 98}, {761, 3},
+ {762, 83}, {767, 168}, {769, 120}, {772, 7}, {774, 185},
+ {775, 93}, {777, 29}, {778, 375}, {780, 13}, {782, 329},
+ {783, 68}, {785, 92}, {791, 30}, {793, 253}, {794, 143},
+ {798, 53}, {799, 25}, {801, 217}, {804, 75}, {806, 21},
+ {807, 7}, {809, 15}, {810, 159}, {812, 29}, {814, 21},
+ {815, 333}, {817, 52}, {818, 119}, {820, 123}, {822, 17},
+ {823, 9}, {825, 38}, {826, 255}, {828, 189}, {831, 49},
+ {833, 149}, {834, 15}, {838, 61}, {839, 54}, {841, 144},
+ {842, 47}, {844, 105}, {845, 2}, {846, 105}, {847, 136},
+ {849, 253}, {850, 111}, {852, 159}, {855, 29}, {857, 119},
+ {858, 207}, {860, 35}, {861, 14}, {862, 349}, {865, 1},
+ {866, 75}, {868, 145}, {870, 301}, {871, 378}, {873, 352},
+ {876, 149}, {879, 11}, {881, 78}, {882, 99}, {884, 173},
+ {887, 147}, {889, 127}, {890, 183}, {892, 31}, {894, 173},
+ {895, 12}, {897, 113}, {898, 207}, {900, 1}, {902, 21},
+ {903, 35}, {905, 117}, {906, 123}, {908, 143}, {911, 204},
+ {913, 91}, {916, 183}, {918, 77}, {919, 36}, {921, 221},
+ {924, 31}, {926, 365}, {927, 403}, {930, 31}, {932, 177},
+ {935, 417}, {937, 217}, {938, 207}, {942, 45}, {943, 24},
+ {945, 77}, {948, 189}, {951, 260}, {953, 168}, {954, 131},
+ {956, 305}, {959, 143}, {961, 18}, {964, 103}, {966, 201},
+ {967, 36}, {969, 31}, {972, 7}, {975, 19}, {977, 15},
+ {979, 178}, {982, 177}, {983, 230}, {985, 222}, {986, 3},
+ {988, 121}, {990, 161}, {991, 39}, {993, 62}, {994, 223},
+ {996, 65}, {998, 101}, {999, 59}, {1001, 17}, {1007, 75},
+ {1009, 55}, {1010, 99}, {1012, 115}, {1014, 385}, {1015, 186},
+ {1020, 135}, {1022, 317}, {1023, 7}, {1025, 294}, {1026, 35},
+ {1028, 119}, {1029, 98}, {1030, 93}, {1031, 68}, {1033, 108},
+ {1034, 75}, {1036, 411}, {1039, 21}, {1041, 412}, {1042, 439},
+ {1044, 41}, {1047, 10}, {1049, 141}, {1050, 159}, {1052, 291},
+ {1054, 105}, {1055, 24}, {1057, 198}, {1058, 27}, {1062, 49},
+ {1063, 168}, {1065, 463}, {1071, 7}, {1078, 361}, {1079, 230},
+ {1081, 24}, {1082, 407}, {1084, 189}, {1085, 62}, {1086, 189},
+ {1087, 112}, {1089, 91}, {1090, 79}, {1092, 23}, {1094, 57},
+ {1095, 139}, {1097, 14}, {1098, 83}, {1100, 35}, {1102, 117},
+ {1103, 65}, {1105, 21}, {1106, 195}, {1108, 327}, {1110, 417},
+ {1111, 13}, {1113, 107}, {1116, 59}, {1119, 283}, {1121, 62},
+ {1122, 427}, {1126, 105}, {1127, 27}, {1129, 103}, {1130, 551},
+ {1134, 129}, {1135, 9}, {1137, 277}, {1138, 31}, {1140, 141},
+ {1142, 357}, {1145, 227}, {1146, 131}, {1148, 23}, {1151, 90},
+ {1153, 241}, {1154, 75}, {1156, 307}, {1158, 245}, {1159, 66},
+ {1161, 365}, {1164, 19}, {1166, 189}, {1167, 133}, {1169, 114},
+ {1170, 27}, {1174, 133}, {1175, 476}, {1177, 16}, {1178, 375},
+ {1180, 25}, {1182, 77}, {1183, 87}, {1185, 134}, {1186, 171},
+ {1188, 75}, {1190, 233}, {1191, 196}, {1193, 173}, {1196, 281},
+ {1198, 405}, {1199, 114}, {1201, 171}, {1202, 287}, {1204, 43},
+ {1206, 513}, {1207, 273}, {1209, 118}, {1210, 243}, {1212, 203},
+ {1214, 257}, {1215, 302}, {1217, 393}, {1218, 91}, {1220, 413},
+ {1223, 255}, {1225, 234}, {1226, 167}, {1228, 27}, {1230, 433},
+ {1231, 105}, {1233, 151}, {1234, 427}, {1236, 49}, {1238, 153},
+ {1239, 4}, {1241, 54}, {1242, 203}, {1246, 25}, {1247, 14},
+ {1249, 187}, {1252, 97}, {1255, 589}, {1257, 289}, {1260, 21},
+ {1263, 77}, {1265, 119}, {1266, 7}, {1268, 345}, {1270, 333},
+ {1271, 17}, {1273, 168}, {1276, 217}, {1278, 189}, {1279, 216},
+ {1281, 229}, {1282, 231}, {1284, 223}, {1286, 153}, {1287, 470},
+ {1289, 99}, {1294, 201}, {1295, 38}, {1297, 198}, {1298, 399},
+ {1300, 75}, {1302, 77}, {1305, 326}, {1306, 39}, {1308, 495},
+ {1310, 333}, {1311, 476}, {1313, 164}, {1314, 19}, {1319, 129},
+ {1321, 52}, {1324, 337}, {1326, 397}, {1327, 277}, {1329, 73},
+ {1332, 95}, {1334, 617}, {1335, 392}, {1337, 75}, {1338, 315},
+ {1340, 125}, {1343, 348}, {1345, 553}, {1348, 553}, {1350, 237},
+ {1351, 39}, {1353, 371}, {1354, 255}, {1356, 131}, {1358, 117},
+ {1359, 98}, {1361, 56}, {1362, 655}, {1364, 239}, {1366, 1},
+ {1367, 134}, {1369, 88}, {1372, 181}, {1374, 609}, {1375, 52},
+ {1377, 100}, {1380, 183}, {1383, 130}, {1385, 12}, {1386, 219},
+ {1388, 11}, {1390, 129}, {1391, 3}, {1393, 300}, {1396, 97},
+ {1398, 601}, {1399, 55}, {1401, 92}, {1402, 127}, {1404, 81},
+ {1407, 47}, {1409, 194}, {1410, 383}, {1412, 125}, {1414, 429},
+ {1415, 282}, {1417, 342}, {1420, 33}, {1422, 49}, {1423, 15},
+ {1425, 28}, {1426, 103}, {1428, 27}, {1430, 33}, {1431, 17},
+ {1433, 387}, {1434, 363}, {1436, 83}, {1438, 357}, {1441, 322},
+ {1442, 395}, {1444, 595}, {1446, 421}, {1447, 195}, {1449, 13},
+ {1452, 315}, {1454, 297}, {1455, 52}, {1457, 314}, {1458, 243},
+ {1460, 185}, {1463, 575}, {1465, 39}, {1466, 311}, {1468, 181},
+ {1470, 49}, {1471, 25}, {1473, 77}, {1476, 21}, {1478, 69},
+ {1479, 49}, {1481, 32}, {1482, 411}, {1486, 85}, {1487, 140},
+ {1489, 252}, {1490, 279}, {1492, 307}, {1495, 94}, {1497, 49},
+ {1500, 25}, {1503, 80}, {1505, 246}, {1508, 599}, {1510, 189},
+ {1511, 278}, {1513, 399}, {1514, 299}, {1516, 277}, {1518, 69},
+ {1519, 220}, {1521, 229}, {1524, 27}, {1526, 473}, {1527, 373},
+ {1529, 60}, {1530, 207}, {1534, 225}, {1535, 404}, {1537, 46},
+ {1540, 75}, {1542, 365}, {1543, 445}, {1545, 44}, {1548, 63},
+ {1550, 189}, {1551, 557}, {1553, 252}, {1554, 99}, {1556, 65},
+ {1558, 9}, {1559, 119}, {1561, 339}, {1562, 95}, {1564, 7},
+ {1566, 77}, {1567, 127}, {1569, 319}, {1570, 667}, {1572, 501},
+ {1575, 17}, {1577, 341}, {1578, 731}, {1580, 647}, {1582, 121},
+ {1583, 20}, {1585, 574}, {1586, 399}, {1588, 85}, {1590, 169},
+ {1591, 15}, {1593, 568}, {1596, 3}, {1599, 643}, {1601, 548},
+ {1602, 783}, {1604, 317}, {1606, 153}, {1607, 87}, {1609, 231},
+ {1612, 771}, {1615, 103}, {1617, 182}, {1618, 211}, {1620, 27},
+ {1623, 17}, {1625, 69}, {1628, 603}, {1630, 741}, {1631, 668},
+ {1633, 147}, {1634, 227}, {1636, 37}, {1638, 173}, {1639, 427},
+ {1641, 287}, {1642, 231}, {1647, 310}, {1649, 434}, {1650, 579},
+ {1652, 45}, {1655, 53}, {1657, 16}, {1660, 37}, {1663, 99},
+ {1665, 176}, {1666, 271}, {1668, 459}, {1671, 202}, {1673, 90},
+ {1674, 755}, {1676, 363}, {1678, 129}, {1679, 20}, {1681, 135},
+ {1687, 31}, {1689, 758}, {1692, 359}, {1694, 501}, {1695, 29},
+ {1697, 201}, {1698, 459}, {1700, 225}, {1703, 161}, {1705, 52},
+ {1708, 93}, {1710, 201}, {1711, 178}, {1713, 250}, {1716, 221},
+ {1719, 113}, {1721, 300}, {1722, 39}, {1724, 261}, {1726, 753},
+ {1729, 94}, {1734, 461}, {1735, 418}, {1737, 403}, {1738, 267},
+ {1740, 259}, {1742, 869}, {1743, 173}, {1745, 369}, {1746, 255},
+ {1748, 567}, {1750, 457}, {1751, 482}, {1753, 775}, {1756, 99},
+ {1759, 165}, {1764, 105}, {1767, 250}, {1769, 327}, {1770, 279},
+ {1772, 371}, {1774, 117}, {1775, 486}, {1777, 217}, {1778, 635},
+ {1780, 457}, {1782, 57}, {1783, 439}, {1785, 214}, {1788, 819},
+ {1790, 593}, {1791, 190}, {1793, 114}, {1798, 69}, {1799, 312},
+ {1801, 502}, {1802, 843}, {1804, 747}, {1806, 101}, {1807, 123},
+ {1809, 521}, {1810, 171}, {1814, 545}, {1815, 163}, {1817, 479},
+ {1818, 495}, {1820, 11}, {1823, 684}, {1825, 9}, {1828, 273},
+ {1830, 381}, {1831, 51}, {1833, 518}, {1836, 243}, {1838, 53},
+ {1839, 836}, {1841, 66}, {1844, 339}, {1846, 901}, {1847, 180},
+ {1849, 49}, {1854, 885}, {1855, 39}, {1857, 688}, {1860, 13},
+ {1862, 149}, {1863, 260}, {1865, 53}, {1866, 11}, {1870, 121},
+ {1871, 261}, {1873, 199}, {1878, 253}, {1879, 174}, {1881, 370},
+ {1884, 669}, {1886, 833}, {1887, 353}, {1889, 29}, {1890, 371},
+ {1895, 873}, {1900, 235}, {1902, 733}, {1903, 778}, {1905, 344},
+ {1906, 931}, {1908, 945}, {1911, 67}, {1913, 462}, {1918, 477},
+ {1919, 105}, {1921, 468}, {1924, 327}, {1926, 357}, {1927, 25},
+ {1929, 31}, {1932, 277}, {1934, 413}, {1935, 103}, {1937, 231},
+ {1938, 747}, {1940, 113}, {1943, 11}, {1945, 91}, {1946, 51},
+ {1948, 603}, {1950, 9}, {1951, 121}, {1953, 17}, {1956, 279},
+ {1958, 89}, {1959, 371}, {1961, 771}, {1962, 99}, {1964, 21},
+ {1966, 801}, {1967, 26}, {1969, 175}, {1974, 165}, {1975, 841},
+ {1977, 238}, {1980, 33}, {1983, 113}, {1985, 311}, {1986, 891},
+ {1988, 555}, {1990, 133}, {1991, 546}, {1993, 103}, {1994, 15},
+ {1996, 307}, {1999, 367}};
+
+polynomial_t ansi_pentanomials[] = {
+ {160, 1, 2, 117}, {163, 1, 2, 8}, {164, 1, 2, 49},
+ {165, 1, 2, 25}, {168, 1, 2, 65}, {171, 1, 3, 42},
+ {173, 1, 2, 10}, {176, 1, 2, 43}, {179, 1, 2, 4},
+ {181, 1, 2, 89}, {184, 1, 2, 81}, {187, 1, 2, 20},
+ {188, 1, 2, 60}, {189, 1, 2, 49}, {190, 1, 2, 47},
+ {192, 1, 2, 7}, {195, 1, 2, 37}, {197, 1, 2, 21},
+ {200, 1, 2, 81}, {203, 1, 2, 45}, {205, 1, 2, 21},
+ {206, 1, 2, 63}, {208, 1, 2, 83}, {211, 1, 2, 165},
+ {213, 1, 2, 62}, {216, 1, 2, 107}, {219, 1, 2, 65},
+ {221, 1, 2, 18}, {222, 1, 2, 73}, {224, 1, 2, 159},
+ {226, 1, 2, 30}, {227, 1, 2, 21}, {229, 1, 2, 21},
+ {230, 1, 2, 13}, {232, 1, 2, 23}, {235, 1, 2, 45},
+ {237, 1, 2, 104}, {240, 1, 3, 49}, {243, 1, 2, 17},
+ {245, 1, 2, 37}, {246, 1, 2, 11}, {248, 1, 2, 243},
+ {251, 1, 2, 45}, {254, 1, 2, 7}, {256, 1, 2, 155},
+ {259, 1, 2, 254}, {261, 1, 2, 74}, {262, 1, 2, 207},
+ {264, 1, 2, 169}, {267, 1, 2, 29}, {269, 1, 2, 117},
+ {272, 1, 3, 56}, {275, 1, 2, 28}, {277, 1, 2, 33},
+ {280, 1, 2, 113}, {283, 1, 2, 200}, {285, 1, 2, 77},
+ {288, 1, 2, 191}, {290, 1, 2, 70}, {291, 1, 2, 76},
+ {293, 1, 3, 154}, {296, 1, 2, 123}, {298, 1, 2, 78},
+ {299, 1, 2, 21}, {301, 1, 2, 26}, {304, 1, 2, 11},
+ {306, 1, 2, 106}, {307, 1, 2, 93}, {309, 1, 2, 26},
+ {311, 1, 3, 155}, {312, 1, 2, 83}, {315, 1, 2, 142},
+ {317, 1, 3, 68}, {320, 1, 2, 7}, {323, 1, 2, 21},
+ {325, 1, 2, 53}, {326, 1, 2, 67}, {328, 1, 2, 51},
+ {331, 1, 2, 134}, {334, 1, 2, 5}, {335, 1, 2, 250},
+ {336, 1, 2, 77}, {338, 1, 2, 112}, {339, 1, 2, 26},
+ {341, 1, 2, 57}, {344, 1, 2, 7}, {347, 1, 2, 96},
+ {349, 1, 2, 186}, {352, 1, 2, 263}, {355, 1, 2, 138},
+ {356, 1, 2, 69}, {357, 1, 2, 28}, {360, 1, 2, 49},
+ {361, 1, 2, 44}, {363, 1, 2, 38}, {365, 1, 2, 109},
+ {368, 1, 2, 85}, {371, 1, 2, 156}, {373, 1, 3, 172},
+ {374, 1, 2, 109}, {376, 1, 2, 77}, {379, 1, 2, 222},
+ {381, 1, 2, 5}, {384, 1, 2, 299}, {387, 1, 2, 146},
+ {389, 1, 2, 159}, {392, 1, 2, 145}, {395, 1, 2, 333},
+ {397, 1, 2, 125}, {398, 1, 3, 23}, {400, 1, 2, 245},
+ {403, 1, 2, 80}, {405, 1, 2, 38}, {408, 1, 2, 323},
+ {410, 1, 2, 16}, {411, 1, 2, 50}, {413, 1, 2, 33},
+ {416, 1, 3, 76}, {419, 1, 2, 129}, {421, 1, 2, 81},
+ {424, 1, 2, 177}, {427, 1, 2, 245}, {429, 1, 2, 14},
+ {430, 1, 2, 263}, {432, 1, 2, 103}, {434, 1, 2, 64},
+ {435, 1, 2, 166}, {437, 1, 2, 6}, {440, 1, 2, 37},
+ {442, 1, 2, 32}, {443, 1, 2, 57}, {445, 1, 2, 225},
+ {448, 1, 3, 83}, {451, 1, 2, 33}, {452, 1, 2, 10},
+ {453, 1, 2, 88}, {454, 1, 2, 195}, {456, 1, 2, 275},
+ {459, 1, 2, 332}, {461, 1, 2, 247}, {464, 1, 2, 310},
+ {466, 1, 2, 78}, {467, 1, 2, 210}, {469, 1, 2, 149},
+ {472, 1, 2, 33}, {475, 1, 2, 68}, {477, 1, 2, 121},
+ {480, 1, 2, 149}, {482, 1, 2, 13}, {483, 1, 2, 352},
+ {485, 1, 2, 70}, {488, 1, 2, 123}, {491, 1, 2, 270},
+ {493, 1, 2, 171}, {496, 1, 3, 52}, {499, 1, 2, 174},
+ {501, 1, 2, 332}, {502, 1, 2, 99}, {504, 1, 3, 148},
+ {507, 1, 2, 26}, {509, 1, 2, 94}, {512, 1, 2, 51},
+ {515, 1, 2, 73}, {517, 1, 2, 333}, {520, 1, 2, 291},
+ {523, 1, 2, 66}, {525, 1, 2, 92}, {528, 1, 2, 35},
+ {530, 1, 2, 25}, {531, 1, 2, 53}, {533, 1, 2, 37},
+ {535, 1, 2, 143}, {536, 1, 2, 165}, {539, 1, 2, 37},
+ {541, 1, 2, 36}, {542, 1, 3, 212}, {544, 1, 2, 87},
+ {546, 1, 2, 8}, {547, 1, 2, 165}, {548, 1, 2, 385},
+ {549, 1, 3, 274}, {552, 1, 2, 41}, {554, 1, 2, 162},
+ {555, 1, 2, 326}, {557, 1, 2, 288}, {560, 1, 2, 157},
+ {562, 1, 2, 56}, {563, 1, 4, 159}, {565, 1, 2, 66},
+ {568, 1, 2, 291}, {571, 1, 2, 408}, {572, 1, 2, 238},
+ {573, 1, 2, 220}, {576, 1, 3, 52}, {578, 1, 2, 138},
+ {579, 1, 3, 526}, {581, 1, 2, 138}, {584, 1, 2, 361},
+ {586, 1, 2, 14}, {587, 1, 2, 130}, {589, 1, 2, 365},
+ {591, 1, 2, 38}, {592, 1, 2, 143}, {595, 1, 2, 9},
+ {597, 1, 2, 64}, {598, 1, 2, 131}, {600, 1, 2, 239},
+ {603, 1, 2, 446}, {605, 1, 2, 312}, {608, 1, 2, 213},
+ {611, 1, 2, 13}, {613, 1, 2, 377}, {616, 1, 2, 465},
+ {619, 1, 2, 494}, {621, 1, 2, 17}, {624, 1, 2, 71},
+ {627, 1, 2, 37}, {629, 1, 2, 121}, {630, 1, 2, 49},
+ {632, 1, 2, 9}, {635, 1, 2, 64}, {637, 1, 2, 84},
+ {638, 1, 2, 127}, {640, 1, 3, 253}, {643, 1, 2, 153},
+ {644, 1, 2, 24}, {645, 1, 2, 473}, {648, 1, 2, 235},
+ {653, 1, 2, 37}, {656, 1, 2, 39}, {659, 1, 2, 25},
+ {661, 1, 2, 80}, {664, 1, 2, 177}, {666, 1, 2, 100},
+ {667, 1, 2, 161}, {669, 1, 2, 314}, {672, 1, 2, 91},
+ {674, 1, 2, 22}, {675, 1, 2, 214}, {677, 1, 2, 325},
+ {678, 1, 2, 95}, {680, 1, 2, 91}, {681, 1, 2, 83},
+ {683, 1, 2, 153}, {685, 1, 3, 4}, {688, 1, 2, 71},
+ {691, 1, 2, 242}, {693, 1, 2, 250}, {696, 1, 2, 241},
+ {699, 1, 2, 40}, {701, 1, 2, 466}, {703, 1, 2, 123},
+ {704, 1, 2, 277}, {706, 1, 2, 27}, {707, 1, 2, 141},
+ {709, 1, 2, 9}, {710, 1, 3, 29}, {712, 1, 2, 623},
+ {715, 1, 3, 458}, {717, 1, 2, 320}, {720, 1, 2, 625},
+ {723, 1, 2, 268}, {725, 1, 2, 331}, {728, 1, 2, 51},
+ {731, 1, 2, 69}, {733, 1, 2, 92}, {734, 1, 2, 67},
+ {736, 1, 2, 359}, {739, 1, 2, 60}, {741, 1, 2, 34},
+ {744, 1, 2, 347}, {747, 1, 2, 158}, {749, 1, 2, 357},
+ {752, 1, 2, 129}, {755, 1, 4, 159}, {757, 1, 2, 359},
+ {760, 1, 2, 17}, {763, 1, 2, 17}, {764, 1, 2, 12},
+ {765, 1, 2, 137}, {766, 1, 3, 280}, {768, 1, 2, 115},
+ {770, 1, 2, 453}, {771, 1, 2, 86}, {773, 1, 2, 73},
+ {776, 1, 2, 51}, {779, 1, 2, 456}, {781, 1, 2, 209},
+ {784, 1, 2, 59}, {786, 1, 2, 118}, {787, 1, 2, 189},
+ {788, 1, 2, 375}, {789, 1, 2, 5}, {790, 1, 2, 111},
+ {792, 1, 2, 403}, {795, 1, 2, 137}, {796, 1, 2, 36},
+ {797, 1, 2, 193}, {800, 1, 2, 463}, {802, 1, 2, 102},
+ {803, 1, 2, 208}, {805, 1, 2, 453}, {808, 1, 3, 175},
+ {811, 1, 2, 18}, {813, 1, 2, 802}, {816, 1, 3, 51},
+ {819, 1, 2, 149}, {821, 1, 2, 177}, {824, 1, 2, 495},
+ {827, 1, 2, 189}, {829, 1, 2, 560}, {830, 1, 2, 241},
+ {832, 1, 2, 39}, {835, 1, 2, 350}, {836, 1, 2, 606},
+ {837, 1, 2, 365}, {840, 1, 2, 341}, {843, 1, 2, 322},
+ {848, 1, 2, 225}, {851, 1, 2, 442}, {853, 1, 2, 461},
+ {854, 1, 2, 79}, {856, 1, 2, 842}, {859, 1, 2, 594},
+ {863, 1, 2, 90}, {864, 1, 2, 607}, {867, 1, 2, 380},
+ {869, 1, 2, 82}, {872, 1, 2, 691}, {874, 1, 2, 110},
+ {875, 1, 2, 66}, {877, 1, 2, 140}, {878, 1, 2, 343},
+ {880, 1, 3, 221}, {883, 1, 2, 488}, {885, 1, 2, 707},
+ {886, 1, 2, 227}, {888, 1, 2, 97}, {891, 1, 2, 364},
+ {893, 1, 2, 13}, {896, 1, 2, 19}, {899, 1, 3, 898},
+ {901, 1, 2, 581}, {904, 1, 3, 60}, {907, 1, 3, 26},
+ {909, 1, 3, 168}, {910, 1, 2, 357}, {912, 1, 2, 569},
+ {914, 1, 2, 4}, {915, 1, 2, 89}, {917, 1, 2, 22},
+ {920, 1, 3, 517}, {922, 1, 2, 24}, {923, 1, 2, 142},
+ {925, 1, 2, 308}, {928, 1, 2, 33}, {929, 1, 2, 36},
+ {931, 1, 2, 72}, {933, 1, 2, 527}, {934, 1, 3, 800},
+ {936, 1, 3, 27}, {939, 1, 2, 142}, {940, 1, 2, 204},
+ {941, 1, 2, 573}, {944, 1, 2, 487}, {946, 1, 3, 83},
+ {947, 1, 2, 400}, {949, 1, 2, 417}, {950, 1, 2, 859},
+ {952, 1, 3, 311}, {955, 1, 2, 606}, {957, 1, 2, 158},
+ {958, 1, 2, 191}, {960, 1, 2, 491}, {962, 1, 2, 18},
+ {963, 1, 2, 145}, {965, 1, 2, 213}, {968, 1, 2, 21},
+ {970, 1, 2, 260}, {971, 1, 2, 6}, {973, 1, 2, 113},
+ {974, 1, 2, 211}, {976, 1, 2, 285}, {978, 1, 2, 376},
+ {980, 1, 2, 316}, {981, 1, 2, 383}, {984, 1, 2, 349},
+ {987, 1, 3, 142}, {989, 1, 2, 105}, {992, 1, 2, 585},
+ {995, 1, 3, 242}, {997, 1, 2, 453}, {1000, 1, 3, 68},
+ {1002, 1, 2, 266}, {1003, 1, 2, 410}, {1004, 1, 2, 96},
+ {1005, 1, 2, 41}, {1006, 1, 2, 63}, {1008, 1, 2, 703},
+ {1011, 1, 2, 17}, {1013, 1, 2, 180}, {1016, 1, 2, 49},
+ {1017, 1, 2, 746}, {1018, 1, 2, 27}, {1019, 1, 2, 96},
+ {1021, 1, 2, 5}, {1024, 1, 2, 515}, {1027, 1, 2, 378},
+ {1032, 1, 2, 901}, {1035, 1, 2, 76}, {1037, 1, 2, 981},
+ {1038, 1, 2, 41}, {1040, 1, 2, 429}, {1043, 1, 3, 869},
+ {1045, 1, 2, 378}, {1046, 1, 2, 39}, {1048, 1, 3, 172},
+ {1051, 1, 3, 354}, {1053, 1, 2, 290}, {1056, 1, 2, 11},
+ {1059, 1, 3, 6}, {1061, 1, 2, 166}, {1064, 1, 2, 946},
+ {1066, 1, 2, 258}, {1067, 1, 2, 69}, {1068, 1, 2, 223},
+ {1069, 1, 2, 146}, {1070, 1, 3, 94}, {1072, 1, 2, 443},
+ {1073, 1, 3, 235}, {1074, 1, 2, 395}, {1075, 1, 2, 92},
+ {1076, 1, 2, 22}, {1077, 1, 2, 521}, {1080, 1, 2, 151},
+ {1083, 1, 2, 538}, {1088, 1, 2, 531}, {1091, 1, 2, 82},
+ {1093, 1, 2, 173}, {1096, 1, 2, 351}, {1099, 1, 2, 464},
+ {1101, 1, 2, 14}, {1104, 1, 2, 259}, {1107, 1, 2, 176},
+ {1109, 1, 2, 501}, {1112, 1, 2, 1045}, {1114, 1, 2, 345},
+ {1115, 1, 2, 268}, {1117, 1, 2, 149}, {1118, 1, 2, 475},
+ {1120, 1, 3, 386}, {1123, 1, 2, 641}, {1124, 1, 2, 156},
+ {1125, 1, 2, 206}, {1128, 1, 3, 7}, {1131, 1, 2, 188},
+ {1132, 1, 2, 20}, {1133, 1, 2, 667}, {1136, 1, 2, 177},
+ {1139, 1, 2, 45}, {1141, 1, 2, 134}, {1143, 1, 2, 7},
+ {1144, 1, 2, 431}, {1147, 1, 2, 390}, {1149, 1, 2, 221},
+ {1150, 1, 2, 63}, {1152, 1, 2, 971}, {1155, 1, 2, 94},
+ {1157, 1, 2, 105}, {1160, 1, 2, 889}, {1162, 1, 2, 288},
+ {1163, 1, 2, 33}, {1165, 1, 2, 494}, {1168, 1, 2, 473},
+ {1171, 1, 2, 396}, {1172, 1, 2, 426}, {1173, 1, 2, 673},
+ {1176, 1, 2, 19}, {1179, 1, 2, 640}, {1181, 1, 2, 82},
+ {1184, 1, 2, 1177}, {1187, 1, 2, 438}, {1189, 1, 2, 102},
+ {1192, 1, 3, 831}, {1194, 1, 2, 317}, {1195, 1, 2, 293},
+ {1197, 1, 2, 269}, {1200, 1, 3, 739}, {1203, 1, 2, 226},
+ {1205, 1, 2, 4}, {1208, 1, 2, 915}, {1211, 1, 2, 373},
+ {1213, 1, 2, 245}, {1216, 1, 2, 155}, {1219, 1, 2, 225},
+ {1221, 1, 2, 101}, {1222, 1, 2, 215}, {1224, 1, 2, 157},
+ {1227, 1, 2, 361}, {1229, 1, 2, 627}, {1232, 1, 2, 225},
+ {1235, 1, 2, 642}, {1237, 1, 2, 150}, {1240, 1, 2, 567},
+ {1243, 1, 2, 758}, {1244, 1, 2, 126}, {1245, 1, 2, 212},
+ {1248, 1, 2, 1201}, {1250, 1, 2, 37}, {1251, 1, 2, 1004},
+ {1253, 1, 2, 141}, {1254, 1, 2, 697}, {1256, 1, 2, 171},
+ {1258, 1, 2, 503}, {1259, 1, 2, 192}, {1261, 1, 2, 14},
+ {1262, 1, 2, 793}, {1264, 1, 2, 285}, {1267, 1, 2, 197},
+ {1269, 1, 2, 484}, {1272, 1, 2, 223}, {1274, 1, 2, 486},
+ {1275, 1, 2, 25}, {1277, 1, 2, 451}, {1280, 1, 2, 843},
+ {1283, 1, 2, 70}, {1285, 1, 2, 564}, {1288, 1, 2, 215},
+ {1290, 1, 2, 422}, {1291, 1, 2, 245}, {1292, 1, 2, 78},
+ {1293, 1, 2, 26}, {1296, 1, 2, 379}, {1299, 1, 2, 172},
+ {1301, 1, 2, 297}, {1303, 1, 2, 306}, {1304, 1, 3, 574},
+ {1307, 1, 2, 157}, {1309, 1, 2, 789}, {1312, 1, 2, 1265},
+ {1315, 1, 2, 270}, {1316, 1, 2, 12}, {1317, 1, 2, 254},
+ {1318, 1, 3, 94}, {1320, 1, 2, 835}, {1322, 1, 2, 538},
+ {1323, 1, 2, 1198}, {1325, 1, 2, 526}, {1328, 1, 2, 507},
+ {1330, 1, 2, 609}, {1331, 1, 2, 289}, {1333, 1, 2, 276},
+ {1336, 1, 2, 815}, {1339, 1, 2, 284}, {1341, 1, 2, 53},
+ {1342, 1, 2, 477}, {1344, 1, 2, 469}, {1346, 1, 2, 57},
+ {1347, 1, 2, 61}, {1349, 1, 2, 40}, {1352, 1, 2, 583},
+ {1355, 1, 2, 117}, {1357, 1, 2, 495}, {1360, 1, 2, 393},
+ {1363, 1, 2, 852}, {1365, 1, 2, 329}, {1368, 1, 2, 41},
+ {1370, 1, 2, 108}, {1371, 1, 2, 145}, {1373, 1, 2, 613},
+ {1376, 1, 2, 1201}, {1378, 1, 2, 362}, {1379, 1, 2, 400},
+ {1381, 1, 2, 56}, {1382, 1, 3, 58}, {1384, 1, 2, 1131},
+ {1387, 1, 2, 33}, {1389, 1, 2, 41}, {1392, 1, 2, 485},
+ {1394, 1, 2, 30}, {1395, 1, 2, 233}, {1397, 1, 2, 397},
+ {1400, 1, 2, 493}, {1403, 1, 2, 717}, {1405, 1, 2, 558},
+ {1406, 1, 2, 13}, {1408, 1, 3, 45}, {1411, 1, 2, 200},
+ {1413, 1, 2, 101}, {1416, 1, 3, 231}, {1418, 1, 2, 283},
+ {1419, 1, 2, 592}, {1421, 1, 2, 30}, {1424, 1, 2, 507},
+ {1427, 1, 2, 900}, {1429, 1, 2, 149}, {1432, 1, 2, 251},
+ {1435, 1, 2, 126}, {1437, 1, 2, 545}, {1439, 1, 2, 535},
+ {1440, 1, 3, 1023}, {1443, 1, 2, 413}, {1445, 1, 2, 214},
+ {1448, 1, 3, 212}, {1450, 1, 2, 155}, {1451, 1, 2, 193},
+ {1453, 1, 2, 348}, {1456, 1, 2, 1011}, {1459, 1, 2, 1032},
+ {1461, 1, 2, 446}, {1462, 1, 2, 165}, {1464, 1, 2, 275},
+ {1467, 1, 2, 113}, {1469, 1, 2, 775}, {1472, 1, 2, 613},
+ {1474, 1, 2, 59}, {1475, 1, 2, 208}, {1477, 1, 2, 1325},
+ {1480, 1, 2, 285}, {1483, 1, 2, 1077}, {1484, 1, 2, 61},
+ {1485, 1, 2, 655}, {1488, 1, 2, 463}, {1491, 1, 2, 544},
+ {1493, 1, 2, 378}, {1494, 1, 2, 731}, {1496, 1, 2, 181},
+ {1498, 1, 2, 416}, {1499, 1, 2, 477}, {1501, 1, 2, 60},
+ {1502, 1, 2, 111}, {1504, 1, 2, 207}, {1506, 1, 2, 533},
+ {1507, 1, 2, 900}, {1509, 1, 2, 209}, {1512, 1, 2, 1121},
+ {1515, 1, 2, 712}, {1517, 1, 2, 568}, {1520, 1, 2, 81},
+ {1522, 1, 2, 47}, {1523, 1, 2, 240}, {1525, 1, 2, 102},
+ {1528, 1, 2, 923}, {1531, 1, 2, 1125}, {1532, 1, 2, 466},
+ {1533, 1, 2, 763}, {1536, 1, 2, 881}, {1538, 1, 2, 6},
+ {1539, 1, 2, 80}, {1541, 1, 2, 4}, {1544, 1, 2, 99},
+ {1546, 1, 2, 810}, {1547, 1, 2, 493}, {1549, 1, 2, 426},
+ {1552, 1, 2, 83}, {1555, 1, 2, 254}, {1557, 1, 2, 20},
+ {1560, 1, 2, 11}, {1563, 1, 2, 41}, {1565, 1, 2, 18},
+ {1568, 1, 2, 133}, {1571, 1, 2, 21}, {1573, 1, 2, 461},
+ {1574, 1, 2, 331}, {1576, 1, 2, 147}, {1579, 1, 2, 374},
+ {1581, 1, 2, 160}, {1584, 1, 2, 895}, {1587, 1, 2, 433},
+ {1589, 1, 2, 882}, {1592, 1, 2, 223}, {1594, 1, 2, 971},
+ {1595, 1, 2, 18}, {1597, 1, 2, 42}, {1598, 1, 2, 385},
+ {1600, 1, 2, 57}, {1603, 1, 2, 917}, {1605, 1, 2, 46},
+ {1608, 1, 2, 271}, {1610, 1, 2, 250}, {1611, 1, 2, 58},
+ {1613, 1, 2, 48}, {1614, 1, 2, 1489}, {1616, 1, 2, 139},
+ {1619, 1, 2, 289}, {1621, 1, 2, 1577}, {1622, 1, 2, 1341},
+ {1624, 1, 2, 1095}, {1626, 1, 2, 191}, {1627, 1, 2, 189},
+ {1629, 1, 2, 397}, {1632, 1, 2, 211}, {1635, 1, 2, 113},
+ {1637, 1, 2, 234}, {1640, 1, 2, 715}, {1643, 1, 2, 760},
+ {1644, 1, 2, 236}, {1645, 1, 2, 938}, {1646, 1, 2, 435},
+ {1648, 1, 2, 77}, {1651, 1, 2, 873}, {1653, 1, 2, 82},
+ {1654, 1, 3, 201}, {1656, 1, 2, 361}, {1658, 1, 2, 552},
+ {1659, 1, 2, 374}, {1661, 1, 2, 84}, {1662, 1, 3, 958},
+ {1664, 1, 2, 399}, {1667, 1, 2, 1020}, {1669, 1, 2, 425},
+ {1670, 1, 2, 19}, {1672, 1, 2, 405}, {1675, 1, 2, 77},
+ {1677, 1, 2, 844}, {1680, 1, 2, 1549}, {1682, 1, 2, 354},
+ {1683, 1, 2, 1348}, {1684, 1, 2, 474}, {1685, 1, 2, 493},
+ {1686, 1, 2, 887}, {1688, 1, 2, 921}, {1690, 1, 2, 200},
+ {1691, 1, 2, 556}, {1693, 1, 2, 137}, {1696, 1, 2, 737},
+ {1699, 1, 2, 405}, {1701, 1, 2, 568}, {1702, 1, 2, 245},
+ {1704, 1, 3, 55}, {1706, 1, 2, 574}, {1707, 1, 2, 221},
+ {1709, 1, 2, 201}, {1712, 1, 2, 445}, {1714, 1, 2, 191},
+ {1715, 1, 2, 612}, {1717, 1, 2, 881}, {1718, 1, 2, 535},
+ {1720, 1, 2, 525}, {1723, 1, 2, 137}, {1725, 1, 2, 623},
+ {1727, 1, 2, 22}, {1728, 1, 2, 545}, {1730, 1, 2, 316},
+ {1731, 1, 2, 925}, {1732, 1, 2, 75}, {1733, 1, 2, 285},
+ {1736, 1, 2, 435}, {1739, 1, 2, 409}, {1741, 1, 3, 226},
+ {1744, 1, 2, 35}, {1747, 1, 2, 93}, {1749, 1, 2, 236},
+ {1752, 1, 2, 559}, {1754, 1, 2, 75}, {1755, 1, 2, 316},
+ {1757, 1, 2, 21}, {1758, 1, 2, 221}, {1760, 1, 3, 1612},
+ {1761, 1, 2, 131}, {1762, 1, 2, 318}, {1763, 1, 2, 345},
+ {1765, 1, 2, 165}, {1766, 1, 2, 1029}, {1768, 1, 2, 1403},
+ {1771, 1, 2, 297}, {1773, 1, 2, 50}, {1776, 1, 2, 17},
+ {1779, 1, 3, 1068}, {1781, 1, 2, 18}, {1784, 1, 2, 1489},
+ {1786, 1, 2, 614}, {1787, 1, 2, 457}, {1789, 1, 2, 80},
+ {1792, 1, 2, 341}, {1794, 1, 2, 95}, {1795, 1, 2, 89},
+ {1796, 1, 2, 829}, {1797, 1, 2, 80}, {1800, 1, 2, 1013},
+ {1803, 1, 2, 248}, {1805, 1, 2, 82}, {1808, 1, 2, 25},
+ {1811, 1, 2, 117}, {1812, 1, 2, 758}, {1813, 1, 3, 884},
+ {1816, 1, 2, 887}, {1819, 1, 2, 116}, {1821, 1, 2, 326},
+ {1822, 1, 3, 31}, {1824, 1, 2, 821}, {1826, 1, 2, 298},
+ {1827, 1, 2, 154}, {1829, 1, 2, 162}, {1832, 1, 3, 1078},
+ {1834, 1, 2, 210}, {1835, 1, 2, 288}, {1837, 1, 2, 200},
+ {1840, 1, 2, 195}, {1842, 1, 2, 799}, {1843, 1, 2, 872},
+ {1845, 1, 2, 526}, {1848, 1, 2, 871}, {1850, 1, 2, 79},
+ {1851, 1, 2, 250}, {1852, 1, 2, 339}, {1853, 1, 2, 705},
+ {1856, 1, 2, 585}, {1858, 1, 2, 1368}, {1859, 1, 2, 120},
+ {1861, 1, 2, 509}, {1864, 1, 2, 1379}, {1867, 1, 2, 117},
+ {1868, 1, 2, 250}, {1869, 1, 2, 617}, {1872, 1, 3, 60},
+ {1874, 1, 2, 70}, {1875, 1, 2, 412}, {1876, 1, 2, 122},
+ {1877, 1, 2, 796}, {1880, 1, 2, 1647}, {1882, 1, 2, 128},
+ {1883, 1, 2, 1062}, {1885, 1, 2, 813}, {1888, 1, 2, 923},
+ {1891, 1, 2, 1766}, {1892, 1, 3, 497}, {1893, 1, 2, 461},
+ {1894, 1, 3, 215}, {1896, 1, 2, 451}, {1897, 1, 2, 324},
+ {1898, 1, 2, 613}, {1899, 1, 2, 485}, {1901, 1, 2, 330},
+ {1904, 1, 2, 337}, {1907, 1, 2, 45}, {1909, 1, 2, 225},
+ {1910, 1, 3, 365}, {1912, 1, 2, 599}, {1914, 1, 2, 544},
+ {1915, 1, 2, 473}, {1916, 1, 2, 502}, {1917, 1, 2, 485},
+ {1920, 1, 2, 67}, {1922, 1, 2, 36}, {1923, 1, 4, 40},
+ {1925, 1, 2, 576}, {1928, 1, 2, 763}, {1930, 1, 2, 155},
+ {1931, 1, 2, 648}, {1933, 1, 2, 971}, {1936, 1, 2, 117},
+ {1939, 1, 2, 5}, {1941, 1, 2, 1133}, {1942, 1, 2, 147},
+ {1944, 1, 2, 617}, {1947, 1, 2, 1162}, {1949, 1, 2, 621},
+ {1952, 1, 3, 65}, {1954, 1, 2, 1226}, {1955, 1, 2, 109},
+ {1957, 1, 2, 17}, {1960, 1, 2, 939}, {1963, 1, 2, 1137},
+ {1965, 1, 2, 364}, {1968, 1, 3, 922}, {1970, 1, 2, 388},
+ {1971, 1, 2, 100}, {1972, 1, 2, 474}, {1973, 1, 2, 438},
+ {1976, 1, 3, 1160}, {1978, 1, 2, 158}, {1979, 1, 2, 369},
+ {1981, 1, 2, 96}, {1982, 1, 2, 1027}, {1984, 1, 2, 129},
+ {1987, 1, 2, 80}, {1989, 1, 2, 719}, {1992, 1, 2, 1241},
+ {1995, 1, 2, 37}, {1997, 1, 2, 835}, {1998, 1, 3, 1290},
+ {2000, 1, 2, 981}};
+
+int compare_poly(const void *a, const void *b) {
+ const polynomial_t *one = a;
+ const polynomial_t *other = b;
+ return (one->m - other->m);
+}
+
+bool poly_exists(long m) { return m >= 160 && m <= 2000; }
+
+polynomial_t *poly_find(long m) {
+ if (!poly_exists(m)) {
+ return NULL;
+ }
+ polynomial_t searched = {(int)m};
+ polynomial_t *tri =
+ (polynomial_t *)bsearch(&searched, ansi_trinomials,
+ sizeof(ansi_trinomials) / sizeof(polynomial_t),
+ sizeof(polynomial_t), &compare_poly);
+ if (tri) {
+ return tri;
+ } else {
+ return (polynomial_t *)bsearch(
+ &searched, ansi_pentanomials,
+ sizeof(ansi_pentanomials) / sizeof(polynomial_t),
+ sizeof(polynomial_t), &compare_poly);
+ }
+}
+
+GEN poly_find_gen(long m) { return poly_gen(poly_find(m)); }
+
+GEN poly_gen(polynomial_t *polynomial) {
+ pari_sp ltop = avma;
+
+ GEN coeffs = gtovec0(gen_0, polynomial->m + 1);
+ gel(coeffs, polynomial->m + 1) = gen_1;
+ gel(coeffs, polynomial->e1 + 1) = gen_1;
+ gel(coeffs, polynomial->e2 + 1) = gen_1;
+ gel(coeffs, polynomial->e3 + 1) = gen_1;
+ gel(coeffs, 1) = gen_1;
+
+ GEN poly = gmul(gtopolyrev(coeffs, -1), gmodulss(1, 2));
+ return gerepilecopy(ltop, ffgen(poly, -1));
+}
diff --git a/src/poly.h b/src/poly.h
new file mode 100644
index 0000000..2bb5c96
--- /dev/null
+++ b/src/poly.h
@@ -0,0 +1,48 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#ifndef ECGEN_POLY_H
+#define ECGEN_POLY_H
+
+#include <stdbool.h>
+#include "gp.h"
+
+typedef struct polynomial {
+ int m;
+ int e1;
+ int e2;
+ int e3;
+} polynomial_t;
+
+extern polynomial_t ansi_trinomials[];
+extern polynomial_t ansi_pentanomials[];
+
+/**
+ *
+ * @param m
+ * @return
+ */
+bool poly_exists(long m);
+/**
+ *
+ * @param m
+ * @return
+ */
+polynomial_t *poly_find(long m);
+
+/**
+ *
+ * @param m
+ * @return
+ */
+GEN poly_find_gen(long m);
+
+/**
+ *
+ * @param polynomial
+ * @return
+ */
+GEN poly_gen(polynomial_t *polynomial);
+
+#endif //ECGEN_POLY_H
diff --git a/utils.gp b/utils.gp
deleted file mode 100644
index bfd0326..0000000
--- a/utils.gp
+++ /dev/null
@@ -1,11 +0,0 @@
-print_params(curve) = {
- printf("%x,%x,%x,%x,%x,%x,%x\n", curve[1], curve[2], curve[3], curve[4], curve[5], curve[6], curve[7]);
-}
-
-print_params_pub(curve) = {
- printf("%x,%x,%x,%x,%x,%x,%x,%x,%x,%x\n", curve[1], curve[2], curve[3], curve[4], curve[5], curve[6], curve[7], curve[8], curve[9], curve[10]);
-}
-
-pack_params(p, a, b, G) = {
- return([p, a, b, lift(G[1][1]), lift(G[1][2]), G[2], G[3]]);
-}
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 15:03:02 +0000