This document does three things:
- States and proves exactly when the "hidden primes in
(PQ)!" pattern holds. - Derives the Wilson consequence
(p-3)! = (p-1)/2 (mod p), with14! = 8 (mod 17)as the worked case. - Synthesizes these into a naive factoring attack on an RSA modulus, with several examples, and explains why it is no threat to real RSA.
Throughout, v_p(m) denotes the exponent of the prime p in the factorization of m, and Legendre's formula is used:
v_p(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...
Let N = P * Q with primes P > Q. The earlier claim was that inside N! the prime P sits at exponent Q and the prime Q sits at exponent P + 1. One half of that is a theorem. The other half is only conditional.
Proof. By Legendre's formula,
v_P((PQ)!) = sum over i >= 1 of floor(PQ / P^i).
The i = 1 term is floor(PQ / P) = Q. For i >= 2,
floor(PQ / P^i) = floor(Q / P^(i-1)).
Since P > Q >= 2, we have P^(i-1) >= P > Q whenever i >= 2, so 0 <= Q / P^(i-1) < 1 and every such term is 0. Hence the sum is exactly Q. QED
Note this proof only used P > Q; Q did not even have to be prime. So the "P appears to the power Q" half is robust, and it is what makes 61^53 (P to the Q) appear in 3233!.
Proof. By Legendre's formula,
v_Q((PQ)!) = sum over i >= 1 of floor(PQ / Q^i)
= floor(P) + sum over j >= 1 of floor(P / Q^j)
= P + floor(P/Q) + floor(P/Q^2) + ...
So v_Q((PQ)!) = P + 1 exactly when the tail floor(P/Q) + floor(P/Q^2) + ... equals 1.
Since P > Q, the first tail term satisfies floor(P/Q) >= 1, with equality precisely when P < 2Q. If Q < P < 2Q, then because Q >= 2 we also have P < 2Q <= Q^2, so floor(P/Q^2) and all later terms vanish, and the tail is exactly 1. Conversely, if P >= 2Q, then floor(P/Q) >= 2, so the tail is at least 2 and the exponent is at least P + 2. QED
For balanced RSA primes, P and Q are the same bit length, so Q < P < 2Q always holds, and both halves of the pattern are true. That is the interesting case:
v_P((PQ)!) = Q (always)
v_Q((PQ)!) = P + 1 (because the primes are balanced)
For 3233 = 61 * 53: v_61 = 53 = Q, and since 53 < 61 < 106, v_53 = 62 = P + 1. Both hold.
Counterexample when primes are lopsided: N = 177 = 59 * 3. Here P = 59 >= 2Q = 6, so Proposition 2 fails. Direct computation gives
v_3(177!) = 59 + 19 + 6 + 2 = 86, not 60.
The larger-prime theorem still holds even here: v_59(177!) = 3 = Q.
Wilson's theorem. For a prime p, (p-1)! = -1 (mod p).
Proof. Split off the top two factors of (p-1)!:
(p-1)! = (p-1) * (p-2) * (p-3)!.
Modulo p, p-1 = -1 and p-2 = -2, so
(p-1)! = (-1)(-2)(p-3)! = 2 * (p-3)! (mod p).
By Wilson, the left side is -1, giving
2 * (p-3)! = -1 (mod p).
Because p is odd, 2 is invertible mod p, and its inverse is (p+1)/2 since 2 * (p+1)/2 = p + 1 = 1 (mod p). Multiplying,
(p-3)! = -(p+1)/2 (mod p).
Finally -(p+1)/2 + p = (p-1)/2, and 0 <= (p-1)/2 < p, so
(p-3)! = (p-1)/2 (mod p). QED
For p = 17: (p-1)/2 = 8, and indeed 14! = 8 (mod 17).
| p | (p-3)! | value mod p | (p-1)/2 |
|---|---|---|---|
| 5 | 2! | 2 | 2 |
| 7 | 4! | 3 | 3 |
| 11 | 8! | 5 | 5 |
| 13 | 10! | 6 | 6 |
| 17 | 14! | 8 | 8 |
| 19 | 16! | 9 | 9 |
| 23 | 20! | 11 | 11 |
The point for what follows: factorials taken modulo a prime have clean, forced values. Wilson pins down (p-1)!, and shifts like the one above pin down neighbors. That rigidity is exactly the lever a factorial-based factoring attack pulls.
The RSA modulus N = P * Q is public; the factorization is the secret. A factorial gives a slow but fully correct way to recover it.
Compute the running factorial modulo N, taking a gcd with N at each step:
r = 1
for k = 2, 3, 4, ...:
r = (r * k) mod N
g = gcd(r, N)
if 1 < g < N: output g as a nontrivial factor
Why it works. A key identity is gcd(k! mod N, N) = gcd(k!, N), since reducing mod N does not change the gcd with N. Now with P > Q both prime:
- For
k < Q: no factor1..kis divisible byPorQ(both exceedk), sogcd(k!, N) = 1. - For
Q <= k < P:Qdividesk!butPdoes not, sogcd(k!, N) = Q. - For
k >= P: both dividek!, so the gcd isN(trivial).
Therefore the first k producing a nontrivial gcd is k = Q, and it hands you the smaller prime Q. This is the same fact that made Legendre's formula useful: v_Q(k!) jumps from 0 to positive exactly at k = Q.
Examples (first nontrivial k and the factor found):
| N | factors | attack finds Q at k = | factor |
|---|---|---|---|
| 15 | 3, 5 | 3 | 3 |
| 91 | 7, 13 | 7 | 7 |
| 143 | 11, 13 | 11 | 11 |
| 3233 | 53, 61 | 53 | 53 |
| 10403 | 101, 103 | 101 | 101 |
For N = 3233, the modulus from the RSA example, the smaller prime 53 falls out at step k = 53, and dividing gives 61. No 9945-digit factorial is ever built, since everything is reduced mod N.
Wilson's theorem guarantees a factor by one step earlier. Modulo the smaller prime Q, (Q-1)! = -1, so Q divides (Q-1)! + 1. Hence
gcd((Q-1)! + 1, N) is divisible by Q,
and (barring the rare case where P also divides it) equals Q. So this variant is guaranteed to find Q by k = Q - 1.
In practice it often trips over a factor much earlier, because k! + 1 can happen to be divisible by P or Q for small k. Two real cases from the examples above:
N = 3233: atk = 8,8! + 1 = 40321 = 61 * 661, so the gcd is61. The larger prime appears at step 8.N = 10403: atk = 6,6! + 1 = 721 = 7 * 103, so the gcd is103.
These early hits are number-theoretic coincidences (a factor of N happening to divide k! + 1), so the variant is not monotone or predictable. The rigorous statement remains: it must succeed by k = Q - 1, courtesy of Wilson.
The core attack costs about Q modular multiplications and gcds. For a balanced modulus, Q is close to sqrt(N), so for an n-bit modulus the work is roughly 2^(n/2) operations. For a 2048-bit RSA modulus the smaller prime is about 1024 bits, so the loop would need on the order of 2^1024 steps, which is hopeless. This is asymptotically worse than trivial trial division and vastly worse than real algorithms like Pollard's rho or the number field sieve. It is a naive attack: perfectly correct, and useful only against small or badly unbalanced moduli.
What makes it instructive is the throughline. The same fact that lets Legendre read the exponent of Q in N! (the prime Q first divides k! at k = Q) is exactly the fact the gcd attack exploits, and Wilson's identities are the reason factorials mod a prime are rigid enough to probe with in the first place.
from math import gcd, factorial
# Wilson corollary: (p-3)! = (p-1)/2 (mod p)
def check_wilson(p):
return factorial(p - 3) % p == (p - 1) // 2
# Legendre: exponent of prime q in n!
def legendre(n, q):
e, power = 0, q
while power <= n:
e += n // power
power *= q
return e
# Naive factorial factoring: returns (step, factor) or None
def factor_by_factorial(N):
r = 1
for k in range(2, N):
r = (r * k) % N
g = gcd(r, N)
if 1 < g < N:
return k, g
return None
assert check_wilson(17) # 14! = 8 (mod 17)
assert legendre(3233, 61) == 53 # v_61(3233!) = 53 = Q
assert factor_by_factorial(3233) == (53, 53)v_P((PQ)!) = Qfor all primesP > Q. This half of the pattern is always true.v_Q((PQ)!) = P + 1if and only ifP < 2Q, that is, for balanced primes. It fails for lopsided ones, such as177 = 59 * 3, where the exponent of3is86.- Wilson's theorem gives
(p-3)! = (p-1)/2 (mod p), verified by14! = 8 (mod 17). - The map
k -> gcd(k! mod N, N)factorsNby exposing the smaller primeQat stepk = Q, and Wilson's theorem yields a variant that must succeed by stepQ - 1. Both cost aboutQsteps, which is why they illustrate the structure of RSA without endangering it.