ECM on Graphics Cards

This paper reports record-setting performance for the elliptic-curve method of integer factorization: for example, 926.11 curves/secondfor ECM stage 1 with B1 = 8192 for 280-bit integers on a single PC.The state-of-the-art GMP-ECM software handles 124.71 curves/secondfor ECM stage 1 with B1 = 8192 for 280-bit integers using all four coresof a 2.4 GHz Core 2 Quad Q6600.The extra speed takes advantage of extra hardware, specifically twoNVIDIA GTX 295 graphics cards, using a new ECM implementationintroduced in this paper. Our implementation uses Edwards curves, re-lies on new parallel addition formulas, and is carefully tuned for thehighly parallel GPU architecture. On a single GTX 295 the implementation performs 41.88 million modular multiplications per second for ageneral 280-bit modulus. GMP-ECM, using all four cores of a Q6600,performs 13.03 million modular multiplications per second.This paper also reports speeds on other graphics processors: for exam-ple, 2414 280-bit elliptic-curve scalar multiplications per second on anolder NVIDIA 8800 GTS (G80), again for a general 280-bit modulus. Forcomparison, the CHES 2008 paper “Exploiting the Power of GPUs forAsymmetric Cryptography” reported 1412 elliptic-curve scalar multipli-cations per second on the same graphics processor despite having fewerbits in the scalar (224 instead of 280), fewer bits in the modulus (224instead of 280), and a special modulus (2224 ? 296 + 1).Keywords: Factorization, graphics processing unit, modular arithmetic,elliptic curves, elliptic-curve method of factorization, Edwards curves. * Permanent ID of this document: 6904068c52463d70486c9c68ba045839. Date of this document: 2009.01.27. This work was sponsored in part by the National ScienceFoundation under grant ITR–0716498, in part by Taiwan’s National Science Council(grants NSC-96-2221-E-001-031-MY3 and -96-2218-E-001-001, also through the Tai-wan Information Security Center NSC-97-2219-E-001-001, -96-2219-E-011-008), andin part by the European Commission through the ICT Programme under ContractICT–2007–216676 ECRYPT II. Part of this work was carried out while Bernsteinand Lange visited NTU. The elliptic-curve method (ECM) of factorization was introduced by Lenstrain [34] as a generalization of Pollard’s p ? 1 and Williams’ p + 1 method. Manyspeedups and good choices of elliptic curves were suggested and ECM is now themethod of choice to find factors in the range 1010 to 1060 of general numbers.The largest factor found by ECM was a 222-bit factor of the 1266-bit number10381 + 1 found by Dodson (see [49]).Cryptographic applications such as RSA use “hard” integers with much largerprime factors. The number-field sieve (NFS) is today’s champion method of find-ing those prime factors. It was used, for example, in the following factorizations:integer bitsdetails reportedRSA–130 430at ASIACRYPT 1996 by Cowie et al. [16]RSA–140 463at ASIACRYPT 1999 by Cavallar et al. [12]RSA–155 512at EUROCRYPT 2000 by Cavallar et al. [13]RSA–200 663in 2005 posting by Bahr et al. [4]21039 ? 1 1039 (special) at ASIACRYPT 2007 by Aoki et al. [2]A 1024-bit RSA factorization by NFS would be considerably more difficult thanthe factorization of the special integer 21039 ? 1 but has been estimated to bedoable in a year of computation using standard PCs that cost roughly $1 billionor using ASICs that cost considerably less. See [43], [35], [19], [22], [44], and [29]for various estimates of the cost of NFS hardware. Current recommendations forRSA key sizes — 2048 bits or even larger — are based directly on extrapolationsof the speed of NFS.NFS is also today’s champion index-calculus method of computing discretelogarithms in large prime fields, quadratic extensions of large prime fields, etc.See, e.g., [26], [27], and [5]. Attackers can break “pairing-friendly elliptic curves”if they can compute discrete logarithms in the corresponding “embedding fields”;current recommendations for “embedding degrees” in pairing-based cryptogra-phy are again based on extrapolations of the speed of NFS. See, e.g., [30].NFS factors a “hard” integer n by combining factorizations of many smallerauxiliary “smooth” integers. For example, the factorization of RSA-155 ? 2512generated a pool of ? 250 auxiliary integers < 2200, found ? 227 “smooth” inte-gers factoring into primes < 230, and combined those integers into a factorizationof RSA-155. See [13] for many more details.

how to setting a graphic card, how to overclock graphic card, graphics processing unit overclock, factorization doc, largest factor using ecm, ecm card for mercedes