Extended Gcd Function Having Problems Help Please!!!!

[cinunited14]

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);

[cinunited14]

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);

[Drain]

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:

findD.ExEuclid(E,m,cZERO,dONE,D,fZERO);

[Drain]

public class Test
{
  public static long[] gcd(long a, long b, long q, 
    long r, long s, long t, long result)
  {
    return b == 0 ? new long[] { a, s, t } :
      gcd(b,a%b,s,t,q-result*s,r-result*t,a/b);
  }
  public static void main(String[] args)
  {
    int a = 2322, b = 654;
    long[] 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[0], ans[1], ans[2] );
  }
}

Maybe that'll help...

[cinunited14]

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.

[cjard]

Originally posted by Drain
Maybe that'll help...

like a charm...

1.5 has variable numbers of args huh?
more bloat.. woohoo

[Drain]

Originally posted by cjard
like a charm...

1.5 has variable numbers of args huh?
more bloat.. woohoo

Yeah... I dunno, I like it