EEA31 (org.matheclipse:matheclipse-gpl 3.0.0 API)

java.lang.Object
- de.tilman_neumann.jml.gcd.EEA31

```
public class EEA31
extends Object
```
Extended Euclidean algorithm, mostly used to compute the modular inverse of x (mod y). Extends [Crandall/Pomerance 2005: "Prime numbers", algorithm 2.1.4] to let modInverse(x, y) work on negative x, too. This int implementation is quite fast.

Author:

Tilman Neumann

Nested Class Summary

Nested Classes
Modifier and Type Class Description

static class EEA31.Result

Constructor Summary

Constructors
Constructor Description

EEA31()

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`EEA31.Result`	`computeAll(int x, int y)`	Computes gcd, a = (1/x) mod y and b = (1/y) mod x.
`EEA31.Result`	`computeHalf(int x, int y)`	Computes only gcd and a = (1/x) mod y.
`int`	`modularInverse(int a, int modulus)`	Slightly faster modular inverse initializing variables with first iteration and needing one step less at the end.
`int`	`modularInverse_v1(int x, int y)`	Computes only the modular inverse a = (1/x) mod y.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - EEA31
```
public EEA31()
```
- Method Detail
  - computeAll
```
public EEA31.Result computeAll(int x,
                               int y)
```
    Computes gcd, a = (1/x) mod y and b = (1/y) mod x.
    
    Parameters:
    
    x -
    
    y -
    
    Returns:
    
    {gcd, a, b}
  - computeHalf
```
public EEA31.Result computeHalf(int x,
                                int y)
```
    Computes only gcd and a = (1/x) mod y.
    
    Parameters:
    
    x -
    
    y -
    
    Returns:
    
    {gcd, a, b=-1 (undefined)}
  - modularInverse_v1
```
public int modularInverse_v1(int x,
                             int y)
```
    Computes only the modular inverse a = (1/x) mod y.
    
    Parameters:
    
    x -
    
    y -
    
    Returns:
    
    (1/x) mod y
  - modularInverse
```
public int modularInverse(int a,
                          int modulus)
```
    Slightly faster modular inverse initializing variables with first iteration and needing one step less at the end. Adapted from R.D.Silverman's single_modinv2(), see http://www.mersenneforum.org/showthread.php?t=12963&page=2, post #16.
    
    Parameters:
    
    a -
    
    modulus -
    
    Returns:
    
    (1/a) mod modulus