Problem 182: RSA Encryption

Project Euler Problem 182 Solution

EulerSolve provides an optimized solution for Project Euler Problem 182, RSA Encryption, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We work with the RSA modulus $n=pq$ for the specific primes $p=1009$ and $q=3643$. A public exponent $e$ is valid when $$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$ A message $m\in\{0,1,\dots,n-1\}$ is called unconcealed if encryption leaves it unchanged: $$m^e \equiv m \pmod n.$$ The goal is to find all valid exponents that minimize the number of unconcealed messages and then add those exponents together. Mathematical Approach The important observation is that we never need to test every message for every exponent. For a fixed $e$, the number of fixed points of the map $x\mapsto x^e \pmod n$ has a simple closed form, and that form depends only on two gcd values. Counting fixed points modulo one prime First work modulo a prime $r$, where $r$ is either $p$ or $q$. The congruence $$x^e \equiv x \pmod r$$ can be rewritten as $$x(x^{e-1}-1)\equiv 0 \pmod r.$$ So every solution is either $x=0$ or a nonzero residue satisfying $x^{e-1}=1$. The nonzero residues modulo $r$ form a cyclic multiplicative group of size $r-1$. In a cyclic group of order $r-1$, the equation $y^k=1$ has exactly $\gcd(k,r-1)$ solutions. Therefore the number of unconcealed residues modulo $r$ is $$N_r(e)=\gcd(e-1,r-1)+1.$$ The extra $+1$ is the zero solution....

Detailed mathematical approach

Problem Summary

RSA encryption ^[2] starts from two distinct primes $p$ and $q$, the modulus $n=pq$ and the number $\phi=(p-1)(q-1)$. An exponent $e$ is valid if $1\lt e\lt\phi$ and $\gcd(e,\phi)=1$. A message is a number $m$ with $0\le m\le n-1$; it is encrypted as $c=m^e\bmod n$ and decrypted as $m=c^d\bmod n$, where $ed\equiv1\pmod{\phi}$. A message is called unconcealed if encryption leaves it unchanged, $m^e\bmod n=m$. In the example of the statement, $p=19$ and $q=37$ give $n=703$ and $\phi=648$; the exponent $e=181$ is valid, since $\gcd(181,648)=1$, and yet all $703$ messages are unconcealed. For $p=1009$ and $q=3643$ we must find the sum of all valid exponents $e$ for which the number of unconcealed messages is as small as possible. ^[1]

The whole solution in one sentence: modulo each prime, a greatest common divisor counts the remainders that encryption leaves unchanged, the product of the two counts is the number of unconcealed messages, and instead of encrypting millions of messages we add up the valid exponents for which this product is smallest.

Mathematical Approach

We count by hand in a tiny system, split the count into one count for each prime, find a formula for each prime and then make it as small as possible.

1. A tiny system by hand

Take $p=3$ and $q=5$, so that $n=15$ and $\phi=8$; the valid exponents are $3$, $5$ and $7$. The cubes of $m=0,1,\dots,14$ leave the remainders

$$\begin{aligned}&0,\ 1,\ 8,\ 12,\ 4,\ 5,\ 6,\ 13,\\&2,\ 9,\ 10,\ 11,\ 3,\ 7,\ 14\end{aligned}$$

modulo $15$, so for $e=3$ exactly nine messages are unconcealed: $0,1,4,5,6,9,10,11,14$. The seventh powers leave the same remainders, so $e=7$ has the same nine unconcealed messages, while $e=5$ leaves every message unchanged: $m^5\equiv m\pmod{15}$ for all $m$. The smallest number of unconcealed messages is therefore $9$, reached by $e=3$ and $e=7$, and the answer for this tiny system would be $3+7=10$. Three of the nine are unconcealed for a simple reason: $0^e=0$, $1^e=1$ and $(n-1)^e\equiv(-1)^e=-1\pmod n$, because a valid $e$ is odd here.

2. One prime at a time

