Test de primalidade

Atención: Este artigo ou apartado precisa dun traballo de revisión. tradución sen revisión posterior, redacción non enciclopédica Por favor, vexa a lista de problemas indicados neste modelo e mellóreo de acordo coas indicacións. Cando os problemas se resolvan, retire esta mensaxe, pero non quite esta mensaxe ata que estea todo solucionado. De ser posible, sería mellor substituír este marcador por outro máis específico. (Desde abril de 2016)

Este artigo contén varias ligazóns externas e/ou bibliografía ao fin da páxina, mais poucas ou ningunha referencia no corpo do texto. Por favor, mellora o artigo introducindo notas ao pé, citando as fontes. Podes ver exemplos de como se fai nestes artigos.

Este artigo ou sección precisa dunha revisión do formato que siga o libro de estilo da Galipedia. Pode axudar a mellorar este artigo e outros en condicións semellantes.

Este artigo ou sección precisa revisión por alguén que saiba deste tema. Se ten eses coñecementos mellore este artigo. Vexa na páxina de discusión que aspectos son os que precisan revisión. (Desde abril de 2016.)

A cuestión da determinación de se un número n dado é primo é coñecida como o problema da primalidade. Un test de primalidade (ou recoñecemento da primalidade) é un algoritmo que, dado un número de entrada n, non consegue verificar a hipótese dun teorema cuxa conclusión é que n é composto.

Isto é, un test de primalidade só conxectura que “ante a falta de certificación sobre a hipótese de que n é composto podemos ter certa confianza en que se trata dun número primo”. Esta definición supón un grao menor de confianza que o que se denomina proba de primalidade (ou test verdadeiro de primalidade), que ofrece unha seguridade matemática respecto diso.