Algorithme d'Euclide

Résumé

En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres. Histoire vignette|Peinture censée représenter le mathématicien Euclide d'Alexandrie, par Justus of Ghent. Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes. Il est décrit dans le livre VII (Proposition 1-3) des Éléments d'Euclide (vers 300 av. J.-C.) sous la forme de l'anthyphérèse. Il est aussi décrit dans le livre X (Proposition 2), mais pour un problème de façon géométrique : comment trouver une « unité de mesure » commune pour deux longueurs de segments. Il procède par soustractions répétées de la longueur du plus court segment sur la longueur du plus long. Cela correspond à une adaptation de la méthode naïve de calcul de la divisio

Source officielle

https://fr.wikipedia.org/wiki/Algorithme_d'Euclide

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (37)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (76)

Concepts associés

Chargement

Cours associés (57)

Cours associés

Chargement

Séances de cours associées (142)

Afficher plus

Séances de cours associées

Chargement

Arithmetic Bounds-Lenstra's Constant and Torsion of K-Groups

Julien Houriet

This thesis is concerned with computations of bounds for two different arithmetic invariants. In both cases it is done with the intention of proving some algebraic or arithmetic properties for number fields. The first part is devoted to computations of lower bounds for the Lenstra's constant. For a number field K the Lenstra's constant is denoted Λ(K) and defined as the length of the largest exceptional sequence in K. An exceptional sequence is a set of units in K such that for any two among them their difference is a unit as well. H.W. Lenstra showed that if Λ(K) is large enough – bigger than a constant depending on the degree and the discriminant of K – then the ring of integers of K is Euclidean with respect to the norm. Using computer software PARI/GP and some algorithms from graph theory we construct exceptional sequences in number fields having a small discriminant. These exceptional sequences yield lower bounds for Lenstra's constant which are large enough to prove the existence of 42 new Euclidean number fields of degree 8 to 12. The aim of the second part of this thesis is proving upper bounds for the torsion part of the K-groups of a number field ring of integers. A method due to C. Soulé yields bounds for the torsion of these K-groups depending on an invariant of hermitian lattices over number fields. Firstly we describe some properties of rank one hermitian lattices, especially of ideal lattices. Secondly we apply these properties to arbitrary rank hermitian lattices and this implies a significant improvement of the upper bounds for their invariants and accordingly for the torsion of K-groups. The progress mainly achieves much lower contributions of the number field attributes, particularly the degree and the absolute discriminant.

EPFL2010

Chargement

Exceptional units and Euclidean number fields

Julien Houriet

Springer, Birkhäuser-Verlag; www.birkhäuser.ch2007

Chargement

A Family of Fast Syndrome Based Cryptographic Hash Functions

Recently, some collisions have been exposed for a variety of cryptographic hash functions including some of the most widely used today. Many other hash functions using similar constructions can however still be considered secure. Nevertheless, this has drawn attention on the need for new hash function designs. In this article is presented a family of secure hash functions, whose security is directly related to the syndrome decoding problem from the theory of error-correcting codes. Taking into account the analysis by Coron and Joux based on Wagner's generalized birthday algorithm we study the asymptotical security of our functions. We demonstrate that this attack is always exponential in terms of the length of the hash value. We also study the work-factor of this attack, along with other attacks from coding theory, for non asymptotic range, i.e. for practical values. Accordingly, we propose a few sets of parameters giving a good security and either a faster hashing or a shorter description for the function.

2005

Chargement