11. Extended Euclidean algorithm {VeryLargeIntegers}

Extended Euclidean Algorithm for vli Objects

Description

Computation of the Extended Euclidean algorithm for vli (Very Large Integers) objects. Given two positive integers, x and y, the Extended Euclidean algorithm looks for two integers a and b (called Bezout's coefficients) such that (a * x) + (b * y) = 1. To do this, the algorithm needs to compute the greatest common divisor of x and y, so it is also returned by the function.

Usage

exteuclid(x, y)

## Default S3 method:
exteuclid(x, y)

## S3 method for class 'numeric'
exteuclid(x, y)

## S3 method for class 'vli'
exteuclid(x, y)

Arguments

x

object of class vli or 32 bits integer

y

object of class vli or 32 bits integer

Details

The returned object is a list of 3 elements. To access the numbers, it is necessary to use the list operator [[i]], where "i" has to be 1 for the greatest common divisor, 2 for the first Bezout coefficient and 3 for the second Bezout coefficient (see the example).

Value

list of 3 objects of class vli: the first is the greatest common divisor of x and y, and the other two are the Bezout's coefficients

Author(s)

Javier Leiva Cuadrado

Examples

x <- as.vli("232636113097")
y <- as.vli("52442092785616")
result <- exteuclid(x, y)
( result[[2]] * x ) + ( result[[3]] * y )