Computer Security and Cryptography

12.1 A SHORT NUMBER-THEORETIC DIGRESSION [KOBLITZ, 1987]

Proposition 12.1:If a, k, n are positive integers, the complexity of modular exponentiation a^k (modulo n) is O((log₂ k)(log₂ n)²).

Proof:The complexity of the multiplication two s-bit numbers in O(s²). If we write

each of the O(log₂ k) powers a^2j (modulo n) (j = 1, 2, …) can be computed in time O((log₂ n)²).

Example 12.1

Evaluate y = 1311¹³⁴ (modulo 39,979). First, the base-2 expansion of the exponent 134 is determined:

Next, T_j = 1311^2j (modulo 39,979) for 1 ≤ j ≤ 7 is computed by repeated squaring

Finally, y is expressed as a product

multiplying all of the terms {T_j} for which 2^j appears in the base-2 expansion of 134 to obtain the value of y, y = 17,236.

Proposition 12.2: (Fermat's Little Theorem): If p is a prime number

12.2a a^p = a (modulo p) for any integer, and

12.2b a^p−1 = 1 (modulo p) if a is not divisible by p.