ecgen v0.2: major rewrite0.2.0

7 files changed, 414 insertions, 0 deletions

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