Extended Gcd Function Having Problems Help Please!!!!


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 7 of 7

Thread: Extended Gcd Function Having Problems Help Please!!!!

  1. #1
    Join Date
    Jul 2004
    Posts
    7

    Extended Gcd Function Having Problems Help Please!!!!

    I am having trouble with the Extended Euclid Algorithm. A and B are the two numbers whose gcd I need to compute, c = 0, d = 1, e = 1, f = 0. The function is to return three numbers: gcd(a,b), the coefficient of a, and the coefficient of b. I do not know how to return the three values needed, can someone put me in the right direction, this actually already works when I run it, but I am not doing it correctly because of the return.

    This is my class…

    import java.math.BigInteger;
    public class ExEuclid
    {
    public static BigInteger ExEuclid(BigInteger a,BigInteger b,BigInteger c,BigInteger d,BigInteger e,BigInteger f)
    {
    if(b.compareTo(BigInteger.ZERO) == 0)
    {
    return e; // I HAVE TO RETURN VALUES A,E,F NOT JUST E???
    }
    else
    {
    return ExtendedEuclid(b, a.mod(b), e.subtract(a.multiply(c).divide(b)),f.subtract(a.multiply(d).divide(b)), c, d);
    }
    }
    }


    HERE IS HOW I HAVE BEEN CALLING IT FROM THE MAIN PROGRAM

    do
    {
    BigInteger getD = findD.ExEuclid(E,m,cZERO,dONE,D,fZERO);
    D = getD;
    while(D.compareTo(BigInteger.ZERO) < 0)
    {
    D = D.add(m);
    }
    }while(D.multiply(E.mod(m)).compareTo(BigInteger.ONE) == 0);

  2. #2
    Join Date
    Jul 2004
    Posts
    7
    IT IS SUPPOSED TO BE ExEuclid Not ExtendedEuclid when calling it, so here it is revised... If anyone could help I would greatly appreciate it!!!

    I am having trouble with the Extended Euclid Algorithm. A and B are the two numbers whose gcd I need to compute, c = 0, d = 1, e = 1, f = 0. The function is to return three numbers: gcd(a,b), the coefficient of a, and the coefficient of b. I do not know how to return the three values needed, can someone put me in the right direction, this actually already works when I run it, but I am not doing it correctly because of the return.

    This is my class…

    import java.math.BigInteger;
    public class ExEuclid
    {
    public static BigInteger ExEuclid(BigInteger a,BigInteger b,BigInteger c,BigInteger d,BigInteger e,BigInteger f)
    {
    if(b.compareTo(BigInteger.ZERO) == 0)
    {
    return e; // I HAVE TO RETURN VALUES A,E,F NOT JUST E???
    }
    else
    {
    return ExEuclid(b, a.mod(b), e.subtract(a.multiply(c).divide(b)),f.subtract(a.multiply(d).divide(b)), c, d);
    }
    }
    }


    HERE IS HOW I HAVE BEEN CALLING IT FROM THE MAIN PROGRAM

    do
    {
    BigInteger getD = findD.ExEuclid(E,m,cZERO,dONE,D,fZERO);
    D = getD;
    while(D.compareTo(BigInteger.ZERO) < 0)
    {
    D = D.add(m);
    }
    }while(D.multiply(E.mod(m)).compareTo(BigInteger.ONE) == 0);

  3. #3
    Join Date
    May 2004
    Posts
    219
    If you want to return more than one value, than use an array, or perhaps a class you made that holds all the values. I can't really tell what you're trying to do here. Maybe you could post your entire program?

    This is bizarre:
    Code:
    findD.ExEuclid(E,m,cZERO,dONE,D,fZERO);

  4. #4
    Join Date
    May 2004
    Posts
    219
    Code:
    public class Test
    {
      public static long&#091;&#093; gcd(long a, long b, long q, 
        long r, long s, long t, long result)
      {
        return b == 0 ? new long&#091;&#093; { a, s, t } :
          gcd(b,a%b,s,t,q-result*s,r-result*t,a/b);
      }
      public static void main(String&#091;&#093; args)
      {
        int a = 2322, b = 654;
        long&#091;&#093; ans = gcd(a,b,1,0,0,0,0);
        System.out.printf("GCD:\t%s\nA Coef:\t%s\n"+
          "B Coef:\t%s\n", ans&#091;0&#093;, ans&#091;1&#093;, ans&#091;2&#093; );
      }
    }
    Maybe that'll help...

  5. #5
    Join Date
    Jul 2004
    Posts
    7
    Here is all my classes and main program if this helps, if you could please guide me in the right direction... I feel like I am so close to completing this project. I am doing the RSA algorithm here...

    //Main program class...
    import java.math.BigInteger;
    import javax.swing.*;
    public class RSA
    {
    public static void main(String[] args)
    {
    MillerRabin MR = new MillerRabin();
    BigInteger p = new BigInteger("0");
    BigInteger q = new BigInteger("0");
    BigInteger a = new BigInteger("1");
    BigInteger b = new BigInteger("1");
    BigInteger D = new BigInteger("1");
    BigInteger gcd = new BigInteger("0");
    BigInteger E = new BigInteger("1");
    BigInteger c0 = new BigInteger("0");
    BigInteger d1 = new BigInteger("1");
    BigInteger f0 = new BigInteger("0");
    Euclid findE = new Euclid();
    boolean ProbablePrime = false;
    ExtendedEuclid findD = new ExtendedEuclid();

    do
    {
    p = MR.createPrime(512,100);
    System.out.println("p = " + p + "\n");
    for(int i = 1; i <=100; i++)
    {
    if(MR.isProbablePrime(p))
    {
    if(i == 100)
    {
    System.out.println("p IS a probable prime number\n");
    }
    }
    else
    {
    System.out.println("p is NOT a Probable Prime Number\n");
    break;
    }
    }
    q = MR.createPrime(512,100);
    System.out.println("q = " + q + "\n");
    for(int i = 1; i <=100; i++)
    {
    if(MR.isProbablePrime(q))
    {
    if(i == 100)
    {
    System.out.println("q IS a probable prime number\n");
    }
    }
    else
    {
    System.out.println("q is NOT a Probable Prime Number\n");
    break;
    }
    }

    }while(p == q);
    BigInteger n = p.multiply(q);//value for n
    BigInteger m = (p.subtract (a)).multiply(q.subtract (b));
    while(E.compareTo(n) != 0)
    {
    E = E.add(BigInteger.ONE);//E is incrementing each time through the loop.
    gcd = findE.GCD(E,m);//passing val E and m to GCD method
    if(gcd.compareTo(BigInteger.ONE) == 0) break;
    }
    do
    {
    BigInteger getD = findD.ExtendedEuclid(E,m,c0,d1,D,f0);
    D = getD;
    while(D.compareTo(BigInteger.ZERO) < 0)
    {
    D = D.add(m);
    }
    }while(D.multiply(E.mod(m)).compareTo(BigInteger.ONE) == 0);
    System.out.println("n = " + n + "\n");//prints value for n
    System.out.println("m = " + m);//prints value for m
    System.out.println("\nE = " + E + "\n");
    System.out.println("D = " + D + "\n");

    String userInput = JOptionPane.showInputDialog("Enter the string to encrypt");
    //IM STUCK HERE
    }
    }

    //EUCLID CLASS...
    import java.math.BigInteger;
    public class Euclid
    {
    public static BigInteger GCD(BigInteger num1,BigInteger num2)
    {
    if(num2.compareTo(BigInteger.ZERO) == 0) return num1;
    else return GCD(num2, num1.mod(num2));
    }
    }

    //EXTENDED EUCLID CLASS(THIS IS SUPPOSEd TO RETURN VALUES A, E and F, but I DO NOT KNOW HOW TO MAKE IT RETURN 3 IN THE IF STATEMENT????...

    import java.math.BigInteger;
    public class ExtendedEuclid
    {
    public static BigInteger ExtendedEuclid(BigInteger a,BigInteger b,BigInteger c,BigInteger d,BigInteger e,BigInteger f)
    {
    if(b.compareTo(BigInteger.ZERO) == 0)
    {
    return e;//SUPPOSED TO RETURN A,E,F ????
    }
    else
    {
    return ExtendedEuclid(b, a.mod(b), e.subtract(a.multiply(c).divide(b)),f.subtract(a.multiply(d).divide(b)), c, d);
    }
    }
    }

    MILLER RABIN CLASS...

    import java.math.BigInteger;
    import java.security.SecureRandom;
    class MillerRabin
    {
    public boolean isProbablePrime(BigInteger pval)
    {
    BigInteger[] qandm = getqm(pval);
    BigInteger qval = qandm[0];
    BigInteger neg = new BigInteger("-1");

    if (qval.compareTo(neg)==0) return false;
    SecureRandom r = new SecureRandom();
    BigInteger bval = new BigInteger(pval.bitLength(),r);
    BigInteger mval = qandm[1];
    BigInteger two = new BigInteger("2");
    BigInteger pminusone = pval.subtract(BigInteger.ONE);

    if (bval.modPow(mval,pval).compareTo(BigInteger.ONE)==0) return true;
    BigInteger j = BigInteger.ZERO;
    BigInteger indexval = mval;

    while (j.compareTo(qval)<0)
    {
    if (pminusone.compareTo(bval.modPow(indexval,pval))==0) return true;
    indexval = indexval.multiply(two);
    j = j.add(BigInteger.ONE);
    }
    return false;
    }
    public BigInteger[] getqm(BigInteger p)
    {
    p = p.subtract(BigInteger.ONE);
    BigInteger two = new BigInteger("2");
    BigInteger neg = new BigInteger("-1");
    BigInteger[] rt ={BigInteger.ZERO, BigInteger.ZERO};
    if (p.mod(two).compareTo(BigInteger.ZERO) != 0)
    {
    rt[0] = neg; rt[1] = neg;
    return rt;
    }
    BigInteger divisor = p.divide(two);
    BigInteger counter = BigInteger.ONE;
    while(/*count <= maxq && */divisor.mod(two).compareTo(BigInteger.ZERO)==0)
    {
    counter = counter.add(BigInteger.ONE);
    divisor = divisor.divide(two);
    }
    rt[0] = counter; rt[1] = divisor;
    return rt;
    }
    public BigInteger createPrime(int bitlength, int numTests)
    {
    SecureRandom s = new SecureRandom();
    BigInteger z = new BigInteger(bitlength, s);
    int h = 0;
    boolean testResult = false;
    while(h < numTests)
    {
    testResult = isProbablePrime(z);
    if(!testResult)break;
    else h++;
    }
    if(h==numTests)return z;
    else return createPrime(bitlength, numTests);
    }
    }

    I now need to implement the modular power algorithm which in pseudo-code is like this(I HAVE TO CONVERT THIS CODE BELOW INTO JAVA)...

    Function modPower(x,y,z)
    //x is the base
    //y is the exponent
    //z is the divisor for the modular division
    d = 1
    for i = (# of bits in y) to 0 step -1
    d = d * d
    d = d mod z
    if (the bit in b at position i = 1)
    d = d * x
    d = d mod z
    end if
    next
    return d

    I have to accept a string from a user, convert that string to a BigInteger, and pass that value to the modular power function, I have to use the same function for both encryption and decryption. the formulas for encryption and decryption are:

    Encryption: C = M^E mod n
    Decryption: M = C^D mod n

    We can only accept input using an input box with javax.swing.*; which is JOptionPane.showInputDialog. I am supposed to convert string to BigInteger using constructor public BigInteger(stringval);

    The values for E, D, and n are below + more, this is everything I need to solve it, I just do not know how I would use the function in JAVA, it is confusing me.

  6. #6
    Join Date
    Feb 2004
    Posts
    808
    Originally posted by Drain
    Maybe that'll help...
    like a charm...

    1.5 has variable numbers of args huh?
    more bloat.. woohoo
    The 6th edict:
    "A thing of reference thing can hold either a null thing or a thing to any thing whose thing is assignment compatible with the thing of the thing" - ArchAngel, www.dictionary.com et al.
    JAR tutorial GridBag tutorial Inherited Shapes Inheritance? String.split(); FTP?

  7. #7
    Join Date
    May 2004
    Posts
    219
    Originally posted by cjard
    like a charm...

    1.5 has variable numbers of args huh?
    more bloat.. woohoo
    Yeah... I dunno, I like it

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center