Blockchain tutorial 9: Discrete logarithm Video Lecture | Blockchain Tutorial: A Fundamental Guide - Cryptocurrency

in this video I will explain what this
Creek logarithm is the goal of
Exponential's is to calculate the
product in this example we want to
calculate 2 to the power of 3 the goal
of logarithms is to calculate the
exponent in this example log base 2 of 8
or you can look at a different way it is
2 to the power of X and we are
interested in exponent X in discrete
logarithm you need to apply a module
operation in a letter which means
applying the model operation in this
equation as you can see over here
calculating log base 2 of 8 modulo 13
there's another way of notation is this
way where X is the exponent 2 is the
base 13 is the modulus and 8 is the
remainder if you find this confusing you
can also rewrite it this way take this
equation and add the modulo operation
example to the power of X modulo 7 is 4
the question is what is the x value well
the answer is X can be 2 or 5 if X is 1
0 6 6 is because of the model 7 minus 1
here's the proof 2 to the power of 2 is
4 4 mod 7 is of course 4 2 to the power
of 5 is 32 4 times 7 is 28 and 32 minus
28 is 4 there are two solutions and the
world of cryptography we are only
interested in discrete logarithms where
each exponent has a distinct remainder
it seems that if the modulus P is a
prime number there are certain base
values B which generate distinct remains
for different exponents by the way a
prime number is a number that is
divisible only by itself as 1 for
example 2 3 5 7 11 etc by choosing the
correct base value which generates
distinct remainders for different
exponents so here's an example how to
find such a base value let's calculate a
B to the power of X modulo 7 which
calculates the remainder whereby X will
be a values between 1 and 6 and the
models P is 7 here are different base
values 1 2 3 4 5 and 6 and here are
different powers P to the power 1 mod 7
B to the power of 2 mod 7 B to the power
3 mod 7 etc if you take the base value
of 1 these are the remainders as you can
see these are not distinct here there
are all 1 but this value 3 it generates
these things values here's 1 2 3 4 5 6
the same applies to 5 1 2 3 4 5 6 and
all the others
6 4 2 & 1 doesn't generate the things
remainders the discrete logarithm for
module 7 generates the sink remainders
when using base value of 3 or 5 and the
remainders are in the range 1 till 6 the
base value is 3 & 5 in the previous
example are called the primitive roots
of 7 or generators often indicated by
symbol alpha it is called generator
because applied the multiplication
operation on one single element alpha to
power X generates all elements in the
distinct group 1 till P minus 1 the word
discrete in discrete logarithm refer to
the aspect that we are working in a
discrete group 1 till P minus 1 and not
any real numbers meaning fractions 2.58
for example in this example in the
discrete group is values 1 2 3 4 etc and
not 1.5 or 1.8 or 2.5 calculating 3 to
the power 11 mod 17 is very easy but
doing the opposite calculating the
discrete logarithm 11 is 3 to the power
x mod 17 it's very difficult especially
if the modulus in this case 17 is at
least 300 digits long so if this value
is 300 digits long the discrete
logarithm is very hard to calculate
remember calculating a discrete
logarithm is hard to solve this equation
11 is 3 to the power of X mod 17 a
computer needs to try each exponent
0 1 2 3 etc until the equation matches
so here's an example alpha is 2 P is 11
and the discrete group is one till P
minus 1 here's the base to the modulus
11 and we increase the exponent is
sequentially 1 2 3 4 5 6 7 etc if you
calculate this equation you will get
these values and then you will notice
something so here is 2 3 4 5 6 7 8 9 10
the whole discrete group is covered and
if you calculate 2 to the power of 10
mod 11 the result is 1 and after this
value it repeats again as you can see
two two four four eight eight five five
nine seven seven three three six six
this is called a cyclic group of
generator alpha after a certain number
of exponentiation and modulus operations
we have a loop if the remainder has
value 1 the cycle starts all over again
in the same order in the previous
example that the modulus is 11 the
cyclic group is referred to with
notation CP star for example P was 11 so
you write down see 11 star star means no
zero the discrete group is one till P
minus 1 because P is 11 the discrete
group range will be between 1 and 10 the
number of elements in the discrete group
is P minus 1 is 10 cyclic groups are the
basis of discrete logarithm
cryptosystems