Search

Chudnovsky-type algorithms of multiplication in finite fields are well known for their good bilinear complexity. Recently, two advances have been obtained in the study of these algorithms: a strategy to optimize the scalar complexity of the original algorithm and the development of a generic recursive construction over the projective line. The construction of recursive Chudnodvsky-type algorithms over the projective line makes possible an efficient generic strategy to optimize their complexity (number of scalar and bilinear multiplications and additions in the base field). Then, several examples are given. In particular, considering Baum-Shokrollahi’s experiment (1992), this constructive method provides a Chudnovsky-type algorithm of multiplication in F 256 / F 4 \mathbb {F}_{256}/\mathbb {F}_4 with the best known complexity, while being much more efficient than existing optimization methods.

International audience

International audience; The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear with respect to the degree of the extension. Recently, Ran-driambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this article, we first translate this generalization into the language of algebraic function fields. Then, we propose a strategy to effectively construct asymmetric algorithms using places of higher degrees and without derivated evaluation. Finally, we provide examples of three multiplication algorithms along with their Magma implementation: in F 16 13 using only rational places, in F 4 5 using also places of degree two, and in F 2 5 using also places of degree four.

We propose a Recursive Polynomial Generic Construction (RPGC) of multiplication algorithms in any finite field $\mathbb{F}_{q^n}$ based on the method of D.V. and G.V. Chudnovsky specialized on the projective line. They are usual polynomial interpolation algorithms in small extensions and the Karatsuba algorithm is seen as a particular case of this construction. Using an explicit family of such algorithms, we show that their bilinear complexity is quasi-linear with respect to the extension degree n, and we give a uniform bound for this complexity. We also prove that the construction of these algorithms is deterministic and can be done in polynomial time. We give an asymptotic bound for the complexity of their construction., Comment: 30 pages

We propose a new construction for the multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve scalar algebraic complexity. In particular, we improve the Baum-Shokrollahi construction for multiplication in F256/F4 based on the elliptic Fermat curve x 3 + y 3 = 1.

The percentage of disabled persons pursuing their studies up to an engineering level degree is very low in France. At the same time, companies perceive a shortage of computer engineers. In order to fill this injustice and this economic need, Aix-Marseille University and a collective including big companies have joined forces to create an engineering training dedicated to disabled persons. The implementation and management of such training is complex because, on the one hand, the number of actors involved in the project is large and, on the other hand, some actors have to learn to work together. The objective of this article is to formulate a number of recommendations and pitfalls to avoid in order to facilitate, at the pedagogical level, the implementation of similar trainings. The main aim is to enable students to give their best and prevent dropouts. This article also contains a brief feedback on the HUGo training.; Le pourcentage de personnes en situation de handicap poursuivant leurs études jusqu'à un diplôme de niveau I est très faible en France. Parallèlement, les entreprises perçoivent un manque d'ingénieurs informaticiens. Afin de combler cette injustice et ce besoin économique, l'Université d'Aix-Marseille et un collectif comprenant de grandes entreprises se sont associés pour créer une formation d'ingénieurs dédiée aux personnes en situation de handicap. La mise en place et la gestion d'une telle formation sont complexes car d'une part, le nombre d'acteurs impliqués dans le projet est important et d'autre part, certains acteurs doivent apprendre à travailler ensemble. L'objectif de cet article est de formuler un certain nombre de recommandations et de pièges à éviter afin de faciliter, au niveau pédagogique, la mise en place de formations similaires. Il s'agit principalement de permettre aux élèves de tirer le meilleur d'eux mêmes et de prévenir les abandons. Cet article contient également un retour d'expérience succinct concernant la formation HUGo.

International audience; We propose a new construction for the multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve scalar algebraic complexity. In particular, we improve the Baum-Shokrollahi construction for multiplication in F256/F4 based on the elliptic Fermat curve x 3 + y 3 = 1.

Discussions about the choice of a tree hash mode of operation for a standardization have recently been undertaken. It appears that a single tree mode cannot address adequately all possible uses and specifications of a system. In this paper, we review the tree modes which have been proposed, we discuss their problems and propose solutions. We make the reasonable assumption that communicating systems have different specifications and that software applications are of different types (securing stored content or live-streamed content). Finally, we propose new modes of operation that address the resource usage problem for three representative categories of devices and we analyse their asymptotic behavior., IACR Transactions on Symmetric Cryptology, Volume 2017, Issue 4

International audience; Presented by the Editorial Board The Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity uniformly linear with respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this note, we describe the construction of this asymmetric method without derived evaluation. To do this, we translate this generalization into the language of algebraic function fields and we give a strategy of construction and implementation.; L'algorithme de multiplication dans les corps finis de Chudnovsky a une complexité bilinéaire uniformément linéaire en le degré de l'extension. Randriambololona a récemment généralisé cette méthode en introduisant l'asymétrie dans la procédure d'interpolation et en obtenant ainsi de nouvelles bornes sur la complexité bilinéaire. Dans cette note, nous décrivons la construction de cette méthode asymétrique sans évaluation dérivée. Pour ce faire, nous traduisons cette généralisation dans le langage des corps de fonctions algébriques, et nous donnons une stratégie de construction et d'implantation.

The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear whith respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. We describe the effective algorithm of this asymmetric method, without derivated evaluation. Finally, we give examples with the finite field $\F_{16^{13}}$ using only rational places, $\F_{4^{13}}$ using also places of degree two and $\F_{2^{13}}$ using also places of degree four., Comment: arXiv admin note: text overlap with arXiv:1510.00090

Thanks to a new construction of the so-called Chudnovsky-Chudnovsky multiplication algorithm, we design efficient algorithms for both the exponentiation and the multiplication in finite fields. They are tailored to hardware implementation and they allow computations to be parallelized while maintaining a low number of bilinear multiplications. We give an example with the finite field ${\mathbb F}_{16^{13}}$.

International audience; The concept of randomness is fundamental in many domains and in particular in cryptography. Intuitively, a system, which is unpredictable is more difficult to attack and as a consequence, creating sequences that look like random represents a major issue. In this paper, we first study theoretically how a source of symbols with positive entropy can be turned into a true random generator called Bernoulli. We concentrate on a special type of generators, which consists in randomly choosing k elements out of n elements. After studying some existing algorithms, which are of Las Vegas type, we introduce new constructions from a binary generator taken as a primary random source of symbols. Our method is based on combinatorial block designs and we construct algorithms of Monte Carlo type involving random walks. We analyze in detail properties of our general method. Several explicit constructions of k-out-of-n generators are given. We show that the speed of convergence to the uniform distribution is better than any known method using algorithms with bounded running times.