  It is well known that the inverse function of y = x with the derivative y' =
1 is x = y, the inverse function of y = c with the derivative y' = 0 is
inexistent, and so on. Hence, on the assumption that the noninvertibility of
the univariate increasing function y = f(x) with x > 0 is in direct proportion
to the growth rate reflected by its derivative, the authors put forward a
method of comparing difficulties in inverting two functions on a continuous or
discrete interval called asymptotic granularity reduction (AGR) which
integrates asymptotic analysis with logarithmic granularities, and is an
extension and a complement to polynomial time (Turing) reduction (PTR). Prove
by AGR that inverting y = x ^ x (mod p) is computationally harder than
inverting y = g ^ x (mod p), and inverting y = g ^ (x ^ n) (mod p) is
computationally equivalent to inverting y = g ^ x (mod p), which are compatible
with the results from PTR. Besides, apply AGR to the comparison of inverting y
= x ^ n (mod p) with y = g ^ x (mod p), y = g ^ (g1 ^ x) (mod p) with y = g ^ x
(mod p), and y = x ^ n + x + 1 (mod p) with y = x ^ n (mod p) in difficulty,
and observe that the results are consistent with existing facts, which further
illustrates that AGR is suitable for comparison of inversion problems in
difficulty. Last, prove by AGR that inverting y = (x ^ n)(g ^ x) (mod p) is
computationally equivalent to inverting y = g ^ x (mod p) when PTR can not be
utilized expediently. AGR with the assumption partitions the complexities of
problems more detailedly, and finds out some new evidence for the security of
cryptosystems.

Computational Complexity