summary in french

We present a FDECM algorithm allowing to remove — if they exist — all prime factors less than 2³² from a composite input number n. Trying to remove those factors naively either by trial-division or by multiplying together all primes less than 2³², then doing a GCD with this product both prove extremely slow and are unpractical. We will show in this article that with FDECM it costs about a hundred well-chosen elliptic curves, which can be very fast in an optimized ECM implementation with optimized B₁ and B₂ smoothness bounds. The speed varies with the size of the input number n. Special attention has also been paid so that our FDECM be the most implementation-independent possible by choosing a widespread elliptic-curve parametrization and carefully checking all results for smoothness with Magma. Finally, we have considered possible optimizations to FDECM first by using a rational family of parameters for ECM and then by determining when it is best to switch from ECM to GCD depending on the size of the input number n. To the best of our knowledge, this is the first detailed description of a fully deterministic ECM algorithm.

summary in french

This presentation is about a kind of ordinary elliptic curves introduced by Scott at INDOCRYPT 2005. These curves' CM discriminant is -3 or -1, then they have endomorphism for reducing Miller's loop length to half. These curves are also restricted in terms of the form of group order. Therefore, these are generated by Cocks-Pinch method. Cocks-Pinch method is a general method to obtain elliptic curve parameters with rho-value approximately 2. This method enables to fix group order, CM disciminant and embedding degree in advance as long as they meet the requirements. Elliptic curves introduced by Scott with CM discriminant -3, they were investigated by Scott and Takashima but CM discriminant -1 are not. In this presentation, we show the result of generating curve parameters with CM discriminant -1 and what amount of parameters meet the requirements.

One of the primary uses of lattice reduction algorithms is to approximate short vectors in a lattice. I present a new algorithm which produces approximations of short vectors in certain lattices. It does this by generating a reduced basis of a sub-lattice which is guaranteed to contain all short vectors in the given lattice. This algorithm has a complexity which is less dependent on the size of the input basis vectors and more dependent on the size of the output vectors.
To illustrate the usefulness of the new algorithm I will show how it can be used to give new complexity bounds for factoring polynomials in Z[x] and reconstructing algebraic numbers from approximations.

summary in french

The Maximal Determinant Problem was first posed around 1898. It asks for a square matrix of largest possible determinant, with the entries of the matrix restricted to be drawn from the set {0, 1}, or equivalently {+1, -1}.
Emperical investigations show an intriguing amount of structure in this problem, both in the numerical sequence of maximal determinants, and in the corresponding maximal determinant matrices themselves. But naive brute force search becomes infeasible beyond very small orders, due to the exponential nature of the search space.
High and maximal determinant matrices are useful in applications, particularly in statistics, which is one reason why it is desirable to have at hand a means of constructing these matrices. For certain sparse infinite subsequences of orders, constructive algorithms have been found - some relating to finite fields. However progress over the last one hundred years has been distinctly patchy, depending on elementary number theoretic properties of the matrix order: particularly its remainder upon division by four.
We discuss ways of setting up computations which may be feasible with current computing power and yet still yield new maximal determinant matrices that would not be accessible to a naive search.

Originally introduced in cryptography by Menezes, Okamoto and Vanstone (1993) then Frey and Rück (1994) to attack the discrete logarithm problem over a particular class of elliptic curves, pairings have since then been put to a constructive use in various useful cryptographic protocols such as short digital signature or identity-based encryption. However, evaluating these pairings relies heavily on finite field arithmetic, and their computation in software is still expensive. Developing hardware accelerators is therefore crucial.
In the second part of this double-talk, we will focus on the other end of the hardware design spectrum. While the first part (given by Jean-Luc Beuchat) presented a co-processor which, although quite slow, would strive to minimize the amount of hardware resources required to compute the Tate pairing, in this second part we will describe another co-processor architecture, designed to achieve much lower computation times, at the expense of hardware resources.

Originally introduced in cryptography by Menezes, Okamoto and Vanstone (1993) then Frey and Rück (1994) to attack the discrete logarithm problem over a particular class of elliptic curves, pairings have since then been put to a constructive use in various useful cryptographic protocols such as short digital signature or identity-based encryption. However, evaluating these pairings relies heavily on finite field arithmetic, and their computation in software is still expensive. Developing hardware accelerators is therefore crucial.
In this talk, we will then present a hardware co-processor designed to accelerate the computation of the Tate pairing in characteristics 2 and 3. As the title suggests, this talk will emphasize on reducing the silicon footprint (or in our case the usage of FPGA resources) of the circuit to ensure scalability, while trying to minimize the impact on the overall performances.

