martes, 30 de junio de 2015

IMPLEMENTACIÓN DEL ALGORITMO BIG MCD


Con la implementación de este algoritmo podemos realizar operaciones mcd pero con números de n cifras y con una velocidad considerable

Por medio de teoría matemática usamos el modulo de una parte del numero para reemplazar el numero grande por uno mas pequeño de esta manera reducimos la complejidad y tiempo del problema

Ejemplo:

Paso 1: BIG_MCD(3421689512460,1442)
 
    big_num=3421689512460
    small=1442
 
Paso 2: Usamos un temporal para partir el numero big_num
 
    temp=342168951
    big_num=2460

Paso 3: Y buscamos su mod con small

    temp=temp%small
    temp=1097

Paso 4: Luego concatenamos el nuevo temporal con el big_num

    big_num=concatenar(temp,big_num)
    big_num=concatenar(1097,2460)
    big_num=10972460

Paso  5: Con los nuevos números en el MCD verificamos si los números resultantes son operables computacionalmente o si es necesario regresar al Paso 2 y aplicar otra vez el algoritmo para reducir big_num a menos cifras

    En este caso aplicamos mcd directamente


Ahora si el código en Java

Private void calcularActionPerformed(java.awt.event.ActionEvent evt) {                                         
        // TODO add your handling code here:
        String a,b,aux_b = null,aux,resul = "No Econtrado :(";
        boolean bucle=true;
        int cif1,cif2;
        a=n1.getText();
        b=n2.getText();
        Operaciones operar =new Operaciones();
        while(bucle)
        {
            if (a.compareTo(b)==0) {
                bucle=false;
                resul=a;
            } 
            else if(a.compareTo("0")==0)
            {
                bucle=false;
                resul=b;
            }
            else if(b.compareTo("0")==0)
            {
                bucle=false;
                resul=a;
            }            
            else if((a.length()>9)&&(b.length()>9))
            {
                resul = "No Econtrado :(";
            }
            else 
            {
                if(a.length()>9)
                {
                    //System.out.println("EL NUMERO 1 TIENEN MAS DE 9 CIFRAS");
                    //System.out.println(a);
                    a=operar.modular(a,b);
                    //System.out.println("EL nuevo A es : "+a);
                    //System.out.println("EL nuevo B es : "+b);
                }
                else if(b.length()>9)
                {
                    //System.out.println("EL NUMERO 2 TIENEN MAS DE 9 CIFRAS");
                    //System.out.println(b);
                    aux=a;        
                    a=b;
                    b=aux;
                    //System.out.println("EL nuevo A es : "+a);
                    //System.out.println("EL nuevo B es : "+b);
                }
                else
                {
                    //System.out.println("YA TERMINO :)");
                    //System.out.println(a+" , "+b);
                    resul=operar.mcd(a,b);
                    bucle=false;
                }
            }
        }
        resultado.setText(resul);
    }                                        

    private void limpiarActionPerformed(java.awt.event.ActionEvent evt) {                                        
        // TODO add your handling code here:
        n1.setText("");
        n2.setText("");
        resultado.setText("");
    }      

    public boolean mayor(String a, String b) {
        if(a.length()>b.length())
        { 
            return true;
        }
        else if(a.length()==b.length())
        { 
            int i=0;
            while(i<=a.length()-1)
            { 
                if(sacarnumero(a,i)>sacarnumero(b,i))
                { 
                    return true; 
                }
                if(sacarnumero(a,i)<sacarnumero(b,i))
                { 
                    return false;
                }
                else
                    i++;
                
            }
        }
        return false;
    }

    public String restar(String a, String b) {
        int i=a.length()-1;
        int j=b.length()-1;
        int an,bn,acarreo = 0;
        String res = ""; 
        while(i>=0)
        {    
            an=sacarnumero(a,i);
            if (j>=0) {
                bn=sacarnumero(b,j);
            }
            else
                bn=0; 
            if(an>=bn)
            { 
                    if (an-bn-acarreo<0) { 
                        res=res+String.valueOf(10+an-bn-acarreo); 
                        acarreo=1;
                    }
                    else
                    {
                        res=res+String.valueOf(an-bn-acarreo); 
                        acarreo=0;
                    }
            }
            else
            { 
                res=res+String.valueOf(10+an-bn-acarreo); 
                acarreo=1;
            }
            i--;
            j--;
        }
        StringBuilder builder=new StringBuilder(res);
        return builder.reverse().toString();
    }
    
    public String limpiador(String a) {
        String b="";
        char cero='0';
        int i = 0;
        while(a.charAt(i)==cero&&i<a.length()) 
        {
            i++;
        }
        while(i<a.length()) 
        {
            b=b+a.charAt(i); 
            i++;
        }
        return b;
    }
    
    public String modular(String a, String b) { 
        String temp,nBig;
        int n1,n2;
        temp=a.substring(0, 9);
        nBig=a.substring(9, a.length());
        n1=Integer.parseInt(temp);
        n2=Integer.parseInt(b); 
        if (n1>n2) {
            nBig=String.valueOf(n1%n2)+nBig;
        }
        return nBig;
    }

    public String mcd(String n1, String n2) {
        int a,b;
        a=Integer.parseInt(n1);
        b=Integer.parseInt(n2);
        while(b>0){
            if(a>b)
            {
                a=a-b;
            }
            else
            {
                b=b-a;
            }
 }
        n1=String.valueOf(a);
        return n1;
    }
    
    private static int sacarnumero(String a, int i) {
        return Integer.parseInt(String.valueOf(a.charAt(i)));
    }

