Euclidean algorithm

Summary

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5

Official source

https://en.wikipedia.org/wiki/Euclidean_algorithm

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (37)

Related publications

Related people

Related units

Related concepts (76)

Related concepts

Related courses (57)

Related courses

Related lectures (142)

Related lectures

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

Exceptional units and Euclidean number fields

Julien Houriet

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

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