BinaryExtendedGcd

A fast implementation of the binary extended GCD algorithm for Elixir.

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

Features

Fast Performance: Uses binary operations instead of division for better performance on large integers
Extended GCD: Computes both the GCD and Bézout coefficients
Mathematically Correct: Implements the binary extended GCD algorithm with proper coefficient tracking
Well Tested: Includes comprehensive randomized test suite
Documented: Full documentation with examples and mathematical explanations

Installation

The package can be installed by adding binary_extended_gcd to your list of dependencies in mix.exs:

def deps do
  [
    {:binary_extended_gcd, "~> 0.1.0"}
  ]
end

Usage

Basic Usage

# Compute extended GCD of 48 and 18
{gcd, x, y} = BinaryExtendedGcd.of(48, 18)
# Returns {6, -1, 3}
# This means: 6 = 48 * (-1) + 18 * 3

# Compute extended GCD of 17 and 13
{gcd, x, y} = BinaryExtendedGcd.of(17, 13)
# Returns {1, 4, -5}
# This means: 1 = 17 * 4 + 13 * (-5)

Edge Cases

# When one number is 0
BinaryExtendedGcd.of(0, 5)   # Returns {5, 0, 1}
BinaryExtendedGcd.of(12, 0)  # Returns {12, 1, 0}

# Coprime numbers
BinaryExtendedGcd.of(17, 13) # Returns {1, 4, -5}

Mathematical Background

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 known as Bézout's identity and is useful in many applications including:

Cryptography (RSA, modular arithmetic)
Solving linear Diophantine equations
Computing modular multiplicative inverses

Binary GCD Algorithm

The binary GCD algorithm is an efficient variant of the Euclidean algorithm that:

Eliminates division: Uses only bit shifts and additions
Handles even numbers efficiently: Divides by 2 using bit shifts
Maintains Bézout coefficients: Tracks coefficients throughout the computation

The algorithm works by:

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

Performance

The binary algorithm is generally faster than the Euclidean algorithm for large integers because:

Bit shifts are faster than division operations
Fewer arithmetic operations are required
Better cache locality due to simpler operations

API Reference