domingo, 28 de junio de 2015

IMPLEMENTACION DEL ALGORITMO RHO POLLARD EN JAVA



El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.
El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.

Algoritmo:

Entrada:  Un número entero  “n” que no sea una potencia prima. 
Salida : Factor no trivial de «n»
a ← 2;
b ← 2;
PARA (i = 1, 2, . . .);
a ← a2 + 1 mod n;
b ← b2 + 1 mod n;
b ← b2 + 1 mod n;
d ← mcd(abs(a – b), n);
SI (1 < d < n)
Retornar d; 
SI (d >= n)
Retornar Sin exito; 
FIN PARA;
//Observación: Una potencia prima es una potencia entera y positiva de un
// número primo. Por ejemplo 5=5¹, 9=3² son potencias primas, 
//mientras que 6=2×3, 15=3×5 y 36=6²=2²×3² no lo son.
Implementación: 

Nota:La función rho usa como función auxiliar una llamada mcd, puedes usar cualquiera que ya hallas implementado en mi caso yo use el algoritmo de euclides extendido (ver publicación acerca de euclides extendido).

Función rho:
public boolean rho()
    {
        int a=2, b=2,d=1;
        boolean bandera;
        while(d==1)
        {
            a=((a*a)+1)%numero;
            b=((b*b)+1)%numero;
            b=((b*b)+1)%numero;
            d=(int) EuclidesIterativo(abs(a-b),numero);
            ca.add(a);
            cb.add(b);
            cd.add(d);
        }
        if(d>1 && d < numero)
        {
            bandera=true;
            return  bandera;
        }
        else
        {
            //NO EXISTE FACTOR TRIVIAL
            bandera=false;
            return bandera;
        }
    }
//Estoy almacenando cada valor que toma a,b y d para mostrarlo posteriormente
//en una interfaz, pero si deseas obtener el primer factor directamente , basta
//con imprimir el ultimo valor de "d".
Ejemplo:
Sea n = 8051 un número entero, el algoritmo reporta el factor no trivial 97. El otro factor es 83(Este factor se obtiene dividiendo n entre el factor no trivial obtenido por el algoritmo de Rho Pollard).




sábado, 27 de junio de 2015

ALGORITMO DE LA RAÍZ CUADRADA MODULAR CUANDO N ES NUMERO COMPUESTO EN JAVA



En una publicación anterior pudimos observar tanto el algoritmo que se usa para obtener la raíz cuadrada si es que la hubiera así como la implementación , claro esta esto fue cuando N era numero Primo , en esta oportunidad lo  haremos cuando N es numero Compuesto, cabe recalcar que para mayor comodidad de mi parte habrá partes en la implementación que solo mencionare las funciones usadas ya que como indique en la publicación anterior , la raíz cuadrada abarca muchas operaciones extra que ya hemos implementado anteriormente por lo que les dejare el link correspondiente a estas cuando se les haga mención, bueno comencemos.

Algoritmo



