Project Euler 182: RSA encryption
The RSA encryption is based on the following procedure:
Generate two distinct primes p and q.
Compute n=pq and φ=(p-1)(q-1).
Find an integer e, 1<e<φ, such that gcd(e,φ)=1.
A message in this system is a number in the interval [0,n-1].
A text to be encrypted is then somehow converted to messages (numbers in the interval [0,n-1]).
To encrypt the text, for each message, m, c=me mod n is calculated.
To decrypt the text, the following procedure is needed: calculate d such that ed=1 mod φ, then for each encrypted message, c, calculate m=cd mod n.
There exist values of e and m such that me mod n=m.
We call messages m for which me mod n=m unconcealed messages.
An issue when choosing e is that there should not be too many unconcealed messages.
For instance, let p=19 and q=37.
Then n=19*37=703 and φ=18*36=648.
If we choose e=181, then, although gcd(181,648)=1 it turns out that all possible messages
m (0≤m≤n-1) are unconcealed when calculating me mod n.
For any valid choice of e there exist some unconcealed messages.
It’s important that the number of unconcealed messages is at a minimum.
Choose p=1009 and q=3643.
Find the sum of all values of e, 1<e<φ(1009,3643) and gcd(e,φ)=1, so that the number of unconcealed messages for this value of e is at a minimum.
At the heart of this problem is the simple formula: [gcd(e-1,p-1)+1][gcd(e-1,q-1)+1] as outlined in many texts such as Recent Advances in RCA Cryptography in the chapter Properties of the RSA cryptosystem. Specifically Lemma 5.1 on page 69 shows a nice proof of this equation.
So encoding this into a program is straightforward and simple. Just sum all values of e where gcd(e,phi) = 1 and gcd(e-1,q-1) and gcd(e-1,p-1) are at a minimum (equal 2).
Project Euler 182 SolutionRuns < 1.8 seconds in Python 2.7.
from Euler import gcd p, q, s, e = 1009, 3643, 0, 3 phi = (p-1) * (q-1) while (e < phi): if gcd(e, phi)==1 and gcd(e-1, q-1)==2 and gcd(e-1, p-1)==2: s += e e += 4 print "Project Euler 182 Solution =", sUse this link to get the Project Euler 182 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
gcdis listed in Common Functions and Routines for Project Euler.