/*
@author: Christopher Evans

This code is a C++ implementation of the code originally written by Andrew Blumenfeld in Java. It borrows heavily from the original, but is adapted for maximum portability, efficiency and extensionability.
This class takes a prime number (curve_order) and finds all elliptic curves of order curve_order. It saves these curves to a vector (part of the C++ standard library), which can then be written to a text file.

As of the current implementation, curve_order is limited by the maximum integer that can be stored on the average computer, so (if I got my facts straight), curve_order should be less than about 32,700. Future implementations 
may include an adaptation to use an arbitrary precision library such as GMP, which would allow the calculations of curves of arbitrary order, limited only by the computing resources available to the user.

This class has multiple dependencies, including the C++ standard library (for container classes mostly), the elliptic_curves.h and elliptic_curves.cpp files and


In a similar vein, this code is intended to be used alongside a collection of classes that will compute statistics for the elliptic curve functional graphs (ECFGs) induced by the elliptic curves found by this class.
The actual implementation, however, is independent of the statistics package, and can be used for its own purposes.

The user is warned that even for relatively small values of curve_order (such as 997), this program involves a significant amount of computation, memory, and storage space. Future implementations may introduce
the Message Passing Interface (MPI) standard, which would allow distribution of computational and memory resources across a parallel cluster, but the computational and and memory resource requirements will still be 
significant.
*/


#ifndef _FIND_CURVES_H
#define _FIND_CURVES_H


#include <iostream>
#include <vector>
#include "find_curves.h"
#include "elliptic_curves.h"



class Find_Curves{
private:
	int curve_order; //private variable that stores the number of points on the elliptic curve
	vector<Elliptic_Curve> curve_list; //a standard library container to hold the elliptic curve data until program completion
	void smallestM(const long& b, int& m, const long& p); // helper method for shanks
	
	vector<long> prime_array;
	

public:
	Find_Curves(); //standard constructor
	Find_Curves(const int& n, const vector<long>& _prime_array); //constructor that takes an integer n. n should be prime
	long modExp(long a, long b, const long& p); // computes a^b mod p
	long jacobi(const long& a, const long& p); // computes the jacobi symbol (a / p)
	long shanks(const long& a, const long& p); // computes sqrt(a) mod p
	bool isEC(const long& a, const long& b, const long& p); //checks for multiple roots in equation
	long ecOrder(const long& a, const long& b, const long& p); //hopefully implements Shoof's algorithm for O(log^8 p), otherwise uses Blumenfeld's original with O(p log p)
	void findGenerators(const long& a, const long& b, const long& p); //might need some modifications for portability
	void findECs(const long& p); //also might need some modifications for portability
	void ECsOfOrderCurveOrder(); //also might need some modifications for portability
	void write_to_file(); //prints list of curves with generators to file named (curve_order)_curve_list.txt
	void printCurves();

};
#endif