#
CADO workshop on integer factorization

INRIA Nancy Grand-Est – LORIA, Villers-lès-Nancy, France

October 7 – 9, 2008

#
CADO workshop

October 7 – 9, 2008

The workshop is now over.

## 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: 1. experimental results generated from factorization of c176 in 11,281+, 2. Mixed special-Q usage of algebraic side and rational side, 3. Experiences of hardware failures in long term factorization, 4. R311 ECM.

### Daniel J. Bernstein

Predicting NFS time

The time T(n,f,y1,...) 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 y1, etc. One can accurately compute T(n,f,y1,...) 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*. An integer

^{+}(1)=1*n*is said to be

*y*-friable if

*P*.

^{+}(n)<=yA 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

*ε >0*, we have

*P*for a positive proportion of positive integers

^{+}(F(a,b))<max(a,b)^{ε}*(a,b)*.

We establish this conjecture in the case of cubic, reducible binary forms.

When

*F*is either cubic irreducible or has degree

*>=4*, we show that there exists a non trivial exponent

*α*such that, for every

_{F}*ε>0*, we have

*|{1<=a,b<=x : P*In particular, we show that, if

^{+}(F(a,b))<x^{αF+ε}}|\asymp x^2 (x>=1).*F*is irreducible and has degree

*d>=3*, then the value

*α_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.

© 2008 Emmanuel Thomé ; XHTML 1.0 valide, CSS valide