User:Randomblue/tmp2

In mathematics and more precisely in algebraic number theory, modular arithmetic is a set of methods allowing one to solve problems concerning the integers. These methods derive from the study of the remainder obtained after applying a Euclidean division.

Even though its origins may be retraced to antiquity, historians generally associate its birth with the year 1801, date of publication of Carl Friedrich Gauss's book Disquisitiones Arithmeticae (Latin, "Arithmetical Investigations"). His new approach, based on a greater abstraction, helped verify famous conjectures and simplify the proof of important results. Despite number theory being the natural domain of these methods, the consequences of Gauss's ideas spread in other fields such as algebra and geometry.

The 20th century changed the status of modular arithmetic. On the one hand, other methods were necessary to progress in number theory. On the other, the development of many industrial applications forced the creation of algorithms using modular arithmetic techniques. These essentially resolved questions brought up by information theory, a branch now mainly considered as applied mathematics.

History

Origins

In the third century BC, Euclid formalizes in his book the Elements the foundations of arithmetic. Therein we find Euclid's lemma and a dated version of the fundamental theorem of arithmetic and a study of the perfect numbers in the proposition 36 of the book IX. Diophantus of Alexandria wrote the Arithmetica containing 130 equations. He deals essentially with problems having a unique integer or fractional solution. The fact that the numbers which are sum of two squares are never of the form n + 3 are also discussed. The equations with integer coefficients and whose sought solutions are also integers are nowadays called diophantine equations.

China developed at the same time a modular arithmetic. Sun Tzu wrote in approximately 300 a major mathematical treatise where the problem 26 of chapter 3 reads as follow: "Given objects where the total number is unknown. When counting them 3 by 3, 2 remain, when counting them 5 by 5, 3 remain and when counting them 7 by 7, 2 remain. How many objects are there?"

Qin Jiushao developed the Chinese remainder theorem. His treatise is remarkably advanced. It deals with a system of linear equations of congruencesin the case where the moduli are not pairwise coprime. His works on the system of congruences supersede those of Leonhard Euler. We can cite George Sarton for whom: "Qin Jiushao was one of the greatest mathematicians of the Chinese race of his time, and in fact of all times."

These results progressively decline in the 14th century and eventually get forgotten. The knowledge of Qin Jiushao does not pass the Chinese boundaries before the 20th century. It is rediscovered by the works of the science historian Joseph Needham. On the other hand, many similarities between Arab and Chinese notation suggest contacts during preceding periods.

India possesses as well a strong tradition in arithmetic. Aryabhata searches systematicallythe integer solutions of the integer coefficient linear equation with two unknowns. For this, he uses an algorithm called Kuttaka published in his book called Aryabhatiya. The diaphantine equations of degree two are studied by Brahmagupta using the chakravala method.

The Islamic civilisation plays a double role in arithmetic: it conveys the knowledge gained by the Greeks, Indians, Chinese and Europeans, and brings new knowledge especially in the study of the properties of certain sets of integers such as the prime numbers, the perfect numbers, the amicable numbers or the figurate numbers. In this context, Qusta ibn Lûqâ translates partially the Arithmetica of Diophantus; his colleague al-Khwārizmī writes a book on Indian numeration. The book was lost but a Latin translation remains, the Algoritmi de numero Indorum. Thābit studies the amicable numbers and the perfect numbers. Alhazen continues his work on the perfect numbers and discovers Wilson's theorem.

Appearance in Europe

Pierre de Fermat greatly developes arithmetic. The properties of Euclidean division, foundations of modular arithmetic, are largely used by this mathematician.

