Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
Year: 2011
Issue: 39
Volume: 412
Page: 5374-5386
1 . 1 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 8
SCOPUS Cited Count: 11
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: