1. Base Expansions
Theorem 1
Let . Every positive integer can be written uniquely as
where , each digit , and .
This is the base expansion of , written . The subscript 10 is usually omitted for decimal.
Example: .
Algorithm 1 — Constructing base expansions
Repeatedly divide by ; the remainders are the digits (least significant first).
procedure base_b_expansion(n, b: positive integers, b > 1)
q := n
k := 0
while q ≠ 0
a_k := q mod b
q := q div b
k := k + 1
return (a_{k-1}, ..., a_1, a_0)
Trace: 165 in base 8
| step | q | q mod 8 | q div 8 |
|---|---|---|---|
| 0 | 165 | 20 | |
| 1 | 20 | 2 | |
| 2 | 2 | 0 |
⇒ .
2. Binary Addition — Algorithm 2
Pad and to bits each. Add bit by bit with a carry.
procedure add(a, b: positive integers)
c := 0 { carry }
for j := 0 to n − 1
d := ⌊(a_j + b_j + c) / 2⌋ { new carry: 0 if sum < 2, else 1 }
s_j := a_j + b_j + c − 2d { sum bit }
c := d
s_n := c
return (s_n, s_{n-1}, ..., s_0) { n + 1 bits }
Example:
carry 0 1 1 1 0
1 0 1 1 1
+ 0 0 1 0 1
-----------
1 1 1 0 0
(23 + 5 = 28 ✓). The result has at most bits.
3. Binary Multiplication — Algorithm 3
Partial products: (i.e. shifted left places) if , else .
procedure multiply(a, b: positive integers)
for i := 0 to n − 1
if b_i = 1 then c_i := a shifted i places
else c_i := 0
p := 0
for i := 0 to n − 1
p := p + c_i
return p
Example: : partial products , , , , ; sum them.
4. Computing div and mod — Algorithm 4
Repeated subtraction, then fix up for negative :
procedure division_algorithm(a: integer, d: positive integer)
q := 0
r := |a|
while r ≥ d
r := r − d
q := q + 1
if a < 0 and r > 0 then
r := d − r
q := −(q + 1)
return (q, r) { q = a div d, r = a mod d }
5. Fast Modular Exponentiation — Algorithm 5
Goal: compute for huge (essential in cryptography). Computing first is impractical.
Idea: use the binary expansion :
- Compute by repeated squaring.
- Multiply together only those with .
- Reduce mod after every multiplication so numbers stay small.
procedure modular_exponentiation(b: integer, n = (a_{k-1}...a_1a_0)_2, m: positive integer)
x := 1
power := b mod m
for i := 0 to k − 1
if a_i = 1 then x := (x · power) mod m
power := (power · power) mod m
return x { x = b^n mod m }
Practice: .
(Here ; multiply in mod 645.)