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

public class findcurves {

	/*
	 * @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
	 */

	public static long modExp(long a, long b, long p) { /* compute a^b mod 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){ /* compute (a/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) { /* helper method for shanks */
		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 % 4) == 3) /* easy for p = 3 (mod 4) */
			return modExp(a, (p+1)/4, p);
		if((p % 8) == 5 && 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 findGenerators(long a, long b, long p, long N, PrintStream fout) {
		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;
			if(jacobi(temp, p) == 1) {
				long y = shanks(temp, 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) {
		for(long a = 0; a < p; a++) {
			for(long b = 1; b < p; b++) { /* b = 0 ==> E has even order... */
				if(isEC(a, b, p) && ecOrder(a, b, p) == N) {
					System.out.println(new EllipticCurve(a, b, p) + ", order " + ecOrder(a, b, p));
					findGenerators(a, b, p, N, fout);				}
			}
		}
	}

	public static void ecsOfOrderN(long N, long[] primes, PrintStream fout) {
		int i = 0;
		while(i < primes.length && ((primes[i] + 1) + 2*(long)Math.sqrt(primes[i])) <= N)
			i++; /* find first prime in the range implied by Hasse's Theorem */
		while(primes[i] <= N) { /* loop through primes up to N */
			findECs(primes[i], N, fout);
			i++;
		}
	}

	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, 1481, 1483, 1487, 1489,
				1493, 1499, 1511, 1523, 1531, 1543, 1549, 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, 99431, 99439, 99469, 99487, 99497,
				99523, 99527, 99529, 99551, 99559, 99563, 99571, 99577, 99581, 99607,
				99611, 99623, 99643, 99661, 99667, 99679, 99689, 99707, 99709, 99713,
				99719, 99721, 99733, 99761, 99767, 99787, 99793, 99809, 99817, 99823,
				99829, 99833, 99839, 99859, 99871, 99877, 99881, 99901, 99907, 99923,
				99929, 99961, 99971, 99989, 99991, 100003, 100019, 100043, 100049, 100057};
		String filename = "997curves.txt";
		long N = 997;
		try { /* write file */
			PrintStream fout = new PrintStream(new FileOutputStream(filename));
			ecsOfOrderN(N, primes, fout);
		} catch(Exception e) {
			System.err.println(e);
		}
	}
}