The Power of Leibniz-Like Functions as Oracles

摘要

A Leibniz-like function x is an arithmetic function (i.e., X : N → N) satisfying the product rule (which is also known as "Leibniz's rule"): x(MN) = x(M)·N + M·x(N). In this paper we study the computational power of efficient algorithms that are given oracle access to such functions. Among the results, we show that certain families of Leibniz-like functions can be use to factor integers, while many other families can used to compute the radicals of integers and other number-theoretic functions which are believed to be as hard as integer factorization [1,2].