Timor Leste - They don't really care about us...

SYURADIKARA

Wednesday, July 7, 2010

Number Theory

Number Theory








Elementary number theory provides a rich set of tools for the implementation of cryptographic schemes. Most public­key cryptosystems are based in one way or another on number­theoretic id
Bignum computations


Many cryptographic schemes, such as RSA, work with large integers, also known as “bignums” or “multi­
precision integers.” Here “large” may mean 160–4096 bits (49–1233 decimal digits), with 1024­bit integers
(308 decimal digits) typical. We briefly overview of some implementation issues and possibilities.

When RSA was invented, efficiently implementing it was a problem. Today, standard desktop CPU’s perform bignum computations quickly. Still, for servers doing hundreds of SSL connections per second, a hardware assist may be needed, such as the SSL accelerators produced by nCipher www.ncipher.com/.

A popular C/C++ software subroutine library supporting multi­precision operations is GMP (GNU Multi­
precision package) www.swox.com/gmp/. A more elaborate package (based on GMP) is Shoup’s NTL
(Number Theory Library) www.shoup.net/ntl/. For a survey, see
https://www.cosic.esat.kuleuven.ac.be/nessie/call/mplibs.html.

Java has excellent support for multiprecision operations in its BigInteger class java.sun.com/j2se/1.4.1/docs/api/java/math/BigInteger.html; this includes a primality­ testing routine.

Python www.python.org/ is a personal favorite; it includes direct support for large integers.

Scheme www.swiss.ai.mit.edu/projects/scheme/ also provides direct bignum support.

Some other pointers to software and hardware implementations can be found in the “Practical Aspects”
section of Helger Lipmaa’s “Cryptology pointers” www.tcs.hut.fi/˜helger/crypto/=.

When working on k­bit integers, most implementations implement addition and subtraction in time O(k), multiplication, division, and gcd in time O(k2 ) (although faster implementations exist for very large k), and modular exponentation in time O(k3 ).

To get you roughly calibrated, here are some timings, obtained from a simple Python program on my IBM Thinkpad laptop (1.2 GHz PIII processor) on 1024­bit inputs. SHA­1 is included just for comparison. The last column gives the approximate ratio of running time to addition.

2.2 microseconds addition 455,000 per second 1
4.4 microseconds SHA1 hash (on 20­byte input) 227,000 per second 2
10.8 microseconds modular addition 93,000 per second 5
41 microseconds multiplication 24,000 per second 20
135 microseconds modular multiplication 7,400 per second 60
2.3 milliseconds modular exponentiation (exponent is 2**16+1) 440 per second 1000
5.5 milliseconds gcd 180 per second 2500
204 milliseconds modular exponentiation (1024­bit exponent) 5 per second 93000










Divisors and Divisibility



Definition 1 (Divides relation, divisor, common divisor) We say that “d divides a”, written d | a, if there exists an

integer k such that a = kd. If d does not divide a, we write “d
If d | a and d | b, then d is a common divisor of a and b.

| a”. If d | a and d ≥ 0, we say that d is a divisor of a.




Example 1 Every integer d ≥ 0 (including d = 0) is a divisor of 0. While 0 divides no integer except itself, 1 is a divisor of every integer. The divisors of 12 are {1, 2, 3, 4, 6, 12}. A common divisor of 14 and 77 is 7. If d | a then d | (−a).


Definition 2 (prime) An integer p > 1 is prime if its only divisors are 1 and p.


Definition 3 (Greatest common divisor, relatively prime) The greatest common divisor, gcd(a, b), of two integers a and b is the largest of their common divisors, except that gcd(0, 0) = 0by definition. Integers a and b are relatively prime if gcd(a, b) =. 1


Example 2

gcd(24, 30) = 6 gcd(4, 7) = 1 gcd(0, 5) = 5 gcd(−6, 10) = 2


Example 3 For all a ≥ 0, a and a + 1are relatively prime. The integer 1 is relatively prime to all other integers.


