Fast Modular Exponentiation, and Testing a Number for Primality
Chapter Thirty-Three
Syllabus topic Module 1, row 1, Connection with Other Courses: "Discrete Mathematics (number theory and cryptographic foundations)"
Pages 194 to 201 of 678
In one line
Square and multiply your way up the bits of the exponent, and never let the numbers grow. That turns an exponentiation with a 1,024-bit exponent from impossible into a few thousand multiplications, and a companion test tells you whether a number is prime without factoring it.
In the wording a student can write in an examination: modular exponentiation by the square and multiply method computes a to the power b modulo n in a number of steps proportional to the number of bits of b, rather than to b itself. Write b in binary; scan the bits from the most significant; at each bit square the running result modulo n, and where the bit is 1 also multiply by a modulo n. Primality testing by the Miller and Rabin algorithm decides whether a number is prime with high confidence without factoring it, by strengthening Fermat's test with the observation that in a field the only square roots of 1 are 1 and minus 1.
Why both are needed before RSA
Without fast exponentiation there is no RSA. Encrypting with e of 65,537 means computing M to the power 65,537. Done naively that is 65,536 multiplications of numbers hundreds of digits long, and decryption with a 1,024-bit d would be 2 to the power 1,024 of them, which is not a number of operations anybody will perform. Square and multiply brings both within reach.
Without primality testing there is no RSA key. Key generation needs two primes of 1,024 bits or more. There is no table of them; they have to be found, and found means: pick a random odd number of the right size and test it, repeatedly, until one is prime. So the cost of generating an RSA key is the cost of the primality test times the number of candidates.
Square and multiply
The identity is simply that a to the power 2k is (a to the power k) squared, and a to the power 2k + 1 is a times that. Reading the exponent's bits from the top and applying that rule at each step gives the algorithm.
Two things keep it practical. Reduce modulo n at every step, so no intermediate value exceeds n squared. And count the steps by bits: an exponent of k bits takes k squarings and at most k multiplications.
The run
# Square and multiply, and Miller and Rabin. The two algorithms without which
# RSA is arithmetic nobody can perform.
def modexp(base, exp, mod):
result = 1
base %= mod
for bit in bin(exp)[2:]:
result = (result * result) % mod
if bit == "1":
result = (result * base) % mod
return result
def modexp_trace(base, exp, mod):
rows, result = [], 1
for i, bit in enumerate(bin(exp)[2:], 1):
squared = (result * result) % mod
result = (squared * base) % mod if bit == "1" else squared
rows.append((i, bit, squared, result))
return rows, result
print("7 to the power 560 mod 561, by squaring and multiplying:")
print(" 560 in binary is", bin(560)[2:], "so there are", len(bin(560)[2:]),
"steps, not 560")
rows, answer = modexp_trace(7, 560, 561)
print(" step bit after squaring after multiplying")
for i, bit, sq, res in rows:
print(" %4d %s %14d %17d" % (i, bit, sq, res))
print(" answer:", answer, " and Python's own pow agrees:", pow(7, 560, 561))
print()
print("the saving, counted in multiplications:")
for e in (560, 65537, 2 ** 1024):
naive = e - 1
fast = 2 * len(bin(e)) - 2
print(" exponent of %d bits: naive about %s multiplications, fast about %d"
% (e.bit_length(), format(naive, ",") if e < 10 ** 12 else "2 to the power %d" % e.bit_length(), fast))
print()
def miller_rabin(n, bases=(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)):
if n < 2:
return False
for p in bases:
if n % p == 0:
return n == p
d, r = n - 1, 0
while d % 2 == 0:
d //= 2
r += 1
for a in bases:
x = pow(a, d, n)
if x in (1, n - 1):
continue
for _ in range(r - 1):
x = (x * x) % n
if x == n - 1:
break
else:
return False
return True
print("Miller and Rabin sees what Fermat's test cannot:")
for n in (561, 1105, 1729, 2465, 104729, 4294967297):
print(" %12d prime by Miller and Rabin: %-5s Fermat base 2 says: %s"
% (n, miller_rabin(n), "prime" if pow(2, n - 1, n) == 1 else "composite"))
print(" 4294967297 is the Fermat number 2 to the power 32 plus 1, which Euler")
print(" factorised in 1732 as 641 times 6700417:", 641 * 6700417 == 4294967297)
print()
print("how many primes there are to choose from, near the sizes RSA uses:")
import math
for bits in (512, 1024, 2048):
density = 1 / (bits * math.log(2))
print(" near 2 to the power %4d, about 1 in %d odd numbers is prime,"
% (bits, int(1 / density / 2) * 2 // 2 * 2))
print(" so about %d candidates are tried to find one" % int(bits * math.log(2) / 2))
print()
print("finding a 512-bit prime, for real:")
import random
random.seed(3)
tries = 0
while True:
tries += 1
cand = random.getrandbits(512) | (1 << 511) | 1
if miller_rabin(cand):
break
print(" candidates tested:", tries)
print(" the prime found has", cand.bit_length(), "bits and ends in",
str(cand)[-6:])
print(" it is prime by Miller and Rabin:", miller_rabin(cand))Fast Modular Exponentiation, and Testing a Number for Primality
7 to the power 560 mod 561, by squaring and multiplying:
560 in binary is 1000110000 so there are 10 steps, not 560
step bit after squaring after multiplying
1 1 1 7
2 0 49 49
3 0 157 157
4 0 526 526
5 1 103 160
6 1 355 241
7 0 298 298
8 0 166 166
9 0 67 67
10 0 1 1
answer: 1 and Python's own pow agrees: 1
the saving, counted in multiplications:
exponent of 10 bits: naive about 559 multiplications, fast about 22
exponent of 17 bits: naive about 65,536 multiplications, fast about 36
exponent of 1025 bits: naive about 2 to the power 1025 multiplications, fast about 2052
Miller and Rabin sees what Fermat's test cannot:
561 prime by Miller and Rabin: False Fermat base 2 says: prime
1105 prime by Miller and Rabin: False Fermat base 2 says: prime
1729 prime by Miller and Rabin: False Fermat base 2 says: prime
2465 prime by Miller and Rabin: False Fermat base 2 says: prime
104729 prime by Miller and Rabin: True Fermat base 2 says: prime
4294967297 prime by Miller and Rabin: False Fermat base 2 says: prime
4294967297 is the Fermat number 2 to the power 32 plus 1, which Euler
factorised in 1732 as 641 times 6700417: True
how many primes there are to choose from, near the sizes RSA uses:
near 2 to the power 512, about 1 in 354 odd numbers is prime,
so about 177 candidates are tried to find one
near 2 to the power 1024, about 1 in 708 odd numbers is prime,
so about 354 candidates are tried to find one
near 2 to the power 2048, about 1 in 1418 odd numbers is prime,
so about 709 candidates are tried to find one
finding a 512-bit prime, for real:
candidates tested: 107
the prime found has 512 bits and ends in 446633
it is prime by Miller and Rabin: TrueFast Modular Exponentiation, and Testing a Number for Primality
Read six things out of that run.
560 in binary is ten bits, so the trace has ten rows rather than 560. That is the whole saving, made visible. Each row shows the value after squaring and then after multiplying if the bit was 1.
The answer is 1, and Python's own pow agrees. This is the same computation the previous chapter used to show that 561 passes Fermat's test, now performed step by step.
The saving, counted. An exponent of 17 bits, which is e of 65,537, needs about 36 multiplications instead of 65,536. An exponent of 1,025 bits needs about 2,052 instead of 2 to the power 1,025. That ratio is the reason public-key cryptography exists at all.
Fast Modular Exponentiation, and Testing a Number for Primality
Miller and Rabin sees through all four Carmichael numbers, every one of which Fermat's test calls prime. So the stronger test is not a refinement; it detects a class of composites that the weaker test cannot detect at all.
It also factors nothing and still reports 4,294,967,297 composite. That number is the Fermat number 2 to the power 32 plus 1, which Euler factorised in 1732 as 641 times 6,700,417, and the program confirms the multiplication. Fermat's own test calls it prime.
A real 512-bit prime was found in 107 candidates. The chapter predicted about 177 from the prime density near 2 to the power 512, and 107 is a perfectly ordinary draw from that distribution. So generating an RSA key is a few hundred primality tests, which is a fraction of a second.
Why Miller and Rabin works
The idea is one extra observation on top of Fermat's test, and it is worth understanding because it is examinable and short.
Write n - 1 as d times 2 to the power r, with d odd. If n is prime then, by Fermat, a to the power n - 1 is 1. Now look at the chain
a to the power d, then its square, then its square, up to a to the power (n-1)
The chain ends at 1. In a field the only square roots of 1 are 1 and minus 1. So if n is prime, either the chain starts at 1, or somewhere along it a value is minus 1, that is n - 1, and everything after is 1. If neither happens, n is definitely composite: there is a square root of 1 that is neither 1 nor minus 1, which cannot occur modulo a prime.
So a failure is a proof of compositeness, and a pass is evidence of primality. For a composite n, at least three quarters of the bases witness the compositeness, so k random bases leave a chance of error below 1 in 4 to the power k. With the small prime bases the algorithm is deterministic for numbers below 3,215,031,751, which covers every number a student will meet by hand.
A worked example, by hand
Do a short exponent by hand and read a long one off the trace. The listing's ten-step trace of 7 to the power 560 is the authority for that computation, and reproducing ten modular squarings of three-digit numbers under examination conditions is a way to lose marks rather than gain them. So here is one small enough to be safe.
Compute 3 to the power 13 modulo 17.
Fast Modular Exponentiation, and Testing a Number for Primality
Step 1: the exponent in binary. 13 is 1101, four bits. So four squarings and three multiplies.
Step 2: scan from the left, starting with the result at 1.
Bit 1 is 1. Square 1 to get 1, then multiply by 3: the result is 3.
Bit 2 is 1. Square 3 to get 9, then multiply by 3 to get 27, and 27 modulo 17 is 10.
Bit 3 is 0. Square 10 to get 100, and 100 modulo 17 is 15, since 17 times 5 is 85. No multiply.
Bit 4 is 1. Square 15 to get 225, and 225 modulo 17 is 4, since 17 times 13 is 221; then multiply by 3 to get 12.
Step 3: the answer is 12. Check it against the run's own method: the trace format is exactly the one above, and 3 to the power 13 is 1,594,323, which divided by 17 leaves 12, since 17 times 93,783 is 1,594,311.
Step 4: read the long trace the same way. In the printed ten-step trace of 7 to the power 560 modulo 561, the results after each step are 7, 49, 157, 526, 160, 241, 298, 166, 67 and finally 1. Four of those steps are multiplies, at bits 1, 5 and 6 of 1000110000, and the rest are squarings alone. Notice step 6: 160 squared is 25,600, which modulo 561 is 355, and multiplying by 7 gives 2,485, which modulo 561 is 241. That is the step a careless hand computation gets wrong, which is the reason for step 1 of this example.
The step that carries the marks. Naming the method, writing the exponent in binary, stating the step count, and performing three or four steps correctly. A question asking for a large exponentiation is testing the method, not your patience.
How many candidates a key needs
The density of primes near a number N is about 1 in the natural logarithm of N. Near 2 to the power 512 that logarithm is about 355, and since only odd candidates are worth testing the effective density is about 1 in 177. The run's 107 is a single draw from that distribution and is entirely typical.
So an RSA-2048 key, which needs two 1,024-bit primes, costs about 2 times 354 primality tests, each of which is a handful of modular exponentiations. That is why key generation takes a moment rather than a month, and it is the practical fact behind "RSA keys are generated on demand".
Distinctions that carry marks
| Naive exponentiation | Square and multiply | |
|---|---|---|
Multiplications for exponent b | about b | about 2 times the bit length of b |
For e of 65,537 | 65,536 | about 36 |
For a 1,024-bit d | 2 to the power 1,024 | about 2,052 |
| Intermediate size | unbounded | never above n squared |
Fast Modular Exponentiation, and Testing a Number for Primality
| Fermat's test | Miller and Rabin | |
|---|---|---|
| Can prove composite | yes | yes |
| Can prove prime | no | no, but the error falls as 1 in 4 to the power k |
| Fooled by Carmichael numbers | always | never |
| Extra idea | none | the only square roots of 1 modulo a prime are 1 and minus 1 |
| Primality testing | Factoring | |
|---|---|---|
| Asks | is n prime | what are n's factors |
| Cost for 1,024 bits | milliseconds | beyond reach |
| Needed for | generating an RSA key | breaking one |
| The gap between them | is what makes RSA possible |
What beginners get wrong here
Reading the exponent's bits from the wrong end. The left-to-right form squares first and multiplies on a 1 bit. There is a right-to-left form as well; pick one and be consistent.
Forgetting to reduce at every step. Without reduction the intermediate values grow without limit and the method loses its point.
Saying Miller and Rabin factors the number. It does not. It reports composite without producing a factor, which is why a 2,048-bit modulus can be recognised as composite in milliseconds and not factored at all.
Thinking primality testing and factoring are the same difficulty. They are not, and the whole of public-key cryptography lives in the gap: finding primes is easy, factoring their product is not.
Attempting ten modular squarings by hand in an examination. Show the method on a small exponent and state the bit count for a large one.
Quick revision
- Square and multiply: scan the exponent's bits from the most significant, square at each bit, multiply by the base where the bit is 1, reduce modulo
nevery time. - Cost is about 2 times the bit length of the exponent: about 36 multiplications for
eof 65,537, about 2,052 for a 1,024-bit exponent. - Miller and Rabin: write
n - 1asdtimes 2 to the powerrwithdodd; the chainato the powerd, squared repeatedly, must reach 1 through 1 or throughn - 1, because the only square roots of 1 modulo a prime are 1 and minus 1. - A failure proves compositeness; at least three quarters of bases witness a composite, so
kbases give an error below 1 in 4 to the powerk. - It sees through all four Carmichael numbers that Fermat's test calls prime, and reports 2 to the power 32 plus 1 composite without factoring it.
- Primes near 2 to the power 512 have density about 1 in 355, so about 177 odd candidates per prime. The run found one in 107.
- Finding primes is easy; factoring their product is not. That gap is where RSA lives.
Fast Modular Exponentiation, and Testing a Number for Primality
Test yourself
1. Describe the square and multiply method and state its cost. Write the exponent in binary and scan its bits from the most significant. Start with a result of 1; at each bit square the result modulo n, and where the bit is 1 also multiply by the base modulo n. The cost is one squaring per bit and at most one multiplication per bit, so about twice the bit length of the exponent, rather than a number of multiplications equal to the exponent.
2. Compute 3 to the power 13 modulo 17 by square and multiply. 13 is 1101 in binary. Start at 1. Bit 1 is 1: square to 1, multiply by 3 to get 3. Bit 2 is 1: square to 9, multiply by 3 to get 27, which is 10 modulo 17. Bit 3 is 0: square 10 to get 100, which is 15. Bit 4 is 1: square 15 to get 225, which is 4, then multiply by 3 to get 12. The answer is 12.
3. Why must the reduction be done at every step? Because otherwise the intermediate values grow to the full size of the unreduced power, which for a 1,024-bit exponent is astronomically large, and the method's advantage disappears. Reducing at each step keeps every value below n squared, so each multiplication is a fixed cost.
4. State the idea that makes Miller and Rabin stronger than Fermat's test. That modulo a prime the only square roots of 1 are 1 and minus 1. Writing n - 1 as d times 2 to the power r with d odd, the sequence starting at a to the power d and repeatedly squared must reach 1; if n is prime the sequence either starts at 1 or passes through n - 1. If it reaches 1 from anything else, that value is a square root of 1 which is neither 1 nor minus 1, so n is definitely composite.
5. What is the error probability of Miller and Rabin, and what does a failure prove? For a composite n at least three quarters of the possible bases reveal the compositeness, so testing k independent random bases leaves a probability of wrongly reporting prime below 1 in 4 to the power k. A failure at any base is a proof that n is composite, with no probability attached.
6. Why can Fermat's test not be repaired by trying more bases? Because Carmichael numbers pass for every base coprime to them. The chapter checked all four smallest ones exhaustively and found no coprime base that fails, so no number of extra bases helps. Miller and Rabin is required because it uses a property Fermat's test does not test.
Fast Modular Exponentiation, and Testing a Number for Primality
7. How many candidates must be tried to find a 512-bit prime, and what does that mean for RSA key generation? The density of primes near 2 to the power 512 is about 1 in 355, so about 1 in 177 odd candidates is prime and roughly that many must be tested. The chapter's run found one in 107. Since each test is a handful of modular exponentiations, generating both primes of an RSA-2048 key is a few hundred tests and takes a fraction of a second.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.