Deterministic factoring with oracles (Q6115442): Difference between revisions

In this paper the problem of integer factorization is studied. Lattice-based techniques are used to factoring a positive integer with number-theoretic oracles. We denote by \(\phi(N)\), \(\lambda(N)\) and \(\sigma(N)\) the value of the Euler totient function, the value of the Carmichael lambda function, and the sum of all positive divisors of \(N\). It is proved that if \(N\) is square-free and has at least three prime factors, of which the largest \(p\) satisfies \(p > \sqrt{N}\), then \( p\) is computed in deterministic polynomial time in \(\log N\), provided that one of the quantities \(\phi(N)\), \(\lambda(N)\), or \(\sigma(N)\) is known. Next, suppose that \(N=p_1p_2p_3\), where \(p_1\), \(p_2\), \(p_3\) are primes with \(p_1 > p_2 > p_3\), and put \(a_i = \log p_i/\log N\) \((i=1,2)\). Then we can compute a nontrivial factor of \(N\) in deterministic polynomial time in \(\log N\) given \(\phi(N)\) or \(\sigma(N)\), provided that either \(a_1> 1/2\), or \(2a_1+3a_2 \geq 2\), or \(a_2 > (-1 + \sqrt{17})/8\). Several examples are given.