Nevermind I was able to figure it out. Thanks! Will give lifesaver if you can he
ID: 3623149 • Letter: N
Question
Nevermind I was able to figure it out. Thanks!
Will give lifesaver if you can help my code!
I'm having issues getting the inverse mod to print out. The program needs to:
1. Find the GCD(a,n) - which it does without a problem.
2. Find the inverse of a(mod n). Something is really screwed up there and I can't seem to fix it.
Code:
import java.util.Scanner;
public class inverse
{
public static void main (String[] args)
{
Scanner keyboard = new Scanner(System.in);
long a, n, c, x;
long gcd = 0;
System.out.println("Please enter your dividend (or mod):");
n = keyboard.nextLong();
System.out.println("Please enter your divisor:");
a = keyboard.nextLong();
n = c;
a = x;
while (n != 0)
{gcd=a;
a = n % a;
n = gcd;
}
System.out.println("Results: GCD(" + c + ", " + x + ") = " + gcd);
//Name: Inverse Mod m
//Find v such that d=gcd(a,m)=a x v mod m, if d=1 then v is the inverse of a modulo m
long d1, m, v1, v2, d2, q, t2, t3, v, d;
d1 = n;
v1 = 0; v2 = 1; d2 = a; v=0;
while (d2 != 0)
{
q = d1 / d2;
t2 = v1 - q*v2;
t3 = d1 - q*d2;
v1 = v2; d1 = d2;
v2 = t2; d2 = t3;
v=v2;
}
System.out.println("The inverse of "+n+" mod "+a+" is "+v);
}
}
Explanation / Answer
class Inverse {
static int[] gcd(int p, int q) {
if (q == 0)
return new int[] { p, 1, 0 };
int[] vals = gcd(q, p % q);
int d = vals[0];
int a = vals[2];
int b = vals[1] - (p / q) * vals[2];
return new int[] { d, a, b };
}
static int inverse(int k, int n) {
int[] vals = gcd(k, n);
int d = vals[0];
int a = vals[1];
int b = vals[2];
if (d > 1) { System.out.println("Inverse does not exist."); return 0; }
if (a > 0) return a;
return n + a;
}
public static void main(String[] args) {
int k = 30;
int n = 25;
System.out.println("GCD Is "+ gcd(k,n)[0] + " And its Inverse is " + inverse(k, n));
System.out.println("Your Implementation is ");
int u1 = 1,u2 = 0,d1 = n;
int v1 = 0,v2 = 1,d2 = k;
while (d2 != 0)
{
//loop computations
int q = d1/d2;
int t1 = u1 - q*u2;
int t2 = v1 - q*v2;
int t3 = d1 - q*d2;
u1 = u2; v1 = v2; d1 = d2;
u2 = t1; v2 = t2; d2 = t3;
}
int u=u1;
int v=v1;
int d=d1;
System.out.println("GCD Is "+ d);
while (d2 != 0)
{
int q = d1/ d2;
int t2 = v1 - q*v2;
int t3 = d1 - q*d2;
v1 = v2; d1 = d2;
v2 = t2; d2 = t3;
}
v=v1;
d=d1;
if (d > 1) System.out.println("Inverse does not exist.");
else System.out.println("Inverse is" + d);
}
}