BinaryExtendedGcd (Binary extended gcd v1.0.1)

A fast implementation of the binary extended GCD algorithm.

This module provides an efficient implementation of the extended greatest common divisor (GCD) algorithm using the binary GCD method. The binary GCD algorithm is particularly efficient for large integers as it eliminates the need for expensive division operations by using only bit shifts and additions.

Extended GCD

The extended GCD not only computes the greatest common divisor of two integers a and b, but also finds Bézout coefficients $x$ and $y$ such that:

$$ gcd(a, b) = ax + by $$

This is useful in many cryptographic applications, modular arithmetic, and solving linear Diophantine equations.

Algorithm

The binary extended GCD algorithm works by:

  1. Extracting common factors of 2 from both numbers
  2. Using bit operations to handle even/odd cases efficiently
  3. Maintaining Bézout coefficients throughout the computation
  4. Restoring the common factors at the end

Performance

The binary algorithm is generally faster than the Euclidean algorithm for large integers because it avoids expensive division operations, using only bit shifts and additions.

Examples

iex> BinaryExtendedGcd.of(48, 18)
{6, 2, -5}

iex> BinaryExtendedGcd.of(17, 13)
{1, -16, 21}

iex> BinaryExtendedGcd.of(0, 5)
{5, 0, 1}

iex> BinaryExtendedGcd.of(12, 0)
{12, 1, 0}

Summary

Functions

of(a, b)

Computes the extended GCD of two integers.

Functions

of(a, b)

@spec of(integer(), integer()) :: {integer(), integer(), integer()}

Computes the extended GCD of two integers.

Returns a tuple {gcd, x, y} where:

  • gcd is the greatest common divisor of a and b
  • x and y are Bézout coefficients such that $gcd(a, b) = ax + by$

Parameters

  • a - First integer
  • b - Second integer

Returns

{gcd, x, y} where:

  • gcd is the greatest common divisor of a and b
  • x and y are integers satisfying $gcd(a, b) = ax + by$

Examples

iex> BinaryExtendedGcd.of(48, 18)
{6, 2, -5}
# 6 = 48 * 2 + 18 * (-5)

iex> BinaryExtendedGcd.of(17, 13)
{1, -16, 21}
# 1 = 17 * (-16) + 13 * 21

iex> BinaryExtendedGcd.of(0, 5)
{5, 0, 1}
# When one number is 0, the other is the GCD

iex> BinaryExtendedGcd.of(12, 0)
{12, 1, 0}
# When one number is 0, the other is the GCD

Mathematical Properties

The result satisfies the following properties:

  • gcd divides both a and b
  • gcd is the largest number that divides both a and b
  • $gcd(a, b) = ax + by$ (Bézout's identity)