Editing Number theory (section)

=== Computational number theory ===
{{Main|Computational number theory}}[[File:Computer History Museum (4145886786).jpg|thumb|A [[Lehmer sieve]], a primitive [[digital computer]] used to find [[primes]] and solve simple [[Diophantine equations]]]]While the word ''algorithm'' goes back only to certain readers of [[al-Khwārizmī]], careful descriptions of methods of solution are older than proofs: such methods (that is, algorithms) are as old as any recognisable mathematics—ancient Egyptian, Babylonian, Vedic, Chinese—whereas proofs appeared only with the Greeks of the classical period.
An early case is that of what is now called the Euclidean algorithm. In its basic form (namely, as an algorithm for computing the [[greatest common divisor]]) it appears as Proposition 2 of Book VII in ''Elements'', together with a proof of correctness. However, in the form that is often used in number theory (namely, as an algorithm for finding integer solutions to an equation <math>a x + b y = c</math>, or, what is the same, for finding the quantities whose existence is assured by the [[Chinese remainder theorem]]) it first appears in the works of [[Aryabhata#Indeterminate equations|Āryabhaṭa]] (fifth to sixth centuries) as an algorithm called ''kuṭṭaka'' ("pulveriser"), without a proof of correctness.

There are two main questions: "Can this be computed?" and "Can it be computed rapidly?" Anyone can test whether a number is prime or, if it is not, split it into prime factors; doing so rapidly is another matter. Fast algorithms for [[primality test|testing primality]] are now known, but, in spite of much work (both theoretical and practical), no truly fast algorithm for factoring.

The difficulty of a computation can be useful: modern protocols for [[cryptography|encrypting messages]] (for example, [[RSA (algorithm)|RSA]]) depend on functions that are known to all, but whose inverses are known only to a chosen few, and would take one too long a time to figure out on one's own. For example, these functions can be such that their inverses can be computed only if certain large integers are factorized. While many difficult computational problems outside number theory are known, most working encryption protocols nowadays are based on the difficulty of a few number-theoretical problems.

Some things may not be computable at all; in fact, this can be proven in some instances. For instance, in 1970, it was proven, as a solution to [[Hilbert's tenth problem]], that there is no [[Turing machine]] which can solve all Diophantine equations.<ref>{{cite book |editor=Felix E. Browder |editor-link=Felix Browder |title=Mathematical Developments Arising from Hilbert Problems |series=[[Proceedings of Symposia in Pure Mathematics]] |volume=XXVIII.2 |year=1976 |publisher=[[American Mathematical Society]] |isbn=978-0-8218-1428-4 |pages=323–378 |first1=Martin |last1=Davis |author-link1=Martin Davis (mathematician) |first2=Yuri |last2=Matiyasevich |author-link2=Yuri Matiyasevich |first3=Julia |last3=Robinson |author-link3=Julia Robinson |chapter=Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution |zbl=0346.02026}} Reprinted in ''The Collected Works of Julia Robinson'', [[Solomon Feferman]], editor, pp. 269–378, American Mathematical Society 1996.</ref> In particular, this means that, given a [[computably enumerable]] set of axioms, there are Diophantine equations for which there is no proof, starting from the axioms, of whether the set of equations has or does not have integer solutions. (i.e., Diophantine equations for which there are no integer solutions, since, given a Diophantine equation with at least one solution, the solution itself provides a proof of the fact that a solution exists. It cannot be proven that a particular Diophantine equation is of this kind, since this would imply that it has no solutions.)