Class ModularArith

java.lang.Object
  |
  +--ModularArith

public class ModularArith

extends java.lang.Object

Modular Arithmetic This program calculates the GCD, Extended GCD and Inverse Modulus (a^(-1) mod b) for long integers.

Classes used: Tools, LabMenu

Version:

0.1 Feb. 26, 2002

Author:

Moshe

Method Summary

static long	extGCD(long[] aux, long a, long b) Calculates the extended GCD.
static long	GCD(long a, long b) Calculates the GCD of two integers.
static long	inverseMod(long[] aux, long a, long b) Calculates the inverse modulus: a^(-1) mod b
static void	main(java.lang.String[] args) Driver

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

main

public static void main(java.lang.String[] args)

Driver

GCD

public static long GCD(long a,
                       long b)

Calculates the GCD of two integers.

Parameters:

a - the first integer

b - the second integer

Returns:

the greatest common divisor of a & b

extGCD

public static long extGCD(long[] aux,
                          long a,
                          long b)

Calculates the extended GCD.

Parameters:

aux - the helper array

a - the first integer

b - the second integer

Returns:

the greatest common divisor of the a & b. GCD(a,b) = m*a + n*b. Stores m and n in the helper array.

inverseMod

public static long inverseMod(long[] aux,
                              long a,
                              long b)

Calculates the inverse modulus: a^(-1) mod b

Parameters:

aux - the helper array

a - the base

b - the the modulus

Returns:

a^(-1) mod b, or -1 if the inverse does not exist.