收录:
摘要:
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 nonexistent, and so on. Hence, on the assumption that the noninvertibility of the univariate increasing function y = (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 equivalent to x(x) (mod p) is computationally harder than inverting y equivalent to g(x) (mod p), and inverting y equivalent to g(xn) (mod p) is computationally equivalent to inverting y equivalent to g(x) (mod p), which are compatible with the results from PTR. Besides, apply AGR to the comparison of inverting y equivalent to x(n) (mod p) with y equivalent to g(x) (mod p), y equivalent to g(g1x) (mod p) with y equivalent to g(x) (mod p), and y equivalent to x(n) + x + 1 (mod p) with y equivalent to 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 equivalent to x(n)g(x) (mod p) is computationally equivalent to inverting y equivalent to g(x) (mod p) when PTR cannot 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. (C) 2011 Elsevier B.V. All rights reserved.
关键词:
通讯作者信息:
电子邮件地址: