Test de primalidade: Diferenzas entre revisións
Contido eliminado Contido engadido
Recuperando 1 fontes e etiquetando 0 como mortas. #IABot (v2.0beta8) |
mSen resumo de edición |
||
Liña 13:
Por outra banda, algunhas aplicacións das matemáticas que utilizan o problema da factorización precisan dunha serie de números primos moi grandes escollidos de forma aleatoria. O algoritmo para obter un número primo aleatorio moi grande sería algo así:
O tempo de finalización deste algoritmo non é determinado, pero existe unha alta probabilidade de que finalice en tempo
O primeiro que podemos establecer é que o cardinal do conxunto de primos no conxunto dos [[Número natural|números naturais]] <math>\mathbb{N}</math> é [[Infinitude dos números primos|infinito]] (isto é, que hai infinitos números primos).
Claro que,
Do visto até aquí podemos co''n''cluír que o algoritmo anterior pode obter unha resposta en tempo
En calquera caso unha modificación moi frecuente para facer o algoritmo determinista é partir dunha semente aleatoria e logo facer unha procura secuencial da cota inferior do conxunto de curmáns maiores que a semente de partida.
Liña 26:
Antes de entrar a tratar as técnicas modernas que se aplican ao problema da primalidade non está de máis facer un breve repaso á historia do problema e ás solucións achegadas ao longo dos séculos.
Os problemas da factorización dun número dado e a determinación de números primos son moi antigos. Os rexistros históricos sobre o estudo de números primos remónt[[Século -III|a]]<nowiki/>nse a [[Euclides]] ([[Século -III|século III
Con todo, o primeiro procedemento matemático coñecido concernente estes números remóntase a [[Eratóstenes]] ([[Século -II|século II]] a. C.) e é a coñecida [[criba de Eratóstenes]], que aínda se estuda nos centros de educación primaria. O método é sinxelo: para obter os números primos menores que un dado, primeiro colocamos os números de 1 a n nunha lista e empezamos tachando todas as posicións pares. Logo, sobre a lista que queda tachamos todos os que son múltiplo de tres (o seguinte número da lista despois do 2). Logo sobre os que quedan todos os que son múltiplos de cinco (o seguinte número da lista despois do 3).▼
▲Con todo, o primeiro procedemento matemático coñecido concernente estes números remóntase a [[Eratóstenes]] ([[Século -II|século II
Hoxe en día, este algoritmo ten un valor máis histórico que práctico. Funciona ben, pero é moi ineficiente.
Liña 36 ⟶ 38:
Outro problema da criba é que non responde o problema da simple determinación de primalidade dun número dado, senón que ofrece unha lista (potencialmente infinita) de números primos.
O problema, máis concreto, de determinar
Como moitas outras achegas matemáticas, o problema da primalidade chegou á Europa moderna a través dos árabes, pero non foi até moitos séculos despois que apareceron os primeiros rexistros escritos sobre a primalidade e a súa solución. Estes corresponden ao matemático italiano [[Leonardo Fibonacci|Leonardo de Pisa]] (Fibonacci) quen presentou un algoritmo moi simple para determinar
O primeiro en utilizar relacións observadas entre os números para determinar a primalidade foi o boloñés [[Pietro Antonio Cataldi]] co seu traballo sobre os números perfectos.
Liña 44 ⟶ 46:
Un [[número perfecto]] é aquel que é igual á suma dos seus divisores propios. Por exemplo 6 é perfecto, xa que a suma dos seus divisores (1+2+3) é igual ao mesmo. O sete primeiros números perfectos son 6, 28, 496, 8128, 33550336, 8589869056 e 137438691328.
Cataldi determinou que
En realidade Mersenne cometeu algúns erros xa que M_p non é primo para p = 67 nin 257 e
Contemporáneo de Mersenne e moito máis importante para a historia e a estado da arte actual do problema que estamos a tratar foi o importante matemático [[Pierre de Fermat]] (1607-1665). Fermat é posiblemente o teórico numérico máis renomeado da historia e é moi coñecido por un teorema que esencialmente estivo sen demostración durante máis de trescentos anos. Con referencia á primalidade, Fermat tivo correspondencia con Mersenne e, de feito, estableceu un resultado sobre os números primos que é esencial para as técnicas modernas de determinación da primalidade.
Liña 57 ⟶ 59:
== Tests verdadeiros de primalidade ==
Nos apartados anteriores falouse de dous problemas relacionados (factorización e primalidade) que dalgunha maneira son complementarios. Con todo, as dúas cuestións son de natureza moi distinta. Para convencer a alguén de que un número foi factorizado é suficiente con mostrar os factores e o resultado queda claro. Con todo convencer a esa mesma persoa de que un número dado é primo pode ser moito máis difícil. Como o matemático parisiense do [[século XIX]] [[Fortuné Landry]] sinalou, a menos que a outra parte coñeza os métodos de comprobación da primalidade e realice por
Esta é a visión do matemático; desde o punto de vista do enxeñeiro as cousas non son brancas ou negras. Por iso, convimos en diferenciar os tests (ou recoñecementos) das probas. Antes de proseguir, chegou o momento de definir formalmente ambos os conceptos.<blockquote style=" width:90%; padding: 0.8em; border: 1px solid #880000; background-color: #FFFFFF;">
Liña 92 ⟶ 94:
Os tests probabilísticos están baseados na idea de relaxar a corrección da proba para conseguir un comportamento de resposta [[Tempo polinómico|polinomial ou subpolinomial.]] Baséanse ben no uso PTF (que acabamos de comentar), ben no uso do que se coñecen como verificadores e falsadores de Euler.
O primeiro exemplo de test probabilístico que veremos é o [[Test de primalidade de Fermat|test de Fermat.]] Devandito test está baseado no PTF. O algoritmo baseado neste test aplícase elixindo varios enteiros aleatorios entre 2 e n-2 e calculando .<math>a</math><math>r \equiv a^{n-1} \pmod n</math>
Como vimos na sección anterior, o test de Fermat adoece dun coñecido problema: os [[números de Carmichael]]. Os números de Carmichael pasan a condición de Fermat para todos os posibles valores de ; isto implica que
Outro test moi coñecido e utilizado en criptografía é o [[test de Solovay-Strassen]] (SS). Este test está baseado ''n''o [[criterio de Euler]].
== Avances recentes ==
Desde os [[Década de 1970|anos 70]] estívose traballando na mellora dos algoritmos clásicos para obter mellores probas de primalidade.<ref>Caldwell, Chris: ''The Prime Pages''.</ref> Para iso traballouse coa factorización de formas polinómicas de n. Entre estes algoritmos destacan o debido a Adleman, Pomerance e Rumely (APR) e a mellora que sobre este fixeron Cohen e Lenstra (APR-CL) que obteñen complexidades case
Tamén se está avanzando neste campo utilizando outras formas máis sinxelas de traballo con grupos matemáticos en lugar da aritmética modular dos grupos de Galois.
Neste sentido están a facerse avances no traballo con curvas elípticas módulo n. Unha curva elíptica é unha función que se define da seguinte forma:<center><math>E(a,b): \quad y^2 = x^3+ax+b \quad / \quad 4a^3+27b^2 \neq 0</math></center>En curvas deste tipo estiveron traballando desde [[1986]] Goldwasser, Kilian e Atkin. Este último definiu o método ECPP ou [[proba de primalidade por curva elíptica]] (Elliptic Curve Primality Proving), que ten diversas
Moitas das probas e tests de primalidade que vimos até agora resólvense en tempo polinomial.
Durante anos os sistemas criptográficos estiveron utilizándoos para a xeración de claves seguras. Con todo teñen limitacións. Algúns non son probas de primalidade e en consecuencia non devolven un certificado de primalidade: existe unha probabilidade (aínda que pequena) de que un número sexa considerado primo cando en realidade é composto; son os que se coñecen como algoritmos probabilísticos de orde P (RP). Outros
Por exemplo, o test de Miller é polinomial
=== Test de primalidade AKS ===
O recente descubrimento dun algoritmo determinista de tempo polinomial que non se basea en ningunha conxectura non probada debe ser considerado un fito importante. Concretamente en agosto do ano [[2002]] tres académicos da Universidade de Kanpur (Agrawal, Kayal e Saxena) presentaron un algoritmo determinista de clase P para a determinación da primalidade dun número.<ref>Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin: "PRIMES is in P".</ref> A clave do algoritmo é unha versión simplificada do PTF, isto é a condición:<center><math>(x-a)^p \equiv (x^p-a) \pmod{x^r-1,\;p}</math></center>Os autores arranxáronllas para formular o seguinte algoritmo, que se probou pode executarse nun tempo de complexidade máxima de .<math>\mathcal{O}((\log \, n)^{\frac{21}{2}} f(\log \; \log \, n))</math>
Os autores demostraron ademais que,
</ref><math>\mathcal{O}((\log \, n)^{6+\epsilon})</math>
En realidade este descubrimento non ten implicacións prácticas na computación moderna. O certo é que as partes constantes da complexidade do algoritmo son moito máis custosas que nos actuais algoritmos probabilísticos. É de esperar que no futuro próximo
{{Listaref}}▼
== Referencias ==
Liña 124 ⟶ 129:
* Knuth, Donald. ''The Art of Computer Programming'', Volume 2: ''Seminumerical Algorithms.'' Páxinas 391–396 de sección 4.5.4. Addison-Wesley, 3a edición, 1997. (ISBN 0-201-89684-2.)
* Williams, H.C.: ''Édouard Lucas and Primality Testing.'' John Wiley & Sons, 1998. (ISBN 0-471-14852-0.)
▲=== Notas ===
▲{{Listaref}}
== Véxase tamén ==
|