This page is an archive of the abstracts and slides of the CADO workshop on integer factorization that was held in INRIA Nancy Grand-Est / LORIA, Villers-lès-Nancy, France, on Oct 7--9, 2008. The workshop is now over.
Workshop organizers: Pierrick Gaudry, François Morain, Gérald Tenenbaum, Emmanuel Thomé, Paul Zimmermann. Local arrangements: Anne-Lise Charbonnier
Invited talks:
- Kazumaro Aoki, Numbers related to NFS
- Daniel J. Bernstein, Predicting NFS time
- Thorsten Kleinjung, Polynomial selection
- Reynald Lercier, Discrete Logarithms and Galois Invariant Smoothness Basis
- Peter L. Montgomery, Preliminary Design of Post-Sieving Processing for RSA-768
- Jason S. Papadopoulos, A Self-Tuning Filtering Implementation for the Number Field Sieve
Contributed talks:
- Joppe Bos, Cryptanalysis on a PlayStation 3 Cluster
- Peter Birkner, Edwards Curves and the ECM Factorisation Method
- Cécile Dartyge, Friable values of binary forms
- Alexander Kruppa, Factoring into large primes with P-1, P+1 and ECM
- Tanja Lange, ECM on graphics cards
- Patrick Stach, Optimizations to NFS Linear Algebra
Abstracts for invited talks#
Kazumaro Aoki, Numbers related to NFS#
NFS requires a large amount of parameters. Though the order of the parameters is known, setting optimal values requires some art. Not much data from large integer factorizations is available, however experimentalists are helped a lot by seeing the numbers. I provide as detailed figures as I have, including the following topics:
- experimental results generated from factorization of c176 in 11,281+, 2. Mixed special-Q usage of algebraic side and rational side,
- Experiences of hardware failures in long term factorization,
- R311 ECM.
Daniel J. Bernstein, Predicting NFS time#
The time \( T(n,f,y_1,\ldots) \) used by NFS depends not only on the integer $n$ to be factored but also on various parameters chosen by the NFS user, such as a polynomial \( f \), an initial smoothness bound \( y_1 \), etc. One can accurately compute \( T(n,f,y_1,\ldots) \) by running NFS, but of course this is rather slow, especially if one wants to compute several values of this function \( T \). I'll discuss the speed and accuracy of various approximations to \( T \).
Thorsten Kleinjung, Polynomial selection#
This talk will describe some tricks for polynomial selection for GNFS. An analysis and some results will also be given.
Reynald Lercier, Discrete Logarithms and Galois Invariant Smoothness Basis#
The difficulty of computing discrete logarithms in the multiplicative
group of finite fields GF(q) with the function field sieve relies
mostly on the ability of finding relations between elements of a
smoothness basis. We noticed in the past that in some very
particularly cases (Kummer and Artin-Schreier theories), the factor
basis can be constructed in such a way that it is left invariant by
automorphisms of GF(q). This significantly accelerates discrete
logarithm computations since it turns out that in such cases the
dimensions of the linear system to be solved at the end of the
computation is much smaller. In this talk, we are going to explain
how this nice property can be generalized to a broad class of finite
fields.
(joint work with J.-M. Couveignes)
Peter L. Montgomery, Preliminary Design of Post-Sieving Processing for RSA-768#
The security of the RSA cryptosystem relies on the believed difficulty of factoring large composite integers. About eight sites are attempting to factor RSA-768, a 768-bit challenge number. The best known algorithm is the Number Field Sieve, whose current record is 663 bits. Existing software needs upgrades to 64-bit manycore systems. I will describe some proposed algorithmic adjustments as we work to meet this challenge on state-of-the-art hardware.
Jason S. Papadopoulos, A Self-Tuning Filtering Implementation for the Number Field Sieve#
This talk will describe the NFS filtering module of Msieve, an integer factorization library that has helped complete some of the largest public factorizations. This module performs the task of building a linear algebra problem from the collection of relations produced by NFS sieving. NFS filtering is highly memory-intensive, and the quality of the solution found typically depends on the character of the input dataset, user experience, and the values of many internal parameters. Msieve's filtering is designed to be memory-efficient and completely automatic, with no user tuning expected, and produces matrix solutions of significantly higher quality compared to published results. We will cover the algorithmic techniques that make this adaptive behavior possible, as well as ideas that can potentially further improve the result quality.
Abstracts for contributed talks#
Joppe Bos, Cryptanalysis on a PlayStation 3 Cluster#
The Cell Broadband Engine (Cell) Architecture is the heart of the PlayStation 3 (PS3) video game console. In this presentation more technical details about the Cell are given. It is explained how the SIMD organization inside the PS3 can be used in order to obtain high-performance cryptanalytic algorithms. Examples are high-throughput hashing, factorization using the elliptic curve method and solving the elliptic curve discrete logarithm problem using the Pollard rho method.
Peter Birkner, Edwards Curves and the ECM Factorisation Method#
The ECM method, introduced about 20 years ago by Lenstra, is one of the best algorithms for factoring integers. This method employs elliptic curves, usually in Montgomery form, to find a factor of a given integer. The recently introduced Edwards and Twisted Edwards curves offer very efficient arithmetic and can improve the speed of the ECM algorithm. We give a brief overview of the ECM method and Edwards curves, and show how to construct Edwards curves which are suitable for ECM, that is, Edwards curves with large torsion and positive rank over Q.
Cécile Dartyge, Friable values of binary forms#
joint work with Antal Balog (Budapest), Valentin Blomer (Göttingen–Toronto), Gérald Tenenbaum (IECN Nancy).Let \( P^+(n) \) denote the greatest prime factor of a natural integer \( n \), with the convention that \( P^+(1)=1 \). An integer \( n \) is said to be \( y \)-friable if \( P^+(n)<=y \).
A standard conjecture in probabilistic number theory is that the values of an irreducible polynomial in one or many variables behave statistically as a random integer of similar size. Accordingly, it is expected that, given any binary form \( F \) and a real number \( \epsilon >0 \), we have \( P^+(F(a,b))<\max(a,b)^\epsilon \) for a positive proportion of positive integers \( (a,b) \).
We establish this conjecture in the case of cubic, reducible binary forms.
When \( F \) is either cubic irreducible or has degree \( \geq 4 \), we show that there exists a non trivial exponent \( \alpha_F \) such that, for every \( \epsilon>0 \), we have \( |\{1\leq a,b\leq x, P^+(F(a,b))<x^\alpha_F+\epsilon\}|\asymp x^2\quad (x\geq1). \) In particular, we show that, if \( F \) is irreducible and has degree \( d>=3 \), then the value \( \alpha_F = d-2 \) is admissible.
Alexander Kruppa, Factoring into large primes with P-1, P+1 and ECM#
This talk presents an implementataion of the P-1, P+1 and Elliptic Curve Methods for factoring into large primes in the NFS sieving phase. It describes some optimizations used in the implementation, considerations for parameter selection for individual methods, and how to combine methods into efficient factoring strategies.
Tanja Lange, ECM on graphics cards#
no abstract
Patrick Stach, Optimizations to NFS Linear Algebra#
This talk aims to address some of the algorithmic, arithmetic, and I/O bottlenecks associated with the Block Wiedemann algorithm with respect to large matrices. Items to be discussed include scaling Block Wiedemann and Block Lanczos, considerations on modern x86 hardware, considerations on modern GPU hardware, and optimizing distributed computation of matrix vector products.