A message $m$ is unconcealed when $n$ divides $m^e-m$. Because $p$ and $q$ are different primes, $n=pq$ divides a number exactly when $p$ and $q$ both divide it: if $x=pt$ and $q$ divides $x$, then $q$ divides $t$, since $q$ and $p$ are coprime. ^[3] So $m$ is unconcealed exactly when $m^e\equiv m$ holds modulo $p$ and modulo $q$, and each of these conditions depends only on the remainder of $m$ modulo that prime. By the Chinese remainder theorem the $n$ messages correspond one to one to the pairs $(x,y)$ of a remainder $x$ modulo $p$ and a remainder $y$ modulo $q$. ^[4] Writing $N_r(e)$ for the number of remainders $x$ modulo a prime $r$ with $x^e\equiv x\pmod r$, the number of unconcealed messages is therefore

$$N(e)=N_p(e)\cdot N_q(e).$$

For $n=15$ and $e=3$: modulo $3$ all three remainders satisfy $x^3\equiv x$, because $0^3=0$, $1^3=1$ and $2^3=8\equiv2$; modulo $5$ only $0$, $1$ and $4$ do, because $2^3=8\equiv3$, $3^3=27\equiv2$ and $4^3=64\equiv4$. Hence $N(3)=3\cdot3=9$, and the nine messages of Section 1 are exactly the $m$ whose remainder modulo $5$ is $0$, $1$ or $4$.

3. Roots of one modulo a prime

Fix a prime $r$, either $p$ or $q$. The condition $x^e\equiv x\pmod r$ says that $r$ divides the product $x\,(x^{e-1}-1)$, and a prime that divides a product divides one of its factors. ^[3] So either $x\equiv0$ or $x^{e-1}\equiv1\pmod r$: the remainder $0$ is always unconcealed, and $N_r(e)$ is $1$ plus the number of nonzero remainders $y$ with $y^{e-1}\equiv1$.

To count these we use a primitive root modulo $r$: a remainder $g$ whose powers $g^0,g^1,\dots,g^{r-2}$ run through all $r-1$ nonzero remainders. Every prime has one, and $g^{r-1}$ is its first power after $g^0$ that is congruent to $1$. ^[5] Dividing an exponent $a$ by $r-1$ with remainder $t$ gives $g^a\equiv g^t$, so $g^a\equiv1$ exactly when $r-1$ divides $a$. For $r=5$ the powers of $g=2$ are $1,2,4,3$, and $2^4=16\equiv1$.

Claim. For every integer $k\ge0$, exactly $\gcd(k,r-1)$ nonzero remainders $y$ satisfy $y^k\equiv1\pmod r$.

Proof. Every nonzero remainder is $y=g^j$ for exactly one $j$ with $0\le j\le r-2$, and $y^k=g^{jk}\equiv1$ exactly when $r-1$ divides $jk$. Let $d=\gcd(k,r-1)$ and write $r-1=du$ and $k=dv$, so that $u$ and $v$ are coprime. Then $r-1$ divides $jk$ exactly when $u$ divides $jv$, that is, exactly when $u$ divides $j$. ^[3] The multiples of $u$ in the range $0\le j\le r-2$ are $0,u,2u,\dots,(d-1)u$, exactly $d$ of them. $\square$

For $r=5$ and $k=2$ we get $d=u=2$, $j\in\{0,2\}$ and the roots $2^0=1$ and $2^2=4$, as found in Section 2; for $k=4$ every nonzero remainder is a root. With $k=e-1$ the claim gives

$$N_r(e)=1+\gcd(e-1,\,r-1).$$

4. The counting formula

Sections 2 and 3 together give the number of unconcealed messages for every exponent $e\ge1$:

$$\begin{aligned}N(e)={}&\bigl(1+\gcd(e-1,p-1)\bigr)\\&\cdot\bigl(1+\gcd(e-1,q-1)\bigr).\end{aligned}$$

For the example of the statement, $\gcd(180,18)=18$ and $\gcd(180,36)=36$, so $N(181)=19\cdot37=703$. Since $1+\gcd(e-1,p-1)\le p$ and $1+\gcd(e-1,q-1)\le q$, every message is unconcealed exactly when $p-1$ and $q-1$ both divide $e-1$, that is, when their least common multiple divides $e-1$. This number is the Carmichael function $\lambda(n)=\mathrm{lcm}(p-1,q-1)$, the smallest positive exponent with $a^{\lambda(n)}\equiv1\pmod n$ for every $a$ coprime to $n$. ^[6] For $n=703$ it is $\mathrm{lcm}(18,36)=36$, and $180=5\cdot36$. For the primes of the problem $\lambda(n)=611856=\phi/6$, and the five valid exponents $e=1+k\,\lambda(n)$, $k=1,\dots,5$, conceal nothing at all.

