batch-gcd 0.0.2

Pure Python implementation of DJB's Batch GCD algorithm

Batch GCD

Overview

A pure Python implementation of DJB's Batch GCD algorithm.

Installation

Install with make install (standard) or make install_dev (editable). Or, download and install with pip by pointing it at this repository.

Usage

This is a library and cannot be invoked directly.

Test with make test.

The batch_gcd module exposes a batch_gcd function which takes integers and returns a list of their GCDs at the corresponding index.

This calculation involves two intermediate steps: creating a product tree and creating a remainder tree. These functions are also exposed, as products and remainders. products take integers and returns a product tree, remainders takes an integer and a product tree.

Resources

• How to Find Smooth Parts of Integers
• FactHacks: Batch GCD
• FactHacks: RSA Factorization in the Real World