Autor Tema: Factorizacion Fermat  (Leído 511 veces)

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
Factorizacion Fermat
« : marzo 04, 2010, 11:44:57 pm »
a!, como han estado? ;)
Bueno he estado haciendo cositas y pos una de ellas es factorizar un numero y pos recurri a google y me encuentro con
un metodo de uno de mis matematicos favoritos..El metodo de Fermat para factorizar, resulta pasa y acontece que el loco uso lo siguiente, explicado en palabras de un arrogante cabroncete como yo ;)


'y' es un numero que pertenece a los naturales, 'y' es impar y queremos saber su composicion en factores primos pos veamos lo siguiente

'y' al ser un numero compuesto se expresa de la forma y = ab..donde se ve que y es divisible, como sabemos que y es impar pues sus dos factores lo seran, recordemos lo siguiente.... Un Numero impar es de la forma 2x+1, si se le multiplica un impar quedara 4x^2+4x+1 = 2*2(x^2+x)+1 que es un numero impar :P..jejej..

Ahora bien... dado eso, sabemos que la suma de dos numeros impares es uno par, por ende decir p = (a+b)/2 y q = (a-b)/2 es legal...ahora bien,  p+q = a y p-q = b, por ende y = (p+q)(p-q) por ende y = p^2-q^2 entonces y por lo cual tenemos que p^2=y+q^2... el caso es que ahora usamos iteracion breve como les mostrare en el siguiente programa..


Ojo! antes de hacer cualquier demostracion con programa es bueno aclarar, use una libreria llamada BigDecimal pero esta no me proporciona Sqrt() por lo cual cree una funcion en base a este texto que encontre http://mitpress.mit.edu/sicp/chapter1/node9.html

Código: (java) [Seleccionar]
import java.math.*;
public class Facto{
public static void main(String args[]){
BigDecimal cua = new BigDecimal(args[0]),k;
if(String.valueOf(k=Sqrtt(cua)).endsWith(".0000000000")){
System.out.println(k);
return;
}
k = new BigDecimal(String.valueOf(k).substring(0,String.valueOf(k).indexOf("."))).add(BigDecimal.ONE);
//System.out.println(k);
BigDecimal y;
while(!String.valueOf((y=Sqrtt((k.pow(2)).subtract(cua)))).endsWith(".0000000000"))
k=k.add(BigDecimal.ONE);
System.out.println(k.add(y)+"  "+k.subtract(y));
}
public static BigDecimal Sqrtt(BigDecimal cua){
BigDecimal tmp = new BigDecimal("1.0");
while(tmp.compareTo(((cua.divide(tmp,10, BigDecimal.ROUND_HALF_UP)).add(tmp)).divide(new BigDecimal("2.0"),10, BigDecimal.ROUND_HALF_UP))!=0)
tmp = ((cua.divide(tmp,10, BigDecimal.ROUND_HALF_UP)).add(tmp)).divide(new BigDecimal("2.0"),10, BigDecimal.ROUND_HALF_UP);
return tmp;
}
}

Espero que hayan disfrutado esto, es solo un comienzo...el codigo y el metodo son lentos, cosa que ire mejorando(esa es mi meta :p ;)

Saludos
:)

my.opera.com/phicar

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
Re: Factorizacion Euler
« Respuesta #1 : marzo 06, 2010, 12:26:28 pm »
Listo, jejeje ayer nu tenia internet tonces aca queda como factorizar por el metodo de euler en java ;)..

este solo recibe numeros de la forma 4m-1 tonces no intenten nada mas o no les resultara la cosa ;)

me da hartera explicar tonces

http://en.wikipedia.org/wiki/Euler's_factorization_method
 otra vez uso el metodo de raiz cuadrada de Newton en Sqrt() y uso el algoritmo de euclides en GcD para el maximo comun dividor ;)


Código: (java) [Seleccionar]
import java.math.*;
public class FactoEu{
public static void main(String args[]){
//System.out.println(Sqrt(new BigDecimal(args[0])));
BigInteger tmp = new BigInteger(String.valueOf(Sqrt(new BigDecimal(args[0]))).substring(0,String.valueOf(Sqrt(new BigDecimal(args[0]))).indexOf(".")));
System.out.println(tmp);
int p = 1;
BigInteger tod[] = new BigInteger[4];
for(BigInteger epa = new BigInteger("2");epa.compareTo(tmp)<=0;epa = epa.add(new BigInteger("2"))){
for(BigInteger epa2 = new BigInteger("1");((epa.pow(2)).add(epa2.pow(2))).compareTo(new BigInteger(args[0]))<=0;epa2 =epa2.add(new BigInteger("2"))){
if(((epa.pow(2)).add(epa2.pow(2))).compareTo(new BigInteger(args[0]))==0){
if(p==1){
tod[0]=epa;
tod[1]=epa2;
p++;
}else if(p==2){
if((tod[0].compareTo(epa)!=0)&&(tod[1].compareTo(epa2)!=0)){
tod[2]=epa;
tod[3]=epa2;
break;
}
}
}
}
}
//for(int n = 0;n<tod.length;n++)
//System.out.println(tod[n]);
BigInteger a = maxIn(tod[0],tod[2]);
BigInteger c = (a.compareTo(tod[0])==0)?tod[2]:tod[0];
BigInteger d = maxIn(tod[1],tod[3]);
BigInteger b = (d.compareTo(tod[1])==0)?tod[3]:tod[1];
BigInteger m = GcD(a.subtract(c),d.subtract(b));
BigInteger k =(a.subtract(c)).divide(m);
BigInteger l = (d.subtract(b)).divide(m);
BigInteger j = (a.add(c)).divide(l);
System.out.println((((m.divide(new BigInteger("2"))).pow(2)).add((j.divide(new BigInteger("2"))).pow(2)))+" "+((l.pow(2)).add(k.pow(2))));
}
public static BigInteger maxIn(BigInteger a,BigInteger b){
return (a.compareTo(b)>=0)?a:b;
}
public static BigInteger GcD(BigInteger a,BigInteger b){
if(b.compareTo(new BigInteger("0"))==0)
return a;
return GcD(b,a.mod(b));
}
public static BigDecimal Sqrt(BigDecimal cua){
BigDecimal tmp = new BigDecimal("1.0");
while(tmp.compareTo(((cua.divide(tmp,10,BigDecimal.ROUND_HALF_UP)).add(tmp)).divide(new BigDecimal("2.0"),10,BigDecimal.ROUND_HALF_UP))!=0)
tmp = ((cua.divide(tmp,10,BigDecimal.ROUND_HALF_UP)).add(tmp)).divide(new BigDecimal("2.0"),10,BigDecimal.ROUND_HALF_UP);
return tmp;
}
}
:)

my.opera.com/phicar