5. Nine messages that no exponent hides

For odd primes $p$ and $q$, both $p-1$ and $q-1$ are even, so $\phi$ is even and every valid exponent is odd. Then $e-1$ is even, both greatest common divisors are at least $2$, and

$$N(e)\ge(1+2)(1+2)=9.$$

The nine messages behind this bound are those met in Section 1: for odd $e$ the remainders $0$, $1$ and $-1$ are unconcealed modulo each prime, and the Chinese remainder theorem combines the $3\cdot3$ choices into nine messages. ^[2] The bound is reached exactly when $\gcd(e-1,p-1)=2$ and $\gcd(e-1,q-1)=2$, that is, when $1$ and $-1$ are the only roots of $y^{e-1}\equiv1$ modulo both primes. Modulo $3$ the remainders $0$, $1$ and $-1$ are all three remainders, which is why $N_3(e)=3$ for every exponent in Section 1.

The bound is reached for all distinct odd primes. Let $M$ be $4$ times the product of the odd primes dividing $\phi$; it divides $\phi$, since its factors are pairwise coprime divisors of $\phi$. By the Chinese remainder theorem some $e$ with $0\le e\lt M$ is $3$ modulo $4$ and $2$ modulo each of these primes; it is valid, $3\le e\lt\phi$, and $e-1$ is $2$ modulo $4$ and $1$ modulo those primes, so $\gcd(e-1,\phi)=2$ and $N(e)=9$. The programs do not rely on this; they search for the minimum.

6. Worked example: $p=5$ and $q=11$

Here $n=55$, $\phi=40$, $p-1=4$ and $q-1=10$. The valid exponents are the $15$ odd numbers between $1$ and $40$ that are not multiples of $5$, and the formula of Section 4 gives them four different counts:

$N(e)=3\cdot3=9$ for $e=3,7,19,23,27,39$, where both greatest common divisors are $2$;
$N(e)=5\cdot3=15$ for $e=9,13,17,29,33,37$, where $4$ divides $e-1$ but $10$ does not;
$N(e)=3\cdot11=33$ for $e=11$ and $e=31$, where $10$ divides $e-1$ but $4$ does not;
$N(e)=5\cdot11=55$ for $e=21$, where $\lambda(55)=\mathrm{lcm}(4,10)=20$ divides $e-1$.

The minimum is $9$, and the sum asked for would be $3+7+19+23+27+39=118$. The six exponents also follow from congruences: $\gcd(e-1,4)=2$ means $e\equiv3\pmod4$, $\gcd(e-1,10)=2$ rules out $e\equiv1\pmod5$, and validity rules out $e\equiv0\pmod5$; this leaves the classes $3$, $7$ and $19$ modulo $20$. For $e=3$ the nine unconcealed messages are $0,1,10,11,21,34,44,45,54$, the $m$ with remainder $0$, $1$ or $4$ modulo $5$ and $0$, $1$ or $10$ modulo $11$.

7. The primes of the problem

For $p=1009$ and $q=3643$ the factorizations are

$$\begin{aligned}p-1&=1008=2^4\cdot3^2\cdot7,\\q-1&=3642=2\cdot3\cdot607,\end{aligned}$$

so $n=3675787$ and $\phi=3671136$${}=2^5\cdot3^3\cdot7\cdot607$. An exponent is valid when none of $2$, $3$, $7$ and $607$ divides it, and by Section 5 it has exactly $9$ unconcealed messages when $e-1$ is even but divisible neither by $4$ nor by $3$, $7$ or $607$. Modulo $3$ the exponent may therefore be neither $0$ nor $1$, and modulo $4$ it must be $3$:

$$\begin{aligned}&e\equiv3\pmod4,\\&e\equiv2\pmod3,\\&e\bmod7\notin\{0,1\},\\&e\bmod607\notin\{0,1\}.\end{aligned}$$

The first two conditions mean $e\equiv11\pmod{12}$, and $e=11$ passes the other two, so the minimum is $9$ and $e=11$ is the smallest exponent that reaches it. Its nine unconcealed messages are