Básicamente el algoritmo para números compuestos consiste en factorizar a N en dos factores primos distintos e impares(p y q, donde p>q) y aplicarle el algoritmo de raíz cuadrada cuando  N es primo   por separado en la cual obtendremos las raíces (r,-r)  y (s,-s) para luego continuar con lo que resta del algoritmo.



Implementación:
Clase Factorización:
public class Factorizacion {
    public ArrayList< integer > factorizar(int numero)
    {
        ArrayList< integer > factores = new ArrayList<>();
        int i=3;
        while(numero!=1)
        {
            while(numero%2==0)
            {
                factores.add(2);
                numero=numero/2;
            }
            while(numero%i==0)
            {
                factores.add(i);
                numero=numero/i;
            }
            i++;
        }
        return factores;
    }
}
Clase Raíz Cuadrada Compuesta:
public class RaizCompuesta {
    int p,q,a,c,d,x,y,r,s,n;
    int raicesF[]=new int[4];
    ArrayList< Integer > factores = new ArrayList<  >();
    int raizP1[]=new int[2],raizP2[]=new int[2];
    Factorizacion obj= new Factorizacion();
    boolean aux1,aux2;//Sirven para validar la existencia de las raices
    public int[] CalcularRaizCompuesta(int p1,int a1)
    {
        factores=obj.factorizar(p1);
        p=factores.get(1);
        q=factores.get(0);
        a=a1;
        n=p*q;
        System.out.println("p: "+p);
        System.out.println("q: "+q);
        //System.out.println("p: "+p);
        //System.out.println("q: "+q);
        Raiz objRaiz1 = new Raiz();
        Raiz objRaiz2 = new Raiz();
        aux1=objRaiz1.CalcularRaiz(p,a);
        aux2=objRaiz2.CalcularRaiz(q,a);
        if(aux1==false||aux2==false)
        {
            return null;
        }
        else
        {
            raizP1=objRaiz1.getRaiz();
            raizP2=objRaiz2.getRaiz();
            Euclides objEuclides= new Euclides();
            long mcd[]=new long[3];
            mcd= objEuclides.euclidesExtendido((long)p, (long)q);
            c=(int) mcd[1];
            d=(int) mcd[2];
            //System.out.println("c:"+c);
            //System.out.println("d:"+d);
            r=raizP1[0];
            s=raizP2[0];
            //System.out.println("r: "+r);
            //System.out.println("s: "+s);
            x=(r*d*q+s*c*p)%(n);
            y=(r*d*q-s*c*p)%(n);
            //System.out.println("X: "+x);
            //System.out.println("Y: "+y);
            raicesF[0]=x%n;
            raicesF[1]=-1*raicesF[0];
            raicesF[2]=y%n;
            raicesF[3]=-1*raicesF[2];
            for(int i=0;i< 4;i++)
            {
                if(raicesF[i]< 0)
                {
                    raicesF[i]=raicesF[i]+n;
                }
            }
            return raicesF;
        }    
    }
    
}
Fragmento del código de la Interfaz Principal:
public class Factorizacion {
        RaizCompuesta obj= new RaizCompuesta();
        int raices[]=new int[4];
        raices=obj.CalcularRaizCompuesta(Integer.parseInt(numero_p.getText()),Integer.parseInt(numero_a.getText()));
        if(raices==null)
        {
            JOptionPane.showMessageDialog(null, "NO EXISTEN RAICES");
        }
        else
        {
            raiz_1.setText(""+raices[0]);
            raiz_2.setText(""+raices[1]);
            raiz_3.setText(""+raices[2]);
            raiz_4.setText(""+raices[3]);
        }
Espero les sea de utilidad y hasta la siguiente Publicación.

viernes, 26 de junio de 2015

RAIZ CUADRADA MODULAR CUANDO N ES NUMERO PRIMO



El problema de la raíz cuadrada modulo «n» es muy usado en criptografía, donde para hallar la raíz se debe tener en cuenta que un número entero «n» es primo o tal vez compuesto. Si «n» es primo, entonces la raíz cuadrada módulo n es fácilmente obtenida, pero si «n» es un número compuesto entonces hallar tal raíz es difícil ya que sus factores primos son desconocidos.
En este post veremos la implementación  de la raíz cuadrada cuando n es primo.

Algoritmo:





Implementación:
La operación de Raíz cuadrada es una que combina varios conocimientos previos como son:


Por lo que recomendamos ver las publicaciones referentes a cada una ya que por motivos de comodidad solo mencionare cada función:

Función Multiplicación Modular:
public int CalcularMultiplicacion(int a,int b,int z)
    {
        int respuesta;
        respuesta=(a*b)%z;
        return respuesta;
    }
Función Exponencial:
public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }
Función Raíz Cuadrara:
public class Raiz {
    boolean bandera=true;
    int raiz[]= new int[2];

