Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If you can compute discrete logarithms modulo composite n, you can actually factor n.

Suppose that n = p * q. The order of the multiplicative group of the integers modulo n is (p-1) * (q-1). Suppose that, given a randomly generated a, we can find a nontrivial x such that a^x = 1 (mod n). Then x divides the order of n, i.e. (p-1)*(q-1), and we can quickly extract p and q from there.

Edit: Terminology correction. Thanks xyzzyz!



The order of the ring of integers modulo n is (p-1)(q-1)

You mean, the order of the multiplicative group. The order of the ring of integers modulo n is always n, regardless of n.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: