import java.io.FileOutputStream;
import java.io.PrintStream;

public class findcurvesrand {

	/*
	 * @author Aaron Blumenfeld
	 * The following program conducts a search for elliptic curves of order N,
	 * for N prime (that way every finite point is a generator)
	 *
	 * Just change the number N in the main routine and make sure the array of primes
	 * has values in the right range
	 *
	 * h specifies the number of curves you want.  Then h random curves are chosen
	 */

	public static long modExp(long a, long b, long p) {
		long rval = 1;
		while(b > 0) {
			if((b & 1) == 1) /* if b is odd */
				rval = (rval * a) % p;
			b >>= 1;
			a = (a * a) % p;
		}
		return rval;
	}

	public static long jacobi(long a, long p){
		if((a % p) == 0)
			return 0;
		long rval = 1;
		long mod8;
		long temp;

		a = (a % p);
		while(a != 0) {
			while(a % 2 == 0) { /* pull out factors of 2 and compute (2/n) */
				a >>= 1;
				mod8 = (p % 8);
				if(mod8 == 3 || mod8 == 5) {
					if(rval == 1)
						rval = -1;
					else rval = 1;
				}
			}
			temp = a;
			a = p; /* swap a and p */
			p = temp;

			if((a % 4) == 3 && (p % 4) == 3) { /* apply quadratic reciprocity */
				if(rval == 1)
					rval = -1;
				else rval = 1;
			}
			a = a % p;
		}
		return rval;
	}

	public static int smallestM(long b, int m, long p) {
		while(modExp(b, 1<<m, p) != 1)
			m++;
		return m;
	}

	public static long shanks(long a, long p) { /* compute sqrt(a) (mod p) */
		if((p - 3) % 4 == 0) /* easy for p = 3 (mod 4) */
			return modExp(a, (p+1)/4, p);
		if((p - 5) % 8 == 0 && modExp(a, (p-1)/4, p) == 1) /* sometimes easy for p = 5 (mod 8) */
			return modExp(a, (p+3)/8, p);
		long e = 0; long q = p-1;
		while(q%2==0 && q > 0) {
			e++;
			q >>= 1;
		}
		long n = 2;
		while(jacobi(n, p) != -1) {
			n = (long)(Math.random()*p);
		}
		long z = modExp(n, q, p);
		long y, r, x, b, t;
		y = z; r = e; x = modExp(a, (q-1)/2, p); b = (a*x*x)%p; x = (a*x)%p;
		while(b%p != 1) {
			int m = 1;
			m = smallestM(b, m, p);
			t = modExp(y, 1<<(r-m-1), p);
			y = (t*t)%p;
			r = m;
			x = (x*t)%p;
			b = (b*y)%p;
		}
		return x;
	}

	public static boolean isEC(long a, long b, long p) {
		if(((4*a*a*a + 27*b*b) % p) == 0) /* make sure no multiple roots */
			return false;
		return true;
	}

	public static long ecOrder(long a, long b, long p) { /* O(plogp) algorithm, maybe fix
	    later using Shoof's algorithm for O(log^8 p) run-time */
		long order = 1;
		long temp = 0;
		for(long x = 0; x < p; x++) {
			temp = (((x * x) % p) * x) % p;
			temp = (temp + (a * x)) % p;
			temp = (temp + b) % p;
			order += (1 + jacobi(temp, p));
		}
		return order;
	}

	/*public static void findGenerator(long a, long b, long p, long N, PrintStream fout) {
		long x = (long)(p*Math.random());
		long temp = x;
		temp = (((x * x) % p) * x) % p;
		temp = (temp + a * x) % p;
		temp = (temp + b) % p;

		while(jacobi(temp, p) != 1) {
			x = (x + 1) % p;
			temp = (((x * x) % p) * x) % p;
			temp = (temp + a * x) % p;
			temp = (temp + b) % p;
		}
		long y = shanks(temp, p);
		System.out.println(new EllipticCurve(a, b, p) + ", B = (" + x + ", " + y + "), order " + ecOrder(a, b, p));
		fout.println(a); fout.println(b); fout.println(p); fout.println(x); fout.println(y);
	}*/

	public static void findGenerator(long a, long b, long p, long N, PrintStream fout) {
		long x = (long)(p*Math.random());
		long temp = x;
		temp = (((x * x) % p) * x) % p;
		temp = (temp + a * x) % p;
		temp = (temp + b) % p;

		while(jacobi(temp, p) != 1) {
			x = (long)(p*Math.random());
			temp = (((x * x) % p) * x) % p;
			temp = (temp + a * x) % p;
			temp = (temp + b) % p;
		}
		long y = shanks(temp, p);
		System.out.println(new EllipticCurve(a, b, p) + ", B = (" + x + ", " + y + "), order " + ecOrder(a, b, p));
		fout.println(a); fout.println(b); fout.println(p); fout.println(x); fout.println(y);
	}

	/*public static void findECs(long p, long N, PrintStream fout) {
		long a, b;
		a = (long)(Math.random()*p);
		b = (long)(Math.random()*(p-1)) + 1;
		boolean found = false;
		if(!isEC(a, b, p) || ecOrder(a, b, p) != N) {
			for(; !found && a < p; a++)
				for(; !found && b < p; b++)
					if(isEC(a, b, p) && ecOrder(a, b, p) == N) {
						found = true;
						findGenerator(a, b, p, N, fout);
					}
		}
	}*/

	public static void findECs(long p, long N, PrintStream fout) {
		long a, b;
		a = (long)(Math.random()*p);
		b = (long)(Math.random()*(p-1)) + 1;
		while(!isEC(a, b, p) || ecOrder(a, b, p) != N) {
			a = (long)(Math.random()*p);
			b = (long)(Math.random()*(p-1)) + 1;
		}
		findGenerator(a, b, p, N, fout);
	}

	public static void ecsOfOrderN(int h, long N, long[] primes, PrintStream fout) {
		int i = 0;
		while(i < primes.length && ((primes[i] + 1) + 2*(long)Math.sqrt(primes[i])) <= N)
			i++;
		int j = i;
		int count = 0;
		while(primes[i] < N) {
			count++;
			i++;
		}
		long[] goodprimes = new long[count+1];
		for(int k = 0; k < goodprimes.length; k++) {
			goodprimes[k] = primes[j];
			j++;
		}
		goodprimes[count] = N;
		while(h > 0) {
			int r = (int)(goodprimes.length*Math.random());
			findECs(goodprimes[r], N, fout);
			h--;
		}
	}

	public static void main(String[] args) {
		long[] primes = {5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
				67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
				139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
				223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
				293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
				383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
				463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,
				569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
				647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
				743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
				839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937,
				941, 947, 953, 967, 971, 977, 983, 991, 997, 1039, 1049, 1051, 1061,
				1063, 1069, 1087, 1091, 1093, 1097, 1103, 2687, 2689, 2693, 2699, 2707,
				2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 4967,
				4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051,
				5059, 5077, 5081, 5087, 5099, 5101, 5107, 9091, 9103, 9109, 9127, 9133,
				9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
				9239, 9241, 9257, 9277, 9281};
		String filename = "997curves.txt";
		long N = 997;
		int h = 10000; /* number of curves to find */
		try { //write file
			PrintStream fout = new PrintStream(new FileOutputStream(filename));
			ecsOfOrderN(h, N, primes, fout);
		} catch(Exception e) {
			System.err.println(e);
		}
	}
}