$$\begin{aligned}&0,\ 1,\ 346086,\\&1664850,\ 1664851,\ 2010936,\\&2010937,\ 3329701,\ 3675786;\end{aligned}$$

for example, $346086$ is $-1$ modulo $1009$ and $1$ modulo $3643$. Of the next candidates $23,35,47,59,71$, the exponents $23$, $47$ and $59$ reach the minimum, $35$ is invalid because $7$ divides it, and $71$ misses the minimum because $7$ divides $70$. The requested sum is the sum of all $e$ with $1\lt e\lt\phi$ that satisfy the four conditions.

8. Why the validity test matters

The formula of Section 4 holds for every $e\ge1$, valid or not, so a program has to apply the test $\gcd(e,\phi)=1$ itself. Leaving it out changes the result: $N(2)=(1+1)(1+1)=4$, since $x^2\equiv x$ only for $x\equiv0$ and $x\equiv1$ modulo each prime, so the minimum over all exponents would be $4$, reached only by even ones. Even a scan over the odd exponents alone would wrongly add invalid ones such as $3$, $27$ and $35$, which also have $N(e)=9$. They are useless for RSA: if a prime $s$ divides both $e$ and $\phi$ and $ed-1$ were a multiple of $\phi$, then $s$ would divide $ed-(ed-1)=1$, so no decryption exponent $d$ exists. ^[2]

9. A scan or a closed form

The four conditions of Section 7 depend only on the remainder $a$ of $e$ modulo $L=4\cdot3\cdot7\cdot607=50988$, and $\phi=72L$. Each admissible remainder $a$ with $0\le a\lt L$ therefore stands for the $72$ exponents $a+tL$, $t=0,1,\dots,71$, with the sum

$$\sum_{t=0}^{71}(a+tL)=72a+2556L,$$

because $0+1+\dots+71=2556$. The remainders $0$ and $1$ are not admissible, so nothing has to be removed for $e\gt1$, and adding these sums over all admissible $a$ gives the requested sum in closed form. For $p=5$ and $q=11$ the period is $20=\phi/2$, and the remainders $3$, $7$ and $19$ of Section 6 give $2\cdot29+3\cdot20=118$. The programs instead scan $e=2,3,\dots,\phi-1$, skip the invalid exponents and evaluate the formula for the others, which needs no factorization of $p-1$ and $q-1$; the closed form serves as a check below.

How the Code Works

The C++ program ^[7] keeps the primes $1009$ and $3643$ and a checkpoint flag in Options. parse_arguments accepts --p= and --q= with decimal digits, read by parse_int_after_prefix, and --skip-checkpoints; an unknown argument, a value of at most $2$ or two equal values give exit code $1$. It does not test that the two numbers are prime, as the formula requires, and it keeps them and $\phi$ in int without overflow checks, so it needs $(p-1)(q-1)\lt2^{31}$.

unconcealed_count_formula is the formula of Section 4, with two calls of std::gcd. unconcealed_count_bruteforce follows the definition instead: it encrypts every message $m\lt n$ with pow_mod and counts the unchanged ones. pow_mod is binary exponentiation with $O(\log e)$ multiplications: it squares the base for every bit of the exponent and multiplies it into the result for every bit $1$. ^[8] mul_mod forms each product in unsigned __int128, so none overflows.

solve is the scan. For $e=2,3,\dots,\phi-1$ it skips every $e$ with $\gcd(e,\phi)\ne1$, the test of Section 8, and evaluates the formula for the others. The variable best holds the smallest count so far, with $-1$ for none yet, and sum the sum of the exponents that reach it: a smaller count replaces best and restarts sum at $e$, and an equal count adds $e$. brute_solve is the same scan with the brute-force count. Unless --skip-checkpoints is given, run_checkpoints first requires the formula to give $703$ for $e=181$, $p=19$, $q=37$, as in the statement; the formula and the brute force to agree for every valid exponent of $p=5$, $q=11$, the table of Section 6; and solve(19, 37) to equal brute_solve(19, 37), which encrypts all $703$ messages with each of the $215$ valid exponents. A failed check gives exit code $2$; otherwise main prints the result of solve.

