Skip to content

Instantly share code, notes, and snippets.

@primus-lab
Last active December 31, 2019 07:49
Show Gist options
  • Save primus-lab/caf933cced3a0e50548e8513929cfeca to your computer and use it in GitHub Desktop.
Save primus-lab/caf933cced3a0e50548e8513929cfeca to your computer and use it in GitHub Desktop.
Conjectured primality test for numbers of the form M=k*b^n-1
# Author: Pedja
from mpmath import *
print(" ***** MERSENNE *****\n\n\n")
while True:
k=int(input("Enter the coefficient : "))
b=int(input("Enter the base : "))
n=int(input("Enter the exponent : "))
def polynomial(m,x):
if m==1:
return x
else:
p0=2
p1=x
l=2
while l<=m:
p=x*p1-p0
p0=p1
p1=p
l=l+1
return p
def jacobi(a,q):
j=1
while a != 0:
while a%2==0:
a=a/2
if q%8==3 or q%8==5:
j=-j
c=a
a=q
q=c
if a%4==3 and q%4==3:
j=-j
a=fmod(a,q)
if q==1:
return j
else:
return 0
if 2**n<=k:
print("Coefficient must be less than 2^exponent")
elif b<2:
print("Base must be natural number greater than one")
elif n<3:
print("Exponent must be natural number greater than two")
elif b%2==1 and k%2==1:
print(str(k)+"*"+str(b)+"^"+str(n)+"-1 is composite")
else:
M=k*b**n-1
d=3
while not(jacobi(d-2,M)==1 and jacobi(d+2,M)==-1):
d=d+1
s=polynomial(k*b**2/2,d)%M
ctr=1
while ctr<=n-2:
s=polynomial(b,s)%M
ctr=ctr+1
if int(s)==M-2:
print(str(k)+"*"+str(b)+"^"+str(n)+"-1 is prime")
else:
print(str(k)+"*"+str(b)+"^"+str(n)+"-1 is composite")
try_again = ""
# Loop until users opts to go again or quit
while not(try_again == "1") and not(try_again == "0"):
try_again = input("Press 1 to try again, 0 to exit. ")
if try_again in ["1", "0"]:
continue # a valid entry found
else:
print("Invalid input- Press 1 to try again, 0 to exit.")
# at this point, try_again must be "0" or "1"
if try_again == "0":
break
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment