//
// Program to generate "best" BN, BLS12, BLS24 and BLS48 curves (with modulus p=3 mod 8)
//
// g++ -O2 bestpair.cpp zzn8.cpp zzn4.cpp zzn2.cpp zzn.cpp ecn8.cpp ecn4.cpp ecn2.cpp ecn.cpp big.cpp miracl.a -o bestpair.exe
//
// Further tests may be needed to ensure full satisfaction (e.g. twist security, even x, etc.)
//
// Note that finding curves that are both GT and G2 Strong, can take a while
//
// Suggestions:-
// For AES-128 security: bestpair BLS12 64 3
// For AES-192 security: bestpair BLS24 48 4
// FOr AES-256 security: bestpair BLS48 32 4

// Some possible rational points on y^2=x^3+b (x^3+b is a perfect square)
// b=1, x=0, -1 or 2
// b=2, x=-1
// b=3, x=1
// b=4, x=0
// b=5, x=-1
// b=8, x=-2, 1, 2
// b=9, x=0, 3, 6, 40
// b=10, x=-1
// b=12, x=-2, 13

// b=-1, x=1
// b=-2, x=3;
// b=-4, x=2, 5
// b=-7, x=2, 32
// b=-8, x=2
// b=-11, x=3, 15

// of course these points need to be checked for correct order...

#include <iostream>
#include "big.h"
#include "ecn.h"
#include "ecn2.h"
#include "ecn4.h"
#include "ecn8.h"

#define BN 0
#define BLS12 1
#define BLS24 2
#define BLS48 3

using namespace std;

Miracl precision=500;

// Number of ways of selecting k items from n
Big combo(int n,int k)
{ // calculate n C k
	int i;
	Big c,d;

	d=1;
	for (i=2;i<=k;i++)
		d*=i;

	c=1;
	for (i=n;i>n-k;i--)
		c*=i;

	c/=d;
	return c;
}

// Number of candidates to be searched.
Big count(int b,int h)
{
	Big c=combo(b-h+1,h-1)+combo(b-h+1,h-2);
	c*=pow((Big)2,h);
	return c;
}

// Move to next NAF pattern
int iterate(int *x,int n)
{
	int i,j,k,gotone=0;
	for (i=0;i<n-1;i++)
	{
		if (x[i]==1 && x[i+2]==0)
		{
			gotone=1;
			x[i+1]=1;
			x[i]=0;
			if (x[0]==1) break;
			for (k=1;;k++)
				if (x[k]!=0) break;
			for (j=0;j<i-k;j+=2)
			{
				x[j]=x[j+k];
				x[j+k]=0;
			}
			break;
		}
		
	}
	return gotone;
}

