Sorry, you're right! I forgot to say that the p's are primes. OK, let me try again with less cumbersome notation (although my question was mostly about how to make the notation better in the first place...) Pick p,q primes > some composite n. Make sure (p-1) and (q-1) are smooth so that one can use the Pohlig-Hellman algorithm to calculate discrete logs. Also choose them so they both have g as a generator; that is, the powers of the element g give every number mod p and mod q except 0. Let lg_p, p prime, be discrete log base g over p; that is, find x given y,p in the equation y=g^x mod p. Then x=lg_p(y). Let a(x,p) = g^(lg_p(n) - lg_p(x)) mod p Then find x != 1,n such that a(x,p) == a(x,q) The idea is that only factors of n satisfy both sides simultaneously. (I haven't proven that.) It's a strange problem, I think, because it's easy (i.e. polynomial time) to solve either side of the problem, but seems to be very hard to solve both at once. One problem is the notation: usually one writes "equivalent to" with the triple-bar equals and says that both sides of the equation are in the same equivalence class. Here I'm saying that the bits match when one uses the customary "mod" function in your favorite language. a is self-inverse for fixed p: x == a(a(x,p),p) One can rewrite the above problem as: Find x != 1,n such that x == a(a(x,p),q). -- Mike Stay staym@clear.net.nz