#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <cassert>
#include "bigint.h"
#include "numalgo.h"
#include "primes.h"
#include "rsa.h"

using namespace std;

class eof_error : public runtime_error{
public:
	eof_error()
		:runtime_error("EOF"){}
};

int64_t rand64(){
	return ((int64_t)rand()<<32)+(((int64_t)rand()%2)<<31)+rand();
}

Bigint readevalexpr(istream &is){
	Bigint a;
	is>>a;
	if(is.eof())throw eof_error();
	// cerr<<"Read "<<a<<endl;
	if(!is.fail())return a;
	is.clear();
	string s;
	is>>s;
	assert(!is.fail());
	a=readevalexpr(is);
	Bigint b=readevalexpr(is);
	//cerr<<"Operation "<<s<<" on "<<a<<" and "<<b<<endl;
	if(s=="add")return a+b;
	else if(s=="sub")return a-b;
	else if(s=="mul")return a*b;
	else if(s=="div")return a.divmod(b).first;
	else if(s=="mod")return a.divmod(b).second;
	else {
		cerr<<"Unknown operation '"<<s<<'\''<<endl;
		assert(false);
	}
}

void biginttest(){
	srand(time(NULL));

	// cerr<<Bigint(599428191)*Bigint(10)<<endl;
	// cerr<<hex<<Bigint(599428191)*Bigint(10)<<endl;

#if 1
	{
		Bigint bi;
		assert(RAND_MAX==(1U<<31)-1);
		for(int i=0;i<500000;i++){
			int64_t a=rand64(),b=rand64();
			if(a+b<0){i--; continue;}
			stringstream s1,s2,s3;
			s1<<a+b;
			s2<<Bigint(a+b);
			s3<<Bigint(a)+Bigint(b);
			assert(s1.str()==s2.str()&&s1.str()==s3.str());
		}
	}
#endif

#if 1
	{
		for(int i=0;i<1000;i++){
			int64_t n=rand64();
			istringstream ss(to_string(n));
			Bigint bi;
			ss>>bi;
			assert(bi==Bigint(n));
		}
	}
#endif

#if 1
	{
		string s="4405994068155852661780322209877856931246944549396705884037139443014164958640201650440984581318995014";
		istringstream iss(s);
		Bigint bi;
		iss>>bi;
		uint32_t digs[11]={1752788038,953502834,2175607868,1627159508,1754291416,1207689192,3196357285,3165170272,3313904421,3194703103,2062};
		for(int i=0;i<11;i++)assert(bi._digit(i)==digs[i]);
		ostringstream oss;
		oss<<bi;
		assert(oss.str()==s);
	}
#endif
}

void repl(int argc,char **argv){
	istream *in;
	if(argc==2)in=new ifstream(argv[1]);
	else in=&cin;
	for(int i=0;;i++){
		try {
			cout<<readevalexpr(*in)<<endl;
		} catch(eof_error){
			break;
		}
	}
}

void testisqrt(int argc,char **argv){
	int randsize=argc==2?strtol(argv[1],nullptr,10):1;
	assert(randsize>=1);
	for(int i=0;i<1000;i++){
		Bigint n(rand64());
		for(int j=1;j<randsize;j++){
			n<<=63;
			n+=rand64();
		}
		// cout<<hex<<n<<dec<<endl;
		Bigint root(isqrt(n));
		assert(root*root<=n);
		root+=Bigint::one;
		assert(root*root>n);
	}
}

void performrsa(){
	PrivateKey privkey;
	Bigint p(1000000007),q(3000000019);
	privkey.pub.mod=3000000040000000133LL;
	privkey.pub.exp=65537;
	{
		Bigint x;
		egcd((p-Bigint::one)*(q-Bigint::one),privkey.pub.exp,x,privkey.pexp);
	}
	cout<<"d = "<<privkey.pexp<<endl;
	Bigint msg(123456789);
	cout<<"msg = "<<msg<<endl;
	Bigint encr=encrypt(privkey.pub,msg);
	cout<<"encr = "<<encr<<endl;
	Bigint msg2=decrypt(privkey,encr);
	cout<<"msg = "<<msg2<<endl;
}

void fermatpseudo(){
	fillsmallprimes();
	for(int i=2;i<65000;i++){
		if(!strongPseudoPrime2(Bigint(i)))continue;
		if(!binary_search(smallprimes.begin(),smallprimes.end(),i))cout<<i<<' ';
	}
	cout<<endl;
}

void lucaspseudo(){
	fillsmallprimes();
	for(int i=2;i<65000;i++){
		// cerr<<"TRYING "<<i<<endl;
		if(!strongLucasPrime(Bigint(i)))continue;
		if(!binary_search(smallprimes.begin(),smallprimes.end(),i))cout<<i<<' ';
	}
	cout<<endl;
}

int main(int argc,char **argv){
	(void)argc;
	(void)argv;
	// biginttest();
	// repl(argc,argv);
	// performrsa();
	// testisqrt(argc,argv);
	// randprime(Bigint(20),Bigint(42));
	// fermatpseudo();
	// strongLucasPrime(Bigint(5));
	lucaspseudo();
}