Method 2:
We should always use this method first, if the factoring gives us more
than one prime.
let us define some of the general terms,
5^{x} congruent 3 mod 2017
so , a = 5, b =3, n = 2017
n-1 = 2016 = 2^{5} x 3^{2} x 7
so, we have 3 prime, p_{1} =2, p_{2} = 3, p_{3} =7
steps : now, we still deal with prime 3, in order to let us see
the constrast
p_{2} = 3, x congruent n_{0} mod 9 .............we
have to find n0
Let x = 9q + r .........we form this equation for
multiply 9, r is remainder
Deal with both sides
5^{x} = 3 mod 2017.........subsitute x = 9q + r
5^{9q + r} = 3 mod 2017.........raise both side power
to the rest of the prime factor
( 5^{9q + r} )^{2^5 x 7 } = 3 ^ {2^5 x 7 } mod
2017.........by doing this is to let us to cancel off all the
numbers with power of (n-1) to 1 , as theorem
a ^ {n - 1} mod n = 1, so we can cancel off
the q and to solve r
5 ^ {2016q + 224r} = 3 ^ {224} mod 2017
5 ^ { 224r} = 3 ^ {224} mod 2017
calculation:
5 ^ {5} = 1108 mod n
5 ^ {10} = 1328
5 ^ {20} = 726
5 ^ {40} = 639
5 ^ {80} = 887
5 ^ {160} = 139
5 ^ {320} = 1168
5 ^ {640} = 732
calculation:
3 ^ {7} = 170 mod n
3 ^ {14} = 662mod n
3 ^ {28} = 555 mod n
3 ^ {56} = 1441 mod n
3 ^ {112} = 988 mod n
3 ^ {224} = 1933 mod n
3 ^ {448} = 1005 mod n
3 ^ {896} = 1525 mod n
5 ^ { 224r} = 3 ^ {224} mod 2017
576 ^{ r } = 1933 mod n .............as you can see
here, r is the remainder form with multiply
of 9,
so the possible r value could be 0,1,2,3,4,5,6,7,8
Since right not giving us 1 mod n, we will cry if the
multiply is 81, the we have to test each of them
the worst is 81 times.
so, now subsitue r for possible number
when r = 2, 576 ^{ 2 } = 988
when r = 3, 576 ^{ 3 } = 294
when r = 4, 576 ^{ 4 } = 1933 ...........bingo, stop
the loop
conclude r =4, so our equation for prime 3
x congruent 4 mod 9
Friday, August 14, 2009
Pohlig-Hellman Part 1 - method 1 Options
i was struggling for one whole day to figure out the technique to use it.
Hence, I will write a few topic about this algorithmn.
1st of all, I have found there are 2 main methods to solve this kind of question.
So now, let us explore this 2 methods. We should always use method 2
first because it is fast, if it doesn't give us ans then only look for
method 1 to solve.
let us define some of the general terms,
5^{x} congruent 3 mod 2017
so , a = 5, b =3, n = 2017
n-1 = 2016 = 2^{5} x 3^{2} x 7
so, we have 3 prime, p_{1} =2, p_{2} = 3, p_{3} =7
Method 1:
Normally this is called baby steps, which as it named very tedious with a lot of steps to perform. This method for sure will let u find the answer but a lot of steps. We have to choose method wisely based on question.
We choose this method if the power of factoring prime (p) very large and method 2 does'nt help us to find the asnwer if the exponent is big.
When the fatoring only give us one prime also use this method.
step 1: Remeber formula to deal with right hand side:-
b ^ {(n-1)/p_{i}}........p is prime, raise the power of prime from 1 until the last constants.
Example above i take prime = 3 to solve
my p_{2} = 3,
FIRST, come out the equation first, raise the power of 3 less than the maximun.
this example, max exponent for 3 is 2, so we raise until 1.
And sure we will have the constants need to be solved.
let constants be c_{i}
x = c_{0}3^{0} + c_{1}3^{1}
.......see, we have constants needed to be solved,
if the power of prime 3 larger, the
longer the steps i need to deal in order to
find all my constants.
step 2: Start to solve 1st constant 0
c0 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/3} = 3 ^ {672}
calculation:
3 ^ {7} = 170 mod n
3 ^ {14} = 662mod n
3 ^ {28} = 555 mod n
3 ^ {56} = 1441 mod n
3 ^ {112} = 988 mod n
3 ^ {224} = 1933 mod n
3 ^ {448} = 1005 mod n
3 ^ {896} = 1525 mod n
3 ^ {672} = 294 mod n...............
oh no, if we see 1 mod n here ,
we are done, else we have to continue
to deal with left hand side.
Bec a^{0} = 1 mod n
step 3: Now we have to calclate left hand in order to solve constant 0
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it,
so left hand also need to power with the same
thing
(5 ^ {x}) ^ {672} ....................replace x
with equation we have formend in step 1,
x = c_
{0}3^{0} + c_{1}3^{1} = c0 + 3c1
(5 ^ {c0 + 3c1}) ^ {672} .............multiply 672
with each of the items, as u will find all the numbers
give us
(n-1)t except the current constant we want to solve.
As we
know whatever number power of (n-1)t mod n will give us 1.
Hence,
we can cancel it bec of 1. t is any integer number.
(5 ^ {672c0 + 2016c1})
5 ^ {672c0} x 5 ^{2016c1}
5 ^ {672c0} x 1
( 5 ^ {672} ) ^ {c0}
calculation:
5 ^ {5} = 1108 mod n
5 ^ {10} = 1328
5 ^ {20} = 726
5 ^ {40} = 639
5 ^ {80} = 887
5 ^ {160} = 139
5 ^ {320} = 1168
5 ^ {640} = 732
( 5 ^ {672} ) ^ {c0} = 294 ^ {c0}
NOW, put both sides to gether
294 ^ {c0} = 294 mod n, as very clear the constant
should be 1 to make both side tally.
NOTE: in baby steps
method, every time we solve the constants,
the
constants range sure less the the current prime
so, 0 <= c_{i} < 3..........current prime is 3
ans : c0 = 1
step 4: Continue to solve constant 1
c1 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/
9} ..........as u can see i raise the prime power ( bottom)
= 3 ^ {224}
= 1933 mod
n ..........since not 1 mod n, so proceed to deal left hand
step 5: Continue to solve constant 1 - left hand
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it, so left hand
also
need to power with the same thing
(5 ^ {x}) ^ {224} ....................replace x
with equation we have formend in step 1 & step 3
x = c_
{0}3^{0} + c_{1}3^{1} = 1 + 3c1
(5 ^ { 1 + 3c1}) ^ {224}
(5 ^ { 224 + 672c1})
5 ^ {224} x 5 ^{672c1}
576 x 294^ {c1}
now put both sides together
576 x 294^ {c1} = 1933 mod n .........we have to
subsitue all the possible constanst to find
the answer, c1 can be 0,1,2
when c1=1, 576 x 294 = 1933 mod n, hence c1=
1
step 6: Calculate the equation
now, subsitue all the constants into step 1 equation.
x = c_{0}3^{0} + c_{1}3^{1} = 1 + 3c1
x = 1 + 1 x 3 = 4
Hence, the equation for prime 3 is:-
x congruent 4 mod 9
Method 2: please look at another topic
Hence, I will write a few topic about this algorithmn.
1st of all, I have found there are 2 main methods to solve this kind of question.
So now, let us explore this 2 methods. We should always use method 2
first because it is fast, if it doesn't give us ans then only look for
method 1 to solve.
let us define some of the general terms,
5^{x} congruent 3 mod 2017
so , a = 5, b =3, n = 2017
n-1 = 2016 = 2^{5} x 3^{2} x 7
so, we have 3 prime, p_{1} =2, p_{2} = 3, p_{3} =7
Method 1:
Normally this is called baby steps, which as it named very tedious with a lot of steps to perform. This method for sure will let u find the answer but a lot of steps. We have to choose method wisely based on question.
We choose this method if the power of factoring prime (p) very large and method 2 does'nt help us to find the asnwer if the exponent is big.
When the fatoring only give us one prime also use this method.
step 1: Remeber formula to deal with right hand side:-
b ^ {(n-1)/p_{i}}........p is prime, raise the power of prime from 1 until the last constants.
Example above i take prime = 3 to solve
my p_{2} = 3,
FIRST, come out the equation first, raise the power of 3 less than the maximun.
this example, max exponent for 3 is 2, so we raise until 1.
And sure we will have the constants need to be solved.
let constants be c_{i}
x = c_{0}3^{0} + c_{1}3^{1}
.......see, we have constants needed to be solved,
if the power of prime 3 larger, the
longer the steps i need to deal in order to
find all my constants.
step 2: Start to solve 1st constant 0
c0 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/3} = 3 ^ {672}
calculation:
3 ^ {7} = 170 mod n
3 ^ {14} = 662mod n
3 ^ {28} = 555 mod n
3 ^ {56} = 1441 mod n
3 ^ {112} = 988 mod n
3 ^ {224} = 1933 mod n
3 ^ {448} = 1005 mod n
3 ^ {896} = 1525 mod n
3 ^ {672} = 294 mod n...............
oh no, if we see 1 mod n here ,
we are done, else we have to continue
to deal with left hand side.
Bec a^{0} = 1 mod n
step 3: Now we have to calclate left hand in order to solve constant 0
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it,
so left hand also need to power with the same
thing
(5 ^ {x}) ^ {672} ....................replace x
with equation we have formend in step 1,
x = c_
{0}3^{0} + c_{1}3^{1} = c0 + 3c1
(5 ^ {c0 + 3c1}) ^ {672} .............multiply 672
with each of the items, as u will find all the numbers
give us
(n-1)t except the current constant we want to solve.
As we
know whatever number power of (n-1)t mod n will give us 1.
Hence,
we can cancel it bec of 1. t is any integer number.
(5 ^ {672c0 + 2016c1})
5 ^ {672c0} x 5 ^{2016c1}
5 ^ {672c0} x 1
( 5 ^ {672} ) ^ {c0}
calculation:
5 ^ {5} = 1108 mod n
5 ^ {10} = 1328
5 ^ {20} = 726
5 ^ {40} = 639
5 ^ {80} = 887
5 ^ {160} = 139
5 ^ {320} = 1168
5 ^ {640} = 732
( 5 ^ {672} ) ^ {c0} = 294 ^ {c0}
NOW, put both sides to gether
294 ^ {c0} = 294 mod n, as very clear the constant
should be 1 to make both side tally.
NOTE: in baby steps
method, every time we solve the constants,
the
constants range sure less the the current prime
so, 0 <= c_{i} < 3..........current prime is 3
ans : c0 = 1
step 4: Continue to solve constant 1
c1 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/
9} ..........as u can see i raise the prime power ( bottom)
= 3 ^ {224}
= 1933 mod
n ..........since not 1 mod n, so proceed to deal left hand
step 5: Continue to solve constant 1 - left hand
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it, so left hand
also
need to power with the same thing
(5 ^ {x}) ^ {224} ....................replace x
with equation we have formend in step 1 & step 3
x = c_
{0}3^{0} + c_{1}3^{1} = 1 + 3c1
(5 ^ { 1 + 3c1}) ^ {224}
(5 ^ { 224 + 672c1})
5 ^ {224} x 5 ^{672c1}
576 x 294^ {c1}
now put both sides together
576 x 294^ {c1} = 1933 mod n .........we have to
subsitue all the possible constanst to find
the answer, c1 can be 0,1,2
when c1=1, 576 x 294 = 1933 mod n, hence c1=
1
step 6: Calculate the equation
now, subsitue all the constants into step 1 equation.
x = c_{0}3^{0} + c_{1}3^{1} = 1 + 3c1
x = 1 + 1 x 3 = 4
Hence, the equation for prime 3 is:-
x congruent 4 mod 9
Method 2: please look at another topic
RSA Cryptosystem
Every encryption will have K, so
RSA K ={ (n p q a e): ae congruent to 1 mod phi(n) },
just remember front and back are public key for encryption purpose,
the rest are private key.
so n , e are public key
encryption: e(x) = x^{e} mod n-->n , e are public key
decryption: d(y) = y^{a} mod n
where a is multiplicative invers of
e mod phi(n) --> e^{-1} mod phi (n)
since n = pq, ( p is prime, q is prime),
so phi(n) = phi(q) x phi(p)
q always bigger than p, q - p = 2d > 0
extra 2 formula : -
1) (q - p)/2 = d
2) (p + q)/2 = sqrt( n + d^{2}) ******* to be used for below step 2
[(p + q)/2]^{2} = n + d^{2}
a) How to factoring?
....as long as we can find the d to be sqrt to an integer
let n = 18923
step 1: take sqrt(18923) = 137.56
= Math.Ceiling rounds up (137.56 ) = 138
step 2: 138^{2} = 19044, 18923 + 121 = 19044
18923 + 121 = 138^{2}
formula above (2), n + d^{2}= [(p + q)/2]^{2}
........so sqrt(121) = 11 = d
step 3: now we can have 2 equation to solve the p and q
(1)........q - p = 2d , q - p = 2(11), q - p = 22
(2)........p +q = (2)138
(1) + (2) .........2q = (2)138 + 22,2q = 298,q=149
substiute q = 149 into (2).......p = (2)138 - 149 = 127
solved, n = pq, 18923 = 127 x 149
b) encryption
e(x) = x^{e} mod n, let e = 1261
encrypt x = 2, e(2) = 2^{1261} mod 18923
caculation:-
2^{10} = 1024 mod 18923 ..............all mod 18923
.......always take the previous to be square,
e.g. (2^{10} )^{2} = (1024 )^{2} mod 18923 ,2^{20} = ?
2^{20} = 1024^{2} mod 18923
= 1048576 mod 18923
= 7811
///////////// technique using calculator start /////////////////////
(....technique using calculator, **becareful,
step 1: 1024 --> 'x2' -> 'a b/c' -> 18923
....screen will appear 1024^2 ] 18923
step 2: '='....screen will appear 55.4127781
..........so we can see the number before decimal is 55, so
we minus 55
step3 : 'Ans' - 55....screen will appear 0.4127781
..........since we mod with 18923 ,
so times with 18923
step4 : 'Ans' ->'x' ->18923
....screen will appear 7811
.....p/s: if we see ans 7811.9999 then ans will be 7812,
if ans is 7811.00000888 then ans will be 7811
)end of technique
if hard to understand just use traditional way to deal with it
//////////// technique using calculator end ///////////////////
2^{40} = 7811^{2} mod 18923 = 3969
2^{80} = 3969^{2} mod 18923 = 9025
2^{160} = 9025^{2} mod 18923 = 6033
2^{320} = 6033^{2} mod 18923 = 8160
2^{640} = 8160^{2} mod 18923 = 14486
start to calculate 2^{1261} mod 18923
(^^ just like last time SPM we do decimal changed to binary)
step 1:..noted 1261 enough to be minus by 640 so we put 1 and take remainder
step 2:..noted 621 enough to be minus by 320 so we put 1 and take remainder
step 3:..noted 301 enough to be minus by 160 so we put 1 and take remainder
step 4:..noted 141 enough to be minus by 80 so we put 1 and take remainder
step 5:..noted 61 enough to be minus by 40 so we put 1 and take remainder
step 6:..noted 21 enough to be minus by 20 so we put 1 and take remainder
step 7:..noted 1 will be 2^{1}
................2^ {1} g
2^{10} = 1024
2^{20} = 7811 ..............1 ( 21- 20= 1) f
2^{40} = 3969 ..............1 ( 61- 40 = 21) e
2^{80} = 9025 ..............1 ( 141 - 80 = 61) d
2^{160} = 6033 ..............1 ( 301 - 160 = 141 ) c
2^{320} = 8160 ..............1 ( 621- 320= 301) b
2^{640} = 14486 ..............1 ( 1261 - 640 = 621) a
calculate from bottom to up:-
ans = a x b x c x d x e x f x g mod 18923
a x b mod 18923 = 14486 x 8160 mod 18923 =12702
a x b x c mod 18923 = 12702 x 6033 mod 18923 =11939
a x b x c x d mod 18923 = 11939 x 9025 mod 18923 =1913
a x b x c x d x e mod 18923 = 1913 x 3969 mod 18923 =4574
a x b x c x d x e x f mod 18923 = 4574 x 7811 mod 18923 = 890
a x b x c x d x e x f x g mod 18923 = 890 x 2 mod 18923 = 1780
......so ans, encrypt x = 2, e(2) = 2^{1261} mod 18923
encrypted of 2 is 1780
c)decryption
find the e^{-1} mod phi(n)
d(y) = y^{a} mod n
........becareful here RSA decryption is mod phi(n) NOT mod n
example:
n = 18923 , e = 1261, .........as we calculated in the beginning
so , we have ,n = pq, 18923 = 127 x 149
phi(n) = phi(p) x phi(q) ........please refer my Euler Function
phi(18923 ) = phi(127 ) x phi(149 )
= 126 x 148
= 18648............phi(n)
now, in order to decrypt we need to find multiplicative inverse of
exponent (e^{-1}) in which is 'a' in the formula..............pls
refer to my "Multiplicative Inverse"
find, e^{-1} mod phi(n) = 1261^{-1} mod 18648
= 5797..............a
d(y) = y^{a} mod n , if my friend send me 1780, so i have to
decrypt it.
d(1780) = 1780^{5797} mod 18923
start prepare calculation:-
1780^{1} ..............1
1780^{2} = 8259 mod 18923
1780^{4} = 12589 mod 18923 ..............1
1780^{8} = 2796 mod 18923
1780^{16} = 2417 mod 18923
1780^{32} = 13605 mod 18923 ..............1
1780^{64} = 10162 mod 18923
1780^{128} = 3433 mod 18923 ..............1
1780^{256} = 15383 mod 18923
1780^{512} = 4574 mod 18923 ..............1
1780^{1024} = 11561 mod 18923 ..............1
1780^{2048} = 3572 mod 18923
1780^{4096} = 5082 mod 18923 ..............1 ( 5797- 4096=1701)
5082 x 11561 =16010 x4574 =16653 x 3433 =3366 x13605 =770 x12589
=4954 x1780 = 2 mod 18923
...........congratulation, you are master ^^ haha, dont beat me.
ans is 2 ( plaintext)
RSA K ={ (n p q a e): ae congruent to 1 mod phi(n) },
just remember front and back are public key for encryption purpose,
the rest are private key.
so n , e are public key
encryption: e(x) = x^{e} mod n-->n , e are public key
decryption: d(y) = y^{a} mod n
where a is multiplicative invers of
e mod phi(n) --> e^{-1} mod phi (n)
since n = pq, ( p is prime, q is prime),
so phi(n) = phi(q) x phi(p)
q always bigger than p, q - p = 2d > 0
extra 2 formula : -
1) (q - p)/2 = d
2) (p + q)/2 = sqrt( n + d^{2}) ******* to be used for below step 2
[(p + q)/2]^{2} = n + d^{2}
a) How to factoring?
....as long as we can find the d to be sqrt to an integer
let n = 18923
step 1: take sqrt(18923) = 137.56
= Math.Ceiling rounds up (137.56 ) = 138
step 2: 138^{2} = 19044, 18923 + 121 = 19044
18923 + 121 = 138^{2}
formula above (2), n + d^{2}= [(p + q)/2]^{2}
........so sqrt(121) = 11 = d
step 3: now we can have 2 equation to solve the p and q
(1)........q - p = 2d , q - p = 2(11), q - p = 22
(2)........p +q = (2)138
(1) + (2) .........2q = (2)138 + 22,2q = 298,q=149
substiute q = 149 into (2).......p = (2)138 - 149 = 127
solved, n = pq, 18923 = 127 x 149
b) encryption
e(x) = x^{e} mod n, let e = 1261
encrypt x = 2, e(2) = 2^{1261} mod 18923
caculation:-
2^{10} = 1024 mod 18923 ..............all mod 18923
.......always take the previous to be square,
e.g. (2^{10} )^{2} = (1024 )^{2} mod 18923 ,2^{20} = ?
2^{20} = 1024^{2} mod 18923
= 1048576 mod 18923
= 7811
///////////// technique using calculator start /////////////////////
(....technique using calculator, **becareful,
step 1: 1024 --> 'x2' -> 'a b/c' -> 18923
....screen will appear 1024^2 ] 18923
step 2: '='....screen will appear 55.4127781
..........so we can see the number before decimal is 55, so
we minus 55
step3 : 'Ans' - 55....screen will appear 0.4127781
..........since we mod with 18923 ,
so times with 18923
step4 : 'Ans' ->'x' ->18923
....screen will appear 7811
.....p/s: if we see ans 7811.9999 then ans will be 7812,
if ans is 7811.00000888 then ans will be 7811
)end of technique
if hard to understand just use traditional way to deal with it
//////////// technique using calculator end ///////////////////
2^{40} = 7811^{2} mod 18923 = 3969
2^{80} = 3969^{2} mod 18923 = 9025
2^{160} = 9025^{2} mod 18923 = 6033
2^{320} = 6033^{2} mod 18923 = 8160
2^{640} = 8160^{2} mod 18923 = 14486
start to calculate 2^{1261} mod 18923
(^^ just like last time SPM we do decimal changed to binary)
step 1:..noted 1261 enough to be minus by 640 so we put 1 and take remainder
step 2:..noted 621 enough to be minus by 320 so we put 1 and take remainder
step 3:..noted 301 enough to be minus by 160 so we put 1 and take remainder
step 4:..noted 141 enough to be minus by 80 so we put 1 and take remainder
step 5:..noted 61 enough to be minus by 40 so we put 1 and take remainder
step 6:..noted 21 enough to be minus by 20 so we put 1 and take remainder
step 7:..noted 1 will be 2^{1}
................2^ {1} g
2^{10} = 1024
2^{20} = 7811 ..............1 ( 21- 20= 1) f
2^{40} = 3969 ..............1 ( 61- 40 = 21) e
2^{80} = 9025 ..............1 ( 141 - 80 = 61) d
2^{160} = 6033 ..............1 ( 301 - 160 = 141 ) c
2^{320} = 8160 ..............1 ( 621- 320= 301) b
2^{640} = 14486 ..............1 ( 1261 - 640 = 621) a
calculate from bottom to up:-
ans = a x b x c x d x e x f x g mod 18923
a x b mod 18923 = 14486 x 8160 mod 18923 =12702
a x b x c mod 18923 = 12702 x 6033 mod 18923 =11939
a x b x c x d mod 18923 = 11939 x 9025 mod 18923 =1913
a x b x c x d x e mod 18923 = 1913 x 3969 mod 18923 =4574
a x b x c x d x e x f mod 18923 = 4574 x 7811 mod 18923 = 890
a x b x c x d x e x f x g mod 18923 = 890 x 2 mod 18923 = 1780
......so ans, encrypt x = 2, e(2) = 2^{1261} mod 18923
encrypted of 2 is 1780
c)decryption
find the e^{-1} mod phi(n)
d(y) = y^{a} mod n
........becareful here RSA decryption is mod phi(n) NOT mod n
example:
n = 18923 , e = 1261, .........as we calculated in the beginning
so , we have ,n = pq, 18923 = 127 x 149
phi(n) = phi(p) x phi(q) ........please refer my Euler Function
phi(18923 ) = phi(127 ) x phi(149 )
= 126 x 148
= 18648............phi(n)
now, in order to decrypt we need to find multiplicative inverse of
exponent (e^{-1}) in which is 'a' in the formula..............pls
refer to my "Multiplicative Inverse"
find, e^{-1} mod phi(n) = 1261^{-1} mod 18648
= 5797..............a
d(y) = y^{a} mod n , if my friend send me 1780, so i have to
decrypt it.
d(1780) = 1780^{5797} mod 18923
start prepare calculation:-
1780^{1} ..............1
1780^{2} = 8259 mod 18923
1780^{4} = 12589 mod 18923 ..............1
1780^{8} = 2796 mod 18923
1780^{16} = 2417 mod 18923
1780^{32} = 13605 mod 18923 ..............1
1780^{64} = 10162 mod 18923
1780^{128} = 3433 mod 18923 ..............1
1780^{256} = 15383 mod 18923
1780^{512} = 4574 mod 18923 ..............1
1780^{1024} = 11561 mod 18923 ..............1
1780^{2048} = 3572 mod 18923
1780^{4096} = 5082 mod 18923 ..............1 ( 5797- 4096=1701)
5082 x 11561 =16010 x4574 =16653 x 3433 =3366 x13605 =770 x12589
=4954 x1780 = 2 mod 18923
...........congratulation, you are master ^^ haha, dont beat me.
ans is 2 ( plaintext)
Multiplicative Inverse
It can be done by using Euclidean Algorithm :
Example 1:
Find multiplicative inverse of 3 mod 26.
so let e = 3,n = 26, e^{-1} = ?
formula: gcd(e, n) , gcd(3, 26)
steps:always put bigger number at left, then only start to divide and
fill up numbers and remainder
26 = (3)
(1) 26 = 8(3) + 2
.......always take down bracket and remainder
3 = (2)
(2) 3 = 1(2) + 1
2 = 2(1) ......stop bec remainder is 0
Extended Euclidean Algorithm : to reverse it
(2)...... 3 = 1(2) + 1
........always let the equation to be 1 = ab - c , let 1 to be left
1 = 3 - 1(2)
........always replace the figure in bracket that smallest
with something, as u noted there will always is the remainder
in above calucation,
2 in (1).....26 = 8(3) + 2,
so 2 = 26 - 8(3)
1 = 3 - 1 [26 - 8(3)]
.......dont break the small bracket whenever we expand
1 = 3 - 1(26) + 8(3)
......find the common number in bracket and sum up
1 = 1(3) + 8(3) - 1(26)
1 = 9(3) - 1(26)
so, we can see 9(3), the multiplicative invers of 3 =9 mod 26,
3^{-1} = 9 mod 26
Example 2:
Find multiplicative inverse of 5 mod 26.
so let e = 5,n = 26, e^{-1} = ?
Euclidean Algorithm :
(1) 26 = 5(5) + 1
5 = 5(1)
Extended Euclidean Algorithm :
(1) 1 = 26 - 5(5)
so 5^{-1} congruent (-5) mod 26,
26 - 5 = 12
so 5^{-1} congruent 12 mod 26, ans is 12
Example 3:
Find multiplicative inverse of 1261 mod 18648.
so let e = 1261,n = 18648, e^{-1} = ?
Euclidean Algorithm :
(1) 18648 = 14(1261) + 994
(2) 1261 = 1(994) + 267
(3) 994 = 3(267) + 193
(4) 267 = 1(193) + 74
(5) 193 = 2(74) + 45
(6) 74 = 1(45) + 29
(7) 45 = 1(29) + 16
(8) 29 = 1(16) + 13
(9) 16 = 1(13) + 3
(10) 13 = 4(3) + 1
3 = 3(1)
Extended Euclidean Algorithm :
(10) 1 = 13 - 4(3)
(9) 1 = 13- 4[16-1(13)]
1 = 13- 4(16)+4(13)
1 = 5(13)- 4(16)
(8) 1 = 5[29-1(16)]- 4(16)
1 = 5(29)-5(16)- 4(16)
1 = 5(29)-9(16)
(7) 1 = 5(29)-9[45-1(29)]
1 = 5(29)-9(45)+9(29)
1 = 14(29)-9(45)
(6) 1 = 14(29)-9(45)
1 = 14[74-1(45)]-9(45)
1 = 14(74)-14(45)-9(45)
1 = 14(74)-23(45)
(5) 1 = 14(74)-23[193 - 2(74)]
1 = 14(74)-23(193) + 46(74)
1 = 60(74)-23(193)
(4) 1 = 60[267-1(193)]-23(193)
1 = 60(267)-60(193)-23(193)
1 = 60(267)-83(193)
(3) 1 = 60(267)-83[994-3(267)]
1 = 60(267)-83(994)+249(267)
1 = 309(267)-83(994)
(2) 1 = 309[1261 - 1(994)]-83(994)
1 = 309(1261) - 309(994)-83(994)
1 = 309(1261) - 392(994)
(1) 1 = 309(1261) - 392[18648 - 14(1261)]
1 = 309(1261) - 392(18648) + 5488(1261)
1 = 5795(1261) - 392(18648)
so 1261^{-1} congruent (5795) mod 18648, ans is 5795
Example 1:
Find multiplicative inverse of 3 mod 26.
so let e = 3,n = 26, e^{-1} = ?
formula: gcd(e, n) , gcd(3, 26)
steps:always put bigger number at left, then only start to divide and
fill up numbers and remainder
26 = (3)
(1) 26 = 8(3) + 2
.......always take down bracket and remainder
3 = (2)
(2) 3 = 1(2) + 1
2 = 2(1) ......stop bec remainder is 0
Extended Euclidean Algorithm : to reverse it
(2)...... 3 = 1(2) + 1
........always let the equation to be 1 = ab - c , let 1 to be left
1 = 3 - 1(2)
........always replace the figure in bracket that smallest
with something, as u noted there will always is the remainder
in above calucation,
2 in (1).....26 = 8(3) + 2,
so 2 = 26 - 8(3)
1 = 3 - 1 [26 - 8(3)]
.......dont break the small bracket whenever we expand
1 = 3 - 1(26) + 8(3)
......find the common number in bracket and sum up
1 = 1(3) + 8(3) - 1(26)
1 = 9(3) - 1(26)
so, we can see 9(3), the multiplicative invers of 3 =9 mod 26,
3^{-1} = 9 mod 26
Example 2:
Find multiplicative inverse of 5 mod 26.
so let e = 5,n = 26, e^{-1} = ?
Euclidean Algorithm :
(1) 26 = 5(5) + 1
5 = 5(1)
Extended Euclidean Algorithm :
(1) 1 = 26 - 5(5)
so 5^{-1} congruent (-5) mod 26,
26 - 5 = 12
so 5^{-1} congruent 12 mod 26, ans is 12
Example 3:
Find multiplicative inverse of 1261 mod 18648.
so let e = 1261,n = 18648, e^{-1} = ?
Euclidean Algorithm :
(1) 18648 = 14(1261) + 994
(2) 1261 = 1(994) + 267
(3) 994 = 3(267) + 193
(4) 267 = 1(193) + 74
(5) 193 = 2(74) + 45
(6) 74 = 1(45) + 29
(7) 45 = 1(29) + 16
(8) 29 = 1(16) + 13
(9) 16 = 1(13) + 3
(10) 13 = 4(3) + 1
3 = 3(1)
Extended Euclidean Algorithm :
(10) 1 = 13 - 4(3)
(9) 1 = 13- 4[16-1(13)]
1 = 13- 4(16)+4(13)
1 = 5(13)- 4(16)
(8) 1 = 5[29-1(16)]- 4(16)
1 = 5(29)-5(16)- 4(16)
1 = 5(29)-9(16)
(7) 1 = 5(29)-9[45-1(29)]
1 = 5(29)-9(45)+9(29)
1 = 14(29)-9(45)
(6) 1 = 14(29)-9(45)
1 = 14[74-1(45)]-9(45)
1 = 14(74)-14(45)-9(45)
1 = 14(74)-23(45)
(5) 1 = 14(74)-23[193 - 2(74)]
1 = 14(74)-23(193) + 46(74)
1 = 60(74)-23(193)
(4) 1 = 60[267-1(193)]-23(193)
1 = 60(267)-60(193)-23(193)
1 = 60(267)-83(193)
(3) 1 = 60(267)-83[994-3(267)]
1 = 60(267)-83(994)+249(267)
1 = 309(267)-83(994)
(2) 1 = 309[1261 - 1(994)]-83(994)
1 = 309(1261) - 309(994)-83(994)
1 = 309(1261) - 392(994)
(1) 1 = 309(1261) - 392[18648 - 14(1261)]
1 = 309(1261) - 392(18648) + 5488(1261)
1 = 5795(1261) - 392(18648)
so 1261^{-1} congruent (5795) mod 18648, ans is 5795
LFSR
Formula:-
summation -> E,
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
maximum number to run -> m - 1
start number to run -> i = 0
m is the degree
f_{i} will be obtained from the function ........f(x)
formula to find the period of sequence -> 2^{m} - 1 , e.g , degree
m=4, so 2^{4} - 1=15
Example: f(x) = 1 + x^{2} +x^{4}, seed given 0010, generate the
sequence
Solution:
Step 1: Get sequence f_{i} from function,
start to put x^{0} until x^{4}
........NOTE: every function by default sure have the last degree
so we ignore the power of 4
f(x) = [_]. x^{0} + [_]. x^{1} + [_].x^{2} + [_]. x^{3} + [_]. x^{4}
...........fill in the blank based on the funciton given [_]
f(x) = [1]. x^{0} + 0]. x^{1} + [1].x^{2} + [0]. x^{3} + [1]. x^{4}
...........so, we get the
f_{0} + f_{1} + f_{2} + f_{3}
1 0 1 0
Step 2: Use formula
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
we know this is degree 4 based on function given. m = 4,
p/s:seed is the starting of the sequence
i build initial table
n : 1 2 3 4
a_{n} : 0 0 1 0
..........so we have to find number 5 item, n = 5
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
a_{5} = ^{4 - 1} E _{i = 0} f_{i}a_{5 - 4 + i}
a_{5} = f_{0}a_{5 - 4 + 0} +
f_{1}a_{5 - 4 + 1} +
f_{2}a_{5 - 4 + 2} +
f_{3}a_{5 - 4 + 3}
........we susitute f number only so we can find the common formula
a_{5} = 1 x a_{5 - 4 + 0} +
0 x a_{5 - 4 + 1} +
1 x a_{5 - 4 + 2} +
0 x a_{5 - 4 + 3}
........we remove the f with 0 value
a_{5} = 1 x a_{5 - 4 + 0} +
1 x a_{5 - 4 + 2}
........substitue the item value 5 back to n
a_{n} = a_{n - 4 + 0} +
a_{n - 4 + 2}
........we got the formula
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used
Step 3: Generate Sequence
n :1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
a_{n}:0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0
since we know the period of seq is 15 so 20 should be more than enough
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used
when n = 5,
a_{5} = a_{5 - 4 } + a_{5 - 2} =a_{1} + a_{3} mod 2
= 0 + 1 = 1 mod 2
repeat until n = 20
when n = 6, a_{6} = a_{6 - 4 } + a_{6 - 2}
= a_{2} + a_{4} mod 2
= 0 + 0 = 0 mod 2
summation -> E,
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
maximum number to run -> m - 1
start number to run -> i = 0
m is the degree
f_{i} will be obtained from the function ........f(x)
formula to find the period of sequence -> 2^{m} - 1 , e.g , degree
m=4, so 2^{4} - 1=15
Example: f(x) = 1 + x^{2} +x^{4}, seed given 0010, generate the
sequence
Solution:
Step 1: Get sequence f_{i} from function,
start to put x^{0} until x^{4}
........NOTE: every function by default sure have the last degree
so we ignore the power of 4
f(x) = [_]. x^{0} + [_]. x^{1} + [_].x^{2} + [_]. x^{3} + [_]. x^{4}
...........fill in the blank based on the funciton given [_]
f(x) = [1]. x^{0} + 0]. x^{1} + [1].x^{2} + [0]. x^{3} + [1]. x^{4}
...........so, we get the
f_{0} + f_{1} + f_{2} + f_{3}
1 0 1 0
Step 2: Use formula
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
we know this is degree 4 based on function given. m = 4,
p/s:seed is the starting of the sequence
i build initial table
n : 1 2 3 4
a_{n} : 0 0 1 0
..........so we have to find number 5 item, n = 5
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
a_{5} = ^{4 - 1} E _{i = 0} f_{i}a_{5 - 4 + i}
a_{5} = f_{0}a_{5 - 4 + 0} +
f_{1}a_{5 - 4 + 1} +
f_{2}a_{5 - 4 + 2} +
f_{3}a_{5 - 4 + 3}
........we susitute f number only so we can find the common formula
a_{5} = 1 x a_{5 - 4 + 0} +
0 x a_{5 - 4 + 1} +
1 x a_{5 - 4 + 2} +
0 x a_{5 - 4 + 3}
........we remove the f with 0 value
a_{5} = 1 x a_{5 - 4 + 0} +
1 x a_{5 - 4 + 2}
........substitue the item value 5 back to n
a_{n} = a_{n - 4 + 0} +
a_{n - 4 + 2}
........we got the formula
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used
Step 3: Generate Sequence
n :1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
a_{n}:0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0
since we know the period of seq is 15 so 20 should be more than enough
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used
when n = 5,
a_{5} = a_{5 - 4 } + a_{5 - 2} =a_{1} + a_{3} mod 2
= 0 + 1 = 1 mod 2
repeat until n = 20
when n = 6, a_{6} = a_{6 - 4 } + a_{6 - 2}
= a_{2} + a_{4} mod 2
= 0 + 0 = 0 mod 2
Auto Key Options
If it is english in alphabet so, Z_{26}....mod 26
0 <= k <=25
formula:- first number a_{1} = x_{1} + k.........where x is
plaintext, k is your auto key
consequences a_{i} = x_{i-1} , i >= 2
encryption: e(x_{1}) = x_{1} + k...........for 1st one character
decryption: d(y_{1}) = y_{1} - k ...........for 1st one character
decryption ( is minus)
Example: k = 8
Ciphertext is: B H R D Y ...............y
1 7 17 3 24
start to solve:
step 1:
Keystream : 8 .........k,
always put the k value in the 1st place
step 2:
Plaintext : d(y_{1}) = y_{1} - k
d(1) = 1 - 8 = -7 mod 26 = 26 - 7 =19 mod 26
so...P : 19
step 3:
Keystream : 8 19 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(7) = 7 - 19 = 14 mod 26
repeate step 3:
Keystream : 8 19 14 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(17) = 17 - 14 = 3mod 26
repeate step 3:
Keystream : 8 19 14 3 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(3) = 3- 3 = 0 mod 26
repeate step 3:
Keystream : 8 19 14 3 0 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(24) = 24 - 0= 24mod 26
repeate step 3:
Keystream : 8 19 14 3 0 24
......finally we have
Ciphertext is: B H R D Y ...............y
1 7 17 3 24
Keystream : 8 19 14 3 0
Plaintext : 19 14 3 0 24
solved : T O D A Y
///////////encryption ( is plus) ////////////
Example: k = 8
Plaintext : T O D A Y .................x
code : 19 14 3 0 24
start to solve:
step 1:
Keystream : 8 .........k, always put the k value in the 1st place
step 2: .........here can directly put the key stream
Keystream : 8 19 14 3 0 ......put the key in ascending order
step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(19) = 19 + 8 = 1 mod 26
so...Ciphertext : 1
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(14) = 14 + 19 = 7 mod 26
so...Ciphertext : 1 7
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(3) = 3 + 14= 17 mod 26
so...Ciphertext : 1 7 17
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(0) = 0 + 3= 3 mod 26
so...Ciphertext : 1 7 17 3
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(24) = 24 + 0= 24 mod 26
so...Ciphertext : 1 7 17 3 24
......finally we have
solved : T O D A Y.................x
code : 19 14 3 0 24
Keystream : 8 19 14 3 0
Ciphertext : 1 7 17 3 24
Ciphertext is : B H R D Y ...............y
0 <= k <=25
formula:- first number a_{1} = x_{1} + k.........where x is
plaintext, k is your auto key
consequences a_{i} = x_{i-1} , i >= 2
encryption: e(x_{1}) = x_{1} + k...........for 1st one character
decryption: d(y_{1}) = y_{1} - k ...........for 1st one character
decryption ( is minus)
Example: k = 8
Ciphertext is: B H R D Y ...............y
1 7 17 3 24
start to solve:
step 1:
Keystream : 8 .........k,
always put the k value in the 1st place
step 2:
Plaintext : d(y_{1}) = y_{1} - k
d(1) = 1 - 8 = -7 mod 26 = 26 - 7 =19 mod 26
so...P : 19
step 3:
Keystream : 8 19 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(7) = 7 - 19 = 14 mod 26
repeate step 3:
Keystream : 8 19 14 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(17) = 17 - 14 = 3mod 26
repeate step 3:
Keystream : 8 19 14 3 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(3) = 3- 3 = 0 mod 26
repeate step 3:
Keystream : 8 19 14 3 0 ......always put the previous ans for the following keystream
repeate step 2:
Plaintext : d(24) = 24 - 0= 24mod 26
repeate step 3:
Keystream : 8 19 14 3 0 24
......finally we have
Ciphertext is: B H R D Y ...............y
1 7 17 3 24
Keystream : 8 19 14 3 0
Plaintext : 19 14 3 0 24
solved : T O D A Y
///////////encryption ( is plus) ////////////
Example: k = 8
Plaintext : T O D A Y .................x
code : 19 14 3 0 24
start to solve:
step 1:
Keystream : 8 .........k, always put the k value in the 1st place
step 2: .........here can directly put the key stream
Keystream : 8 19 14 3 0 ......put the key in ascending order
step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(19) = 19 + 8 = 1 mod 26
so...Ciphertext : 1
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(14) = 14 + 19 = 7 mod 26
so...Ciphertext : 1 7
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(3) = 3 + 14= 17 mod 26
so...Ciphertext : 1 7 17
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(0) = 0 + 3= 3 mod 26
so...Ciphertext : 1 7 17 3
repeat step 3:
Plaintext : e(x_{1}) = x_{1} + k
e(24) = 24 + 0= 24 mod 26
so...Ciphertext : 1 7 17 3 24
......finally we have
solved : T O D A Y.................x
code : 19 14 3 0 24
Keystream : 8 19 14 3 0
Ciphertext : 1 7 17 3 24
Ciphertext is : B H R D Y ...............y
Euler Function
Method 1:
phi(12) = ?
12 = 2^{2} x 3 ( where 2 and 3 are prime)
let p = 2, q = 3, so formula is phi(n) = n x (1 - 1/p) x (1 - 1/q)
so, phi(12) = 12 x (1 - 1/2) x (1 - 1/3)
= 12 x (1/2) x (2/3)
= 4
Method 2: Use this method if and only if we can factor the number into
prime that no repeatation. (but, i seem can find some way to fix it,
need further clarification with Dr lim, will update here once succeed)
if we can find ....phi(n) = phi(p) x phi(q) x phi(r) x ...... where
p , q , r are prime and no repeat,
example phi(26) = phi(2) x phi(13)
= (how many number that < 2 are prime with 2,
find 0<a<2, where gcd(a,2)= 1) x
(how many number that < 13 are prime with
13, find 0<a<13, where gcd(a,13)= 1)
= 1 x 12
= 12
******p/s: we need method 2 for RSA
phi(12) = ?
12 = 2^{2} x 3 ( where 2 and 3 are prime)
let p = 2, q = 3, so formula is phi(n) = n x (1 - 1/p) x (1 - 1/q)
so, phi(12) = 12 x (1 - 1/2) x (1 - 1/3)
= 12 x (1/2) x (2/3)
= 4
Method 2: Use this method if and only if we can factor the number into
prime that no repeatation. (but, i seem can find some way to fix it,
need further clarification with Dr lim, will update here once succeed)
if we can find ....phi(n) = phi(p) x phi(q) x phi(r) x ...... where
p , q , r are prime and no repeat,
example phi(26) = phi(2) x phi(13)
= (how many number that < 2 are prime with 2,
find 0<a<2, where gcd(a,2)= 1) x
(how many number that < 13 are prime with
13, find 0<a<13, where gcd(a,13)= 1)
= 1 x 12
= 12
******p/s: we need method 2 for RSA
Primitive Root
Finally i understand primitive root, so happy so share here.
1st - How many primitive root of mod n ?
let n = 11
total primitive root is:-
phi(n-1) = phi(10)
...How to find phi(n-1) in case it is too big ???????
Got method 10 = 2 x 5 ( 2 also prime, 5 also prime),
let p = 2, q = 5,
so formula is phi(a) = a x ( 1 - 1/p) x (1 - 1/q)
phi(10) = 10 x (1 - 1/2) x (1 - 1/5)
= 10 x (1/2) x(4/5)
=4
**** teacher method is
phi(10) = phi(5) x phi(2)
= ( how many prime number less than 5) x
( how many prime number less than 2)
= 4 x 1
= 4
2nd - What is primitive root of mod n?
let n = 11
primitive root of n where all the integer numbers < 10 that
your power of mod n there is no repeatation
we start to test with 2
2^k, where 0 < k < 10
a , b , c , d, e, f , g , h , i
2^1, 2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,
2 , 4 , 8, 5 ,10 , 9, 7, 3, 6 ------------>( mod 11)
.... see, there is no number repeat,
so we conclude 2 is primitive root of mod 11
3rd - Find all primitive root of mod n
continue..... let n = 11
once we have found one primitive root, we can find the rest of primitive root already
how?
let's look at the above calculation,
b is power 2, is gcd(2,10)= 1? no, so 4 is not primitive root
c is power 3, is gcd(3,10)= 1? yes, so 8 is not primitive root
d is power 4, is gcd(4,10)= 1? no, so 5 is not primitive root
e is power 5, is gcd(5,10)= 1? no, so 10 is not primitive root
f is power 6, is gcd(6,10)= 1? no, so 9 is not primitive root
g is power 7, is gcd(7,10)= 1? yes, so 7 is not primitive root
h is power 8, is gcd(8,10)= 1? no, so 3 is not primitive root
i is power 9, is gcd(9,10)= 1? yes, so 6 is not primitive root
so, we conclude that all primitive root for mod 11 are:-
2,8,7,6 ( total 4 as proved in part 1)
1st - How many primitive root of mod n ?
let n = 11
total primitive root is:-
phi(n-1) = phi(10)
...How to find phi(n-1) in case it is too big ???????
Got method 10 = 2 x 5 ( 2 also prime, 5 also prime),
let p = 2, q = 5,
so formula is phi(a) = a x ( 1 - 1/p) x (1 - 1/q)
phi(10) = 10 x (1 - 1/2) x (1 - 1/5)
= 10 x (1/2) x(4/5)
=4
**** teacher method is
phi(10) = phi(5) x phi(2)
= ( how many prime number less than 5) x
( how many prime number less than 2)
= 4 x 1
= 4
2nd - What is primitive root of mod n?
let n = 11
primitive root of n where all the integer numbers < 10 that
your power of mod n there is no repeatation
we start to test with 2
2^k, where 0 < k < 10
a , b , c , d, e, f , g , h , i
2^1, 2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,
2 , 4 , 8, 5 ,10 , 9, 7, 3, 6 ------------>( mod 11)
.... see, there is no number repeat,
so we conclude 2 is primitive root of mod 11
3rd - Find all primitive root of mod n
continue..... let n = 11
once we have found one primitive root, we can find the rest of primitive root already
how?
let's look at the above calculation,
b is power 2, is gcd(2,10)= 1? no, so 4 is not primitive root
c is power 3, is gcd(3,10)= 1? yes, so 8 is not primitive root
d is power 4, is gcd(4,10)= 1? no, so 5 is not primitive root
e is power 5, is gcd(5,10)= 1? no, so 10 is not primitive root
f is power 6, is gcd(6,10)= 1? no, so 9 is not primitive root
g is power 7, is gcd(7,10)= 1? yes, so 7 is not primitive root
h is power 8, is gcd(8,10)= 1? no, so 3 is not primitive root
i is power 9, is gcd(9,10)= 1? yes, so 6 is not primitive root
so, we conclude that all primitive root for mod 11 are:-
2,8,7,6 ( total 4 as proved in part 1)
Subscribe to:
Comments (Atom)