Number Theory

Introduction

The overlying and high level theme of numbers is the division of the world into the same and the different. The first classification of number theory is even and odd. The second classification is prime numbers. Throughout the history of mathematics, ever since the beginning of abstract strokes and slashes on rock walls, various discoveries and inventions were made for representing numbers such as hand gestures, written symbols, positional notation, various bases, the zero and infinity. Including Prime Numbers, Fermat’s Theorem, CRT, and Euclid’s Algorithm, the following are some parts of Number Theory.

Relative Divisibility

Perfect Number

A perfect number is an integer such that the sum of its own divisors is twice the number. For instance, 6 is a perfect number because when its divisors are added together we have 1 + 2 + 3 + 6 = 12.

Deficient Number

If the sum of a number's divisible parts, except itself, is less than the whole number then the number is called deficient. For instance, 10 is deficient because the sum of all its divisors is 1 + 2 + 5 = 8.

Abundant Number

If the sum of a number's divisible parts, except itself, is greater than that whole number then the number is called abundant. For instance, 12 is less than the sum of its own parts 1 + 2 + 3 + 4 + 6 = 16.

Amicable Number

When the sum of one number's divisors is equal to the sum of another number's divisors, the two numbers are said to be amicable. For instance, 220 and 284 are amicable.

Modular Arithmetic

Modular arithmetic is remainder arithmetic. So for instance, 7 mod 5 = 2 because 5 goes into 7 once with a remainder of 2. Congruent modulo is an interesting concept and important to cryptography. a ≡ b mod(n) says that a and b are congruent modulo n if a mod(n) = b mod(n). Furthermore, additional modulo arithmetic properties are:

Reducibility

1. (a + b) mod(n) = [(a mod(n)) + (b mod(n))] mod(n)
2. (a - b) mod(n) = [(a mod(n)) - (b mod(n))] mod(n)
3. (a * b) mod(n) = [(a mod(n)) * (b mod(n))] mod(n)

Distributivity

1. a * (b + c) mod(n) = [(a * b) + (a * c)] mod(n)

Identities

1. a + 0 mod(n) = a + 0 mod(n) = a
2. a * 1 mod(n) = 1 * a mod(n)

Inverses

1. a + (-a) mod n = 0
2. a * a^-1 mod(n) = 1 if a not equal 0

Additive Inverse

The additive inverse modulo n to an integer x is y such that x + y ≡ 0 mod n.

Multiplicative Inverse

The multiplicative inverse modulo n to an integer x is y such that x * y ≡ 1 mod n. You can find the multiplicative inverse using Euclid’s Extended Algorithm.

Euler's Theorem

First let's introduce the Euler's Totient Function:

Φ(p) = p - 1 where Φ(p) is the number of positive integers less than n and relatively prime to n and p is prime.

So now the Euler's theorem is for every a and n that are relatively prime:

a^Φ(p) ≡ 1 mod n

Discrete Logarithms

Discrete Logarithms are used in public key cryptosystems such as Diffie-Hellman. A discrete logarithm is an index or rather can be thought of as an exponent k of x for a base y mod z, where z is prime. As in:

x = y^k mod z where 0 ≤ k < z

y has to first be a primitive root of prime z such that all of the values of y raised to some positive integer exponent ranging from 1 to z - 1 mod z is distinct. For instance, 7 is a primitive root of modulo 13 because the following holds:

7¹ mod 13 = 7
7² mod 13 = 10
7³ mod 13 = 5
7⁴ mod 13 = 9
7⁵ mod 13 = 11
7⁶ mod 13 = 12
7⁷ mod 13 = 6
7⁸ mod 13 = 3
7⁹ mod 13 = 8
7¹⁰ mod 13 = 4
7¹¹ mod 13 = 2
7¹² mod 13 = 1

Where as:

3¹ mod 13 = 3
3² mod 13 = 9
3³ mod 13 = 1
3⁴ mod 13 = 3 <-- repeating so 3 isn't a primitive root of modulo 13.

So, given y, k and z for the formula x = y^k mod z, x can easily be attainable. However, given x, y and z it is computainally unfeasible to come up with k which is the discrete logarithm. The whole idea of a discrete logarithm is that even though it is fairly easy to compute exponentials mod a prime it is extremely hard to compute a discrete logarithm.

Links

http://www.swox.com/gmp/
http://www.cacr.math.uwaterloo.ca/hac/
http://www.claymath.org/prizeproblems/p_vs_np.pdf
http://www.utm.edu/research/primes/ftp/all.txt
http://documents.wolfram.com/v4/AddOns/NumT_NumberTheoryFunctions-.html
http://www.utm.edu/research/primes/prove/
http://directory.google.com/Top/Science/Math/Applications/Communication_Theory/Cryptographyhttp://directory.google.com/Top/Science/Math/Number_Theory/Computational/
http://sigact.acm.org/