Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### arjun95's blog

By arjun95, history, 12 months ago, ,

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.

•
• -1
•

 » 12 months ago, # |   -8 As far as I understand, you want to solve the equation . If , you can use baby-step giant-step algorithm.Let m1 be product of all prime powers pk such that pk|m and p|a. m2 = m / m1. By construction m1 and m2 are coprime. For sufficiently large x (at least ) . Check the small values separately.If , there are no solutions. Otherwise we need to solve the equation modulo m2. . This case has been analyzed above.
•  » » 12 months ago, # ^ |   0 can you elaborate the calculations of m1.
•  » » » 12 months ago, # ^ |   0 m is product of some powers of primes piki. Some of these primes divide a, some don't. m1 is a product of those powers for which pi divide a. m2 is a product of other powers.For example, if a = 60 = 22·3·5, m = 126 = 2·32·7, m1 = 2·32 = 18 (2|a, 3|a), m2 = 7 ().
•  » » » » 12 months ago, # ^ |   +1 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
•  » » » » » 12 months ago, # ^ |   0 Nice example. That's why we should care about small values of x. , but for all x ≥ 2 .If x is too small, we can look at x + tφ(m2). . For sufficiently large t we get .In this example φ(m2) = 6, so for t = 1 we find x = 7.
•  » » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » 12 months ago, # ^ |   0 Did you know how to do it if m is prime? In the same manner we can find the smallest x such that and x is large enough (). It remains to check small values of x.
•  » » » » » » » » 12 months ago, # ^ |   0 no, i don't know how to calculate smallest x when m is prime.
•  » » » » » » » » » 12 months ago, # ^ |   0 map> pows; int k = sqrt(m); for (int i = 0; i <= k; ++i) pows[Pow(a, k * i)].push_back(i); for (int i = 0; i <= k; ++i) find something in pows[b * Pow(a, i) % m] 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.
•  » » » » » » » » » 12 months ago, # ^ |   0 thanks a lot, now i got it.thanks for giving your precious time.
•  » » » » » » » » 12 months ago, # ^ |   0 Can you explain the reason for the inequality ?
•  » » » » » » » » » 12 months ago, # ^ |   +1 If , we want to get . It means that for each prime p its power in ax is not less than its power in m1. Power of p in m1 is at most . On the other hand, if , power of p in ax is at least .