int main(int argc, char *argv[])
{
	int HW,BITS,S,type,xm8,xm3,xm24,percent,pc;
	Big cnt,odds,total;
    int i,j,k,m,jj,bt,hw,twist,pb,nb,b,cb[40],ip;
	int xb[256];
	BOOL G2,GT,gotH,gotB,gotT,progress;
    Big msb,c,r,m1,n,p,q,t,x,y,w,X,Y,cof,cof2,coft,tau[9];
    Big PP,TT,FF;
	Big xp[10];
	int pw[10];
    miracl *mip=&precision;
    ECn P;

	argc--; argv++;

    if (argc<2)
    {
       cout << "Missing arguments" << endl;
	   cout << "Program to find best pairing-friendly curves" << endl;
       cout << "bestpair type bits Hamming-weight" << endl;
	   cout << "where type is the curve (BN, BLS12, BLS24, BLS48)" << endl;
	   cout << "where bits is number of bits in curve x parameter (>30 and <200)" << endl;
       cout << "and hamming-weight is the number of non-zero bits (>1 and <10)" << endl;
       cout << "e.g. bestpair BLS12 77 3" << endl;
	   cout << "Use flag /GT for GT-Strong curves" << endl;
	   cout << "Use flag /G2 for G2-Strong curves" << endl;
	   cout << "Use flag /P to show progress" << endl;

       exit(0);
    }

	ip=0; HW=0; BITS=0; 
	G2=GT=gotB=gotH=gotT=progress=FALSE;

	while (ip<argc)
	{
		if (!gotT && strcmp(argv[ip],"BN")==0)
		{
			ip++;
			gotT=TRUE;
			type=BN;
		}
		if (!gotT && strcmp(argv[ip],"BLS12")==0)
		{
			ip++;
			gotT=TRUE;
			type=BLS12;
		}
		if (!gotT && strcmp(argv[ip],"BLS24")==0)
		{
			ip++;
			gotT=TRUE;
			type=BLS24;
		}
		if (!gotT && strcmp(argv[ip],"BLS48")==0)
		{
			ip++;
			gotT=TRUE;
			type=BLS48;
		}
		if (!G2 && strcmp(argv[ip],"/G2")==0)
		{
			ip++;
			G2=TRUE;
			continue;
		}
		if (!GT && strcmp(argv[ip],"/GT")==0)
		{
			ip++;
			GT=TRUE;
			continue;
		}
		if (!progress && strcmp(argv[ip],"/P")==0)
		{
			ip++;
			progress=TRUE;
			continue;
		}
		if (!gotB)
		{
			BITS=atoi(argv[ip++]);
			gotB=TRUE;
			continue;
		}

		if (!gotH)
		{
			HW=atoi(argv[ip++]);
			gotH=TRUE;
			continue;
		}

        cout << "Error in command line" << endl;
        return 0;

	}
    if (!gotH || !gotB || !gotT || HW>9 || HW<2 || BITS>=200 || BITS<30)
    {
        cout << "Error in command line" << endl;
        return 0;
    }

	hw=HW-1;
	msb=pow((Big)2,BITS);

	for (i=0;i<=BITS;i++)
		xb[i]=0;

	for (i=0;i<hw;i++)
		xb[2*i]=1;

	S=0;

	total=count(BITS,HW);
	cout << "search " << total << " candidates" << endl;

// very approximate estimate of odds of success. Assumes primes are not correlated (but they are!)
	if (type==BN)
	{
		odds = (7*(4*BITS+5)/10)*(7*(4*BITS+5)/10);
		if (G2)
			odds*=(7*(4*BITS+5)/10);
		if (GT)
			odds*=(7*(12*BITS+16)/10);
	}
	if (type==BLS12)
	{
		odds = ((7*4*BITS)/10)*((7*6*BITS)/10);
		if (G2)
			odds*=(7*(8*BITS)/10);
		if (GT)
			odds*=(7*(20*BITS)/10);
	}
	if (type==BLS24)
	{
		odds = ((7*8*BITS)/10)*((7*10*BITS)/10);
		if (G2)
			odds*=(7*(32*BITS)/10);
		if (GT)
			odds*=(7*(72*BITS)/10);
	}
	if (type==BLS48)
	{
		odds = ((7*16*BITS)/10)*((7*18*BITS)/10);
		if (G2)
			odds*=(7*(128*BITS)/10);
		if (GT)
			odds*=(7*(272*BITS)/10);
	}

	odds/=8;  // frig factor
	cout << "one in " << odds << " expected to be OK" << endl;

//	gprime(1000);
	percent=-1;
	cnt=0;
	for (;;)
	{
		if (cnt>0 && !iterate(xb,BITS)) break;
		for (i=j=0;i<BITS;i++)
		{ // assign values to set bits
			if (xb[i]==1)
			{
				xp[j]=pow((Big)2,i);
				pw[j]=i;
				j++;
			}
		}
		xp[j]=msb;
		pw[j]=BITS;
		j++;

		// iterate through all combinations of + and - terms
		for (i=0;i<(1<<j);i++)
		{
			cnt+=1; 
			if (progress)
			{
				pc=toint((100*cnt)/total);

				if (percent<pc)
				{
					percent=pc;
					cout << pc << "\%" << endl;
				}
			}
			x=0;
			bt=1;
			//cout << "x= ";
			for (k=0;k<j;k++)
			{
				if ((bt&i)!=0) {x+=xp[k]; /*cout << "+2^" << pw[k];*/}
				else {x-=xp[k]; /*cout << "-2^" << pw[k];*/}
				bt<<=1;
			}

			if (type==BLS12)
			{
				xm24=x%24;
				if (x<0) xm24+=24;
				xm24%=24;
				xm3=xm24%3;
				if (xm3!=1) continue;   // quick exit for p%3=0
				xm8=xm24%8;
				if (xm8!=0 && xm8!=7) continue;  // quick exit for p=3 mod 8 condition

				q=pow(x,4)-x*x+1;
				p=q*(((x-1)*(x-1))/3)+x;

				t=x+1;
				n=p+1-t;

			}
			if (type==BLS24)
			{
				xm24=x%24;
				if (x<0) xm24+=24;
				xm24%=24;
				xm3=xm24%3;
				if (xm3!=1) continue;   // quick exit for p%3=0
				xm8=xm24%8;
				if (xm8!=0 && xm8!=7) continue;  // quick exit for p=3 mod 8 condition

				q=pow(x,8)-pow(x,4)+1;
				p=q*(((x-1)*(x-1))/3)+x;

				t=x+1;
				n=p+1-t;
				
			}

			if (type==BLS48)
			{
				xm24=x%24;
				if (x<0) xm24+=24;
				xm24%=24;
				xm3=xm24%3;
				if (xm3!=1) continue;   // quick exit for p%3=0
				xm8=xm24%8;
				if (xm8!=0 && xm8!=7) continue;  // quick exit for p=3 mod 8 condition

				q=pow(x,16)-pow(x,8)+1;
				p=q*(((x-1)*(x-1))/3)+x;
		
				t=x+1;
				n=p+1-t;
				
			}

			if (type==BN)
			{
				xm8=x%8;
				if (x<0) xm8+=8;
				xm8%=8;
				if (xm8!=3 && xm8!=7) continue;  // quick exit for p=3 mod 8 condition

				p=36*pow(x,4)+36*pow(x,3)+24*x*x+6*x+1;
				t=6*x*x+1;
				n=p+1-t;
				q=n;
			}

			if (p%8!=3) continue;                           // restriction here could be eased

			if (small_factors(q)) continue;
			if (small_factors(p)) continue;

			cof=n/q;

			if (type==BLS24)
			{
				coft=(pow(p,8)-pow(p,4)+1)/q;
			}

			if (type==BLS48)
			{
				coft=(pow(p,16)-pow(p,8)+1)/q;
			}

			if (type==BLS12 || type==BN)
			{
				coft=(pow(p,4)-p*p+1)/q;
			}

			if (GT)
			{
				if (small_factors(coft)) continue;
			}

			if (type==BLS12)
			{
				TT=t*t-2*p;
				PP=p*p;
				FF=t*(2*x*x*x-2*x*x-x+1)/3;
				m1=PP+1-(-3*FF+TT)/2;
			}

			if (type==BLS24)
			{
				TT=t*t*t*t-4*p*t*t+2*p*p;
				PP=pow(p,4);
				FF=sqrt((4*PP-TT*TT)/3);
				m1=PP+1-(3*FF+TT)/2;
			}
			if (type==BLS48)
			{
				tau[0]=2;  // count points on twist over extension p^8
				tau[1]=t;
				for (jj=1;jj<8;jj++ ) tau[jj+1]=t*tau[jj]-p*tau[jj-1];

				TT=tau[8];

				PP=pow(p,8);
				FF=sqrt((4*PP-TT*TT)/3);
				m1=PP+1-(3*FF+TT)/2;  //?
			}
			if (type==BN)
			{
				TT=t*t-2*p;
				PP=p*p;
				FF=sqrt((4*PP-TT*TT)/3);
				m1=PP+1-(3*FF+TT)/2;
			}
			cof2=m1/q;

			if (G2)
			{
				if (small_factors(cof2)) continue;
			}

			if (!prime(q)) continue;
			if (!prime(p)) continue;
			modulo(p);

			ZZn2 xi;

			xi.set(1,1);                // for p=3 mod 8
		
// make sure its irreducible
			if (pow(xi,(p*p-1)/2)==1)
				continue;
		
			if (pow(xi,(p*p-1)/3)==1) 
				continue;  // make sure that x^6-c is irreducible

			if (G2)
			{
				if (!prime(cof2)) continue;
			}

			if (GT)
			{
				if (!prime(coft)) continue;
			}

			
// we have a solution
// Find curve b parameter - uses first positive one found (but collect some other possibilities)
			pb=0;
			b=0;
			m=0;
			while (pb<=20 || b==0)
			{
				pb+=1;
				ecurve(0,pb,p,MR_AFFINE);
				while (!P.set(rand(p))) ;
				P*=cof;
				if ((q*P).iszero())
				{
					if (b==0) b=pb;
					else cb[m++]=pb;
				}

			}
			nb=0;
			while (nb>=-20)
			{
				nb-=1;
				ecurve(0,nb,p,MR_AFFINE);
				while (!P.set(rand(p))) ;
				P*=cof;
				if ((q*P).iszero())
					cb[m++]=nb;
			}

			ecurve(0,b,p,MR_AFFINE);
// find number of points on sextic twist..
			twist=MR_SEXTIC_D;
			mip->TWIST=MR_SEXTIC_D;

			if (type==BLS12 || type==BN)
			{
				ECn2 Q;
				ZZn2 rr;

				do
				{
					rr=randn2();
				} while (!Q.set(rr));
        
				Q*=cof2;
				if (!(n*Q).iszero()) 
				{
					twist=MR_SEXTIC_M;
					mip->TWIST=MR_SEXTIC_M;
					do
					{
						rr=randn2();
					} while (!Q.set(rr));
        
					Q*=cof2;
					if (!(n*Q).iszero()) 
					{
						cout << "Never Happens" << endl;
						continue;
					}
				}
			}
			if (type==BLS24)
			{
				ECn4 Q;
				ZZn4 rr;
				do
				{
					rr=randn4();
				} while (!Q.set(rr));

				Q*=cof2;
				if (!(n*Q).iszero()) 
				{
					twist=MR_SEXTIC_M;
					mip->TWIST=MR_SEXTIC_M;
					do
					{
						rr=randn4();
					} while (!Q.set(rr));
        
					Q*=cof2;
					if (!(n*Q).iszero()) 
					{
						cout << "Never Happens" << endl;
						continue;
					}
				}
			}
			if (type==BLS48)
			{
				ECn8 Q;
				ZZn8 rr;
				do
				{
					rr=randn8();
				} while (!Q.set(rr));

				Q*=cof2;
				if (!(n*Q).iszero()) 
				{
					twist=MR_SEXTIC_M;
					mip->TWIST=MR_SEXTIC_M;
					do
					{
						rr=randn8();
					} while (!Q.set(rr));
        
					Q*=cof2;
					if (!(n*Q).iszero()) 
					{
						cout << "Never Happens" << endl;
						continue;
					}
				}
			}
			S++;
			cout << endl;
			cout << "Solution " << S << endl;
			x=0;
			bt=1;
			mip->IOBASE=16;

			cout << "x= ";
			for (k=0;k<j;k++)
			{
				if ((bt&i)!=0) {x+=xp[k]; cout << "+2^" << pw[k];}
				else {x-=xp[k]; cout << "-2^" << pw[k];}
				bt<<=1;
			}
			cout << " = " << x << endl;
			cout << "Curve is y^2=x^3+" << b;
			if (m>0)
			{
				cout << " (or) ";
				for (jj=0;jj<m;jj++)
					cout << cb[jj] << " ";
			}
			else cout << endl;
			cout << "\np= " << p << " (" << bits(p) << " bits)";
			if (twist==MR_SEXTIC_D) cout << " D-Type" << endl;
			if (twist==MR_SEXTIC_M) cout << " M-Type" << endl;
			if (progress) cout << endl;
			mip->IOBASE=10;
		//	cout << "twist= " << p+1+t << endl;
		}
	}

	cout << endl;
	cout << cnt << " candidates searched" << endl;

	if (S==0)
	{
		cout << "No solutions found" << endl;
		return 0;
	}
	if (S==1)
	{
		cout << "One solution found" << endl;
		return 0;
	}
	cout << S << " solutions found" << endl;
	return 0;
}