Factoring with hints

DOI10.1515/JMC-2020-0078MaRDI QIDQ2027274zbMATH OpenOpenAlexFDO

Authors Francesco Sica

Publication date 25 May 2021

Published in Journal of Mathematical Cryptology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complex analysisfactorisation of RSA moduliRiemann zeta function

Mathematics Subject Classification ID

(zeta (s)) and (L(s, chi)) (11M06) Algebraic number theory computations (11Y40) Cryptography (94A60)

Abstract: We introduce a new deterministic factoring algorithm, which could be described in the cryptographically fashionable term of "factoring with hints": we show that, given the knowledge of the factorisations of $O(N^{1/3+epsilon})$ terms surrounding $N=pq$ product of two large primes, we can recover deterministically $p$ and $q$ in $O(N^{1/3+epsilon})$ bit operations. Although this is slower than the current best factoring algorithms, this method shows that the factorisations of close integers are related and that consequently one can expect more results along this line of thought.

Recommendations

• A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
• Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
• Differential Factoring for Integers
• Factorization of Square-Free Integers with High Bits Known
• Further improvement of factoring RSA moduli with implicit hint

Cites work

• A babystep-giantstep method for faster deterministic integer factorization
• A Method of Factoring and the Factorization of F 7
• A Rigorous Time Bound for Factoring Integers
• Convergence Acceleration of Alternating Series
• Factoring integers with elliptic curves
• scientific article; zbMATH DE number 3708485 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 1552275 (Why is no real title available?)
• scientific article; zbMATH DE number 3801619 (Why is no real title available?)
• The development of the number field sieve

Cited in

(3)

• Factoring Numbers with Waves
• scientific article; zbMATH DE number 503356 (Why is no real title available?)
• Distribution of powers modulo p and security of RSA

This page was built for publication: Factoring with hints

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