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