How to solve the Diffie-Hellman problem if $g$ is unknown? I am trying to solve the Diffie-Hellman problem modulo a composite number $N$, which I have factored. In this question, it was answered how to deal with such a situation. But how can I solve the problem if I don't know $g$? 
$$y = g^x \pmod{N}$$

The exact numbers are:
$$N=442101689710611$$
$$g^a = 421049228295820 \pmod{N}$$
$$g^b  = 105262307073955\pmod{N}$$

And I need to find $g^{ab}\bmod N$.
In general, there are a huge number of possible values for $g^{ab}$, depending on what $g$ is.

However, in this case, whoever set up this problem took care to radically reduce the number of possibilities.

Here's how you would attack this problem:


Step 1: factor $N$
Step 2: for each prime power factor $q^k$ of $N$, we need to determine the set of values of $g^{ab} \bmod q^k$.  Two special cases where this is easy:


If $g^a = 0 \pmod q$, then obviously $(g^a)^b = g^{ab} = 0 \pmod {q^k}$, and so we have one solution to this subproblem.
If $g^a = 1 \pmod{q^k}$, then $(g^a)^b = g^{ab} = 1 \bmod {q^k}$, and so we have one solution to this subproblem.



In practice, these special cases don't come up that often, in this case, it does.


Step 3: once we have the set of possible solutions to each of the subproblems, we can use the Chinese Remainder Theorem to join them together to come up with the set of solutions to the original problem.


Now, normally, each subproblem comes up with a large number of potential solutions, and so the combinatorics of step 3 comes up with a truly huge number of solutions.

However, in this case, it turns out to be only two solutions to the overall problem (and, as luck would have it, you really don't need the CRT to join those solutions in step 3; there's a simpler way to compute them).