Factoring N = prqs for large r and s

Jean Sébastien Coron; Jean Charles Faugère; Guénaël Renault; Rina Zeitoun

doi:10.1007/978-3-319-29485-8_26

Factoring N = p^rq^s for large r and s

Jean Sébastien Coron
, Jean Charles Faugère
, Guénaël Renault
, Rina Zeitoun

University of Luxembourg
INRIA Institut National de Recherche en Informatique et en Automatique
Sorbonne Université
LIP6, UPMC Sorbonne Universités - Paris 6
Oberthur Technologies

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

15 Citations (Scopus)

Résumé

Boneh et al. showed at Crypto 99 that moduli of the form N = p^rq can be factored in polynomial time when r ≃ logp. Their algorithm is based on Coppersmith’s technique for finding small roots of polynomial equations. In this paper we show that N = p^r q^s can also be factored in polynomial time when r or s is at least (log p)³; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli with k prime factors N =∏^k _i=1 p^ri _i; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the exponents r_i is large enough.

langue originale	Anglais
titre	Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016
rédacteurs en chef	Kazue Sako
Editeur	Springer Verlag
Pages	448-464
Nombre de pages	17
ISBN (imprimé)	9783319294841
Les DOIs	https://doi.org/10.1007/978-3-319-29485-8_26
état	Publié - 1 janv. 2016
Modification externe	Oui
Evénement	2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016 - San Francisco, États-Unis Durée: 29 févr. 2016 → 4 mars 2016

Série de publications

Nom	Lecture Notes in Computer Science
Volume	9610
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016
Pays/Territoire	États-Unis
La ville	San Francisco
période	29/02/16 → 4/03/16

Accès au document

10.1007/978-3-319-29485-8_26

Contient cette citation

@inproceedings{e9504c33b313493693d7a096dceb08f3,

title = "Factoring N = prqs for large r and s",

abstract = "Boneh et al. showed at Crypto 99 that moduli of the form N = prq can be factored in polynomial time when r ≃ logp. Their algorithm is based on Coppersmith{\textquoteright}s technique for finding small roots of polynomial equations. In this paper we show that N = pr qs can also be factored in polynomial time when r or s is at least (log p)3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli with k prime factors N =∏k i=1 pri i; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the exponents ri is large enough.",

author = "Coron, \{Jean S{\'e}bastien\} and Faug{\`e}re, \{Jean Charles\} and Gu{\'e}na{\"e}l Renault and Rina Zeitoun",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016 ; Conference date: 29-02-2016 Through 04-03-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-29485-8\_26",

language = "English",

isbn = "9783319294841",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "448--464",

editor = "Kazue Sako",

booktitle = "Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016",

}

Coron, JS, Faugère, JC, Renault, G & Zeitoun, R 2016, Factoring N = p^rq^s for large r and s. Dans K Sako (Ed.), Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016. Lecture Notes in Computer Science, VOL. 9610, Springer Verlag, p. 448-464, 2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016, San Francisco, États-Unis, 29/02/16. https://doi.org/10.1007/978-3-319-29485-8_26

Factoring N = p^rq^s for large r and s. / Coron, Jean Sébastien; Faugère, Jean Charles; Renault, Guénaël et al.
Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016. Ed. / Kazue Sako. Springer Verlag, 2016. p. 448-464 (Lecture Notes in Computer Science; Vol 9610).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - Factoring N = prqs for large r and s

AU - Coron, Jean Sébastien

AU - Faugère, Jean Charles

AU - Renault, Guénaël

AU - Zeitoun, Rina

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Boneh et al. showed at Crypto 99 that moduli of the form N = prq can be factored in polynomial time when r ≃ logp. Their algorithm is based on Coppersmith’s technique for finding small roots of polynomial equations. In this paper we show that N = pr qs can also be factored in polynomial time when r or s is at least (log p)3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli with k prime factors N =∏k i=1 pri i; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the exponents ri is large enough.

AB - Boneh et al. showed at Crypto 99 that moduli of the form N = prq can be factored in polynomial time when r ≃ logp. Their algorithm is based on Coppersmith’s technique for finding small roots of polynomial equations. In this paper we show that N = pr qs can also be factored in polynomial time when r or s is at least (log p)3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli with k prime factors N =∏k i=1 pri i; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the exponents ri is large enough.

U2 - 10.1007/978-3-319-29485-8_26

DO - 10.1007/978-3-319-29485-8_26

M3 - Conference contribution

AN - SCOPUS:84959017756

SN - 9783319294841

T3 - Lecture Notes in Computer Science

SP - 448

EP - 464

BT - Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016

A2 - Sako, Kazue

PB - Springer Verlag

T2 - 2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016

Y2 - 29 February 2016 through 4 March 2016

ER -