The Python and Java programs contain only the scan, with the primes fixed and no checkpoints. Python uses math.gcd and unbounded integers; Java computes gcd with its own Euclidean loop on the remainder operator, ^[9] keeps $e$ and $\phi$ in int and the count and the sum in long, like long long in C++. The sum needs 64 bits, because a priori it can reach the sum of all $e\lt\phi$, about $6.7\cdot10^{12}$.

Complexity and Verification

The scan visits $\phi-2=3671134$ exponents and computes one greatest common divisor for each; $1047167$ of them are valid and need two more. Counting operations on machine-sized integers as single steps, each greatest common divisor costs $O(\log\phi)$: Java's loop, and CPython's math.gcd at this size, run the Euclidean algorithm, which by Lamé's theorem needs at most five divisions per decimal digit of the smaller number, at most $35$ here, ^[9] and GCC's std::gcd runs Stein's binary algorithm, which at least halves the product of the two numbers in each round. The time is therefore $O(\phi\log\phi)$, and the memory is a few integers. Timed from start to finish on a laptop with an Apple M4 Max chip, a run takes about $0.2$ s in C++ (g++ -O2, checkpoints included), $0.24$ s in Java and $0.4$ s in CPython. Encrypting every message with every valid exponent instead would take $1047167\cdot3675787\approx3.8\cdot10^{12}$ modular powers; the checkpoints need only $151145$ for $p=19$, $q=37$ and $825$ for $p=5$, $q=11$.

For this article the formula was checked against direct encryption for all $120$ pairs of distinct odd primes below $60$ and every exponent from $1$ to $\phi$, $81096$ cases. For $p=1009$ and $q=3643$ the claim of Section 3 was checked for every remainder of $e-1$ modulo $r-1$, for both primes, which covers every exponent, since $y^{r-1}\equiv1$ for every nonzero $y=g^j$; encrypting all $3675787$ messages directly gave $15$, $9$, $91$, $51$ and $3675787$ unconcealed messages for $e=5$, $11$, $13$, $17$ and $611857$, as the formula says. A separate scan confirmed that the minimum is $9$ and that the exponents reaching it are exactly those of the four conditions of Section 7, and the closed form of Section 9 gives the same sum as the three programs, which print the same number. The minimum is $9$ for all $990$ pairs of distinct odd primes below $200$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts; the counting formula, the bound $9$ and the worked examples are derived in this article.

Project Euler 182 — RSA Encryption. The official statement takes exponents 1 < e < φ = (p − 1)(q − 1) with gcd(e, φ) = 1, calls a message m unconcealed when mᵉ mod n = m, shows with p = 19, q = 37 and e = 181 that all 703 messages can be unconcealed, and asks for the sum of the e with the fewest unconcealed messages for p = 1009 and q = 3643.
Wikipedia — RSA (cryptosystem). Key generation takes two distinct primes, n = pq, an exponent e coprime to λ(n), or to φ(n) = (p − 1)(q − 1) in the original paper, and d as the inverse of e. A note on encryption says that at least nine messages give c = m, those equal to −1, 0 or 1 modulo p and modulo q, and more if p − 1 or q − 1 shares divisors other than 2 with e − 1.
Wikipedia — Euclid's lemma. A prime that divides a product ab of two integers divides a or b; more generally, if n divides ab and is coprime with a, then n divides b.
Wikipedia — Chinese remainder theorem. For pairwise coprime moduli with product N, the map sending x mod N to the tuple of its remainders is a ring isomorphism, so every tuple of remainders comes from exactly one remainder modulo N.
Wikipedia — Primitive root modulo n. A number g is a primitive root modulo n if every number coprime to n is congruent to a power of g. Primitive roots exist modulo every power of an odd prime, and the multiplicative order of a primitive root is φ(n), which is p − 1 for a prime p.
Wikipedia — Carmichael function. λ(n) is the smallest positive m with aᵐ ≡ 1 (mod n) for every a coprime to n. The article gives λ(lcm(a, b)) = lcm(λ(a), λ(b)) and λ(n) = φ(n) for a power of an odd prime, so λ(pq) = lcm(p − 1, q − 1) for distinct odd primes p and q.
C++ — Euler182.cpp. The linked immutable revision contains unconcealed_count_formula, solve, brute_solve and run_checkpoints. It is the implementation record for this article.
Wikipedia — Modular exponentiation. The right-to-left binary method squares the base for every binary digit of the exponent and multiplies it into the result for every digit 1; its running time is O(log e).
Wikipedia — Euclidean algorithm. Lamé proved in 1844 that the algorithm never needs more steps than five times the number of decimal digits of the smaller number.

