Slight Introduction to Number Theory

  • 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 public-key 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 < p2 < … < pt 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 {a2 = 2, a3 = 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 pn can be divided only by an integer that is of a lesser or equal power of the same prime number pj with j
    n. Thus, we can say the following:
    • Given and . If a|b 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 public-key algorithms, including Diffie-Hellman 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 dloga.p(b).
  • Properties of Discrete Logarithms:
    • dloga.p(1) = 0 -> a0mod n = 1
    • dloga.p(a) = 1 -> a1 mod n = a
    • dloga.p(XY) = dloga.p(X) + dloga.p(Y)
    • dloga.p(XY) = Y dloga.p(X).

5 thoughts on “Slight Introduction to Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s