Deterministic factoring with oracles

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 $ϕ(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 > √ N$ , then we can recover p in deterministic polynomial time given $ϕ(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.
Type de document :
Pré-publication, Document de travail
2018
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01715832
Contributeur : François Morain <>
Soumis le : vendredi 23 février 2018 - 09:16:35
Dernière modification le : jeudi 10 mai 2018 - 02:06:01

Fichiers

oracles.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01715832, version 1
  • ARXIV : 1802.08444

Citation

François Morain, Guénaël Renault, Benjamin Smith. Deterministic factoring with oracles. 2018. 〈hal-01715832〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

59