Number Theory and Mathematical Foundations of Cryptography Questions

Direct answer

Yes: if you know $\phi(n)$ for an RSA (the Rivest, Shamir, and Adleman public-key cryptosystem) modulus $n = pq$, you can recover $p$ and $q$ in polynomial time by solving a quadratic equation, no trial division or guessing required. This is why $\phi(n)$ must be kept exactly as secret as the factorization itself.

Structured elaboration

RSA modulus $n = pq$ for distinct primes has Euler's totient

$\phi(n) = (p-1)(q-1) = pq - p - q + 1 = n - (p+q) + 1$

Rearranging gives the sum of the two primes directly from $n$ and $\phi(n)$:

$S = p + q = n - \phi(n) + 1$

Since $p$ and $q$ are also the two roots of the quadratic $x^2 - (p+q)x + pq = 0$, and $pq = n$ is already known, they are the roots of

$x^2 - Sx + n = 0$

Worked example

Reusing $n = 3233$, $\phi(n) = 3120$ (from the RSA parameters $p=61, q=53$, kept hidden here on purpose to demonstrate the recovery):

$S = p + q = n - \phi(n) + 1 = 3233 - 3120 + 1 = 114$

The discriminant of the quadratic:

$D = S^2 - 4n = 114^2 - 4(3233) = 12996 - 12932 = 64$

Since $D$ is a perfect square, $\sqrt{D} = 8$, and the roots are

$p = \frac{S + \sqrt{D}}{2} = \frac{114 + 8}{2} = 61, \qquad q = \frac{S - \sqrt{D}}{2} = \frac{114 - 8}{2} = 53$

which recovers exactly $p = 61$ and $q = 53$, using nothing but $n$ and $\phi(n)$. Every step (computing $S$, computing $D$, taking an integer square root, solving the quadratic) is ordinary polynomial-time arithmetic, so this is a genuine efficient reduction, not an exhaustive search.

Trade-offs and pitfalls

The discriminant $D = (p-q)^2$ is always a perfect square for valid RSA primes, since $p \neq q$; a failed integer square root would signal invalid input, not a flaw in the method. This proof is exactly why "compute $\phi(n)$" and "factor $n$" are treated as equivalent problems in RSA's security analysis: an attacker does not need to factor $n$ directly if they can obtain $\phi(n)$ by some other route (for example, a poorly designed protocol that leaks it, or a side-channel during key generation), because this reduction turns that leak straight into the private key. The one edge case worth naming is $p = q$ (not valid RSA, since the primes must be distinct), where $D = 0$ and the quadratic has a repeated root $p = q = S/2$.

Direct answer

