Golden ratio primes

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.


. More details

Leave a Reply