    public int[] getRaiz() {
        return raiz;
    }

    public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }
    public boolean CalcularRaiz(int p,int a)
    {
       int aux=0,auxc=0,b = 0,s=0,t,Ia=0,c=0,r=0,d=0,base=0,exponente=0,aux_exp;
        Jacobi obj = new Jacobi();
        if(obj.Opjacobi(a,p)==-1)
        {
            bandera=false;
            return bandera;
        }
        
        while(aux!=-1)
        {
            auxc++;
            aux=obj.Opjacobi(auxc, p);
            b=auxc;
        }
        
        s=funcion_exponencial(p-1);
        aux_exp=(int)Math.pow(2,s);
        t= ((p-1)/aux_exp);
        Inverso inv= new Inverso();
        Ia=(int) inv.CalcularInverso((long)a, (long)p);
        Exponenciacion exp = new Exponenciacion();
        c=exp.CalcularExp(b, t, p);
        r=exp.CalcularExp(a, ((t+1)/2), p);
        for(int i=1;i<=s-1;i++)
        {
            base=r*r*Ia;
            exponente=(int) Math.pow(2,s-i-1);
            d=exp.CalcularExp(base,exponente,p);
            if((d+1)%p==0)
            {
                Multiplicacion mul=new Multiplicacion();
                r=mul.CalcularMultiplicacion(r, c, p);
            }
        }
        System.out.println(r);
        c=exp.CalcularExp(c, 2, p);
        this.raiz[0]=r;
        this.raiz[1]=-r;
        return bandera;
    }
}
Fragmento de codigo de Interfaz Principal
        boolean rpta;
        int raices[]=new int[2];
        Raiz obj = new Raiz();
        rpta=obj.CalcularRaiz(Integer.parseInt(numero_p.getText()),Integer.parseInt(numero_a.getText()));
        if(rpta==false)
        {
            JOptionPane.showMessageDialog(null, "NO EXISTEN RAICES");
        }
        else
        {
            raices=obj.getRaiz();
            raiz_1.setText(String.valueOf(raices[0]));
            raiz_2.setText(String.valueOf(raices[1]));
        }
Bueno espero que les sea de utilidad esta es una de las operaciones mas importantes de la criptografía , en otra publicación realizare la implementación de la raíz cuadrada pero para números compuestos.

Actualización

Aquí les dejo la implementacion cuando N es un numero compuesto:



IMPLEMENTACIÓN DE LA EXPONENCIACIÓN MODULAR EN Z


La exponenciación modular es un tipo de exponenciación realizada sobre un módulo. Es particularmente útil en ciencias de la computación, especialmente en el campo de la criptografía.

Algoritmo:
Entrada:  a E Zn , k E Z  tal que 0 ≤ k < n
Salida : ak mod n
 int exp=1;
 int xp= a%n;
 Mientras (k>0) Hacer     
     si(k%2!=0) 
                         exp= (exp*xp)%n;
             fin si
     xp=(xp*xp)%n;
     k= k/2;
     Fin Mientras
 Retornar (exp)
Implementación:

public int CalcularExp(int a,int k,int z)
    {
        int exp=1;
        int xp=a%z;
        while(k>0)
        {
            if((k%2)!=0)
            {
                exp=(exp*xp)%z;
            }
            xp=(xp*xp)%z;
            k=k/2;
        }
        return exp;
    }

IMPLEMENTACIÓN DEL INVERSO MULTIPLICATIVO MODULAR EN JAVA

Dados los números enteros a y n > 0, el inverso multiplicativo de «a modulo n» esta dado por el numero entero «y» E Zn , tal que

a*y ≡ 1(mod n)

Es importante tener en cuenta que si «y» existe, entonces es único, y «a» es llamado invertible. Por notación, el inverso de «a» se denota por:


