Factoring into coprimes in essentially linear time

DOI10.1016/j.jalgor.2004.04.009zbMath1134.11352OpenAlexW2117370345MaRDI QIDQ4651807

Daniel J. Bernstein

Publication date: 22 February 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.04.009

zbMATH Keywords

Coprime basesFactor refinementFactoring into coprimes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Factorization (11Y05)

Related Items (18)

The Power of Leibniz-Like Functions as Oracles ⋮ Algorithmic theory of arithmetic rings, Prüfer rings and Dedekind rings. (Théorie algorithmique des anneaux arithmétiques, des anneaux de Prüfer et des anneaux de Dedekind.) ⋮ A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing ⋮ Chinese Remainder Theorem for bivariate lexicographic Gröbner bases ⋮ New Characterization of the Factor Refinement Algorithm with Applications ⋮ Deterministic factoring with oracles ⋮ Computing the binomial part of a polynomial ideal ⋮ Computing canonical heights on elliptic curves in quasi-linear time ⋮ Circulant graphs and GCD and LCM of subsets ⋮ A characterization of nonprime powers ⋮ Testing set proportionality and the Ádám isomorphism of circulant graphs ⋮ Solving structured linear systems with large displacement rank ⋮ Topics in computational algebraic number theory ⋮ Dynamical Gröbner bases over Dedekind rings ⋮ Minimizing representations over number fields. II: Computations in the Brauer group. ⋮ Testing Isomorphism of Lattices over CM-Orders ⋮ Character sums and deterministic polynomial root finding in finite fields ⋮ Detecting perfect powers by factoring into coprimes

This page was built for publication: Factoring into coprimes in essentially linear time