summary in french

summary in french

Triangular representations are a versatile data structure; however, even basic arithmetic operations raise difficult questions with such objects. I will present an algorithm for multiplication modulo a triangular set that relies on deformation techniques and ultimately evaluation and interpolation. It features a quasi-linear running time (without hidden exponential factor), at least in some nice cases. More or less successful applications include polynomial multiplication, operations on algebraic numbers and arithmetic in Artin-Schreier extensions.

http://www.jjj.de/arctan/arctanpage.html

summary in french

summary in french

summary in french

summary in french

In 1996, Coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations. One technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. Since then, these methods have been used in a huge variety of cryptanalytic applications. Some applications also use extensions of Coppersmith's techniques on more variables. However, these extensions are heuristic methods.
In this presentation, we present and analyze a new variation of Coppersmith's algorithm on three variables over the integers. We also study the applicability of our method to short RSA exponents attacks. In addition to lattice reduction techniques, our method also uses Gröbner bases computations. Moreover, at least in principle, it can be generalized to four or more variables.

summary in french

summary in french

summary in french

summary in french

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area. In this talk, we first describe an accelerator for the $\eta_T$ pairing over $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$. Our architecture is based on a unified arithmetic operator which performs addition, multiplication, and cubing over $\mathbb{F}_{3^{97}}$. This design methodology allows us to design a compact coprocessor ($1888$ slices on a Virtex-II Pro~$4$ FPGA) which compares favorably with other solutions described in the open literature. We then describe ways to extend our approach to any characteristic and any extension field.
The talk will be based on the following research reports:

• http://eprint.iacr.org/2007/091
• http://eprint.iacr.org/2007/045
• http://eprint.iacr.org/2006/327

Let K be an imaginary quadratic field with Hilbert class field H and maximal order OK. We consider elliptic curves E defined over H with the properties that the endomorphism ring of E is isomorphic to OK and E is isogenous to E over H for all \sigma\in Gal(H/K). Taking the Weil restriction W_{H/K} of such an E from H to K, one obtains an abelian variety whose endomorphism ring will be either a field or a quaternion algebra. The question of which quaternion algebras may be obtained in this way is one of our motivations.
For quaternion algebras to occur, the class group of K must have non-cyclic 2-Sylow subgroup, the simplest possible examples occuring when K has class number 4. In this case, investigating when W_{H/K}(E) has a non-abelian endomorphism algebra is closely related to finding extensions L/H such that Gal(L/K) is either the dihedral or quaternion group of order 8.

summary in french

The $j$-invariant of an elliptic curve with complex multiplication by $K$ is well-known to generate the Hilbert class field of $K$. Such $j$-invariants, or rather their minimal polynomials in $\ZZ[x]$, can be determined by means of complex analytic methods from a given CM lattice in $\CC$. A construction of CM moduli by $p$-adic lifting techniques was introduced by Couveignes and Henocq. Efficient versions of one-dimensional $p$-adic lifting were developed by Br\"oker. These methods provide an alternative application of $p$-adic canonical lifts, as introduced by Satoh for determining the zeta function of an elliptic curves $E/\FF_{p^n}$.

Construction of such defining polynomials for CM curves is an area of active interest for use in cryptographic constructions. Together with Gaudry, Houtmann, Ritzenthaler, and Weng, we generalised the elliptic curve CM construction to genus 2 curves using $2$-adic canonical lifts. The output of this algorithm is data specifying a defining ideal for the CM Igusa invariants $(j_1,j_2,j_3)$ in $\ZZ[x_1,x_2,x_3]$. In contrast to Mestre's AGM algorithm for determining zeta functions of genus 2 curves $C/\FF_{2^n}$, this construction pursues the alternative application of canonical lifts to CM constructions. With Carls and Lubicz, I developed an analogous $3$-adic CM construction using theta functions. In this talk I will report on recent progress and challenges in extending and improving these algorithms.

summary in french

Schönhage proposed in the paper "Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2" (Acta Informatica, 1977) an O(n log(n) log(log(n))) algorithm to multiply polynomials over GF(2)[x]. We describe that algorithm and report on its implementation in NTL.

Abstract: We describe a new multi-level blocking algorithm for distinct-degree factorization of polynomials over GF(2). The idea of the algorithm is to use one level of blocking to replace most GCD computations by multiplications, and a finer level of blocking to replace most multiplications by squarings (which are much faster than multiplications over GF(2)). As an application we give an algorithm that searches for all irreducible trinomials of given degree. Under plausible assumptions, the expected running time of this algorithm is much less than that of the classical algorithm. For example, our implementation gives a speedup of more than 60 over the classical algorithm for trinomials of degree 6972593 (a Mersenne exponent). [Joint work with Paul Zimmermann.]

