Divisors in residue classes, constructively

DOI10.1090/S0025-5718-07-02007-8zbMath1131.11080MaRDI QIDQ5429512

Don Coppersmith, N. A. Howgrave-Graham, Santosh V. Nagaraj

Publication date: 30 November 2007

Published in: Mathematics of Computation (Search for Journal in Brave)

zbMATH Keywords

divisors; residue classes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

11Y16: Number-theoretic algorithms; complexity

11Y05: Factorization

11Y11: Primality

Related Items

An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient, Deterministic factoring with oracles, Egyptian fractions of bounded length, On the Diophantine equation \(ax^3 + by + c = xyz\), Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, EQUIDISTRIBUTION OF DIVISORS IN RESIDUE CLASSES AND REPRESENTATIONS BY BINARY QUADRATIC FORMS, List Decoding for Binary Goppa Codes, A deterministic version of Pollard’s $p-1$ algorithm

Uses Software

• NTL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials with rational coefficients
• Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
• Divisors in Residue Classes
• New Primality Criteria and Factorizations of 2 m ± 1