Golden Ratio Primes With Python
Python can be used for some amazing mathematical and scientific purposes (hence its popularity in data science). Read on to see an example of this power.
Join the DZone community and get the full member experience.
Join For FreeThe golden ratio is the larger root of the equation
φ² - φ - 1 = 0.
By analogy, golden ratio primes are prime numbers of the form
p = φ² – φ – 1
where φ is an integer. To put it another way, instead of solving the equation
φ² - φ - 1 = 0
over the real numbers, we're looking for prime numbers p where the equation can be solved in the integers mod p.
Application
When φ is a large power of 2, these prime numbers are useful in cryptography because their special form makes modular multiplication more efficient. (See the previous post on Ed448.) We could look for such primes with the following Python code.
from sympy import isprime
for n in range(1000):
phi = 2**n
q = phi**2 - phi - 1
if isprime(q):
print(n)
This prints 19 results, including n = 224, corresponding to the golden ratio prime in the previous post. This is the only output where n is a multiple of 32, which was useful in the design of Ed448.
Golden Ratio Primes in General
Of course you could look for golden ratio primes where φ is not a power of 2. It's just that powers of 2 are the application where I first encountered them.
A prime number p is a golden ratio prime if there exists an integer φ such that
p = φ² – φ – 1
which, by the quadratic theorem, is equivalent to requiring that m = 4 p + 5 is a square. In that case
φ = (1 + √m)/2.
Here's some code for seeing which primes less than 1000 are golden ratio primes.
from sympy import primerange
def issquare(m):
return int(m**0.5)**2 == m
for p in primerange(2, 1000):
m = 4*p + 5
if issquare(m):
phi = (int(m**0.5) + 1) // 2
assert(p == phi**2 - phi - 1)
print(p)
By the way, there are faster ways to determine whether an integer is a square. See this post for algorithms.
Instead of looping over primes and testing whether it's possible to solve for φ, we could loop over φ and test whether φ leads to a prime number.
for phi in range(1000):
p = phi**2 - phi - 1
if isprime(p):
print(phi, p)
Examples
The smallest golden ratio prime is p = 5, with φ = 3.
Here's a cute one: the pi prime 314159 is a golden ratio prime, with φ = 561.
The golden ratio prime that started this rabbit trail was the one with φ = 2 224, which Mike Hamburg calls the Goldilocks prime in his design of Ed448.
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments