modular_arithmetic.hpp

/**
* Ðåàë³çàö³ÿ ê³ëüöÿ ëèøê³â
*/

#include <cstdint>

#ifndef MODULAR_ARITHMETIC_H
#define MODULAR_ARITHMETIC_H

/**
* Çíàõîäèòü ö³ëó ÷àñòèíó â³ä êîðåíÿ ö³ëîãî ÷èñëà
*/
uint_fast64_t bsqrt(uint_fast64_t a);


/**
* Ïåðåâ³ðÿº ÷è º äàíå íàòóðàëüíå ÷èñëî a ïðîñòèì
*/
bool isprime(uint_fast64_t a);


/**
* ʳëüöå ëèøê³â çà ìîäóëåì mod
*/
class Galois
{
private:
    int_fast64_t value;
    int_fast64_t mod;

public:
    /**
    * x òà n ìàþòü áóòè íå ìåíøå 0
    * value = x % n
    * mod = n
    */
    Galois(int_fast64_t x, int_fast64_t n);
    Galois();

    /**
    * Ïîð³âíÿííÿ íà ð³âí³ñòü äâîõ åëåìåíò³â ç îäíîãî ê³ëüöÿ
    */
    bool operator == (const Galois& other);

    bool operator == (Galois& other);

    /**
    * Ïîð³âíÿííÿ íà ð³âí³ñòü ç ö³ëèì ÷èñëîì ïî ìîäóëþ mod
    */
    bool operator == (int_fast64_t other);

    bool operator != (const Galois& other);

    bool operator != (int_fast64_t other);

    Galois& operator = (const Galois& other);

    Galois& operator = (int_fast64_t other);

    Galois operator+ (const Galois& other);

    Galois operator- (const Galois& other);

    Galois operator- ();

    Galois operator* (const Galois& other);

    Galois operator* (Galois& other);

    Galois operator* (int_fast64_t other);

    /**
    * Çíàõîäæåííÿ îáåðíåíîãî åëåìåíòà, ÿêùî mod º ïðîñòèì ÷èñëîì. ²íàêøå áóäå âèêëþ÷åííÿ.
    */
    Galois inverse();

    Galois operator/ (const Galois& other);

    /**
    * ϳäíåñåííÿ äî ö³ëîãî ñòåïåííÿ other
    */
    Galois pow(int_fast64_t other);

    Galois operator += (const Galois other);

    Galois operator -= (const Galois other);

    Galois operator *= (const Galois other);

    Galois operator /= (const Galois other);

    const int_fast64_t get_mod();

    const int_fast64_t get_value();
};

#endif