Propiedad:
Sea «a» E Zn , entonces «a» es invertible si y solamente si el mcd(a, n)= 1.

Algoritmo:
Entrada:  a E Zn
Salida : Existencia  del inverso
Hallar «x» e «y» tal que nx + ay = d; es decir usar: euclides_extendido(Zn,a)
    SI (d > 1)
    retornar (Inverso no existe)
CASO  CONTRARIO
    SI (y<0)
     retornar (y+n)
    CASO CONTRARIO
  retornar (y)
    FIN_SI
FIN_SI

IMPLEMENTACIÓN:

Clase Euclides:
public class Euclides {
    public int x=0,y=0;

    public double getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
    public double getX() {
        return x;
    }
    public void setX(int x){
        this.x = x;
    }
    public double euclidesExtendido(double a, double b){ 
        int d=0,x=0,y=0;
        if(b==0)
        {
            d=(int) a;
            x=1;
            y=0; 
            return d;
        }
        int x2 = 1, x1 = 0, y2 = 0, y1 = 1;
        double q=0, r=0;
        while(b>0)
        {
            q = (a/b);
            r = a%b;
            x = (int) (x2-q*x1);
            y = (int) (y2-q*y1);
            a = b;
            b = r;
            x2 = x1;
            x1 = x;
            y2 = y1;            
            y1 = y;
            d=(int) a;
        }
        x = x2;
        y = y2;
        this.setY(y);
        this.setX(x);
        return d;
    }
}
Clase Inverso:
/**
 *
 * @author Andres Esquivel
 */
import javax.swing.JOptionPane;

public class Inverso {
    public double CalcularInverso(long n,long z)
    {
        long mcd[] =new long[3];
        int x=0,y = 0;
        Euclides obj = new Euclides();
        if(n >z)
        {
            mcd=obj.euclidesExtendido(n,z);
        }
        if(n< z)
        {
            mcd=obj.euclidesExtendido(z,n);
        }
        
        System.out.println("MCD: "+mcd[0]);
        if(mcd[0] >1)
        {
            System.out.println("EL INVERSO NO EXISTE");
            y=0;
        }
        else
        {
            y=(int) mcd[2];
            if(y< 0)
            {
                y=(int) (y+z);
            }
        }
        //System.out.println("Hola y:" +y);
        return y;
    }
}
Clase Principal:
public class Principal {
    public static void main(String[] args) {
        Inverso obj = new Inverso();
        double aux_resultado;
        //numero_a  y numero_z son los datos que se ingresan por el usuario , donde numero_a es el numero que quiere hallar la inversa y numero_z representa a Z
        aux_resultado=obj.CalcularInverso(numero_a,numero_z);
        if(aux_resultado==0)
        {
            JOptionPane.showMessageDialog(null, "LA INVERSA NO EXISTE");
        }
        else
        {
            System.out.println("EL INVERSO ES: "+aux_resultado);
        }
    } 
}
Espero les sea de mucha utilidad ,saludos y hasta la próxima publicación.

IMPLEMENTACIÓN DE LA CRIBA DE ERASTOTENES EN JAVA



La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado n. Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera:

  • Hallamos la raíz cuadrada de n(rc).
  • Obtenemos los primos menores a la raíz cuadrada de n(rc).
  • Se presenta gráficamente el proceso de Erastotenes  aplicado a cada uno de los primos menores a rc.Se marca todos los múltiplos mayores a cada primo menor que rc.
  • Después  de marcar , todos los números que quedan diferentes de 1 serán los números primos existentes entre 2 y n.
Ejemplo: Aplicar la criba de Erastotenes para los primeros 100 números naturales.

Paso 1: Raíz cuadrada de 100 = 10
Paso 2: Primos menos que 10= {2,3,5,7}
Paso 3: 







Paso 4: Listar números primos de 2 a N: 
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

IMPLEMENTACIÓN EN JAVA:

