 A prime number is an integer that can only be divided without remainder by positive and negative values of itself and 1. Prime numbers play a critical role both in number theory and in cryptography.
 Discrete logarithms are fundamental to a number of publickey algorithms. Discrete logarithms are analogous to ordinary logarithms, but operate over modular arithmetic.
 1 is not considered as prime number.
Prime Numbers

Fundamental Theorem of Arithmetic:
 Any integer a > 1 can be factorized in a unique way as: .
 Where p1 < p_{2} < … < p_{t} are prime numbers and where each is a positive integer.
 The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation: The integer 12 is represented by {a_{2} = 2, a_{3} = 1}.

Multiplication of two numbers is equivalent to adding the corresponding exponents. Given and . Define. We know that the integer k can be expressed as the product of powers of primes: . It follows that for all .
 Example:

Any integer of the form p^{n} can be divided only by an integer that is of a lesser or equal power of the same prime number p^{j} with j
n. Thus, we can say the following: Given and . If ab then for all p.
Fermat’s Theorem

Fermat’s theorem states the following:
 If p is prime and a is a positive integer not divisible by p, then:
 If p is prime and a is a positive integer, then: .

Euler’s Totient Function:
 Euler’s totient function written as , defined as the number of positive integers less than n and relatively prime to n. By convention, .
 It should be clear that for a prime number p, .

Now suppose that we have two prime numbers p and q, with . Then we can show that for .
 .

Euler’s Theorem:
 Euler’s theorem states that for every a and n that are relatively prime:
Discrete Logarithms
 Discrete logarithms are fundamental to a number of publickey algorithms, including DiffieHellman key exchange and the digital signature algorithm (DSA).
 More generally, we can say that the highest possible exponent to which a number can belong (mod n) is (n). If a number is of this order, it is referred to as a primitive root of n. The importance of this notion is that if a is a primitive root of n, then its powers are distinct (mod n) and are all relatively prime to n. In particular, for a prime number p, if a is a primitive root of p, then .

for any integer b and a primitive root a of prime number p, we can find a unique exponent i such that
1
 This exponent i is referred to as the discrete logarithm of the number b for the base a (mod p). We denote this value as dlog_{a.p}(b).

Properties of Discrete Logarithms:
 dlog_{a.p}(1) = 0 > a^{0}mod n = 1
 dlog_{a.p}(a) = 1 > a^{1} mod n = a
 dlog_{a.p}(XY) = dlog_{a.p}(X) + dlog_{a.p}(Y)
 dlog_{a.p}(X^{Y}) = Y dlog_{a.p}(X).
[…] This post was mentioned on Twitter by Abdelrahman AlOgail. Abdelrahman AlOgail said: has a new blog post "Slight Introduction to Number Theory" http://lnkd.in/PkRPZP […]
Nice Post 😉
Thanks dude!
nice Abdelrahman…Go on 🙂
You too also 🙂