# # Barrett reduction algorithm (Python) # # Copyright (c) 2021 Project Nayuki # All rights reserved. Contact Nayuki for licensing. # https://www.nayuki.io/page/barrett-reduction-algorithm # import random, unittest class BarrettReducerTest(unittest.TestCase): def test_basic(self) -> None: for _ in range(10000): mod: int = BarrettReducerTest.random_modulus() modsqr: int = mod**2 br = BarrettReducer(mod) for _ in range(100): x: int = random.randrange(modsqr) if br.reduce(x) != x % mod: raise AssertionError() @staticmethod def random_modulus() -> int: bitlen: int = random.randint(2, 100) return random.randint((1 << bitlen) + 1, (2 << bitlen) - 1) class BarrettReducer: modulus: int shift: int factor: int def __init__(self, mod: int): if mod <= 0: raise ValueError("Modulus must be positive") if mod & (mod - 1) == 0: raise ValueError("Modulus must not be a power of 2") self.modulus = mod self.shift = mod.bit_length() * 2 self.factor = (1 << self.shift) // mod # For x in [0, mod^2), this returns x % mod. def reduce(self, x: int) -> int: mod = self.modulus assert 0 <= x < mod**2 t = (x - ((x * self.factor) >> self.shift) * mod) return t if (t < mod) else (t - mod) if __name__ == "__main__": unittest.main()