Isogenies — surjective homomorphisms of algebraic groups with finite kernel — are of great interest in number theory and cryptography. Algorithms for computing with isogenies of elliptic curves are well-known, but in higher dimensions, the situation is more complicated, and few explicit examples of non-trivial isogenies are known. We will discuss some of the computational issues, and describe some examples and applications of isogenies of Jacobians of hyperelliptic curves.

summary in french

summary in french

summary in french

summary in french

summary in french

Shift registers are very common hardware devices. They are always associated with a combinatorial/sequential feedback. Linear Feedback Shift Registers (LFSRs) are certainly the most famous setup amongst those circuits. LFSRs are used everywhere in communication systems: scramblers, stream-ciphers, spread spectrum, Built-in Self Test (BIST)... Despite their popularity, the impact of LFSRs characteristics has never been clearly studied. I have studied the LFSRs synthesis on Xilinx Spartan2E FPGA with several goals (area, critical path, throughput). Studying high throughtput synthesis is particularly interesting since it is a circuitous way to study software synthesis. I will describe which properties can be observed for both synthesis. In conclusion, other shift registers setups will be considered like Feedback with Carry Shift Registers (FCSRs) or Non Linear Feedback Shift Registers (NLFSRs).

Using Deurings theory of correspondences we are able to construct homomorphisms between the degree zero classgroups of function fields. Correspondences are divisors of function fields with transcendent constant fields of degree one. They form an entire ring which is for example in the case of elliptic function fields isomorphic to an order of an imaginary quadratic number field. In this talk we show how to compute endomporphisms of elliptic and hyperelliptic curves using correspondences.

summary in french

summary in french

In a factor ring, i.e., in a polynomial ring F[z]/(m) or the integer ring Z_n, the conventional way of performing division a/b consists of two steps: first, the inverse b^{-1} is computed and then the product ab^{-1}. In this talk we describe a technique called "direct division" which computes the division a/b for given a,b directly, only using addition and multiplication in the underlying structure, i.e., finite field operations in F for the polynomial ring F[z]/(m) and addition and multiplication by 2 in the integer ring Z_n. This technique requires that the module m is not divisible by z, and the module n is odd.

summary in french

TBA

summary in french

summary in french

The enhanced standard continuation of the P-1, P+1 and ECM factoring methods chooses pairs (a,b), where a is a multiple of a suitably chosen d, so that every prime in the desired stage 2 interval can be written as a-b. Montgomery [1] showed how to include more than one prime per (a,b) pair by instead evaluating f(a)-f(b) so that this bivariate polynomial has algebraic factors. However, he restricts his analysis to the algebraic factors a-b and a+b, and considers only prime values taken by these factors. We present a framework for generalising Montgomery's ideas by choosing (a,b) pairs as nodes in a partial cover of a bipartite graph, which allows utilising large prime factors of composite values, and algebraic factors of higher degree.
[1] P. L. Montgomery, Speeding the Pollard and elliptic Curve Methods of factorization, Math. Comp. 48 (177), 1987.

summary in french

The talk surveys various algorithms for computing in the divisor class groups of general non singular curves and gives a running time discussion.

summary in french

summary in french

Digital signatures have the sometimes unwanted property of being universally verifiable by anybody having access to the signer's public key. In recent work with F. Laguillaumie and P. Pailler, we have proposed a signature scheme where the verification requires interaction with the signer. Its security relies on the « xyz » variant of the classical Diffie-Hellman problem. We present in this talk the underlying algorithmical problem within its cryptographical context, and give some assessment of its difficulty

A curve of genus g defined over the complex field C is isomorphic to a torus with g holes, or equivalently to a quotient of the form C^g/(Z^g.1⊕Z^g.τ), τ being a g×g matrix called a Riemann matrix.

When the genus g equals one, the computation of τ from the equation of an elliptic curve is one of the classical applications of the arithmetico-geometric mean (AGM). The AGM can be interpreted using functions called theta constants.

We show how this special case extends to higher genus, using a generalization of the AGM known as the Borchardt mean.

In particular, we develop an algorithm for computing genus 2 Riemann matrices in almost linear time. This algorithm can be implemented easily.

As we also show, this technique allows for rapid computation of modular forms and functions, and we discuss the applications thereof (construction of CM curves, explicit computation of isogenies, …).