public ArrayList< Integer > CribaE()
    {
        ArrayList< Integer > aux_primos = new ArrayList<>();
        ArrayList< Integer > listade2aN = new ArrayList<>();
        int aux,i=3;
        aux=(int) Math.sqrt(numero);//SACANDO LA RAIZ CUADRADA DE N
        aux_primos.add(2);//PRIMER ELEMENTO DEL ARRAY AUXLIAR D EPRIMOS QUE SERVIRAM PARA APLICAR LA CRIBA
        int contador=0;
        while(i< aux)
        {
            if(aux_primos.size()==1)
            {
                aux_primos.add(i);
            }
            else
            {
                for(int k=0;k < aux_primos.size();k++)
                {
                    if(i%aux_primos.get(k)==0)
                    {
                        contador++;
                    }
                }
                if(contador==0)
                {
                    aux_primos.add(i);//AGREGANDO A LA LISTA AUXLIAR TODOS LOS PRMOS MENORES QUE LA RAIZ CUADRADA
                }
            }
            i=i+2;
            contador=0;
        }
        for(int j=0;j < (numero);j++)
        {
            listade2aN.add(j+1);
        }
        for(int m=0;m< aux_primos.size();m++)
        {
            for(int h=0;h< listade2aN.size();h++)
            {
                if(listade2aN.get(h)==1)
                {
                    listade2aN.remove(h);//PARA ELIMINAR EL 1
                }
                if((listade2aN.get(h)%aux_primos.get(m)==0)&&(listade2aN.get(h)!=aux_primos.get(m)))
                {
                    listade2aN.remove(h);//ELIMINANDO A LOS MULTIPLOS DE LOS PRIMOS MENORES A LA RAIZ DE N
                }
            }
        }
        return listade2aN;
    }

IMPLEMENTACIÓN DEL SIMBOLO DE JACOBI EN JAVA




Antes de hablar acerca del símbolo de jacobi es necesario hablar acerca del símbolo de Legendre , ya que esta es una generalización de este.

Símbolo de Legendre:
Sean «p» un número primo e impar, «a» un número entero positivo menor que «p». Entonces el símbolo de Legendre (a/p) se define por:


De acuerdo con la definición anterior podemos notar que es posible tener un conjunto de residuos cuadráticos , denotados por Qp,cuyo valor es 1.
Ejemplo:



Como ya mencione antes Jacobi es una generalización de Legendre.
Jacobi se define como:
Existe un algoritmo de tiempo polinomial que computa el símbolo de Jacobi (a/n) , siempre que “n” es un número impar grande mayor que l y «a» es un numero que va desde cero hasta «n-1».

Algoritmo:
Función Exponencial , necesario para hallar el Símbolo de Jacobi
Func_exp(x)
 cont=0
 Mientras (x mod 2 == 0) hacer
  x=x/2
  cont=cont+1
 Fin mientras
retornar (cont)

Función Jacobi:




IMPLEMENTACIÓN:

Función Exponencial:

public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }

Función para calcular el símbolo de jacobi:

    public int Opjacobi(int a , int n)
    {
        int a1,e,s = 0,n1;
        if(a==0)
        {
            return 0;
        }
        if(a==1)
        {
            return 1;
        }
        e=funcion_exponencial(a);
        a1=(int) (a/Math.pow(2,e));
        //  Asignando valores
        if(e%2==0)
        {
            s=1;
        }
        else
        {
            if(((n-1)%8==0)||((n-7)%8==0))
            {
                s=1;
            }
            else
            {
                if(((n-3)%8==0)||((n-5)%8==0))
                {
                    s=-1;
                }
            }
        }
        //Cambiando Signo
        if(((n-3)%4==0)&&((a1-3)%4==0))
        {
            s=-1*s;
        }
        n1=n%a1;
        if(a1==1)
        {
            return s;
        }
        else
        {
            return s*Opjacobi(n1,a1);
        }
    }



IMPLEMENTACIÓN DEL ALGORITMO DE EUCLIDES EN JAVA






El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebrateoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
Algoritmo:




EuclidesVersión Interativa:

public double EuclidesIterativo(double a, double b){
            
       while(b>0){
         
           if(a>b){
               a = a - b;
           }
           else{
               b = b - a;
           }
       }
      
       return a;
       
    }

EuclidesVersión Recursiva:

ublic double EuclidesRecursivo(double p, double q) {
        if (q == 0) return p;
        else return EuclidesRecursivo(q, p % q);
    }

    public Euclides() {
    }

Espero que les sea de utilidad , hasta la siguiente publicación.

IMPLEMENTACIÓN DEL ALGORITMO DE EUCLIDES EXTENDIDO EN JAVA






