Factoring integers and computing discrete logarithms via diophantine approximation

DOI10.1007/3-540-46416-6_24MaRDI QIDQ4037472zbMATH OpenOpenAlexFDO

Authors Claus Peter Schnorr

Publication date 18 May 1993

Published in Advances in Cryptology — EUROCRYPT ’91 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46416-6_24

zbMATH Keywords

algorithmdiscrete logarithmsfactoring integers via diophantine approximation

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Factorization (11Y05) Cryptography (94A60)

Review text

[For the entire collection see Zbl 0756.00008.] The author discusses the factoring of integers \(N\) via diophantine approximations. Those approximations are determined by computing vectors in suitable lattices which are sufficiently close to a given one. He shows that under reasonable assumptions his algorithm terminates though no complexity results or running times are included. In a final section of the paper discrete logarithms in \((\mathbb Z/N\mathbb Z)^\times\) are calculated by a variant of that method.

Recommendations

• scientific article; zbMATH DE number 549859
• Computation of discrete logarithms in an arbitrary finite field
• scientific article; zbMATH DE number 4077312
• scientific article; zbMATH DE number 3970826
• scientific article; zbMATH DE number 3909733

Cited in

(13)

• Simultaneous reduction of a lattice basis and its reciprocal basis
• Polylog depth circuits for integer factoring and discrete logarithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Using the inhomogeneous simultaneous approximation problem for cryptographic design
• scientific article; zbMATH DE number 549859 (Why is no real title available?)
• scientific article; zbMATH DE number 1996321 (Why is no real title available?)
• Thrackles: an improved upper bound
• Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
• Cloud-assisted LLL: a secure and efficient outsourcing algorithm for approximate shortest vector problem
• Using LLL-reduction for solving RSA and factorization problems
• scientific article; zbMATH DE number 6607548 (Why is no real title available?)
• A new lower bound in the abc conjecture
• Attribute-based signatures with advanced delegation, and tracing

This page was built for publication: Factoring integers and computing discrete logarithms via diophantine approximation

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