Deterministic factoring with oracles

DOI10.1007/S00200-021-00521-8MaRDI QIDQ6115442zbMATH OpenOpenAlexFDO

Authors

Publication date 12 July 2023

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.08444

zbMATH Keywords

continuous fractionsCoppersmith's methoddeterministic integer factorizationlattice basis reductionLLL algorithm

Mathematics Subject Classification ID

Arithmetic functions; related numbers; inversion formulas (11A25) Factorization; primality (11A51) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

Abstract: We revisit the problem of integer factorization with number-theoretic oracles, including a well-known problem: can we factor an integer $N$ unconditionally, in deterministic polynomial time, given the value of the Euler totient ${\displaystyle }$Phi$(N)$? We show that this can be done, under certain size conditions on the prime factors of N. The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show for example that if $N$ is a squarefree integer with a prime factor $p>$sqrt$N$ , then we can recover p in deterministic polynomial time given ${\displaystyle }$Phi$(N)$. We also shed some light on the analogous problems for Carmichael's function, and the order oracle that is used in Shor's quantum factoring algorithm.

Review text

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.

Recommendations

• Deterministic integer factorization with oracles for Euler's totient function
• On oracle factoring of integers
• scientific article; zbMATH DE number 503356
• On the oracle complexity of factoring integers
• Smooth factors of integers and elliptic curve based factoring with an oracle

Cites work

• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• A babystep-giantstep method for faster deterministic integer factorization
• A deterministic version of Pollard's p-1 algorithm
• A New Proof of a Theorem of Van Der Corput
• A time-space tradeoff for Lehman's deterministic integer factorization method
• A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
• Advances in Cryptology - EUROCRYPT 2004
• An exponent one-fifth algorithm for deterministic integer factorisation
• An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient
• An LLL algorithm with quadratic complexity
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• Approximate Integer Common Divisor Problem Relates to Implicit Factorization
• Detecting perfect powers by factoring into coprimes
• Deterministic polynomial-time equivalence of computing the RSA secret key and factoring
• Divisors in Residue Classes
• Divisors in residue classes, constructively
• Efficient Factoring Based on Partial Information
• Factor Refinement
• Factoring N=p^rq^s for Large r and s
• Factoring into coprimes in essentially linear time
• Factoring Large Integers
• Factoring polynomials with rational coefficients
• Faster deterministic integer factorization
• Finding a small root of a bivariate integer equation; factoring with high bits known
• Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
• Further results on implicit factoring in polynomial time
• scientific article; zbMATH DE number 5306932 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 3569835 (Why is no real title available?)
• scientific article; zbMATH DE number 1303120 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1182510 (Why is no real title available?)
• scientific article; zbMATH DE number 1852134 (Why is no real title available?)
• scientific article; zbMATH DE number 1852136 (Why is no real title available?)
• scientific article; zbMATH DE number 799791 (Why is no real title available?)
• scientific article; zbMATH DE number 1418303 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• Implicit Factoring with Shared Most Significant and Middle Bits
• Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Miller's primality test
• Modern computer algebra
• On the average number of divisors of the Euler function
• On the Sum ∑k=1xd(f(k))
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• PRIMES is in P
• Reductions among number theoretic problems
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Some remarks on computing the square parts of integers
• Sums of Divisors, Perfect Numbers and Factoring

Cited in

(6)

• Complete divisibility problems for slowly utilized oracles
• scientific article; zbMATH DE number 503356 (Why is no real title available?)
• Factor Oracles
• New Characterization of the Factor Refinement Algorithm with Applications
• Hyperelliptic curves and integer factorization
• Elliptic-curve factoring, witnesses and oracles

This page was built for publication: Deterministic factoring with oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115442)