Introduction to number theory and abstract algebra

NUMBER THEORY AND ABSTRACT ALGEBRA plays an important role in the development of cryptosystems. Their basic knowledge acts as a key ingredient to the fields like cryptography and coding theory. Therefore, in this chapter, we will give a detailed overview of these basic concepts to build a strong foundation before diving deep into the field of searchable encryption and data management. This chapter is divided two parts, the first part covers the concepts related to number theory and the second part covers the basic concepts of abstract algebra.

Number Theory

Number theory is an interesting facet of mathematics that has attracted everyone from professional mathematicians to amateurs with its captivating concepts. Number theory concepts and theorems are natural and make sense even to a layman. However, proving them essentially requires both the basic knowledge and strong background we expect from a graduate in Computer Engineering. In this section, we will cover all the necessary concepts of number theory needed for the development of searchable encryption schemes along with their detailed proofs [1].

Divisibility

Divisibility is the fundamental concept of number theory. Consider a set of integers, Z = {...,-1,0,1,...}, we say b divides a, (b I a), if a = k b, where a,b,keZ [2]. Alternatively, one can also say that a is divisible by b, or a is a multiple of b, or b is a factor/divisor of a. The trivial cases include: i) Vb e Z, b 10, which denotes that every number divides 0, and ii) /a e Z, 11 a, which denotes that 1 divides every number.

Divisibility properties

The following are key properties of divisibility, which can be easily verified with the definition of divisibility:

  • • If a and bc then ac
  • • If a then ac, Ус e Z
  • • If a and cd then acd
  • If m: non-zero integer, then a|b iff mamb
  • • If ax and ay then acx + dy, where c,d g Z
  • • If ci: non-zero integer such thatd|d and a*0 then |d|<|a|
  • a and ba iff a = ±b
  • If a and ac then a±c

If a, b = k-a and bc, c = k1b = k1-(kd) = ka, where k = kik2eZ. Hence, by definition, ac. Similarly, other properties can also be proved using the basic algebraic properties and the definition of divisibility and are left as an exercise due to constraints on the book length.

An integer may not be completely divisible by another; in that case there will be a quotient (q) and a remainder (r). The division theorem states this fact as, for any integer a and a positive integer n, 3 a unique integer q and r: 0 and a = q ■ n + r. If a number is completely divisible then r = 0; otherwise, r G

Prime Numbers

For any integer, x > 1, there exists at least two positive divisors, x and 1, which are called trivial divisors for that number. A number is said to be prime if there exists no non-trivial divisor for it. If there exists at least one non-trivial divisor, then that number is called a composite number [2].

Theorem 1: There are infinite number of primes.

Proof: The proof is by contradiction. Let there are finite number of primes: (2,3,......,pk) and pk is the largest prime. Construct another number m: product of all primes +1.

Observation: None of the primes can divide m (leaves remainder 1). So, m is divisible by 1 and itself, hence m must be another prime number. In this way one can construct an infinite number of primes.

Fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every positive integer can be represented uniquely as the product of primes, i.e. n = p' ■ p2 ......p4,T, where

pi < pi <......< p,„ and all are distinct [3]. For example: 100 = 2 • 2 • 5 • 5 = 21 52;

81 = 34.

The proof is by contradiction. Let there are two different prime factorizations of n:

  • » = P?-Pf......Pm
  • n=qi'q$1......qd/

Therefore, p' p?......p%‘ = qd' qi1......qf. Now, we have to prove px =qx

and ex = dx provided pi = qt.

• If pi ^ qh then pi can’t divide any of the primes qu......qr-pi is relatively

prime to all qx,......qr, then pi cannot divide n (because u = qd' - qi1......qf).

But this is not true. Hence p, = qt

Assume di then di = et + b, h >0

From the above equation we can observe that RHS is divisible by qt while the LHS is not, which is impossible. Hence = dt

Prime number properties

Following are the key properties of the prime numbers:

  • • If a prime number p divides ab then either pa or p.
  • • If m|a and na, and if m and n has no divisor greater than 1 in common (i.e. m and n are relatively prime) then mna.
  • • If p“||и, then рр|и for some 0 < (3 < a.

Let n = рх' ■ p“2 - ...-p?', the total number of divisors of n is the product of the number of possibilities for each prime power, i.e. (oti + l)(a2 +1)......(ar +1)

 
Source
< Prev   CONTENTS   Source   Next >