Implementing 2-descent for Jacobians of hyperelliptic curves
Implementing the Round Four maximal order algorithm
Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions
La primalité en temps polynomial
Le problème de la primalité est l’un des problèmes les plus simples et les plus anciens de la théorie des nombres. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu’Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L’exposé présentera ces travaux, et il fera également le point sur les différents autres...
Nedávné poznatky o čísle
Nový pohled na algoritmickou matematiku
On Elkies subgroups of -torsion points in elliptic curves defined over a finite field
As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic , there exists an algorithm that computes, for an Elkies prime, -torsion points in an extension of degree at cost bit operations in the favorable case where .We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the -adic approach followed by Joux and Lercier to get an algorithm valid without any limitation...
On reduced Arakelov divisors of real quadratic fields
We generalize the concept of reduced Arakelov divisors and define C-reduced divisors for a given number C ≥ 1. These C-reduced divisors have remarkable properties, similar to the properties of reduced ones. We describe an algorithm to test whether an Arakelov divisor of a real quadratic field F is C-reduced in time polynomial in with the discriminant of F. Moreover, we give an example of a cubic field for which our algorithm does not work.
On Shank's algorithm for modular square roots.
On the discrete logarithm problem for plane curves
In this article the discrete logarithm problem in degree 0 class groups of curves over finite fields given by plane models is studied. It is proven that the discrete logarithm problem for non-hyperelliptic curves of genus 3 (given by plane models of degree 4) can be solved in an expected time of , where is the cardinality of the ground field. Moreover, it is proven that for every fixed natural number the following holds: We consider the discrete logarithm problem for curves given by plane models...
On the division polynomials of elliptic curves.
On the -th extension of the sieve of Eratosthenes.
On zero-testing and interpolation of sums of characters.
Relaxed algorithms for -adic numbers
Current implementations of -adic numbers usually rely on so called zealous algorithms, which compute with truncated -adic expansions at a precision that can be specified by the user. In combination with Newton-Hensel type lifting techniques, zealous algorithms can be made very efficient from an asymptotic point of view.In the similar context of formal power series, another so called lazy technique is also frequently implemented. In this context, a power series is essentially a stream of coefficients,...
Signed bits and fast exponentiation
An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...
Some doubly exponential sums over ℤₘ
Stapled sequences and stapling coverings of natural numbers.
Summatory function of the Möbius function. I: Experimental upper bounds. (Fonction sommatoire de la fonction de Möbius. I: Majorations expérimentales.)
Summatory function of the Möbius function. II: Elementary asymptotic upper bounds. (Fonction sommatoire de la fonction de Möbius. II: Majorations asymptotiques élémentaires.)
The discrete logarithm problem over prime fields: the safe prime case. The Smart attack, non-canonical lifts and logarithmic derivatives
We connect the discrete logarithm problem over prime fields in the safe prime case to the logarithmic derivative.