Example 4 If p is prime and 1 ≤ a < p, then gcd(a, p) =. 1That is, a and p are relatively prime.


Definition 4 For any positive integer n, we define Euler’s phi function of n, denoted φ(n), as the number of integers d,
1 ≤ d ≤ n, that are relatively prime to n. (Note that φ(1) = 1.)


Example 5 If p is prime, then φ(p) = p − 1. For any integer k > 0, φ(2k ) =k 2−1 .


Definition 5 The least common multiple lcm(a, b) of two integers a ≥ 0, b ≥ 0, is the least m such that a | m and
b | m.

Exercise 1 Show that the number of divisors of n = pe1 e2 ek �

ei ).


Exercise 2 Show that lcm(a, b) = ab/ gcd(a, b).

1 p2





• • • pk





(where the pi ’s are distinct primes) is





1≤i≤k (1 +






Fermat’s Little Theorem



Theorem 1 (Fermat’s Little Theorem) If p is prime and a ∈ Z∗
p , then ap−1 = 1 (mop) d.


Theorem 2 (Lagrange’s Theorem) The order of a subgroup must divide the order of a group.


Fermat’s Little Theorem follows from Lagrange’s Theorem, since the order of the subgroup a generated by a in Z∗ is

the least t > 0 such that at = 1 (mod p), and Z∗ = p − 1.

�� p


| p |

Euler’s Theorem generalizes Fermat’s Little Theorem, since Z∗ = φ(n) for all n > 0.
| n |


Theorem 3 (Euler’s Theorem) For any n > 1 and any a ∈ Z∗
n , aφ(n) = 1 (modn) .


A somewhat tighter result actually holds. Define for n > 0 Carmichael’s lambda function λ(n) to be the least positive

t such that at

= 1 (mod n) for all a ∈ Z∗
n . Then λ(1) =λ(2) = , 1λ(4) = , 2λ(2e ) = e 2−2 for e > 2,

λ(pe ) = pe−1 (p − 1) if p is an odd prime, and if n = pe1 • • • pek , then
1 k


λ(n) =


λ(pe1lcm(


ek )) .

1 ), . . . , λ(pk


Computing modular inverses. Fermat’s Little Theorem provides a convenient way to compute the modular inverse a−1
(mod p) for any a ∈ Z∗
p , where p is prime:


a−1 = ap−2


(mod p) .


(Euclid’s extended algorithm for computing gcd(a, p) is more efficient.)

Primality testing. The converse of Fermat’s Little Theorem is “almost” true. The converse would say that if 1 ≤ a < p
and ap−1 = 1 (mod p), then p is prime. Suppose that p is a large randomly chosen integer, and that a is a randomly chosen integer such that 1 ≤ a < p. Then if ap−1 = 1 (mod p), then p is certainly not prime (by FLT), and otherwise p is “likely” to be prime. FLT thus provides a heuristic test for primality for randomly chosen p; refinements of this approach yield tests effective for all p.


Exercise 1 Prove that λ(n) is always a divisor of φ(n), and characterize exactly when it is a proper divisor.


Exercise 2 Suppose a > 1 is not even or divisible by 5; show that a100 (in decimal) ends in 001.



Exercise 3 Let p be prime. (a) Show that ap = a (mod p) for any a ∈ Zp . (b) Argue that (a + b)p = ap + bp
for any a,b in Zp . (c) Show that (me )d = m (mod p) for all m ∈ Zp if ed = 1 (mod p − 1).



(mod p)











Generators



Definition 1 A finite group G = (S, •) may be cyclic, which means that it contains a generator g such that every group element h ∈ S is a power h = gk of g for some k ≥ 0. If the group operation is addition, we write this condition as
g + g + • • • + g = kg .h =
� �� �
k


Example 1 For example, 3 generates Z10 under addition, since the multiples of 3, modulo 10, are:

3, 6, 9, 2, 5, 8, 1, 4, 7, 0 .


Fact 1 The generators of (Zm , +) are exactly those φ(m) integers a ∈ Zm relatively prime to m.


Example 2 The generators of (Z10 , +) are {1, 3, 7, 9}.


Example 3 The group (Z∗
11 , •) is generated by g = 2, since the powers of 2 (modulo 11) are:

2, 4, 8, 5, 10, 9, 7, 3, 6, 1 .


Fact 2 Any cyclic group of size m is isomorphic to (Zm , +). For example, (Z∗ ) ↔ (Z10 , +) via:
11 , •

2x (mod 11) ←→ x (mod 10) .


Theorem 1 If p is prime, then (Z ∗ ) is cyclic, and contains φ(p − 1) generators. More generally, the group (Zn , •) is
p , •
cyclic if and only if n = 2, n = 4, n = pe , or n = 2pe , where p is an odd prime and e ≥ 1; in these cases the group contains φ(φ(n)) generators.


Finding a generator of Z∗
p . If the factorization of p − 1 is unknown, no efficient algorithm is known, but if p − 1 has known factorization, it is easy to find a generator. Generators of Z∗
p are relatively common (φ(n) ≥ n/(6 ln n ln) for n ≥ 5), so one can be found by searching at random for an element g whose order is p − 1. (Note g has order p − 1 if gp−1 = 1 (mod p) but g(p−1)/q = 1 (mod p) for all prime divisors q of p − 1).

Group generated by an element. In any group G, the set �g� of elements generated by g is always a cyclic subgroup of
G; if �g� = G then g is a generator of G.

Groups of prime order. If a group H has prime order, then every element except the identity is a generator. For example, the subgroup QR11 = {1, 4, 9, 5, 3} of squares (quadratic residues) in Z∗
11 has order 5, so 4, 9, 5, and 3 all generate QR11 . For this reason, it is sometimes of interest to work with the group QRp of squares modulo p, where p = 2q + 1 and q is prime.



p , •); prove that gxExercise 1 (a) Find all of the generators of (Z11 , •) and of (Z2k , +). (b) Let g be a generator of (Z
generates Z∗
p if and only if x generates (Zp−1 , +).








Orders of Elements



Definition 1 The order of an element a of a finite group G is the least positive t such that at = 1. (If the group is written additively, it is the least positive t such that a + a + • • • + a (t times) = 0.)



1 2 3 4 5 6 7 . . . Order

1 1 1 1 1 1 1 1 . . . 1







Row a column k contains ak mod p for p = 7; bold­
k

2 2 4 1 2 4 1 2 . . . 3

3 3 2 6 4 5 1 3 . . . 6

4 4 2 1 4 2 1 4 . . . 3

5 5 4 6 2 3 1 5 . . . 6

face entries illustrate the fundamental period of a
(mod p) as k increases. The length of this period is the order of a, modulo p. By Fermat’s Little The­ orem the order always divides p − 1; thus ap−1 is always 1 (see the column marked with an uparrow). Elements 3 and 5 have order p − 1, and so are gen­ erators of Z∗
7 . Element 6 is −1, modulo 7, and thus


6 6 1 6 1 6 1 6 . . . 2


has order 2.






Fact 1 The order of an element a ∈ G is a divisor of the order of G. (The order |G| of a group G is the number of
elements it contains.) Therefore a|G| = 1 in G . Thus when p is prime, the order of an element a ∈ Z∗ is a divisor of
p
Z∗ = p − 1, and in general the order of an element a ∈ Z∗ is a divisor of Z∗ = φ(n).

| p |

|n n |



Computing the order t of an element a ∈ G. If the factorization of |G| is unknown, no efficient algorithm is known,

but if G has known factorization G = pe1 e2 ek

1f f2 fk

| | | |

1 p2

• • • pk , it is easy. Basically, compute the order t as t = p1 p2

• • • pk

where each fi is initially ei , then each fi is decreased in turn as much as possible (but not below zero) while keeping
at = 1 in G.


Fact 2 When p is prime, the number of elements in Z∗ of order d, where d | (p − 1), is φ(d). For example, since
p
φ(2) =, 1there is a unique square root of 1 modulo p, other than 1 itself (it is −1 = p − 1 (modp)).



Exercise 1 Let ord(a) denote the order of a ∈ G. (a) Prove that ord(a) = ord(a−1 ) and ord(ak ) |



ord(a). (b) Prove

that ord(ab) is a divisor of lcm(ord(a), ord(b)), and show that it may be a proper divisor. (c) Show that ord(ab) =
ord(a) ord(b) if gcd(ord(a), ord(b)) =. 1


Exercise 2 Show that there are at least as many elements of order p − 1 (i.e. generators) of Z∗ as there are elements of
p
any other order.


Exercise 3 Show that the order of a in (Zn , +) is n/ gcd(a, n).






Euclid’s Algorithm for Computing GCD


It is easy to compute gcd(a, b). This is surprising because you might think that in order to compute gcd(a, b) you would need to figure out their divisors, i.e. solve the factoring problem. But, as you will see, we don’t need to figure out the divisors of a and b to find their gcd.

Euclid (circa 300 B.C.) showed how to compute gcd(a, b) for a ≥ 0 and b ≥ 0:


gcd(a, b) =


a if b = 0
gcd(b, a mod b) otherwise



The recursion terminates since (a mod b) < b; the second argument strictly decreases with each call. An equivalent non­recursive version sets a0 = a, a1 = b, and then computes ai+1 for i = 2, 3, . . . as ai+1 = ai−1 mod ai until ai+1 = 0, then returns ai .


Example 1 Euclid’s Algorithm finds the greatest common divisor of 12 and 33 as:

gcd(12, 33) = gcd(33, 12) = gcd(12, 9) = gcd(9, 3) = gcd(3, 0) = 3.


The equivalent non­recursive version has a0 = 12, a1 = 33, and
a2 = a0 mod a1 = 12 mod 33 = 12 a3 = a1 mod a2 = 33 mod 12 = 9 a4 = a2 mod a3 = 12 mod 9 = 3
a5 = a3 mod a4 = 9 mod 3 = 0

So gcd(12, 33) =. 3

It can be shown that the number of recursive calls is O(log b); the worst­case input is a pair of consecutive Fibonacci numbers. Euclid’s algorithm (even if extended) takes O(k2 ) bit operations when inputs a and b have at most k bits; see Bach and Shallit.























Euclid’s Extended Algorithm



Theorem 1 For all integers a, b, one can efficiently compute integers x and y such that

gcd(a, b) = ax + by .


We give a “proof by example,” using Euclid’s Extended Algorithm on inputs a = 9, b = 31, which for each ai of the nonrecursive version of Euclid’s algorithm finds an xi and yi such that ai = axi + byi :

a0 = a = 9 = a ∗ 1 +b ∗ 0
a1 = b = 31 = a ∗ 0 +b ∗ 1

2a =
3a =
4a =
5a =

a0 mod a1 =
a1 mod a2 =
a2 mod a3 =
a3 mod a4 =

=9 (a ∗ 1 +b ∗ 0) − 0 ∗ (a ∗ 0 +b ∗ 1) =
=4 (a ∗ 0 +b ∗ 1) − 3 ∗ (a ∗ 1 +b ∗ 0) =
=1 (a ∗ 1 +b ∗ 0) − 2 ∗ (a ∗ (−3) +b ∗ 1) =
0

a ∗ 1 +b ∗ 0 a ∗ (−3) +b ∗ 1 a ∗ 7 +b ∗ (−2)



Thus Euclid’s Extended Algorithm computes x = 7 and y = −2 for a = 9 and b = 31.


Corollary 1 (Multiplicative inverse computation) Given integers n and a where gcd(a, n) =, 1using Euclid’s Ex­ tended Algorithm to find x and y such that ax + ny = 1 finds an x such that ax ≡ 1 (modn); such an x is the multiplicative inverse of a modulo n: x = a−1 (mod n).


Example 1 The multiplicative inverse of 9, modulo 31, is 7. Check: 9 ∗ 7 = 63 = 1mod (31).


Exercise 1 Find the multiplicative inverse of 11 modulo 41.


Exercise 2 Prove that if gcd(a, n) > 1, then the multiplicative inverse a−1 (mod n) does not exist.


Exercise 3 Show that Euclid’s algorithm is correct by arguing that d is a common divisor of a and b if and only if d is a common divisor of b and (a mod b).


















Chinese Remainder Theorem


When working modulo a composite modulus n, the Chinese Remainder Theorem (CRT) can both speed computation modulo n and facilitate reasoning about the properties of arithmetic modulo n.


Theorem 1 (Chinese Remainder Theorem (CRT)) Let n = n1 n2 • • • nk be the product of k integers ni that are pair­
wise relatively prime. The mapping

f (a) =a(1 , . . . , ak ) =a(mod n1 , . . . , a mod nk )

is an isomorphism from Zn to Zn1 × • • • × Znk : if f (a) =a(1 , . . . , ak ) and f (b) =b (1 , . . . , bk ), then

f ((a ± b) mod n) = ((a1 ± b1 ) mod n1 , . . . , (ak ± bk ) mod nk )
f ((ab) mod n) = ((a1 b1 ) mod n1 , . . . , (ak bk ) mod nk )
f (a−1 mod n) = a(−1 mod n1 , . . . , a−1 mod nk ) if a−1 (mod n) exists

1
f −1 ((a1 , . . . , ak )) = a =


� k
ai ci (mod n) where mi = n/ni and ci = mi (m−1 mod ni ) .
i i



When n = pq is the product of two primes, working modulo n is equivalent to working independently on each component of its CRT (i.e. (mod p, mod q)) representation. It can be worthwhile to convert an input to its CRT representation, compute in that representation, and then convert back.


Example: For n = 35 = 5•


7put (a mod 35) in row a1 = (a mod 5) and column a2 = (a mod 7):


0 1 2 3 4 5 6


f (8) = (3, 1)

0 0 15 30 10 25 5 20
1 21 1 16 31 11 26 6

f (−8) =f (27)
f (12)

= (−3, −1) = , (26)
= (2, 5)

2 7 22 2 17 32 12 27
3 28 8 23 3 18 33 13
4 14 29 9 24 4 19 34

f (12−1 ) = (2−1 , 5−1 ) = , (33) =f (3)
f (8 + 12)f =(20) = (3 +, 1 2 + 5) , =6) (0
f (8 • 12) =f (96) =f (26) = (3 • 2, 1 • 5) = , (15)


Here m1 = 7, m2 = 5, c1 = 7 • (7−1 mod 5) = 7•


3 =, c212 = 5 • (5−1 mod 7) = 5•


3 =, 15so


f −1 ((a1 , a2 )) = 21a1 + 15a2 (mod 35).


(Note: f (21) = , (10), f (15) = , (01).) Thus, f −1 ((1, 5)) = 21 +•


5 15 = 96mod =35). 26 (


Speeding up Modular Exponentation. A significant application is speeding up exponentiation modulo n = pq when p
and q are known. To compute y = xd mod n, where f (x) =x(1 , x2 ):


f (y) = f (xd ) =xd( d


d mod (p−1) mod p, xd mod (q−1) mod q) .


Note xp−1

1 mod p, x2 mod q) =x(1 2



1 = 1 mod p for x1 = 0 by Fermat’s Little Theorem. Then convert back from (y mod p, y mod q) to y mod n. Since exponentiation takes time cubic in the input size, two half­size exponentiations are about four times faster than one full­size exponentiation (including conversion).


Exercise 1 Prove that x is a square mod n = pq if and only if it is a square mod p and mod q.