Pohlig-Hellman Part 1 - method 2

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