Skip to content

Instantly share code, notes, and snippets.

@primus-lab
Created January 6, 2020 08:09
Show Gist options
  • Save primus-lab/7fc9cf1e70b67066a3c0a47829185936 to your computer and use it in GitHub Desktop.
Save primus-lab/7fc9cf1e70b67066a3c0a47829185936 to your computer and use it in GitHub Desktop.
Primality test for specific class of Proth numbers
# Author: Pedja
print(" ***** PROTH *****\n\n\n")
while True:
k=int(input("Enter the coefficient : "))
n=int(input("Enter the exponent : "))
def polynomial(m,x):
if m==0:
return 2
elif 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 test(k,n):
N=k*2**n+1
s=polynomial(k,8)
ctr=1
while ctr<=n-2:
s=(s*s-2)%N
ctr=ctr+1
return int(s)==0
if k%2==0:
print("Coefficient must be an odd number")
elif k<=0:
print("Coefficient must be greater than zero")
elif n<3:
print("Exponent must be greater than two")
elif k>=2**n:
print("Coefficient must be less than 2^exponent")
elif not(((k%30==1 or k%30==7) and n%4==0) or ((k%30==11 or k%30==23) and n%4==1) or ((k%30==13 or k%30==19) and n%4==2) or ((k%30==17 or k%30==29) and n%4==3)):
print("That combination of the coefficient and exponent is not supported by this test")
else:
if test(k,n):
print(str(k)+"*2^"+str(n)+"+1 is prime")
else:
print(str(k)+"*2^"+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