Created
May 3, 2023 02:06
-
-
Save chadbrewbaker/84f50f7eedeb2413e8a457dbfa06218f to your computer and use it in GitHub Desktop.
AKS Primality Test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# ChatGPT4 spit it out with some coaxing - looks legit, haven't tested. | |
import math | |
def is_prime(n): | |
def is_power(a, b): | |
if a == 1: | |
return b != 1 | |
power = 1 | |
while power < b: | |
power *= a | |
return power == b | |
def find_r(n): | |
max_r = math.ceil(math.log2(n) ** 2) | |
for r in range(2, max_r + 1): | |
if not is_power(n, r): | |
return r | |
return -1 | |
def check_a(a, n, r): | |
for k in range(1, r + 1): | |
val = (pow(a, k, n) - k) % n | |
if val != 0: | |
return False | |
return True | |
# Check if n is a power of a smaller number | |
for a in range(2, n): | |
if is_power(a, n): | |
return False | |
# Find the smallest r such that ord_r(n) > log^2(n) | |
r = find_r(n) | |
# Check a-values from 1 to r | |
for a in range(1, r + 1): | |
if math.gcd(a, n) > 1: | |
return False | |
if not check_a(a, n, r): | |
return False | |
return True | |
n = 97 # Try with any number | |
print(f"{n} is prime: {is_prime(n)}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Bash version it gave