Adelmann, Clemens; Winterhof, Arne Interpolation of functions related to the integer factoring problem. (English) Zbl 1151.94471 Ytrehus, Øyvind (ed.), Coding and cryptography. International workshop, WCC 2005, Bergen, Norway, March 14–18, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-35481-6/pbk). Lecture Notes in Computer Science 3969, 144-154 (2006). Summary: The security of the RSA public key cryptosystem depends on the intractability of the integer factoring problem. This paper shall give some theoretical support to the assumption of hardness of this number theoretic problem.We obtain lower bounds on degree, weight, and additive complexity of polynomials interpolating functions related to the integer factoring problem, including Euler’s totient function, the divisor sum functions, Carmichael’s function, and the RSA-function.These investigations are motivated by earlier results of the same flavour on the interpolation of discrete logarithm and Diffie-Hellman mapping.For the entire collection see [Zbl 1102.94002]. Cited in 2 Documents MSC: 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 68W25 Approximation algorithms Keywords:polynomials; degree; weight; additive complexity; factoring problem; RSA-problem; Euler’s totient function; divisor sum function; Carmichael’s function PDFBibTeX XMLCite \textit{C. Adelmann} and \textit{A. Winterhof}, Lect. Notes Comput. Sci. 3969, 144--154 (2006; Zbl 1151.94471) Full Text: DOI