mod 11 tables

Layman's Number Theory And Elgamal

Blog tags: 

Quick simple (and probably not entirely correct) definitions:

  • Prime - a prime number is a number which cannot be divided by any other numbers except itself or 1
  • Modulo - in computation, it means that it returns the remainder of a number when it is divided by another
  • Natural number - any negative or positive whole number
  • Real number - in layman's terms, when you don't have a whole number
  • Set - a group of numbers which could be generated by a generator for example
  • Generator - every number is a generator; generates a group or set of integers

Main concepts

  • Cannot divide numbers (otherwise a real number could result)
  • Instead of dividing, a number can be inverted and multiplied
  • Every number has an inverse
  • Groups - are a set of integers, a set of mathematical operations and some rules which these numbers abide by
  • A safe prime is a number where p is a prime and is the result of q (another prime) times 2 + 1 (p = 2q + 1)
  • Order - Order of an element g (generator) is the smallest t such that g to the power of t = 1 mod p. In other words the values until 1 for that generator.

If we want to get the Order of all g's mod p (where p = 11), it will be one of { 1, 2, 5, 10 }

p - 1 = 10 (if p is 11)
10 = 1 *10
10 = 2 * 5
10 = 10 * 1
10 = 5 * 2

Generate the below two tables for mod p using these programs (where p is a prime, is 11 and is also Safe).

./mult 11
      1   2   3   4   5   6   7   8   9  10
  1   1   2   3   4   5   6   7   8   9  10
  2   2   4   6   8  10   1   3   5   7   9
  3   3   6   9   1   4   7  10   2   5   8
  4   4   8   1   5   9   2   6  10   3   7
  5   5  10   4   9   3   8   2   7   1   6
  6   6   1   7   2   8   3   9   4  10   5
  7   7   3  10   6   2   9   5   1   8   4
  8   8   5   2  10   7   4   1   9   6   3
  9   9   7   5   3   1  10   8   6   4   2
 10  10   9   8   7   6   5   4   3   2   1

./exp 11
      0   1   2   3   4   5   6   7   8   9  10
  1   1   1   1   1   1   1   1   1   1   1   1
  2   1   2   4   8   5  10   9   7   3   6   1
  3   1   3   9   5   4   1   3   9   5   4   1
  4   1   4   5   9   3   1   4   5   9   3   1
  5   1   5   3   4   9   1   5   3   4   9   1
  6   1   6   3   7   9  10   5   8   4   2   1
  7   1   7   5   2   3  10   4   6   9   8   1
  8   1   8   9   6   4  10   3   2   5   7   1
  9   1   9   4   3   5   1   9   4   3   5   1
 10   1  10   1  10   1  10   1  10   1  10   1

Okay, every number is a generator which generates a group of integers. Generation means taking a number (g) and raising it to a power.

Subscribe to RSS - mod 11 tables