(A) Is the following problem hard (i.e. no known solution in polynomial time)?
For large values of $N$ and $M$ (e.g. $N \ge 4096$, $M \ge 130$), find values for $g,x,c,p$ and $q$ such that:
$ g^x \equiv c\ (p)\ ,\ g^x \equiv c\ (q) \iff \exists\ k \in \mathbb{N} : g^x = c + k \cdot p\cdot q $
$g \ne c$ are small primes and $q \ne p $ are large primes; $ g, c, N < \log p, \log q, \log (|p-q|) $
$p-1$ and $q-1$ have large prime factors $p_0, q_0$ where $M < \log p_0, \log q_0$, and $g$ is a generator of a large group in both $p$ and $q$.
(B) Is there any other types of potentially hard problems that do not require predefined parameters like typical discrete logarithm and semi-prime factoring problems (other than generalizing the above problem)?
Notes:
- In typical Discrete Logarithm problems $g^x \equiv c \space (p)$ $g$, $p$ and $c$ are given, and the problem is to find $x$. I think it is not hard to find values for $g$, $p$, $c$ and $x$ that solve a discrete logarithm and where c is a small prime, e.g. by trying random values for $g^x-c$ until we find a large prime or an easy-to-factor number with a large prime factor.
- This is a theoretical problem and clearly won't be helpful in encryption algorithms.
- My thoughts: to solve the above problem we can brute force all different values for $g$ and $c$ since they are small, then, however, either:
- start from $p$ and solve discrete logarithms $g^x \equiv c \space (p)$ before testing if there is a suitable value for $q$. This is the discrete logarithm problem, it is HARD.
- start from $x$ and factor a hard-to-factor large semi-prime ($g^x - c = k \cdot p \cdot q$). This is semi-prime number factorization; it is HARD
- start with $p$ and $q$ but then the probability of finding a smooth number $c + k \cdot p \cdot q = g^x$ randomly is unrealistically low.