The golden ratio is the larger root of the equationφ² – φ – 1 = 0.
By analogy, golden ratio primes are prime numbers of the formp = φ² – φ – 1where φ is an integer.
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.
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 thatp = φ² – φ – 1which, by the quadratic theorem, is equivalent to requiring that m = 4p + 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.
There are 168 primes less than 1000, and 20 of them are golden ratio primes.
The smallest is p = 5, corresponding to φ = 3.
The pi prime 314159 is a golden ratio prime, with φ = 561.