확장된 유클리드 JAVA 소스

확장된 유클리드 JAVA 소스

/** * <p>확장된 유클리드 알고리즘(Extend Euclid Function)</p> bx mod p = 1 (bx + kp = 1) * 일때 x를 구한다. * * @param b * in GF(p) * @param p * 소수 * @return x */ public static long exEuclid(long b, long p) { long c = p; long d = b; long x = 0; long y = 1; while (d != 1) { long q = c / d; long e = c - d * q; long w = x - y * q; c = d; d = e; x = y; y = w; } if (y < 0) { y += p; } return y; }

public class MainCls { public static void main(String[] args) { // MathUtil utils = new MathUtil() { // }; // System.out.println("확장된 유클리드 : " + utils.exEuclid(13, 127)); int num1 = 161, num2 = 28, invers=0; // System.out.println("* 두 수를 입력하시오 : "); System.out.println(" q r1 r2 r s1 s2 s t1 t2 t\n"); if(num1 > num2) invers = Extended_Euclid(num1, num2); else invers = Extended_Euclid(num2, num1); if(invers !=0) System.out.println(String.format("* 두수의 역원 : %d \n", invers)); else System.out.println(String.format("역원이 존재하지 않습니다. \n")); } private static int Extended_Euclid(int r1, int r2) { int r, q = 0, s, s1 = 1, s2 = 0, t, t1 = 0, t2 = 1, tmp = r1; while (r2 != 0) { q = r1 / r2; r = r1 % r2; s = s1 - q * s2; t = t1 - q * t2; System.out.println(String.format("%4d %4d %4d %4d %4d %4d %4d %4d %4d %4d\n", q, r1, r2, r, s1, s2, s, t1, t2, t)); r1 = r2; r2 = r; s1 = s2; s2 = s; t1 = t2; t2 = t; } System.out.println(String.format("%4d %4d %4d %4d %4d %4d \n\n", q, r1, r2, s1, s2, t1)); System.out.println(String.format("s : %d , t : %d \n", s1, t1)); if (r1 == 1) // 역원이 있음 { if (t1 < 0) t1 += tmp; return t1; } return 0; } }