El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
Algoritmo:


Euclides Extendido Versión Interativa:

public class Euclides {
    public long[] euclidesExtendido(long a, long b) 
{
 long[] resp = new long[3];
 long x=0,y=0,d=0;
 if(b==0)
 {
  resp[0] = a; resp[1] = 1; resp[2] = 0;
 } 
 else
 {
  long x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  long q = 0, r = 0;
  while(b>0)
  {
   q = (a/b);
   r = a - q*b;
   x = x2-q*x1;
   y = y2 - q*y1;
   a = b;
   b = r;
   x2 = x1;
   x1 = x;
   y2 = y1;
   y1 = y;
  }
  resp[0] = a;
  resp[1] = x2;
  resp[2] = y2;
    }
 return resp;  
    } 
}

Euclides Extendido Versión Recursiva:

 
//mcd=0,x=0,y=0 en un inicio
public double euclidesExtendidoRe(double a, double b,double mcd,double x, double y)
{     
        double x2=0.0,y2=0.0,x1=0.0,y1=0.0;
        if (b == 0)  {  
            mcd = a;
            x2 = 1;
            y2 = 0;
        }
        else
        {     
            euclidesExtendidoRe (b,a%b,mcd,x,y);
            x1= x2; y1=y2; x2=y1;
            y2=x1- (a/b)*y1;   
        }
        return mcd;
} 

Espero que les sea de utilidad , hasta la siguiente publicación.

jueves, 18 de junio de 2015

ANÁLISIS Y DISEÑO DE ALGORITMOS - INTRODUCCIÓN




El razonamiento de las computadoras es diferente al de los seres humanos, es por ello que a quienes comienzan a programar les resulta una tarea difícil. El primer paso es no desesperarse, después se debe entender cómo razonan los humanos y posteriormente analizar cómo lo haría una computadora. Es importante hacer hincapié en que la parte más compleja de este proceso es el desarrollo de un algoritmo (diagrama de flujo o pseudocódigo), ya que constituye la parte lógica. Codificar, independientemente del lenguaje, es simplemente trascribir un algoritmo al lenguaje respectivo. El concepto de algoritmo lo utilizamos, en general, todas las disciplinas basadas en las matemáticas y la física, por ende en la programación, y es la etapa previa a la codificación.

1. ¿QUÉ ES UN ALGORITMO?

Un algoritmo es un método para resolver un problema.

Un ser humano piensa y se comporta como tal siguiendo una secuencia lógica de acciones. Esta misma asociación podría acoplarse en cuanto al rol de una computadora se refiere.
Afirmando que una computadora es una máquina electrónica capaz de realizar y manejar datos en memoria siguiendo una secuencia lógica de pasos, para aquellos que haya sido programada.
Los algoritmos poseen hoy una gran importancia tanto para informática , robótica y ciencias de la computación , por medio de algoritmos se llega a un orden de ideas y un  proceso correcto en la elaboración de maquinarias y robots lo que conlleva a un avance en la tecnología y un mayor progreso a nivel mundial
Los algoritmos conllevan a llevar un proceso y un orden de ideas en todos los aspectos , pues cada actividad por mínima que sea requiere un orden que se da por medio de los grandes algoritmos que creamos así sean mentales.
La resolución de problemas exige el diseño de un algoritmo que resuelva el problema propuesto.



2. ¿QUÉ ES UN LENGUAJE DE PROGRAMACIÓN?

Tendemos a pensar como lenguaje natural aquel medio utilizado por una persona para expresar algún sentimiento o emoción, es decir de manera más general un proceso pues  nos permite interactuar en muchos sentidos.
En el rol de una computadora es más o menos lo mismo pues definimos como lenguaje de programación aquel conjunto de normas o reglas lógicas definidas por medio de símbolos o palabras  claves (reservadas) que nos permitan construir un programa o simplemente otorgar la solución a un problema.
El lenguaje de programación es la combinación de símbolos y reglas que permiten la elaboración de programas con los cuales la computadora puede realizar tareas o resolver problemas de manera eficiente.

3. RELACIÓN ENTRE EL DISEÑO DE ALGORITMOS Y LOS  LENGUAJES DE PROGRAMACIÓN

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta.
En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será el mismo. Así por ejemplo una persona puede expresar una receta de cocina en español, inglés, francés, etc. los pasos para la elaboración del plato serán los mismos sin importar lo mismo.
En la ciencia dela computación y la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectué el proceso correspondiente.

