[HACK] Numeros primos

[Jesus Cea Avion]

> El otro dia me di cuenta que en base dos podemos saber si un numero es
> no primo con una probabilidad del 50%. Los numeros binarios que acaban
> en 0 son no primos, y los que acaban en 1 pueden serlo.

Eso no determina si un número es primo o no con probabilidad del 50%.
Dirás que con ese test eliminas la mitad de los números, que sabes que
no son primos. Pero no sabes nada sobre la otra mitad.

> En base diez, la probabilidad aumenta al 60% (no primos los acabados
> en 0, 2, 4, 5, 6 y 8).

10 es 2*5. Ese test elimina cualquier número múltiplo de 2 y de 5.

Si trabajases con base 2*3*5*7 = 210, eliminarías aún más números.

Pero para convertir un número a la base X necesitas hacer divisiones.
Básicamente estás descomponiendo el número en sus factores según esa
base. No ganas nada de eficiencia. Todo lo contrario.

Es más eficiente dividir el número por TODOS los valores primos menores
a su raíz cuadrada. De esa forma no solo sabes si un número es primo o
no, con total certeza, sino sus factores en el caso de ser un número
compuesto.

En resumen, el esquema no es útil en la práctica, incluso para números
pequeños.

Hay tests probabilísticos con probabilidad del 50% de verdad,
independientemente del tamaño del número. Si quieres tener la certeza
"probabilística" sobre la primalidad de un número, simplemente repite el
test 100 veces, y la probabilidad de que se te cuele un número no primo
es de 2^100 o de 1267650600228229401496703205376 a 1 :-).

> Sabeis si se puede extrapolar? La probabilidad de saber si un numero
> es primo aumenta segun la base que usemos? Links???

Es algo muy básico de la teoría de números.

Si tomas X como base, cualquier número entero se puede representar como
An*X^n+...+A1*X+A0. Si obligas a que los An sean enteros positivos
menores que X, la representación es única.

Por ejemplo, en el caso de base 10, todos los dígitos son menores que 10
(de 0 a 9, menor que 10).

Si X tiene como factores primos F1, F2, etc (en el caso de 10, pues 2 y
5), haciendo el módulo obtenemos:


(An*X^n+...+A1*X+A0) mod Fk = A0 mod Fk

Osea, solo nos interesa el último dígito, en esa base.

Si ese módulo es 0, significa que el número es múltiplo del factor primo
y, por tanto, no es primo, sino compuesto.

En el ejemplo que tu pones, de base 10 y terminaciones 0, 2, 4, 5, 6, 8,
esos números son todos múltiplos de 2 y de 5, por lo que su módulo
respecto a ellos es cero.

0 mod 2 = 0
2 mod 2 = 0
4 mod 2 = 0
5 mod 5 = 0
6 mod 2 = 0
8 mod 2 = 0

:-)

> Se que existen teoremas para comprbar con cierto grado de probabilidad
> si un numero es primo, tienen algo que ver con esto?

No, en absoluto, como ya comenté más arriba.

Por ejemplo, una prueba muy sencillita es que (a^(p-1) mod p) = 1 para
todo valor natural de "a", si "p" es un número primo. Así que bastaría
con hacer esa comprobación para diferenctes valores de "a" para tener
una certeza casi absoluta.

Lamentablemente hay ciertas categorías de números, muy escasas, que dan
positivo en ese test, SEA CUAL SEA el valor de "a". Se llaman "primos de
Carmichael", aunque realmente no son números primos :).

Por cierto, esos números especiales son escasos, pero se ha probado que
hay infinitos :-).

Si te interesa la teoría de números, que es un tema apasionante, hay
muchísimo material en Internet, incluyendo libros universitarios y tesis
doctorales, todo gratis.

El año pasado se descubrió un test de primalidad que no es
probabilístico. Es decir, que dice a ciencia cierta si un número es
primo o no. Pero en la práctica no se usa porque los tests
probabilísticos son más eficiencias y regulas el nivel de confianza
simplemente repitiendo el test las veces necesarias para tu
"tranquilidad".

-- 
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea at argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
                                      _/_/    _/_/          _/_/_/_/_/
PGP Key Available at KeyServ   _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz