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

stepqq mod 8q div 8
016520
1202
220

⇒ .


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.)