Varias cositas que no sobran sobre primos

phicar · 21-Dec-2008, 17:09

Bueno vi que este foro en esta parte esta medio muerto..y pues les queria compartir un poquito de lo que acabe de escribir(gracias ProjectEuler :P)

Hola muchachos, hoy les presento la funcion para determinar la funcion phi de un numero n...junto a esta funcion les presento dos formas de determinar si un numero es primo(ya lo vi por ahi en posts de monje y radical..pero no quiero dannar la estructura del post)..despues les mostrare otros teoremas mucho mas avanzados..miller rabit..fermat bueno entre otros..para terminar por factorizacion de numeros primos como el metodo de monte carlo ya que por el momento no me se mas :P...Bueno para empezar...

Que carajo es un numero primo??

un numero primo es el cual solo es divisible por si mismo y por 1..

Que carajo es la funcion phi???

Phi aunque es prefijo de un nick de un personaje muy chevere xDDD mentiras...la funcion phi es una funcion para buscar los numeros menores o igual a n donde no contengan ningun factor comun..

Como funciona la funcion Phi??

bueno la funcion phi funciona de esta manera...primero se evaluea si el numero n es primo pues todos los numeros exceptuando si mismo va a ser primales a n..o sea que
{Phi(n)=(n-1) | n sea un numero primo}
si n no es primo entonces se procede a buscar los factores primos de n..

y la respuesta seria (n)*(1-(1/pk))...tal que pk son los factores primos de n....

No siendo mas les dejo mejor codigo(java me encanta Java :P)

Metodo uno para determinar si un numero es primo

Código:

public static boolean isPrime(double n){
if(n==2 || n==3) return true;//2 y 3 son primos
if(n%2 == 0) return false;//si es par no es primo
if(n<2) return false;//0 y 1 son una vaina rara
for(double a=3;a<=(n/2);a+=2)//valla por los numeros impares hasta el maximo numero que puede dividir a n(su mitad :))
if(n%a==0) return false;//si resulta que el residuo de alguna de esas divisiones es 0 entonces no es primo
return true;//si no pasa nada entonces es primo

Funcion phi

Código:

public static double phi(double n){
Vector<Double> num = new Vector<Double>();//es como un arreglo dinamico*
if(isPrime(n)) return(n-1);//si es primo como dijimos devuelve el numero -1
double res = n;//donde voy a empezar a iterar los factores
if(n%2 == 0) num.add(2.0);//si es par tiene un dos por ahi
for(double a = 1;a<=(n/2);a+=2)//valla buscando todos los impares hasta su mitad
if(n%a == 0 && isPrime(a))num.add(a);//si el numero es divisible por n y aparte es primo lo agnado a el vector
for(int r = 0;r<num.size();r++)//ahora recorro el vector
res*=(1-(1/(num.get(r))));//y multiplico n por (1-(1/pk)) como dice la funcion
return res;//retorno la multiplicacion
}

*dinamico es que crece en tiempo de ejecucion

Mi funcion consentida en la generacion de primos...la criba de erastotenes

Código:

boolean num[] = new boolean[x];//x es el numero-1 hasta el cual quieren generar primos
Arrays.fill(num,true);//esto viene en java.util, relleno todo de true
num[0]=false;
num[1]= false;//como dije 0 y 1 son vainas raras
for(int n = 2;n<=Math.sqrt(num.length);n++){//recorro hasta la raiz cuadrada de la longitud del arreglo
if(num[n]) 
for(int k = n*n;k<num.length;k+=n) num[k]=false;//recorro todos los multiplos de n numero y digo no son primos
}

//esto ya es pa imprimir algun resultado

for(int n=0;n<num.length;n++)
if(num[n]) System.out.println(n);//eso imprimiria todos los numeros primos hasta x :)

Esperen las otras partecitas :P chao

DragoN · 21-Dec-2008, 19:47

phicar te has sabido ganar un +1, sigue aportando

sorensic · 26-Jan-2009, 05:18

Si, realmente muy bueno... me entretení leendo y comprendiendo.. jeje
Bueno aporte.!

Mighty-D · 30-Apr-2009, 00:14

Hola señores,

Andaba viendo los foros y me encontré este tema un poco muerto (si no estoy mal, desde enero no se publica nada aca.). Como phicar prometió mostrarnos una forma de verificar si un número es primo utilizando algoritmos monte carlo (para los que no saben, se llama monte carlo por que allí quedan o quedaban unos casinos muy famosos) que en realidad son pruebas de compositez (de acuerdo al teorema fundamental de la aritmetica un numero es compuesto cuando se puede descomponer en factores primos elevados a una potencia cualquiera, independiente para cada factor, por lo tanto un número es primo o compuesto por primos o es uno, esto es solo una apreciación común decir que el uno no es ni primo ni compuesto, evidentemente 0 es un número compuesto ya que 0=0*2*3*5*7*11*13, una frase que me gusta decir y que es robada del libro de Victor Shoup A Computational Introduction to Number Theory and Algebra, es que los primos son los bloques fundamentales para construir los números.)

Yo les voy a contar de otra cosa, por que no quiero saltarme a phicar y quiero dejar que el publique los métodos probabilistas (que en realidad son pruebas de compositez) como el uso del teorema de fermat, pseudoprimos, carmichael, pseudoprimos fuertes, miller, etc.

En fín yo les voy a mostrar una forma DETERMINISTA para conocer si un número es primo o no lo es.
Teorema:

Sean N, s enteros con N>1, s>sqrt(N). Si para todo primo q, divisor de s,
existe un entero a tal que a^(q^alfa_sub_q) ~ 1 mod N (donde ~ denota congruencia), con a^(q^(alfa_sub_q-1)) primo relativo con N (esto quiere decir que su máximo común divisor es uno),
siendo alfa_sub_q el número de veces que q divide a s, entonces N es primo.

Para un observador casual puede no ser obvio cual es problema de este teorema, sin embargo es claro que para poder aplicarlo necesitamos conocer la factorización de s, la humanidad aún no ha podido encontrar métodos de factorización efectivos y por lo tanto la aplicación de este teorema puede complicarse, cabe anotar igualmente que la selección de s es arbitraria siempre que se cumpla que s>sqrt(N)

Este es un tema apasionante y díficil de abordar si no se tienen algunos conceptos de teoría de números, algo les prometo, aqui hay para todos, desde los cimientos de computación con enteros grandes (números con los cuales lenguajes como C, JAVA, etc... no pueden ni soñar), las bases para la computación matemática en paralelo, y la aplicación mas famosa, los criptosistemas.

Espero que esto no suene muy UFO y que alguno de ustedes encuentre la información útil por lo menos para saber donde buscar.

Un saludo.

Mighty-D

idol_killer · 22-May-2009, 01:09

q interesante ,

yo hice algo similar sobre los numeros primos pero en python:

Código:

    def esPrimo(n=0):

        if n==1:   #1 no es primo
            primo=0
        else:
            primo=1

        lista=range(2,(n/2))   #Cree una lista con los números empezando desde el 2 hasta un la mitad del número que se quiere averiguar, es decir sus posibles multiplos

        i=0 
        while i<len(lista) and primo:
            if n%lista[i]==0:   #Aqui se comprueba si es divisible por alguno de los multiplos de la lista
                primo=0
            i=i+1

        return primo

antes de esta "version" lo habia intentado hacer con eso de comprobar primero si el numero era 2 o 3, pero pensé q el código deberia ser "independiente d lo que sabe el programador". Aún así no logré hacer lo mismo para el número 1...

lo q he visto por mi cuenta d este tema (teoria de numeros) me ha parecido muy interesante, desafortunadamente donde estudio hay poco enfasis en matematicas aplicadas a ciencias de la computacion, aunque he escuchado que existe una electiva sobre esto e incluso una materia de criptografia

ah y Mighty-D tiene razón , ni python ni java pueden con numeros demasiado grandes...

Mighty-D · 22-May-2009, 01:49

Hola!,

Estuve observando tu código, pero quisiera decirte algo que pienso sobre el.

Abordar las pruebas de primalidad utilizando iteraciones es algo que no es práctico,
en el peor de los casos habría que probar todos los números primos que sean menor o igual que sqrt(n) para que determinar que un número es primo. Ahora bien, si consideramos que existen infinitos primos (diferentes formas de probarlo: Proofs that there are infinitely many primes), no es posible generar una tabla infinita de datos.

Consideremos el caso práctico donde tenemos un número para el cual queremos probar primaldad, en la mayoría de los casos utilizaremos números relativamente grandes (como es el caso de RSA), lo cual nos llevaría a verificar divisibilidad contra una tabla con muchos números.

En definitiva, no quiero que tomes este mensaje como una critica espantosa para decir que tu trabajo no es adecuado, es más una recomendación sobre los algoritmos de pruebas de primaldad y compositez que van a ser mas confiables y eficientes.

Un saludo!