Test de primalidad

El 39.º número primo de Mersenne era el major conegut fins a la data de creació d'este artícul.

La qüestió de la determinació de si un número n donat és primer és coneguda com el problema de la primalidad. Un test de primalidad (o chequeo de primalidad) és un algoritme que, donat un número d'entrada n, no conseguix verificar de forma concloent la hipòtesis d'un teorema que la seua conclusió és que n és compost.

Açò és, un test de primalidad sol conjectura que «davant la falta de certificació sobre l'hipòtesis de que n és compost podem tindre certa confiança en que es tracta d'un número primo». Esta definició supon un grau menor de confiança que lo que es denomina prova de primalidad (o test verdader de primalidad), que oferix una seguritat matemàtica al respecte.

Introducció

Els problemes que impliquen a les matemàtiques discretes estan entre els més difícils de les matemàtiques. Concretament el de la factorización és un problema per al que encara no s'ha trobat una solució que es puga acurtar en temps polinomial.^[1]

Per una atra part, algunes aplicacions de les matemàtiques que utilisen el problema de la factorización precisen d'una série d'número primo molt grans triats de forma aleatòria. L'algoritme per a obtindre un número primo aleatori molt gran seria alguna cosa aixina:

El temps de finalisació d'este algoritme no és determinat, pero existix una alta provabilitat de que finalise en temps polinomial sempre i quan hi haja suficients número primo i estos estiguen distribuïts de forma més o menys uniforme. Afortunadament per a les aplicacions que precisen número primo aleatoris, açò és aixina. Vejam per qué.

Lo primer que podem establir és que el cardinal del conjunt de cosins en el conjunt dels número natural $ℕ$ és infinit (açò és, que hi ha infinits número primo). El teorema de Dirichlet (1837) diu que si mcd(a, n) = 1 llavors hi ha infinits cosins congruents en a mòdul n. En atres paraules (i utilisant un corolari de Dirichlet), els número primo estan uniformemente distribuïts en les classes congruents en la funció φ de Euler en $ℕ_{n}^{*}$ per a qualsevol valor de n.

Clar que, si els número primo estan uniformemente distribuïts, pero hi ha un número chicotet d'ells, la busca podria ser impossible en la pràctica. Per a resoldre este segon problema podem acodir al teorema de Hadamard (1896) que establix que la cardinalidad del conjunt d'número primo en l'interval [2..n] és asintòtic a $n / \log n$ . Este número tendix a infinit molt suaument, lo que implica que encara per a valors grans de n existix una provabilitat suficientment alta de donar en un número primo de forma aleatòria.

De lo vist fins a ací podem concloure que l'algoritme anterior pot obtindre una resposta en temps polinomial si existix un algoritme polinomial per a comprovar que un número n arbitrariamente gran és primer. Lo que nos torna al problema de la primalidad.

En qualsevol cas una modificació molt freqüent per a fer l'algoritme determinista és partir d'una llavor aleatòria i després fer una busca seqüencial de la cota inferior del conjunt de cosins majors que la llavor de partida.

De Euclides a Lucas

Abans d'entrar a tractar les tècniques modernes que s'apliquen al problema de la primalidad no està de més fer un breu repàs a l'història del problema i a les solucions aportades a lo llarc dels sigles.

Els problemes de la factorización d'un número donat i la determinació d'número primo són molt antics. Els registres històrics sobre l'estudi d'número primo es remonten a Euclides (III) encara que hi ha evidències de que el coneiximent de l'existència d'estos números tan particulars es podria remontar a Pitágoras (VI).

No obstant, el primer procediment matemàtic conegut concernent estos números es remonta a Eratóstenes (II) i és la coneguda garbell que du el seu nom, que encara s'estudia en les escoles d'educació primària. El método és senzill: per a obtindre els número primo menors que un $n$ dau, primer coloquem els números d'1 a $n$ en una llista i escomencem tachant totes les posicions pares. Després, sobre la llista que queda tachem tots els que són múltiple de tres (el següent número de la llista despuix del 2). Després sobre els que queden tots els que són múltiples de cinc (el següent número de la llista despuix del 3).

Hui dia, este algoritme té un valor més històric que pràctic. Funciona be, pero és molt ineficiente.

La millora més òbvia atañer a la forma en la que l'algoritme termina (curiosament Eratóstenes no va tindre en conte este fet i va anar el matemàtic àrap ibn al-Banna qui la va propondre sigles despuix): és suficient en iterar fins als divisores primers de $n$ menors que $\sqrt{n}$ .

Un atre problema del garbell és que no respon al problema de la simple determinació de primalidad d'un número donat, sino que oferix una llista (potencialment infinita) d'número primo.

El problema, més concret, de determinar si un número $n$ dau és primer pot derivar-se de l'anterior, simplement se simula el garbell per a $n - 1$ i es comprova si $n$ permaneix en ella. La qüestió és que el cost de seguir este procediment és molt gran.

Com moltes atres aportacions matemàtiques, el problema de la primalidad va aplegar a l'Europa moderna a través dels àraps, pero no va ser fins a molts sigles despuix que varen aparéixer els primers registres escrits sobre la primalidad i la seua solució. Estos corresponen al matemàtic italià Leonardo de Pisa (Fibonacci) qui va presentar un algoritme molt simple per a determinar si un número n donat és primer consistent en comprovar que cap atre número primo inferior a la $\sqrt{n}$ dividix a $n$ . Este algoritme té la característica de ser determinista (sempre obté una solució) encara que tremendament ineficiente. En realitat, Fibonacci és més conegut per la successió que du el seu nom i que també té el seu paper en el problema que nos ocupa (després vorem alguna cosa més sobre la famosa successió de Fibonacci).