In 1621 Claude Gaspard Bachet de Méziriac (1581 - 1638) translates Diophantus's book in Latin. The questions posed interest the then contemporary mathematicians, especially the French ones. Pierre de Fermat (1601 - 1665) proposes a great deal of statements, the three most important probably being his last theorem, his theorem on sums of two squares and his little theorem. The scientific community chalenge each other on this topic, and Fermat asks : "A square number who, added to the sum of his divisors, equals a cube". He concludes that: I am waiting the solution to these questions; if they are not given neither by England, neither by Gaule Belgique or Celtique, it will be given by the Narbonnaise". Marin Mersenne (1588 - 1648) searched for special prime numbers. Fermat replies: "Si je puis une fois tenir la raison fondamentale que 3, 5, 7, 17, 257, 65537, …, sont nombres premiers, il me semble que je trouverai de très belles choses en cette matière, car j'ai déjà trouvé des choses merveilleuses dont je vous ferai part}}. These numbers are now called Fermat numbers and his sentence turned out to be the author's only incorrect conjecture. René Descartes (1596 - 1650) searches, without succeeding, to proove that if the division by eight of a prime number has remainder one or three, then it may be written in the form x² + 2y².

Sur ce type de problèmes, deux éléments sont remarquables :

• Les équations diophantiennes fascinent, le titre d'un des livres de Bachet de Méziriac est évocateur : Problèmes plaisants et délectables qui se font par les nombres, on peut citer encore la remarque de Fermat à propos de son grand théorème : {{Guillemets|J'ai trouvé une solution merveilleuse ...}}