Problem 182 source code

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>

namespace {

using i64 = long long;
using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    int p = 1009;
    int q = 3643;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--p=", options.p) ||
            parse_int_after_prefix(arg, "--q=", options.q)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.p > 2 && options.q > 2 && options.p != options.q;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}

u64 pow_mod(u64 base, u64 exp, const u64 mod) {
    base %= mod;
    u64 result = 1 % mod;
    while (exp > 0) {
        if ((exp & 1ULL) != 0ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1ULL;
    }
    return result;
}

i64 unconcealed_count_formula(const int e, const int p, const int q) {
    const i64 gp = std::gcd(e - 1, p - 1);
    const i64 gq = std::gcd(e - 1, q - 1);
    return (gp + 1) * (gq + 1);
}

i64 unconcealed_count_bruteforce(const int e, const int p, const int q) {
    const int n = p * q;
    i64 count = 0;
    for (int m = 0; m < n; ++m) {
        if (pow_mod(static_cast<u64>(m), static_cast<u64>(e), static_cast<u64>(n)) == static_cast<u64>(m)) {
            ++count;
        }
    }
    return count;
}

i64 solve(const int p, const int q) {
    const int phi = (p - 1) * (q - 1);
    i64 best = -1;
    i64 sum = 0;

    for (int e = 2; e < phi; ++e) {
        if (std::gcd(e, phi) != 1) {
            continue;
        }

        const i64 cnt = unconcealed_count_formula(e, p, q);
        if (best < 0 || cnt < best) {
            best = cnt;
            sum = e;
        } else if (cnt == best) {
            sum += e;
        }
    }

    return sum;
}

i64 brute_solve(const int p, const int q) {
    const int phi = (p - 1) * (q - 1);
    i64 best = -1;
    i64 sum = 0;

    for (int e = 2; e < phi; ++e) {
        if (std::gcd(e, phi) != 1) {
            continue;
        }

        const i64 cnt = unconcealed_count_bruteforce(e, p, q);
        if (best < 0 || cnt < best) {
            best = cnt;
            sum = e;
        } else if (cnt == best) {
            sum += e;
        }
    }

    return sum;
}

bool run_checkpoints() {
    if (unconcealed_count_formula(181, 19, 37) != 703LL) {
        std::cerr << "Checkpoint failed for stated sample e=181, p=19, q=37" << '\n';
        return false;
    }

    for (int e = 2; e < (5 - 1) * (11 - 1); ++e) {
        if (std::gcd(e, (5 - 1) * (11 - 1)) != 1) {
            continue;
        }
        if (unconcealed_count_formula(e, 5, 11) != unconcealed_count_bruteforce(e, 5, 11)) {
            std::cerr << "Checkpoint failed for formula-vs-brute at p=5, q=11" << '\n';
            return false;
        }
    }

    if (solve(19, 37) != brute_solve(19, 37)) {
        std::cerr << "Checkpoint failed for full brute cross-check at p=19, q=37" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.p, options.q) << '\n';
    return 0;
}

Python

# Problem 182: RSA encryption — find the sum of e values that minimize unconcealed messages.
from math import gcd

def solve():
    p, q = 1009, 3643
    phi = (p-1)*(q-1)
    best = -1
    total = 0
    for e in range(2, phi):
        if gcd(e, phi) != 1: continue
        cnt = (gcd(e-1, p-1)+1) * (gcd(e-1, q-1)+1)
        if best < 0 or cnt < best:
            best = cnt
            total = e
        elif cnt == best:
            total += e
    print(total)

solve()

Java

public class Euler182 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        int p = 1009, q = 3643, phi = (p - 1) * (q - 1);
        long best = -1, sum = 0;
        for (int e = 2; e < phi; e++) {
            if (gcd(e, phi) != 1)
                continue;
            long cnt = (long) (gcd(e - 1, p - 1) + 1) * (gcd(e - 1, q - 1) + 1);
            if (best < 0 || cnt < best) {
                best = cnt;
                sum = e;
            } else if (cnt == best)
                sum += e;
        }
        System.out.println(sum);
    }
}