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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Topics in Cryptology - The Cryptographers Track at the RSA Conference, CT-RSA 2016
Editors	Kazue Sako
Publisher	Springer Verlag
Pages	448-464
Number of pages	17
ISBN (Print)	9783319294841
DOIs	https://doi.org/10.1007/978-3-319-29485-8_26
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016 - San Francisco, United States Duration: 29 Feb 2016 → 4 Mar 2016

Publication series

Name	Lecture Notes in Computer Science
Volume	9610
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016
Country/Territory	United States
City	San Francisco
Period	29/02/16 → 4/03/16

Access to Document

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

Cite this

@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. in 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, pp. 448-464, 2016 Conference on Cryptographer's Track at the RSA, CT-RSA 2016, San Francisco, United States, 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -