viernes, 26 de junio de 2015

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.
banner
Previous Post
Next Post

Hola, me llamo Andrés.Soy egresado de la carrera de Ingeniería Informática en la Universidad Nacional de Trujillo (Perú).Me considero autodidacta de corazón ,amante del mundo de la programación, software libre y hacking ético

2 comentarios: