Add (non-working yet) Lucas test

1 files changed, 5 insertions, 2 deletions

diff --git a/numalgo.cpp b/numalgo.cpp
index 9b1681c..c3bfa1b 100644
--- a/numalgo.cpp
+++ b/numalgo.cpp
@@ -8,7 +8,7 @@ Bigint gcd(Bigint a,Bigint b){
 	while(true){
 		if(a==0)return b;
 		if(b==0)return a;
-		if(a>=b)a=a.divmod(b).second;
+		if(a.compareAbs(b)==1)a=a.divmod(b).second;
 		else b=b.divmod(a).second;
 	}
 }
@@ -45,13 +45,16 @@ Bigint expmod(const Bigint &b,const Bigint &e,const Bigint &m){
 
 int jacobiSymbol(Bigint a,Bigint n){
 	//https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol
+	// cerr<<"jacobiSymbol("<<a<<','<<n<<')'<<endl;
 	assert(n>0&&n.odd());
 	int res=1;
 	while(true){
+		// cerr<<" a="<<a<<" n="<<n<<endl;
 		a=a.divmod(n).second;
 		if(a<0)a+=n;
 		int nmod8=n.divmod(Bigint(8)).second.lowdigits();
 		int two_over_n=nmod8==1||nmod8==7?1:-1;
+		if(a==0)return 0;
 		while(a.even()){
 			res*=two_over_n;
 			a>>=1;
@@ -84,7 +87,7 @@ Bigint isqrt(const Bigint &n){
 		if(xnext==x)break;
 		x=xnext;
 	}
-	cerr<<iter<<endl;
+	// cerr<<iter<<endl;
 	assert(iter<maxiter);
 	switch((x*x).compare(n)){
 		case -1:{