4. FASES PARA LA RESOLUCIÓN DE PROBLEMAS INFORMÁTICOS

La Principal razón para que las personas aprendan a programar en general  y los lenguajes de programación en particular es utilizar la computadora como herramienta para la resolución de problemas. Ayudando por una computadora, la  resolución de un problema se puede dividir en 3 fases importantes:




    4.1.  Análisis del Problema:


El propósito del análisis de un problema es ayudar al programador para llegar a una cierta comprensión de la naturaleza del problema.
El Problema debe de estar bien definido si se desea llegara una solución satisfactoria.
Para poder definir con precisión el problema se requiere que las especificaciones de entrada y salida sean descritas con detalle.


Ejemplo:

Leer el radio de un círculo y calcular e imprimir su superficie y la longitud  de la circunferencia.

Análisis:

*   Definición del Problema:Calcular e imprimir su superficie y la longitud  de la circunferencia.
*   Especificaciones de entrada: Los datos de entrada en este problema se concretan en el radio del círculo.
*   Especificaciones de Salida: Las salidas serán 2 variables que son la superficie y la longitud de la circunferencia

   4.2. Diseño de Algoritmo:

Una Computadora no tiene la capacidad de solucionar problemas más que cuando se le proporciona los sucesivos pasos a realizar.Estos Pasos sucesivos que se indican las instrucciones a ejecutar por la maquina constituye, como ya conocemos, el algoritmo.
La información proporcionada al algoritmo constituye su entrada y la información producida por el algoritmo constituye su salida.
Los problemas más complejos se pueden subdividir en sub problemas que sean más fáciles de solucionar que el original (Divide y vencerás).

La descomposición del problema original en sub problemas más simples y a continuación dividir estos en sub problemas en otros más simples que pueden ser implementados para su solución en la computadora se denomina diseño descendente.


A. DISEÑO DESCENDENTE (DIVIDE Y VENCERÁS): El diseño descendente es una forma de afrontar un proyecto de programación que consiste en empezar por lo más general e ir avanzando nivel a nivel hacia lo más particular.Consiste en dividir el problema en sub problemas más pequeños, que se pueden tratar de forma separada.

B.  REFINAMIENTO POR PASOS: El diseño de un algoritmo no se hace de una sola vez, sino que se va resolviendo en una secuencia de pasos (llamados pasos de refinamiento).
En cada paso el problema es refinado agregando detalles significativos, por lo que el método se conoce como: método de los refinamientos sucesivos.
Como es natural, dependiendo de la complejidad del problema se necesitaran diferentes y sucesivos niveles de refinamiento antes de que pueda obtenerse un algoritmo con suficiente nivel de detalle. 



Ejemplo: El problema del cálculo de la circunferencia y superficie de un círculo se puede descomponer en sub problemas más simples: leer datos de entrada, calcular superficie y longitud, y escribir resultados.




C. HERRAMIENTAS DE REPRESENTACIÓN GRÁFICA DE ALGORITMOS:



Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.




PSEUDOCODIGO


El pseudocódigo es una herramienta utilizada para el diseño de programas que permite al programador expresar sus pensamientos de una forma clara utilizando su lenguaje natural y mostrando el orden de ejecución de las sentencias del programa sin ninguna ambigüedad.


  • Publicación acerca del uso de Pseudocodigo (Pronto).




DIAGRAMAS DE FLUJO:


Un diagrama de flujo utiliza símbolos estándar en el que  cada paso del algoritmo se visualiza dentro del símbolo  y en el orden en que estos pasos se ejecutan, se indica conectándolos con flechas llamadas líneas de flujo, ya que indican el flujo lógico del algoritmo.


  • Publicación acerca del uso de Diagramas de Flujo (Pronto).




DIAGRAMAS N-S
Son una herramienta que favorece la programación estructurada y reúne características gráficas propias de diagramas de flujo y lingüísticas propias de pseudocódigos. Constan de una serie de cajas contiguas que se leerán siempre de arriba-abajo y sus estructuras lógicas son las siguientes:


  • Publicación acerca del uso de Diagramas N-S (Pronto).