Source code for pyecsca.ec.mod

import secrets
from functools import wraps

from public import public

from .context import Action


[docs]@public def gcd(a, b): """Euclid's greatest common denominator algorithm.""" if abs(a) < abs(b): return gcd(b, a) while abs(b) > 0: q, r = divmod(a, b) a, b = b, r return a
[docs]@public def extgcd(a, b): """Extended Euclid's greatest common denominator algorithm.""" if abs(b) > abs(a): (x, y, d) = extgcd(b, a) return y, x, d if abs(b) == 0: return 1, 0, a x1, x2, y1, y2 = 0, 1, 1, 0 while abs(b) > 0: q, r = divmod(a, b) x = x2 - q * x1 y = y2 - q * y1 a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y return x2, y2, a
def check(func): @wraps(func) def method(self, other): if type(self) is not type(other): other = self.__class__(other, self.n) else: if self.n != other.n: raise ValueError return func(self, other) return method
[docs]@public class RandomModAction(Action): """A random sampling from Z_n.""" order: int def __init__(self, order: int): super().__init__() self.order = order def __repr__(self): return f"{self.__class__.__name__}({self.order:x})"
[docs]@public class Mod(object): """An element x of ℤₙ.""" def __init__(self, x: int, n: int): self.x: int = x % n self.n: int = n @check def __add__(self, other): return Mod((self.x + other.x) % self.n, self.n) @check def __radd__(self, other): return self + other @check def __sub__(self, other): return Mod((self.x - other.x) % self.n, self.n) @check def __rsub__(self, other): return -self + other def __neg__(self): return Mod(self.n - self.x, self.n)
[docs] def inverse(self): x, y, d = extgcd(self.x, self.n) return Mod(x, self.n)
def __invert__(self): return self.inverse() @check def __mul__(self, other): return Mod((self.x * other.x) % self.n, self.n) @check def __rmul__(self, other): return self * other @check def __truediv__(self, other): return self * ~other @check def __rtruediv__(self, other): return ~self * other @check def __floordiv__(self, other): return self * ~other @check def __rfloordiv__(self, other): return ~self * other @check def __div__(self, other): return self.__floordiv__(other) @check def __rdiv__(self, other): return self.__rfloordiv__(other) @check def __divmod__(self, divisor): q, r = divmod(self.x, divisor.x) return Mod(q, self.n), Mod(r, self.n)
[docs] @staticmethod def random(n: int): with RandomModAction(n): return Mod(secrets.randbelow(n), n)
def __int__(self): return self.x def __eq__(self, other): if type(other) is int: return self.x == (other % self.n) if type(other) is not Mod: return False return self.x == other.x and self.n == other.n def __ne__(self, other): return not self == other def __repr__(self): return str(self.x) def __pow__(self, n): if type(n) is not int: raise TypeError q = self r = self if n & 1 else Mod(1, self.n) i = 2 while i <= n: q = (q * q) if n & i == i: r = (q * r) i = i << 1 return r
[docs]@public class Undefined(Mod): def __init__(self): object.__init__(self) def __add__(self, other): raise NotImplementedError def __radd__(self, other): raise NotImplementedError def __sub__(self, other): raise NotImplementedError def __rsub__(self, other): raise NotImplementedError def __neg__(self): raise NotImplementedError def __invert__(self): raise NotImplementedError def __mul__(self, other): raise NotImplementedError def __rmul__(self, other): raise NotImplementedError def __truediv__(self, other): raise NotImplementedError def __rtruediv__(self, other): raise NotImplementedError def __floordiv__(self, other): raise NotImplementedError def __rfloordiv__(self, other): raise NotImplementedError def __div__(self, other): raise NotImplementedError def __rdiv__(self, other): raise NotImplementedError def __divmod__(self, divisor): raise NotImplementedError def __int__(self): raise NotImplementedError def __eq__(self, other): return False def __ne__(self, other): return False def __repr__(self): return "Undefined" def __pow__(self, n): raise NotImplementedError