Rigorous analysis of a randomised number field sieve

JOURNAL OF NUMBER THEORY

卷:187

Article

Lee, Jonathan D.^1,2  Venkatesan, Ramarathnam^2,3 

[1] Univ Oxford, Math Inst, Oxford, England

[2] Microsoft Res Redmond, Redmond, WA USA

[3] Microsoft Res India, Bengaluru, India

关键词: Factoring;    Probabilistic combinatorics;    Additive number theory;   

DOI  :  10.1016/j.jnt.2017.10.019

来源: Elsevier

【 摘 要 】

Factorisation of integers n is of number theoretic and cryptographic significance. The Number Field Sieve (NFS) introduced circa 1990, is still the state of the art algorithm, but no rigorous proof that it halts or generates relationships is known. We propose and analyse an explicitly randomised variant. For each n, we show that these randomised variants of the NFS and Coppersmith's multiple polynomial sieve find congruences of squares in expected times matching the best-known heuristic estimates. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free