El primer en utilisar relacions observades entre els números per a determinar la primalidad va ser el boloñés Pietro Antonio Cataldi en el seu treball sobre els número perfecto.

Un número perfecto és aquell que és igual a la suma de les seues divisores propis. Per eixemple 6 és perfecte, ya que la suma de les seues divisores (1+2+3) és igual al mateix. Els sèt primers número perfecto són 6, 28, 496, 8128, 33550336, 8589869056 i 137438691328.

Cataldi va determinar que si $2^{n} - 1$ és primer llavors $n$ ha de ser primer i $2^{n - 1} (2^{n} - 1)$ ha de ser perfecte. Esta teorema nos introduïx una família de números especialment important per a l'història de la primalidad: els cridats números de Mersenne en honor del filòsof Marin Mersenne (1588-1665), que són números de la forma $M_{p} = 2^{p} - 1$ a on p és un número primo. Mersenne va comprovar que dels 257 primers números de la família que du el seu nom, solament 11 són primers (són els $M_{p}$ per a p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 i 257).

En realitat Mersenne va cometre alguns errors ya que $M_{p}$ no és primer per a p = 67 ni 257 i sí ho és per a p = 61, 89 i 107; no obstant el seu treball sobre estos números ha quedat reflectit en el fet de que duen el seu nom.

Contemporàneu de Mersenne i molt més important per a l'història i l'estat de l'art actual del problema que estem tractant va ser l'important matemàtic Pierre de Fermat (1607-1665). Fermat és possiblement el teòric numèric més renombrado de l'història i és molt conegut per una teorema que essencialment va estar sense demostració durant més de trescents anys. En referència a la primalidad, Fermat va tindre correspondència en Mersenne i, de fet, va establir un resultat sobre els número primo que és essencial per a les tècniques modernes de determinació de la primalidad. La teorema en qüestió (conegut com menuda teorema de Fermat o PTF) establix lo següent:

Com a corolari a esta important teorema s'establix que si $p > 2$ és primer, llavors qualsevol número primo $q$ que dividixca a $2^{p} - 1$ té que ser de la forma $q = 2 m p + 1$ per a algun $m \in ℕ$ . També es pot demostrar que si $m \in ℕ$ és el menor número tal que $n | (b^{m} - 1)$ , llavors $q | (b^{t} - 1)$ sempre que $q | t$ .

Fermat buscava números $n > 1$ que li ajudaren a comprovar la primalidad dels número de números de Mersenne. En la seua busca va vore que la teorema abans exposta era útil per a detectar possibles primers $q$ tals que $q | 2^{37} - 1$ . Fermat també va sugerir que els números de la forma $2^{2^{n}} + 1$ (denominats números de Fermat i representats per $𝔉_{n}$ ) devien ser primers i ho va comprovar per a tots els n menors que 4. No va poder demostrar-ho per a $𝔉_{5}$ i hui se sap que $𝔉_{5}$ és compost, com lo són tots els restants fins a $n = 24$ (i possiblement tots els demés, encara que este últim extrem és encara una conjectura).

Un atre eminent matemàtic que va estar interessat en el problema de la primalidad va ser el suís Leonhard Euler. Euler es va sentir atret pels resultats de Fermat i va trobar un divisor de $𝔉_{n}$ (contradient puix la conjectura de Fermat sobre la primalidad de $𝔉_{5}$ ). No obstant, la seua aportació més important al problema va ser l'enunciat d'una teorema relacionada que establix que tot divisor primer de $𝔉_{n}$ deu ser de la forma $2^{n + 1} k + 1$ per a algun $k \in ℕ$ .

Va haver atres matemàtics també molt eminents que varen treballar en el camp de la factorización de números, per eixemple Legendre i Gauss, i que també varen fer algunes contribucions al problema de la primalidad; pero l'últim dels matemàtics clàssics del que parlarem que va obtindre notables resultats sobre la qüestió va ser el francés François Éduard Anatole Lucas. Lucas va treballar sobre els números de Fibonacci i de Mersenne, va obtindre resultats sobre la divisibilidad dels primers i va determinar una prova de primalidad per als números de Mersenne (que va aplicar a la comprovació de primalidad de $M_{127}$ ) que vorem a continuació.

Vore també

Referències

↑ Papadimitriou, Christos H.: Computational Complexity. Secció 10.2: "Primality", pp.222–227. Addison-Wesley, 1era edició, 1993. (ISBN 0-201-53082-1.)

Bibliografia

Cormen; Leirserson, {{{nom2}}}; Rivest, {{{nom3}}}; Stein, {{{nom4}}} (2001). Introduction to Algorithms, 2ª edició, MIT Press & McGraw-Hill, pp. 887-896. ISBN 0-262-03293-7.
Crandall (2001). Prime Numbers: A Computational Perspective, 1ª edició, Springer. ISBN 0-387-94777-9. Capítul 3: «Recognizing Primes and Composites», pp. 109-158. Capítul 4: «Primality Proving», pp. 159-190. Capítul 7: «Elliptic curve arithmetic», pp. 334-340.
Knuth (1997). «4.5.4 Factoring into Primes», The Art of Computer Programming, 3ª edició, Addison-Wesley, pp. 391–396. ISBN 0-201-89684-2.

Williams (1998). Édouard Lucas and Primality Testing, John Wiley & Sons. ISBN 0-471-14852-0.

Referències

Este artícul conté una traducció derivada de «Test de primalidad» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Papadimitriou, Christos H.: Computational Complexity. Secció 10.2: "Primality", pp.222–227. Addison-Wesley, 1era edició, 1993. (ISBN 0-201-53082-1.)

[1]