Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Search

Monday, 13 August 2018

Logarithms and Discrete Logarithm in Block chain

  • 23 = 2 ⤫ 2 ⤫ 2 = 8
  • 2 is called the base
  • 3 is called the exponent and determines the number of times the base should be multiplied
  • 8 is called the product
  • Suppose exponent ⤫ is unknown?  2x = 8
  • If you are only interested in the exponent, the mathematical notation: x = log2 (8)
  • Exponential x = 23 and logarithms x = log2 (8) are each other opposites.
  • How to calculate x = log4 (65536) on your calculator?
  • Enter on your calculator log(65536) / log(4)
  • If there is no base, the value 10 is assumed
Discrete Logarithm
  • The goal of exponential is to calculate the product: x = 23
  • The goal of logarithms is to calculate the exponent: x = log2 (8)   (8 = 2x)
  • In discrete logarithm, you need to apply a modulo operation in the latter: 
  • x = log2 8 (mod 13)
  • Other way of notation: x = dlog2,13 (8)
  • where: x = exponent, 2 = base, 13 = modulus, 8 = remainder
Example :-
  • 2x (mod 7) = 4
  • x = 2 or 5        x = {1,....,6}
  • 4 (mod 7) = 4    and      32 mod 7 = 4
There are two solutions. In the world of cryptography we are only interested in discrete logarithm, where each exponent has a distinct remainder.

If seems that if the modulus (p) is a prime number there are certain base value (b) which generate distinct remainder for different exponents (x = 1, .... p-1). A prime number is a number that is divisible only by itself and l.For examples: 2,3,5,7,11,....

Lets calculate bx (mod 7) = remainder   x = {1,...,6}   modulus p = 7

The base value 3 and 5 are called the primitive roots of 7 or generators, often indicated by symbol ɑ. It is called generator because applying the multiplication operation on one single element (ɑx), generates all elements in the discrete group {1,....p-1}

The word discrete in discrete logarithm refer to the aspect that we are working in a discrete group )1,...p-1} and not any real numbers (meaning fractions 2.58).

Example :-
𝛂 (generator) = 2 and p (modulus) = 11  discrete group {1,...,p-1}
This is called a cyclic group of generator 𝛼. After a certain number of exponentiation and modulus operations, we have loop.

If the remainder has value 1, the cycle starts all over again in the same order.

In the previous example (p = 11) the cyclic group is referred to with notation:𝑍*p

For example: 𝑍*11
  • the * means no zero,
  • the discrete group is {1,...,p-1} = {1,...,10}
  • the number of elements in the discrete group is p-1 = 10 
Cyclic groups are the basis of discrete logarithm crypto systems.

No comments:

Post a Comment