how to solve discrete logarithm over composite modulus, i know over prime modulo using Baby-step giant-step algorithm, but in case of composite modulus i have no idea how to solve this. i think this can be done by factorization of modulo and chinese remainder theorem but i don't know how to do this.

As far as I understand, you want to solve the equation . If , you can use baby-step giant-step algorithm.

Let

m_{1}be product of all prime powersp^{k}such thatp^{k}|mandp|a.m_{2}=m/m_{1}. By constructionm_{1}andm_{2}are coprime. For sufficiently largex(at least ) . Check the small values separately.If , there are no solutions. Otherwise we need to solve the equation modulo

m_{2}. . This case has been analyzed above.can you elaborate the calculations of m1.

mis product of some powers of primesp_{i}^{ki}. Some of these primes dividea, some don't.m_{1}is a product of those powers for whichp_{i}dividea.m_{2}is a product of other powers.For example, if

a= 60 = 2^{2}·3·5,m= 126 = 2·3^{2}·7,m_{1}= 2·3^{2}= 18 (2|a, 3|a),m_{2}= 7 ().thanks for your explanation.

but for your given example, a = 60, m = 126, for b = 18, answer should be 4, but after calculation of m1 and m2, m2 = 7 which gives value of x = 1 then how to come up with final solution(x = 4), correct me if i'm wrong

Nice example. That's why we should care about small values of

x. , but for allx≥ 2 .If

xis too small, we can look atx+tφ(m_{2}). . For sufficiently largetwe get .In this example φ(

m_{2}) = 6, so fort= 1 we findx= 7.thanks for such a nice explanation.

but if we have to find smallest value of x (which is equal 4 in above example) then how it can be calculate.

Did you know how to do it if

mis prime? In the same manner we can find the smallestxsuch that andxis large enough (). It remains to check small values ofx.no, i don't know how to calculate smallest x when m is prime.

If we want to find the smallest solution modulo prime, in the last line we just choose the smallest element from this vector. In our case we need to do some binary search here.

thanks a lot, now i got it.

thanks for giving your precious time.

Can you explain the reason for the inequality ?

If , we want to get . It means that for each prime

pits power ina^{x}is not less than its power inm_{1}. Power ofpinm_{1}is at most . On the other hand, if , power ofpina^{x}is at least .