I am having troubles understanding the concept of reduction and its relation with complexity.
I have defined some problems as follows:
- BreakRSA: From $(n = pq, e)$ find $d$ such that $ed = 1 \mod φ(n)$
- CDH: From $A = g^a$ and $B = g^b$ in a group, find $C = g^{ab}$
- DLOG: From $(g, g^x)$ from a group $G$ find $x ∈ {1, . . . , |G|}$
- ModExp: From $(x, n, e)$ integers compute $x^e \mod n$
- IntegerFact: From $n = pq$ an integer, find $p$ and $q$
From these I am trying to find all the problems such that Prob1 is reductible to Prob2.
What I suggested is that:
- BreakRSA $\leq$ IntegerFact
- IntegerFact $\leq$ BreakRSA
- CDH $\leq$ DLOG
My question is if there are any other problems that can be reductible to others.
For instance I am doubting that:
- DLOG $\leq$ ModExp
Because by simply exponentiating all the $g$ to the power of $x ∈ {1, . . . , |G|}$ I can eventually find my $x$ (bruteforce attack). However my friend told me that it is not reductible because the bruteforce attack is not polynomial time (not P but NP).
Any help will be much appreciated.