• Les problèmes posés sont difficiles. Malgré quelques succès comme l'identité de Bézout probablement due à Bachet de Méziriac, l'essentiel des questions restent sans réponse, comme le théorème des deux carrés de Fermat, ou avec des réponses pour le moins peu convaincantes, comme celle de Fermat pour son grand théorème : {{Guillemets|... mais la place me manque ici pour la développer}} (la première preuve reconnue apparaîtra en 1994, 1995). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec : {{Guillemets|Je vous avoue tout net (car par avance je vous avertis que je ne suis pas capable de m'attribuer plus que je ne sais, je dis avec la même franchise ce que je ne sais pas) que je n'ai pu encore démontrer... cette belle proposition que je vous ai envoyée...}}

Methods used

Leonhard Euler, théoricien des nombres du XVIII^e siècle, résoud plusieurs équations diophantiennes.

The next century sees a revolution of some of these questions, often thanks to Leonhard Euler: he contradicts Fermat by proving that his numbers are not always prime, and proves the two squares theorem. . He also makes mistakes, his attempt to prove the Last theorem for n equal to three is a failure, his first proof is false. He raises other questions such as the law of quadratic reciprocity in 1782. Here again, despite a try by Adrien-Marie Legendre (1752 - 1833), no solution is found.

Jusqu'à l'aube du XIX^e siècle les méthodes utilisées, si elles dénotent une grande astuce chez les mathématiciens, sont finalement peu nombreuses et de principes simples. L'exemple suivant, tiré du problème des deux carrés, en illustre trois : existe-t-il un nombre dont la division par quatre donne pour reste trois et qui est somme de deux carrés ? Soit a² et b² ces deux carrés. Seul l'un est pair car sinon leur somme serait paire et sa division par 4 aurait soit 0 soit 2 comme reste. Supposons a pair et b impair. a est pair donc son carré est un multiple de 4. L'entier b est impair donc s'écrit 2c + 1, son carré est égal à 4c² + 4c + 1, la division de b² par quatre donne pour reste un et la somme des deux carrés donne aussi pour reste un.

• Le premier outil utilisé est celui des nombres premiers, ce raisonnement est exact car 2 est un nombre premier.
• Le deuxième est la transformation algébrique, b est transformé en 2c + 1. Utilisé avec virtuosité, il permet aux mathématiciens de l'époque de résoudre certaines équations diophantiennes. Toute l'astuce réside à choisir avec habileté les bonnes transformations.
• Le troisième est la division euclidienne, les carrés et leur somme sont systématiquement divisés par 4.
• Le quatrième n'est pas illustré dans l'exemple, il correspond à la descente infinie utilisée dans la démonstration d'Euler du théorème des deux carrés. Elle consiste à trouver à partir d'une solution entière positive une autre solution entière positive et plus petite. La suite des solutions descend de manière infinie dans l'ensemble des entiers positifs, ce qui n'est pas possible. Cette méthode fut déjà utilisée par Fermat pour démontrer son grand théorème dans le cas où n est égal à 4.

Le caractère rustique des outils se traduit par des démonstrations longues et techniques, comme par exemple la preuve d'Euler pour le théorème des deux carrés. De plus, et malgré plus d'un siècle d'efforts, l'essentiel des équations diophantiennes résistent à une telle approche.

Theoretical developments

Mathematical concepts, developed in some context, are frequently reused in other areas. For example, group theory is applied in arithmetic and geometry. In the same vein, the methods of modular arithmetic nourish many fields in pure mathematics, such as general algebra and Galois theory. These theories are not nonetheless regarded as special cases of modular arithmetic, for they use also numerous other concepts.

Quotient structure

Further information: Equivalence relation

In modern parlance, modular arithmetic is formalized by the notion of quotient of Euclidean domains. The concept of equivalence relation allows to generalize this concept to the main algebraic structures. For example, the quotient of a group by a normal subgroup is, via the Jordan-Hölder theorem, a basic method of classification of finite groups. Quotient groups are also used in algebraic topology to classify manifolds. In ring theory, the notion of ideals plays an analogous role to normal subgroups in group theory. It allows to construct quotient rings in a more general context than modular arithmetic. Hilbert's Nullstellensatz, underlying the link between commutative algebra and algebraic geometry can be expressed in terms of ideals.

The notions of congruence and modulus are nonetheless reserved for quotients of Euclidean rings.

Residues of polynomials and Galois theory

Further information: Galois theory

Évariste Galois is the founder of the theory bearing his name.

Modular arithemtics apply to a ring of polynomials in a field. It is the starting point of theory of Évariste Galois (1811 - 1832) and consists of the systematic study of the sets of moduli of irreducible polynomials, equivalent to prime numbers. These sets are nowadays called algebraic extensions.

These extensions allow the analysis of solvability of algebraic equations, i.e. equations which are written in polynomial form. If the polynomial is irreducible, its "ensemble de modulo" is the smallest field containing at least one root. It is called rupture field. Reiterating this process, a field containing all roots is constructed, the splitting field. The modular logic of the quotient establishes the algebraic structure which is adapted to this problem.

Galois theory is about many other notions. Studying the solvability of an equation is possible via the study of the automorphism group of the field, the so-called Galois group, thanks to the Galois connection between subfields and subgroups. Beyond the study of solvability of algebraic equations, Galois theory has become a natural framework of solving numerous problems in arithmetic, arithmetic geometry or algebraic geometry, and allows above all to formulate new, more general problems in various domains.

If this theory uses the concept of a quotient of an Euclidean ring, the variety of tools specific to the domain makes it a proper subject, well distinguished of this articles subject. Note that one of the fruits of the theory, finite fields, also called Galois fields, form a natural framework for many applications in modular arithmetic.

Algebraic integer and algebraic number theory

Further information: Algebraic number theory

Ernst Kummer shows Fermat's last theorem for many values of n and founds algebraic number theory.

Modular arithmetic offers a conceptually good framework for solving Fermat's grand theorem. Notwithstanding, if n is bigger than ten, the rings of algebraic integers, constructed with Gauss' method, show what Dirichlet calles an obstruction. He shows that the unit group of this ring, i.e. the elements having a multiplicative inverse, is no longer a cyclic group or finite abelian like the ones Gauss studied. It also contains copies of the ring of integers, hence it is infinite. This fact is referred to as Dirichlet unit theorem. The obstruction comes from this new configuration. It hinders the application of modular techniques used for Gaussian integers because the associated ring is no longer Euclidean.

Ernst Kummer (1810 - 1893) uses a method tied to the generalisation of the quotient now formalised by ideals. The replace the absend prime numbers. Algebraic number theory then goes on, with different techniques. The basic tool is a ring which elements are called algebraic integers and which possesses a so-called Dedekind ring structure. That way, Kummer is able to show the grand theorem for certain prime values n, namely the regular primes. The only values less than 100 not covered are 37, 59 and 67.

Other methods and objects of study show up, such as adele rings, Galois theory, elliptic curves, Dirichlet L-series or modular forms. Some root in almost direct consequences of modular arithmetic, such as finite fields, intensively used in 20th century. Algebraic number theory is much more vast than modular arithmetic, but in the end amounts to techniques sometimes similar.

Dirichlet character and analytic number theory

Further information: Analytic number theory

Absolute value of the Riemann zeta function.

Bernhard Riemann states the conjecture localising the zeroes of Riemann ζ (zeta) function.

Euler's discovery of an infinite product constructed by prime numbers equal to a sixth of the square of a circle of radius one paves the way for a different approach for understanding numbers. Dirichlet uses it to show that every modulus in the integers contains infinitely many primes. This result is called the theorem on arithmetic progressions.

To prove it, Dirichlet develops a specific method, the Dirichlet L-series. One of these series corresponds to a celebrated function called Riemann ζ (zeta) function. Its biggest difficulty consists in proving that its functions don't have a root at the point one. To show this, he uses harmonic analysis of the group of units of classes of modulus.

Nevertheless, again, modular arithmetic is insufficient to accomplish the proof of the theorem. Dirichlet uses numerous analytic techniques, such as power series and complex analysis. The fruit of these efforts gives birth to a new branch of mathematics: analytic number theory. One of its crucial points comes from an article of Bernhard Riemann (1826 - 1866) on number theory: On the Number of Primes Less Than a Given Magnitude. He conjectures the loci of roots of his ζ-function. Searching for roots, initiated by Dirichlet, becomes a central preoccupation and stays a conjecture believed to be one of the most difficult conjectures of mathematics of our time.

Cryptography

Further information: Cryptography

Phishing is a technique trying to obtain confidential information online by wilful deceit. The necessity of confidential information represents a danger in cryptography.

The object of cryptography is to assure safe message transmission. The messages' confidentiality as well as authentication are two examples of the sense attributed to the term security. One can cite two examples: , or

In more mathematical terms, ciphering can be translated to an algorithm, i.e. a function f which assigns to a plaintext m and a key k a ciphered message f(k, m). The knowledge of the ciphertext and the algorithm needs to be insufficient to reconstituate the plaintext without deciphering key. In traditional cryptography, also called symmetric cryptrography the deciphering key is identical to the cipherkey or can be calculated therefrom easily. Hence this key has to stay secret.

Public key cryptography rests on the principle that only the deciphering key has to be secret, and known only by the receiver of the message. It does not have to be communicated to the correspondents. Alice uses the cipherkey of Bob, who published it, to send him a message. Only Bob can decipher it. Even Alice, if she should lose the plaintext could not do that. Bob has to respond using the cipherkey of Alice.

The objective is then to define a function simple to evaluate, but difficile to invert without knowing a secret. Modular arithemetics has been among the first to offer solutions and is still basic to many commercial solutions. For example, Diffie-Hellman key exchange, historically the first example exploits the practical difficulty of inverting modular exponentiation. The latter, or its generalisations to other groups stays fundamental in the area.

Public key cryptography solves in particular the delicate problem of key distribution inherent to symmetric cryptography. If several correspondents communicate by symmetric cryptography, a different key will be necessary for any two parties, whereas in asymmetric cryptography, every correspondent disposes of a private key kept secret and a public key. Anyhow, public key cryptography has not made obsolete symmetric codes, which offer much more efficient algorithms. For an equivalent level of security, symmetric codes are advantageous, because they necessitate much smaller codes - 128 bits for the current AES compared to more than thousand for contre plus d'un millier pour le RSA, but more importantly ciphering as well as deciphering are between hundred and thousand times faster. Modern cryptography systems, like the ones used by credit cards or the SSL/TLS protocol, much used in internet, use public keys only in the beginning of the communication to exchange the keys for a symmetric ciphering which then goes on.

Public key cryptography

Further information: Public key cryptography

The RSA code is a widespread example public key cryptography. It works as follows:

Alice (the choice of first names is traditionnal) wants to receive Bob's messages such that Eva cannot decipher them. Alice chooses two big prime numbers p and q and an integer e, coprime to the order g of the unit group of Z/pqZ. Here g equals (p - 1)(q - 1), the value of Euler's totient function in n=pq. The messages are supposed to be elements of this ring. If Bob wants to send the message m to Alice, he transmits the value m^e modulo n. Before, Alice has published the values n = pq, e and hence the ciphering function f, which is equal to:

$f(m)\ \equiv \ m^{e}\quad {\pmod {n}}$

Eva was able to intercept f, e and n - these informations are public, after all. On the contrary, she cannot intercept the values of p and q which have never been communicated.

For Bob, the coding function is easy: it is just a simple modular exponentiation. For Alice, the deciphering is also easy, it suffices to find a solution of Bézout's identity:

$x.e+y.(p-1)(q-1)\ =\ 1\;$

If (x₀, y₀) is a solution, then est une solution, alors le Euler's theorem shows:

$m\equiv \ f(m)^{x_{0}}\mod n$

Eva, in turn does not a priori know the factorization into a product of prime numbers of n. She has to calculate the discrete logarithm of f(m), which is a hard problem. The fastest known method corresponds to determine the values p and q. If n is big, there is, as of today, no sufficiently effective algorithm to solve this question.

The key which allows the ciphering is the knowledge of e and n. The force of such a system resides in the fact that knowing this key does not allow to decipher the message; hence the key can be published. The deciphering key are the numbers p and q.

Private-key cryptography

Further information: Private-key cryptography

Private-key cryptography would not exist without the methods stemming from modular arithmetics. The latter does not play the same founding rôle in private-key cryptography, but is not absent in it anyway. Private key-cryptography are divided into two big families, one of which, the stream cipher often uses as basic component recurring linear series over a finite field (see below); the other, block ciphers, comprising among others DES and its successor AES (for Advanced Encryption Standard). The latter ones operate with a block of data of a fixed byte size, for exaple 8 for DES. Comparatively simple primitive operations are repeatedely applied to code a block. A byte, or more generally a block of n bits can by viewed as the coefficients of a polynomial in the integers mod 2, of maximal degree n-1. This led cryptologists to study certain operations on finite fields of characteristic 2. This way it became clear that the inversion operation in the finite field F_2ⁿ, composed with an affine transformation has good cryptographic properties to build one of the ciphering blockwise primitives. This has been exploited by the authors of the encryption technique Rijndael, which has later become AES. By the way, the official publication of the latter by the NIST (federal american agency) contains some mathematical preliminaries on the topic. Anyway, an implementation based on algorithms by arithmetics on a finite field, it is not at all necessary: the operations are represented by tables, like the analogous operations of DES, which are obtained in a much more heuristic manner. Certain cryptologists see a potential weakness in a characterisation too algebraic of Rijndael, which would render it more accessible to mathematicians' imagation. This did not prevent Rijndael's adoption by the AES.

Error correction

Main article: Error correction

CD use as cyclic code a variant of the Reed–Solomon error correction code called code C.I.R.C.

A code corrector are designed not to guaranty security but the reliability of a message's transmission. Il permits to restitute the original text even if a moderate random perturbation occurs during transmission. The encoded message is transmitted under a form called word of the code. It contains not only the information of the initial message but also the redundancies allowing the validation of a good communication and sometimes the automatic correction of possible errors.

A word of the code is composed of a family of n letters chosen from an alphabet, generally binary. The most frequent industrial case is the one of the linear code, the value n is constant for every word of the code and is called the dimension of the code. The set of words of the code is equipped with a vector space structure of dimension n.

Linear code use essentially modular arithmetic as mathematical basis. Many enrich the vector space structure with this of a ring of polynomials over a finite field. This field is sometimes the binary field, often a field with cardinality a power of two. We often then refer to cyclic codes.

The linear codes are mainly existent in the industry. Internet or mobile phone telecommunication uses computers as a communication between the memory and the processor, the audio-visual for the compact discs or other formats of the same nature as DVD.