So I'm trying to figure out the connection between the discrete log problem and RSA. I think this is what the following question is trying to do.
Suppose you have an oracle which gives you the smallest positive x satisfying
the following congruence:
g^x ≡ k (mod N)
where N = p*q for some distinct primes p and q, and g and k are any integers.
We also have one more condition that (p -1)/2 and (q -1)/2 are both primes.
What is the quickest way to find p and q? i.e. factor N.
So I'm completely lost on how to approach the solution to this problem. If somebody can provide me with hints/solution to solve this problem I would be really grateful. Thanks.
In g^x = 1, the solution x will always be a divider of (p-1)*(q-1). Choose some different g values, and you will likely find most factors of (p-1)*(q-1). And as (p-1)(q-1) = N - p - q + 1, knowing (p-1)(q-1) and N results in knowing p + q. Knowing N = p*q and p+q is like knowing circumference and area of a rectangle, and can be quickly solved for p and q.