More primes and primality testing

1 files changed, 20 insertions, 0 deletions

diff --git a/numalgo.cpp b/numalgo.cpp
index f2ebac5..9b1681c 100644
--- a/numalgo.cpp
+++ b/numalgo.cpp
@@ -43,6 +43,26 @@ Bigint expmod(const Bigint &b,const Bigint &e,const Bigint &m){
 	return res;
 }
 
+int jacobiSymbol(Bigint a,Bigint n){
+	//https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol
+	assert(n>0&&n.odd());
+	int res=1;
+	while(true){
+		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;
+		while(a.even()){
+			res*=two_over_n;
+			a>>=1;
+		}
+		if(a==1)return res;
+		if(gcd(a,n)!=1)return 0;
+		if(a.divmod(Bigint(4)).second.lowdigits()==3&&nmod8%4==3)res*=-1;
+		swap(a,n);
+	}
+}
+
 Bigint isqrt(const Bigint &n){
 	assert(n>=0);
 	if(n<=1)return n;