ecm

Elliptic Curve factorization - code and slides
git clone https://git.tronto.net/ecm
Download | Log | Files | Refs | README

zmodn.h (2052B)


      1 #ifndef ZMODN_H
      2 #define ZMODN_H
      3 
      4 #include <cstdint>
      5 #include <iostream>
      6 #include <optional>
      7 #include <tuple>
      8 #include <type_traits>
      9 
     10 template<typename T>
     11 concept Integer = requires(T a, T b, int i, std::ostream& os) {
     12 	{T(i)};
     13 
     14 	{a + b} -> std::same_as<T>;
     15 	{a - b} -> std::same_as<T>;
     16 	{a * b} -> std::same_as<T>;
     17 	{a / b} -> std::same_as<T>;
     18 	{a % b} -> std::same_as<T>;
     19 
     20 	{a == b} -> std::same_as<bool>;
     21 	{a != b} -> std::same_as<bool>;
     22 
     23 	{os << a} -> std::same_as<std::ostream&>;
     24 };
     25 
     26 template<Integer T>
     27 std::tuple<T, T, T> extended_gcd(T a, T b) {
     28 	if (b == 0) return {a, 1, 0};
     29 	auto [g, x, y] = extended_gcd(b, a%b);
     30 	return {g, y, x - y*(a/b)};
     31 }
     32 
     33 template<Integer auto N>
     34 requires(N > 1)
     35 class Zmod {
     36 public:
     37 	Zmod(decltype(N) z) : value{(z%N + N) % N} {}
     38 	decltype(N) toint() const { return value; }
     39 
     40 	Zmod operator+(const Zmod& z) const { return value + z.value; }
     41 	Zmod operator-(const Zmod& z) const { return value - z.value; }
     42 	Zmod operator*(const Zmod& z) const { return value * z.value; }
     43 
     44 	Zmod operator+=(const Zmod& z) { return (*this) = value + z.value; }
     45 	Zmod operator-=(const Zmod& z) { return (*this) = value - z.value; }
     46 	Zmod operator*=(const Zmod& z) { return (*this) = value * z.value; }
     47 
     48 	Zmod operator^(decltype(N) z) const {
     49 		if (z == 0) return 1;
     50 		if (z % 2 == 0) return (((*this) * (*this)) ^ (z/2));
     51 		return (*this) * ((*this) ^ (z-1));
     52 	}
     53 
     54 	bool operator==(const Zmod& z) const { return value == z.value; }
     55 	bool operator!=(const Zmod& z) const { return value != z.value; }
     56 
     57 	std::optional<Zmod> inverse() const {
     58 		auto [g, a, _] = extended_gcd(value, N);
     59 		return g == 1 ? Zmod(a) : std::optional<Zmod>{};
     60 	}
     61 
     62 	std::optional<Zmod> operator/(const Zmod& d) const {
     63 		auto i = d.inverse();
     64 		return i ? (*this) * i.value() : i;
     65 	}
     66 
     67 	std::optional<Zmod> operator/=(const Zmod& d) {
     68 		auto q = *this / d;
     69 		return q ? (*this = q.value()) : q;
     70 	}
     71 
     72 	friend std::ostream& operator<<(std::ostream& os, const Zmod<N>& z) {
     73 		return os << "(" << z.value << " mod " << N << ")";
     74 	}
     75 private:
     76 	decltype(N) value;
     77 };
     78 
     79 #endif