4 Number Theory

Dr Kulothungan

Learning Objectives

Ø  To understand the basic exponential and logarithmic functions

Ø   To understand the basic outline to

o   prime numbers

o   Primality Testing

o   Primitive Roots & Discrete Logarithms

o   Euclidean and Extended Euclidean Algorithms.

5.1 Introduction

Number theory is a branch of pure mathematics devoted primarily to the study of integers. It is sometimes called “The Queen of Mathematics” because of its foundational place in the discipline. The encryption algorithms depends heavily on modular arithmetic. We need to develop various machinery (notations and techniques) for manipulating numbers before can describe algorithms in a natural fashion.First we start with divisors.

5.2 Set of Integers

The set of integers, denoted by Z, contains all integral numbers (with no fraction) from negative infinity to positive infinity. The integers are made up of positive numbers, negative numbers and zero. The positive numbers are like the naturals, but with a “plus” before:+1, +2, +3 ….. Nevertheless, the “plus” of the positive numbers does not need to be be written. On the other hand, the negative numbers are like the naturals but with a “minus” before:-1,-2,-3…. The number zero is special, because it is the only one that has neither a plus nor a minus, showing that it is neither positive nor negative. For example, the following numbers are integers:

Z = {…..,-3,-2,-1,0,1,2,3,…..}

5.3 Binary Operations

In cryptography, we are interested in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output. A binary operation on A is a rule that assigns to every pair of elements of A a unique element of A.

5.4 Integer Division

Ø  In integer arithmetic, if we divide a by n, we can get q and r . The relationship between these four integers can be shown as

a = q × n + r

Ø  Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division algorithm.

5.4.1 Integer Division Properties

Ø  Property 1: if a\1, then a=+/- 1.

Ø   Property 2: if a\b and b\a, then a=+/-b.

Ø   Property 3: if a\b and b\c, then a\c.

Ø   Property 4: if a\b and a\c, then a\(m*b+n*c), where m and n are arbitrary integers.

    5.5 Divisors

5.5.1     Definition

Let a, b and c be integers such that

a = b ·c

Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol “|” denotes “divides” so the situation is summarized by:

b | a    ^   c | a

5.5.2     Examples

Which of the following is true?

1.  77 | 7

2.  7 | 77

3.  24 | 24

4.  0 | 24

5.  24 | 0

Answer:

1.      77 | 7: false bigger number can’t divide smaller positive number

2.      7 | 77: true because 77 = 7 · 11

3.      24 | 24: true because 24 = 24 · 1

4.      0 | 24: false, only 0 is divisible by 0

5.      24 | 0: true, 0 is divisible by every number (0 = 24 · 0)

5.5.3 Facts

Fact 1: The integer 1 has only one divisor, itself.

Fact 2: Any positive integer has at least two divisors.1 and itself(but it can have more)

5.6 GCD

The greatest common divisor of two positive integers is the largest integer that can divide both integers.     When gcd (a, b) = 1, we say that a and b are relatively prime.

5.6.1 Relatively Prime Numbers & GCD

•  Two numbers a,b are relatively prime (co prime) if they have no common divisors apart from 1

eg. 8 and 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1, 3, 5,15 and 1 is the only common factor

•   Conversely can determine the greatest common divisor by comparing their prime factorizations and using least powers

eg. 300 = 2^1×3^1×5^2 ; 18

=   2^1×3^2 hence GCD(18,300)

=   2^1×3^1×5^0 = 6

5.6.2 GCD Example

Find the greatest common divisor of 140 and 12.

5.6.3 GCD using Extended Euclidean Algorithm

Given two integers a and b, we often need to find other two integers, s and t, such that

Example

5.7 PRIME NUMBERS

Prime numbers only have divisors of 1 and self – they cannot be written as a product of other numbers – note: 1 is Prime, but is generally not of interest

•  Eg. 2,3,5,7 are prime, 4, 6, 8,9,10 are not

•   Prime numbers are central to number theory

•  List of prime number less than 200 is: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163

167 173 179 181 191 193 197 199

5.7.1 PRIME FACTORIZATION

•   Let us factorize the any number n: n = a x b x c

•   Factoring a number is relatively hard compared to multiplying the factors together to generate the number

•  The prime factorisation of a number n is when its written as a product of primes – eg. 91 = 7 x 13; 3600 = 2^4 x 3^2 x 5^2

5.7.2 PRIMITIVE ROOTS

If n is a positive integer, the integers between 1 and n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group with multiplication modulo n as the operation; it is denoted by Zn× and is called the group of units modulo n or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this group is cyclic if and only if n is equal to 2, 4, pk, or 2pk where pk is a power of an odd prime number.[2][3][4] A generator of this cyclic group is called a primitive root modulo n,[5] or a primitive element of Zn×.The order of (i.e., the number of elements in) Zn× is given by Euler’s totient function φ(n). (sequence A000010 in the OEIS) Euler’s theorem says that aφ(n) ≡ 1 (mod n) for every acoprime to n; the lowest power of a which is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n. For example, if n = 14 then the elements of Zn× are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. Here is a table of their powers modulo 14:

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.

5.7.3 DISCRETE LOGARITHMS

In general, let G be any group, with its group operation denoted by multiplication. Let b and g be any elements of G. Then any integer k that solves bk = g is termed a discrete logarithm (or simply logarithm, in this context) of g to the base b. We write k = logb g. Depending on b and g, it is possible that no discrete logarithm exists, or that more than one discrete logarithm exists. Let H be the subgroup of G generated by b. Then H is a cyclic group, and integral logb g exists for all g in H. If H is infinite, then logb g is also unique, and the discrete logarithm amounts to a group isomorphism.

logb : H ->  Z

On the other hand, if H is finite of size n, then logb g is unique only up to congruence modulo n, and the discrete logarithm amounts to a group isomorphism

logb : H  -> Z_n

where Z_n denotes the ring of integers modulo n. The familiar base change formula for ordinary logarithms remains valid: If c is another generator of H, then

logc(g)=logc(b).logb(g)

Summary

Ø Outlined the concept of number theory

Ø Discussed the integer division

Ø Explained the about the divisibility properties

Ø Introduction to prime numbers and relative prime number

Ø Explored the various examples of GCD.