The Gaussian heuristic (GH) estimates the length of the shortest nonzero vector of an n-dimensional lattice purely from its determinant: it treats lattice points as if spread uniformly with density 1/det(L) (det(L), the lattice's determinant, is the volume of the repeating unit cell its basis vectors sweep out), then asks how large a ball around the origin has to be before it is expected to contain about one nonzero lattice point. That radius is the heuristic estimate.

Structured elaboration

$\lambda_1(L) \approx \sqrt{\frac{n}{2\pi e}} \cdot \det(L)^{1/n}$

Reading the two pieces separately: det(L)^(1/n) is the geometric-mean spacing between lattice points (spreading det(L) worth of "volume" evenly over n dimensions gives roughly this spacing), and sqrt(n/(2·pi·e)) is a dimension-dependent correction factor coming from the volume of an n-dimensional ball (for large n, an n-ball's volume is dominated by a factor close to (2·pi·e/n)^(n/2), and inverting that relationship for "when does the ball's volume equal one unit of lattice density" produces this constant).

Worked example

Take the 2-dimensional lattice generated by b1 = (10, 1) and b2 = (3, 7):

$\det(L) = |10\times7-1\times3| = 67$

$\text{Gaussian heuristic estimate: } \lambda_1 \approx \sqrt{\frac{2}{2\pi e}}\times\sqrt{67} \approx 2.80$

Reducing this basis to find the actual shortest vector uses Gauss's own 2-dimensional lattice-reduction algorithm (the two-dimensional analogue of LLL: the Lenstra-Lenstra-Lovász algorithm, a polynomial-time method that finds a short, nearly-orthogonal basis for a lattice in any number of dimensions; Gauss's algorithm is that same idea specialized to two dimensions). The algorithm repeats one simple step: put the shorter of the two vectors first, subtract the best integer multiple of it from the longer vector to shrink that vector as much as possible, and repeat until neither vector can be shortened any further this way.

Tracing it on this basis, starting from b1=(10,1), b2=(3,7):

• $|b_1|^2 = 10^2+1^2 = 101$ and $|b_2|^2 = 3^2+7^2 = 58$, so b2 is the shorter vector: swap so $b_1=(3,7)$, $b_2=(10,1)$.
• Find how many copies of b1 to remove from b2: $m = \text{round}\!\left(\frac{b_1\cdot b_2}{b_1\cdot b_1}\right) = \text{round}\!\left(\frac{3\times10+7\times1}{3^2+7^2}\right) = \text{round}\!\left(\frac{37}{58}\right) = 1$
• Subtract: $b_2 \leftarrow b_2 - 1\cdot b_1 = (10,1)-(3,7) = (7,-6)$
• Check lengths again: $|b_1|^2=58$ and the new $|b_2|^2 = 7^2+(-6)^2 = 85$; since b2 is no longer shorter than b1, nothing more can be subtracted, so the algorithm stops here.

That leaves the reduced basis (3, 7) and (7, -6), and the true shortest nonzero vector is (3, 7) itself, with length $\sqrt{3^2+7^2}=\sqrt{58}\approx7.62$. The heuristic's estimate of about 2.80 is nearly three times too small for this specific lattice.

Trade-offs and pitfalls

That gap is not a bug in the formula, it is the formula's fundamental limitation on display: the Gaussian heuristic is a statement about what happens on average over random lattices, or asymptotically as n grows large, not a guarantee for any one specific lattice, and it is least reliable exactly in low dimension, like the n=2 example above, where there is no "averaging" over many dimensions to smooth out the variance.

It is also known to be unreliable for highly structured lattices, such as the ideal or cyclotomic lattices used in some ring-based cryptographic constructions, where the extra algebraic structure can make short vectors systematically more or less common than the uniform-density assumption predicts.

In cryptographic parameter selection and cost estimation, GH is used as a heuristic baseline (for example, inside the BKZ root-Hermite-factor relation used to estimate attack cost; BKZ, Block Korkine-Zolotarev, is a stronger and slower generalization of LLL that finds shorter bases by exhaustively solving small sub-blocks of the basis at a tunable block size) but always alongside empirical validation from real lattice-reduction experiments, never as a substitute for it, and treated with extra caution for structured lattices where the heuristic's own assumptions are most likely to be violated.

Direct answer

Sizing an RSA (the Rivest, Shamir, and Adleman public-key cryptosystem) modulus for a target classical security level (say 128 bits) means finding the smallest modulus for which the best known classical attack, the General Number Field Sieve (GNFS), costs at least $2^{128}$ adversary operations. Solving the bare asymptotic GNFS formula directly for that target gives roughly 2500 bits, well below the widely cited recommendation of about 3072 bits from NIST (the U.S. National Institute of Standards and Technology); the gap between "what the raw formula says" and "what standards bodies actually recommend" is closed by calibrating the formula against real factoring records, choosing a concrete adversary hardware model, and adding a margin for uncertainty. All three steps below.

Structured elaboration

The mapping has four distinct pieces, and conflating them is the main source of a wrong answer:

1. Asymptotic shape. GNFS runtime is $L_n[1/3, c] = \exp\big((c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}\big)$ with $c = (64/9)^{1/3} \approx 1.923$. This tells you the trend (sub-exponential), not a precise number, because the $o(1)$ term is unspecified.
2. Calibration against real results. The formula's hidden constant is fit using actual factoring records rather than trusted blindly. The 2009 factorization of a 768-bit RSA modulus (GNFS, international academic team, roughly $10^{20}$ operations, about 2000 CPU-core-years on a single core) is the standard anchor point: the bare formula overestimates that effort by roughly 10 bits, so any credible security-strength table quietly corrects for that overestimate.
3. Adversary hardware model. An "operation" in the formula is an abstract unit, not a real clock cycle. Translating it into a concrete cost requires picking a hardware baseline, since GNFS's dominant cost, the sieving step, behaves very differently on a general-purpose CPU, a GPU, and a dedicated ASIC or FPGA sieving device. Dedicated hardware is not hypothetical: Shamir's TWINKLE design (1999) and Shamir and Tromer's follow-up TWIRL (2003), both proposed devices built specifically to accelerate GNFS sieving, were estimated to be several orders of magnitude more cost-effective than general-purpose hardware for that one step, while the later linear-algebra step parallelizes far worse and has heavy memory-bandwidth requirements that dominate cost differently again. A credible estimate states which of these it assumes and prices accordingly, rather than treating "operation" as hardware-agnostic.
4. Safety margin. Even after calibration, published recommendations add margin for algorithmic uncertainty (a future sieving or linear-algebra improvement), engineering uncertainty (real large-scale distributed computation always costs more than a clean theoretical estimate), and how long the data needs to stay confidential.

Worked example

Solve the asymptotic equation for $\ln N$ with the target set to $128$ bits of classical security, $c(\ln N)^{1/3}(\ln \ln N)^{2/3} = 128 \ln 2 \approx 88.72$. Numerically solving this (bisection on $\ln N$) gives $\ln N \approx 1759$, i.e. a modulus of about

$k = \frac{\ln N}{\ln 2} \approx 2538 \text{ bits}$

That is the bare-formula answer, and it is meaningfully smaller than 3072 bits. Applying step 2's calibration lesson (the raw formula overestimates security by roughly 10 bits at 768-bit scale, and that gap widens rather than shrinks as sizes grow, since the unmodeled constant factors compound) pushes the honest target well past 2538 bits, and folding in step 4's engineering margin (the same margin that makes standards bodies round up rather than cut recommendations close) lands in the same neighborhood as the commonly cited 3072-bit figure. The point of walking through this is not to reproduce 3072 bits digit-for-digit from first principles, no publicly reproducible derivation does that starting only from the bare asymptotic formula, but to show which three adjustments (calibration, hardware model, margin) separate "textbook L-notation" from "the number a standards body actually publishes."

Trade-offs and pitfalls

A senior mistake to avoid is presenting 2538 bits, or any other bare-formula output, as if it were the real recommendation; it is a lower bound on the reasoning, not the answer. Equally important is stating explicitly which hardware model an adversary-cost estimate assumes: a number quoted in "GPU-years" and a number quoted in "dedicated ASIC operations" are not comparable without saying so, and mixing them silently is a same-basis-units error. Finally, these estimates are inherently uncertain and get revised: NIST's own guidance has moved 2048-bit RSA from "acceptable" toward "deprecated" over time as calibration data and adversary capability estimates improved, so any concrete-cost estimate should be dated and treated as provisional rather than as a permanent fact.

Direct answer

Listing powers of 2 modulo 11: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 8$, $2^4 \equiv 5 \pmod{11}$. So $x = 4$.

Structured elaboration

The discrete logarithm problem (DLP) asks: given a group, a generator $g$, and a target value $h$, find the exponent $x$ with $g^x = h$. In the toy group $(\mathbb{Z}/11\mathbb{Z})^\times$ (the nonzero residues mod 11 under multiplication, which has 10 elements), brute-force listing works fine because the group is tiny. For cryptographically sized groups, listing every power is completely infeasible, so the choice of algorithm matters a great deal:

• Brute force / exhaustive search: $O(N)$ time, where $N$ is the group order. Only viable for the smallest toy examples.
• Baby-step giant-step (BSGS): a meet-in-the-middle technique that trades time for memory, running in $O(\sqrt{N})$ time and $O(\sqrt{N})$ space. Deterministic and exact.
• Pollard's rho: also $O(\sqrt{N})$ expected time, but essentially $O(1)$ memory using cycle-detection instead of a stored table, which is why it is the practical choice for large groups (including elliptic curve groups) where BSGS's memory requirement is prohibitive.
• Index calculus: for the multiplicative group of a finite field specifically (not for a generic group, and not for a well-chosen elliptic curve), this exploits the field's extra number-theoretic structure to run in sub-exponential time, faster than either square-root method.

Worked example

$2^1 \equiv 2 \pmod{11}$

$2^2 \equiv 4 \pmod{11}$

$2^3 \equiv 8 \pmod{11}$

$2^4 \equiv 16 \equiv 5 \pmod{11}$

The target 5 appears at the fourth power, so $x = 4$. As a sanity check, continuing the sequence cycles through all 10 nonzero residues mod 11 before returning to 1 at $2^{10}$, confirming 2 generates the full group.

Trade-offs and pitfalls

The difficulty of DLP is not a fixed property of "discrete logs" in general, it depends entirely on which group is used. Because index calculus applies to finite-field multiplicative groups but not to generic elliptic curve groups, cryptographers must use much larger finite-field-based groups (moduli sized like RSA's, the Rivest-Shamir-Adleman public-key cryptosystem, or classical Diffie-Hellman groups, at 2048+ bits) than elliptic curve groups (around 256 bits) to reach the same security level: the finite-field case has a sub-exponential attack available and the curve case does not. A common mistake is assuming any two "2048-bit" or "256-bit" groups offer comparable security just because the numbers are similar; the group's algebraic structure, not just its size, determines which attacks apply.

Direct answer

Shannon entropy measures the average unpredictability of a random variable across its whole distribution; min-entropy measures unpredictability in the worst case, driven entirely by the single most likely outcome. For cryptographic key material, min-entropy is the right measure because an attacker only needs to guess correctly once, so what matters is the probability of the single easiest guess succeeding, not the average behavior of the distribution as a whole.

Structured elaboration

For a discrete random variable $X$ with outcomes having probabilities $p(x)$, Shannon entropy is

$H(X) = -\sum_x p(x) \log_2 p(x)$

the expected number of bits of "surprise" per sample, an average-case measure. Min-entropy is

$H_\infty(X) = -\log_2\left(\max_x p(x)\right)$

determined entirely by the single most probable outcome, ignoring the shape of the rest of the distribution. Min-entropy directly bounds an attacker's best single-guess success probability: an adversary who guesses the most likely value succeeds with probability exactly $2^{-H_\infty(X)}$, no better strategy exists for a single guess. Shannon entropy carries no such direct guarantee, a distribution can have high Shannon entropy while still having one dangerously likely outcome, because Shannon entropy averages over many unlikely outcomes that pull the average up without making the attacker's best single guess any harder.

Worked example

Consider a random number generator (RNG) with 10 possible outputs: one output occurs with probability 0.9, and the other 9 outputs share the remaining probability equally, each at $0.1/9 \approx 0.0111$.

$H(X) = -\left[0.9 \log_2 0.9 + 9 \times (0.0111 \log_2 0.0111)\right] \approx 0.786 \text{ bits}$

$H_\infty(X) = -\log_2(0.9) \approx 0.152 \text{ bits}$

Shannon entropy reports a moderate-looking 0.786 bits, which could be misread as "reasonably unpredictable." Min-entropy reports the truth: an attacker who simply always guesses the dominant outcome succeeds 90% of the time, $2^{-0.152} = 0.9$. A key source with this distribution would be catastrophically weak despite its non-trivial Shannon entropy figure.

Trade-offs and pitfalls

Extractor constructions and key-derivation security proofs are built around min-entropy specifically, because a security proof needs a worst-case guarantee that holds regardless of the distribution's shape, and Shannon entropy simply does not provide that guarantee. A common mistake is quoting a source's Shannon entropy (which is often the easier of the two to estimate from sampled data) as evidence of cryptographic quality, when it is min-entropy, harder to estimate and usually the smaller of the two numbers, that actually determines how much uniform key material can safely be extracted from that source. Shannon entropy remains the right tool for a different class of problem entirely, measuring expected information content for communication and compression, where average-case behavior across many transmissions is what matters, not for assessing a single key's worst-case guessability.