Module safegcd 

Implementation of Bernstein-Yang modular inversion and GCD algorithm (a.k.a. safegcd) as described in: https://eprint.iacr.org/2019/266.

Adapted from the Apache 2.0+MIT licensed implementation originally from: https://github.com/taikoxyz/halo2curves/pull/2 https://github.com/privacy-scaling-explorations/halo2curves/pull/83

Copyright (c) 2023 Privacy Scaling Explorations Team

Modules

boxed 🔒

Implementation of Bernstein-Yang modular inversion and GCD algorithm (a.k.a. safegcd) as described in: https://eprint.iacr.org/2019/266.

Structs

SafeGcdInverter 🔒

Modular multiplicative inverter based on the Bernstein-Yang method.

SignedInt 🔒

A Uint which carries a separate sign in order to maintain the same range.

Constants

GCD_BATCH_SIZE 🔒

Functions

conditional_negate_in_place_wide 🔒

Conditionally negate a wide Uint represented by (lo, hi).

gcd_odd

Calculate the greatest common denominator of odd f, and g.

invert_odd_mod

invert_odd_mod_precomp 🔒

Calculate the multiplicative inverse of a modulo m.

iterations 🔒

Calculate the maximum number of iterations required according to safegcd-bounds: https://github.com/sipa/safegcd-bounds

jump 🔒

Perform batch steps of the gcd reduction process on signed tail values f and g.

jump_step 🔒

Perform one step of the gcd reduction in constant time. This follows the half-delta variant of safegcd-bounds which reduces the round count. https://github.com/sipa/safegcd-bounds

jump_step_vartime 🔒

Perform one step of the gcd reduction in variable time.

shr_in_place_wide 🔒

Right shift a wide Uint represented by (lo, hi) returning any remaining high bits.

update_de 🔒

update_fg 🔒

Type Aliases

Matrix 🔒

Type of the Bernstein-Yang transition matrix multiplied by 2^62