Primitive roots:
A number a from a modulo multiplicative group over p is said to be the primitive
root of p,if it generates all number of the group when modulo multiplication is
performed on power of the number starting from 1 to p-1.
There might be several primitive roots of a prime number.
In general,a number of form 2i has very good chance of being primitive root of
the number. If a number is primitive root, its inverse will also be primitive root.
Check whether 2 is primitive root of 5 or not. Modulo multiplicative group of 5 is {1,2,3,4}.
2 will be primitive root,if when power of 2 is increased from 1 to 4.it generates all numbers of set
i.e.{1,2,3,4}.
Let us start 2(1)mod5=2,2(2)mod5=4,2(3)mod5=3,2(4)mod5=1,since it is generating all numbers of multiplicative group.it is primitive root.What will be inverse of 2 over 5.it will be 3.it will also be primitive root. check!
Check whether 2 is a primitive root of 7 or not.Modulo multiplicative group of 7 is {1,2,3,4,5,6}.
2 will be primitive root if when the power of 2 is increased from 1 to 6.it generates all numbers of set
i.e.{1,2,3,4,5,6}.
Let us start 21mod7=2,22mod7=4,23mod7=1 after generating 1 the same cycle will repeat. since it is not generating all numbers of multiplicative group.it is not a primitive root of 7.
Check 3 : 3(1)mod7=3,3(2)mod7=2,3(3)mod7=6,3(4)mod7=4,3(5)mod7=5,3(6)mod7=1,it is primitive root.
Discrete logarithm:
Alike logs,a discrete logarithm can be defined in the modulo multiplicative group.In mathematics if
(a)x =y then x can be written as x=loga(y).
Similar to that, if (a)x mod p =y.Then ind (a,p)y=x, this is called discrete log problem.
Write discrete log for 2 on modulo multiplicative group 5. ind(2,5)1=4,ind(2,5)2=1,ind(2,5)
4=2,ind(2,5 )8=3 if the prime number is big, the problem of discrete log becomes very
complex. It has been used in designing many important algorithms.
RSA algorithm: RSA is a very popular public key-based algorithm,it can be used both for encryption and authentication.
Let us see how. If let us suppose there is one sender A and its public key is a and the private key is d and one receiver who is also having two keys public key is a and the private key is e.
Calculating multiplicative inverse using the extended Euclid algorithm. This algorithm is very useful in calculating the multiplicative inverse of a number on very big prime numbers.
Let us suppose if we want to calculate the inverse of b over m.
Steps of algorithms:
1.calculate the value of two vectors A and B (A1,A2,A3)=(1,0,m) and (B1,B2,B3)=(0,1,b)
2. if (B3==0) return A3=gcd(m,b);no inverse Extended Euclid:
3.if (B3==1),return B2 is multiplicative inverse.
4.Q=⌊A3/B3⌋ create a temporary vector T.
5.(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3) Update A and B vector.
6.(A1,A2,A3)=(B1,B2,B3)
7.(B1,B2,B3)=(T1,T2,T3)
Goto 2 :
Example:
Calculate the inverse of 17 over 33. Calculate b and m: b=17 and m=33.
Write A and B vectors
(A1,A2,A3)=(1,0,33) and (B1,B2,B3)=(0,1,17) since B3 is neither 0 nor 1
Calculate Q=⌊33/17⌋=1 calculate temporary vector
(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)=(1,-1,16)
Updated vector A and B will be (A1,A2,A3)=(0,1,17) and (B1,B2,B3)=(1,-1,16)
Since B3 is still neither 0 nor 1,calculate Q=⌊17/16⌋=1 New Temporary Vector
RSA algorithm:
(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)=(0-1,1+1,17-16)=(-1,2,1)
Updated A and B vectors (A1,A2,A3)= (1,-1,16) and (B1,B2,B3)=(-1,2,1)
Since B3 is now 1, inverse exists and its value is 2.Sometimes value of B2 may be negative, make it positive by adding Prime number.
A number a from a modulo multiplicative group over p is said to be the primitive
root of p,if it generates all number of the group when modulo multiplication is
performed on power of the number starting from 1 to p-1.
There might be several primitive roots of a prime number.
In general,a number of form 2i has very good chance of being primitive root of
the number. If a number is primitive root, its inverse will also be primitive root.
Check whether 2 is primitive root of 5 or not. Modulo multiplicative group of 5 is {1,2,3,4}.
2 will be primitive root,if when power of 2 is increased from 1 to 4.it generates all numbers of set
i.e.{1,2,3,4}.
Let us start 2(1)mod5=2,2(2)mod5=4,2(3)mod5=3,2(4)mod5=1,since it is generating all numbers of multiplicative group.it is primitive root.What will be inverse of 2 over 5.it will be 3.it will also be primitive root. check!
Check whether 2 is a primitive root of 7 or not.Modulo multiplicative group of 7 is {1,2,3,4,5,6}.
2 will be primitive root if when the power of 2 is increased from 1 to 6.it generates all numbers of set
i.e.{1,2,3,4,5,6}.
Let us start 21mod7=2,22mod7=4,23mod7=1 after generating 1 the same cycle will repeat. since it is not generating all numbers of multiplicative group.it is not a primitive root of 7.
Check 3 : 3(1)mod7=3,3(2)mod7=2,3(3)mod7=6,3(4)mod7=4,3(5)mod7=5,3(6)mod7=1,it is primitive root.
Discrete logarithm:
Alike logs,a discrete logarithm can be defined in the modulo multiplicative group.In mathematics if
(a)x =y then x can be written as x=loga(y).
Similar to that, if (a)x mod p =y.Then ind (a,p)y=x, this is called discrete log problem.
Write discrete log for 2 on modulo multiplicative group 5. ind(2,5)1=4,ind(2,5)2=1,ind(2,5)
4=2,ind(2,5 )8=3 if the prime number is big, the problem of discrete log becomes very
complex. It has been used in designing many important algorithms.
RSA algorithm: RSA is a very popular public key-based algorithm,it can be used both for encryption and authentication.
Let us see how. If let us suppose there is one sender A and its public key is a and the private key is d and one receiver who is also having two keys public key is a and the private key is e.
Calculating multiplicative inverse using the extended Euclid algorithm. This algorithm is very useful in calculating the multiplicative inverse of a number on very big prime numbers.
Let us suppose if we want to calculate the inverse of b over m.
Steps of algorithms:
1.calculate the value of two vectors A and B (A1,A2,A3)=(1,0,m) and (B1,B2,B3)=(0,1,b)
2. if (B3==0) return A3=gcd(m,b);no inverse Extended Euclid:
3.if (B3==1),return B2 is multiplicative inverse.
4.Q=⌊A3/B3⌋ create a temporary vector T.
5.(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3) Update A and B vector.
6.(A1,A2,A3)=(B1,B2,B3)
7.(B1,B2,B3)=(T1,T2,T3)
Goto 2 :
Example:
Calculate the inverse of 17 over 33. Calculate b and m: b=17 and m=33.
Write A and B vectors
(A1,A2,A3)=(1,0,33) and (B1,B2,B3)=(0,1,17) since B3 is neither 0 nor 1
Calculate Q=⌊33/17⌋=1 calculate temporary vector
(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)=(1,-1,16)
Updated vector A and B will be (A1,A2,A3)=(0,1,17) and (B1,B2,B3)=(1,-1,16)
Since B3 is still neither 0 nor 1,calculate Q=⌊17/16⌋=1 New Temporary Vector
RSA algorithm:
(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)=(0-1,1+1,17-16)=(-1,2,1)
Updated A and B vectors (A1,A2,A3)= (1,-1,16) and (B1,B2,B3)=(-1,2,1)
Since B3 is now 1, inverse exists and its value is 2.Sometimes value of B2 may be negative, make it positive by adding Prime number.
