source: comparacioncriptosistemas/interfaz/polynomial.cpp @ 25a5325

// polynomial.cpp

#define _CRT_SECURE_NO_WARNINGS

#include "polynomial.h"
#include <array>
#include <map>
#include <cstdio>
#include <QDebug>

using namespace pol;

u61_t::u61_t(u64_t x):
        data(x % MOD) {
}
inline u61_t::operator pol::u64_t() const {
        return data;
}
inline u61_t u61_t::operator+(const u61_t &x) const {
        return (data + x.data) % MOD;
}
inline u61_t u61_t::operator-(const u61_t &x) const {
        return (data + MOD - x.data) % MOD;
}
u61_t u61_t::operator*(const u61_t &x) const {
//#pragma warning(push)
//#pragma warning(disable:4127)
        if (BUFSIZE > 4) {
//#pragma warning(pop)
                u64_t h1 = data >> 32, h2 = x.data >> 32, l1 = data & M32, l2 = x.data & M32;
                u64_t bot = l1 * l2;
                u64_t mid = h1 * l2 + h2 * l1 + (bot >> 32);
                bot = (mid << 32) + (bot & M32);
                u64_t top = ((h1 * h2 + (mid >> 32)) << (64 - MODSIZE)) + (bot >> MODSIZE);
                return (top + (bot & MOD)) % MOD;
        } else {
                return data * x.data % MOD;
        }
}
u61_t u61_t::operator/(const u61_t &x) const {
        return *this * (x.inverse());
}
u61_t u61_t::inverse() const {
        if (!data) {
                throw "Invalid inverse\n";
        }
        u64_t a = MOD, b = data, r;
        std::array<u64_t, 64> q;
        q[0] = 1;
        u32_t i = 0;
        do {
                ++i;
                r = a % b;
                q[i] = a / b;
                a = b; b = r;
        } while (r);
        for (u32_t j = 2; j < i; ++j) {
                q[j] = q[j] * q[j - 1] + q[j - 2];
        }

        if (i & 1) {
                return u61_t(q[i - 1]);
        } else {
                return u61_t(MOD - q[i - 1]);
        }
}
u61_t& u61_t::operator+=(const u61_t &x) {
        return *this = *this + x;
}
u61_t& u61_t::operator-=(const u61_t &x) {
        return *this = *this - x;
}
u61_t& u61_t::operator*=(const u61_t &x) {
        return *this = *this * x;
}
u61_t& u61_t::operator/=(const u61_t &x) {
        return *this = *this / x;
}
inline u64_t* u61_t::get_addr() {
        return &data;
}
inline const u64_t* u61_t::get_addr() const {
        return &data;
}
inline u64_t& u61_t::get_buf() {
        return data;
}
inline const u64_t& u61_t::get_buf() const {
        return data;
}
void u61_t::print(FILE *fout, u32_t i) const {
        if ((i > 0 && data != 1) || !i) {
                fprintf(fout, "%llu", data);
        }
        if (i > 1) {
                fprintf(fout, "t<sup>%u</sup>", i);
        } else if (i == 1) {
                fprintf(fout, "t");
        }
}
u61_t u61_t::pow(u32_t p) const {
        u61_t res, tmp = *this;
        res = 1;
        while (p > 0) {
                if (p & 1) {
                        res *= tmp;
                }
                p /= 2;
                tmp *= tmp;
        }
        return res;
}

pol_t::pol_t():
        data(1),
        degree(0)
{
        data[0] = 0;
}
void pol_t::change_degree(u32_t ndegree) {
        degree = ndegree;
        data.resize(degree + 1);
        for (u32_t i = 0; i <= degree; ++i) {
                data[i] = 0;
        }
}
pol_t& pol_t::operator=(const pol_t &x) {
        if (&x != this) {
                change_degree(x.degree);
                for (u32_t i = 0; i <= degree; ++i) {
                        data[i] = x[i];
                }
        }
        return *this;
}
u61_t& pol_t::operator[](u32_t i) {
        if (i > degree) {
                throw "Out of array bound";
        }
        return data[i];
}
const u61_t& pol_t::operator[](u32_t i) const {
        if (i > degree) {
                throw "Out of array bound";
        }
        return data[i];
}
u64_t& pol_t::operator()(u32_t i) {
        if (i > degree) {
                throw "Out of array bound";
        }
        return data[i].get_buf();
}
const u64_t& pol_t::operator()(u32_t i) const {
        if (i > degree) {
                throw "Out of array bound";
        }
        return data[i].get_buf();
}
inline u32_t pol_t::get_deg() const {
        return degree;
}
pol_t pol_t::operator+(const pol_t &x) const{
        pol_t tmp;
        u32_t tempdeg;
        if (degree < x.degree) {
                tempdeg = x.degree;
        } else {
                tempdeg = degree;
        }
        tmp.change_degree(tempdeg);
        for (u32_t i = 0; i <= degree; ++i) {
                tmp[i] = data[i];
        }
        for (u32_t i = 0; i <= x.degree; ++i) {
                tmp[i] += x[i];
        }
        while (tmp.degree > 0 && !tmp[tmp.degree]) {
                --(tmp.degree);
        }
        return tmp;
}
pol_t pol_t::operator-(const pol_t &x) const {
        pol_t tmp;
        u32_t tempdeg;
        if (degree < x.degree) {
                tempdeg = x.degree;
        } else {
                tempdeg = degree;
        }
        tmp.change_degree(tempdeg);
        for (u32_t i = 0; i <= degree; ++i) {
                tmp[i] = data[i];
        }
        for (u32_t i = 0; i <= x.degree; ++i) {
                tmp[i] -= x[i];
        }
        while (tmp.degree > 0 && !tmp[tmp.degree]) {
                --(tmp.degree);
        }
        return tmp;
}
pol_t pol_t::operator*(const pol_t &x) const {
        pol_t tmp;
        tmp.change_degree(degree + x.degree);
        for (u32_t i = 0; i <= degree; ++i) {
                for (u32_t j = 0; j <= x.degree; ++j) {
                        tmp[i + j] += data[i] * x[j];
                }
        }
        while (tmp.degree > 0 && !tmp[tmp.degree]) {
                --tmp.degree;
        }
        return tmp;
}
pol_t pol_t::operator%(const pol_t &x) const {
        if (!x) {
                throw "Polinomial denominator = 0";
        }
        pol_t tmp = *this;
        if (!x.degree) {
                return pol_t();
        } else {
                u61_t inv = x[x.degree].inverse();
                for (u32_t i = tmp.degree; i >= x.degree; --i) {
                        u61_t q = tmp[i] * inv;
                        for (u32_t j = 0; j <= x.degree; ++j) {
                                tmp[i - j] -= x[x.degree - j] * q;
                        }
                }
                while (tmp.degree > 0 && !tmp[tmp.degree]) {
                        --tmp.degree;
                }
                return tmp;
        }
}
pol_t pol_t::operator/(const pol_t &x) const {
        if (!x) {
                throw "Polinomial devision by 0";
        } else if (x.degree > degree) {
                return pol_t();
        } else if (x.degree) {
                pol_t tmp = *this, res;
                res.change_degree(tmp.degree - x.degree);
                u61_t q = x[x.degree].inverse();
                for (u32_t i = tmp.degree; i >= x.degree; --i) {
                        res[i - x.degree] = tmp[i] * q;
                        for (u32_t j = 0; j <= x.degree; ++j) {
                                tmp[i - j] -= x[x.degree - j] * res[i - x.degree];
                        }
                }
                return res;
        } else {
                pol_t res = *this;
                u61_t q = x[0].inverse();
                for (u32_t i = 0; i <= res.degree; ++i) {
                        res[i] *= q;
                }
                return res;
        }
}
pol_t& pol_t::operator+=(const pol_t&x) {
        return *this = *this + x;
}
pol_t& pol_t::operator-=(const pol_t&x) {
        return *this = *this - x;
}
pol_t& pol_t::operator*=(const pol_t&x) {
        return *this = *this * x;
}
pol_t& pol_t::operator%=(const pol_t&x) {
        return *this = *this % x;
}
pol_t& pol_t::operator/=(const pol_t&x) {
        return *this = *this / x;
}
pol_t::operator bool() const {
        return degree || data[0];
}
bool pol_t::operator==(const pol_t &x) const {
        if (x.degree != degree) {
                return false;
        } else {
                for (u32_t i = 0; i <= degree; ++i) {
                        if (data[i] != x(i)) {
                                return false;
                        }
                }
        }
        return true;
}
pol_t pol_t::pow(u32_t p) const {
        pol_t res, tmp = *this;
        res(0) = 1;
        while (p > 0) {
                if (p & 1) {
                        res *= tmp;
                }
                p /= 2;
                tmp *= tmp;
        }
        return res;
}
pol_t pol_t::mpow(u64_t p, const pol_t &m) const {
        pol_t res, tmp = *this % m;
        res(0) = 1;
        while (p > 0) {
                if (p & 1) {
                        res = res * tmp % m;
                }
                p /= 2;
                tmp = tmp * tmp % m;
        }
        return res;
}
pol_t pol_t::mpow(u64_t p, u64_t d, const pol_t &m) const {
        pol_t tmp = mpow((p - 1) / 2, m), res;
        res[0] = 1;
        for (u64_t i = 0; i < d; ++i) {
                res = res * tmp % m;
                tmp = tmp.mpow(p, m);
        }
        return res;
}
pol_t pol_t::normalize() const {
        pol_t res = *this;
        u61_t q = data[degree].inverse();
        for (u32_t i = 0; i <= degree; ++i) {
                res[i] *= q;
        }
        return res;
}
pol_t pol_t::deriv() const{
        pol_t res;
        if (degree) {
                res.change_degree(degree - 1);
                for (u32_t i = degree; i > 0; --i) {
                        res[i - 1] = u61_t(i) * data[i];
                }
        }
        while (res.degree > 0 && !res[res.degree]) {
                --res.degree;
        }
        return res;
}

void pol_t::read(FILE *fin, pol_format_t format) {
        degree = 0;
        switch (format)
        {
        case BINPR:
                std::fread(&degree, 1, 1, fin);
                if (degree > 256) {
                        throw "Incorrect polynomial degree";
                }
                data.resize(degree + 1);
                for (u32_t i = 0; i <= degree; ++i) {
                        u64_t buf;
                        std::fread(&buf, BUFSIZE, 1, fin);
                        if (buf >= MOD) {
                                throw "Incorrect polinomial coefficient";
                        }
                        data[i] = buf;
                }
                break;
        case TEXTPR:
                std::fscanf(fin, "%u", &degree);
                if (degree > 256) {
                        throw "Incorrect polynomial degree";
                }
                data.resize(degree + 1);
                for (u32_t i = 0; i <= degree; ++i) {
                        u64_t buf;
                        std::fscanf(fin, "%llu", &buf);
                        if (buf >= MOD) {
                                throw "Incorrect polinomial coefficient";
                        }
                        data[i] = buf;
                }
                break;
        case HTMLPR:
                break;
        default:
                break;
        }
}
void pol_t::write(FILE *fout, pol_format_t format, bool eol) const {
        switch (format)
        {
        case pol::BINPR:
                fwrite(&degree, 1, 1, fout);
                for (u32_t i = 0; i <= degree; ++i) {
                        fwrite(data[i].get_addr(), BUFSIZE, 1, fout);
                }
                break;
        case pol::TEXTPR:
                fprintf(fout, "%u ", degree);
                for (u32_t i = 0; i <= degree; ++i) {
                        fprintf(fout, "%llu ", data[i].get_buf());
                }
                if (eol) fprintf(fout, "\n");
                break;
        case pol::HTMLPR:
                {
                        u32_t i = degree;
                        u32_t min = 0;
                        while (min < degree && !data[min]) ++min;
                        --min;
                        data[i].print(fout, i);
                        --i;
                        for (; i != min; --i) {
                                if (data[i]) {
                                        fprintf(fout, " + ");
                                        data[i].print(fout, i);
                                }
                        }
                        if (eol) fprintf(fout, "<br>");
                }
                break;
        default:
                break;
        }
}
void pol_t::ddf(u32_t max_deg, vector_t &res) const {
        pol_t v = *this, x = get_x(), xp = x, tmp;
        res.resize(max_deg + 1);
        for (u32_t i = 0; i <= max_deg; ++i) {
                res[i](0) = 1;
        }
        u32_t i = 1;
        for (; i <= max_deg; ++i)  {
                xp = xp.mpow(MOD, v);
                tmp = gcd(xp - x, v);
                if (tmp.degree > 0) {
                        res[i] = tmp;
                        v /= tmp;
                }
        //fprintf(stderr, "%d of %d\n", i, max_deg);
        }
        res[0] = v;
}
void pol_t::split(u32_t deg, vector_t &res) const {
        u32_t count = degree / deg, found = 0;
        pol_t r_pol, r_gcd, unit;
        unit[0] = 1;
        std::list<pol_t> l1, l2;
        l1.push_back(*this);
        std::list<pol_t> *cur = &l1, *next = &l2;
        while (found < count) {
                r_pol = get_rand_pol(deg);
                next->clear();
                for (auto i = cur->begin(), end = cur->end(); i != end; ++i) {
                        if (i->degree == deg) {
                                res.push_back(*i);
                                ++found;
                        } else {
                                r_gcd = gcd(r_pol.mpow(MOD, deg, *i) - unit, *i);
                                if (r_gcd.degree && r_gcd.degree < i->degree) {
                                        *i /= r_gcd;
                                        if (i->degree == deg) {
                                                res.push_back(*i);
                                                ++found;
                                        }
                                        else {
                                                next->push_back(*i);
                                        }
                                        if (r_gcd.degree == deg) {
                                                res.push_back(r_gcd);
                                                ++found;
                                        }
                                        else {
                                                next->push_back(r_gcd);
                                        }
                                }
                                else {
                                        next->push_back(*i);
                                }
                        }
                }
                std::swap(cur, next);
        }
}
void pol_t::fact(u32_t max_deg, vector_t &res) const {
        pol_t d = gcd(deriv(), *this), tmp;
        if (d.degree) {
                tmp = *this / d;
        } else {
                tmp = *this;
        }
        std::vector<pol_t> ddf_pol;
        tmp.ddf(max_deg, ddf_pol);
        for (u32_t i = 1; i <= max_deg; ++i) {
                if (ddf_pol[i].degree > 0) {
                        ddf_pol[i].split(i, res);
                }
        }
        if (d.degree) {
                for (size_t i = 0, size = res.size(); i < size && d.degree; ++i) {
                        while (!(d % res[i])) {
                                res.push_back(res[i]);
                                d /= res[i];
                        }
                }
        }
}

deg_t::deg_t() : key(0) {}
deg_t::deg_t(u32_t a, u32_t b) :
        x(a),
        y(b)
{
}
bool deg_t::operator<(const deg_t &deg) const{
        return key < deg.key;
}
bool deg_t::operator==(const deg_t &deg) const{
        return key == deg.key;
}
deg_t deg_t::operator+(const deg_t &deg) const {
        return deg_t(x + deg.x, y + deg.y);
}

pol3v_t::pol3v_t() {
        data.clear();
        data.push_back(pol3v1_t());
        dx = 0; dy = 0; dt = 0;
}
pol3v_t::pol3v_t(const polmap_t &m) :
        data(),
        dx(0),
        dy(0),
        dt(0)
{
        data.clear();
        bool empty = true;
        for (auto i = m.begin(); i != m.end(); ++i) {
                if (i->second) {
                        if (empty) {
                                empty = false;
                        }
                        data.push_back(*i);
                        if (dx < i->first.x) dx = i->first.x;
                        if (dy < i->first.y) dy = i->first.y;
                        if (dt < i->second.get_deg()) dt = i->second.get_deg();
                }
        }
        if (empty) {
                data.push_back(pol3v1_t());
        }
}
pol3v_t& pol3v_t::operator=(const pol3v_t &x) {
        if (&x != this) {
                data.clear();
                data = x.data;
                dx = x.dx; dy = x.dy; dt = x.dt;
        }
        return *this;
}
pol3v_t pol3v_t::operator+(const pol3v_t &x) const {
        polmap_t tmp;
        for (auto i = data.begin(); i != data.end(); ++i) {
                if (tmp.find(i->first) == tmp.end()) {
                        tmp.insert(*i);
                } else {
                        tmp[i->first] += i->second;
                }
        }
        for (auto i = x.data.begin(); i != x.data.end(); ++i) {
                if (tmp.find(i->first) == tmp.end()) {
                        tmp.insert(*i);
                } else {
                        tmp[i->first] += i->second;
                }
        }
        return tmp;
}
pol3v_t pol3v_t::operator-(const pol3v_t &x) const {
        polmap_t tmp;
        for (auto i = data.begin(); i != data.end(); ++i) {
                if (tmp.find(i->first) == tmp.end()) {
                        tmp.insert(*i);
                } else {
                        tmp[i->first] += i->second;
                }
        }
        for (auto i = x.data.begin(); i != x.data.end(); ++i) {
                if (tmp.find(i->first) == tmp.end()) {
                        tmp.insert(pol3v1_t(i->first, pol_t() - i->second));
                } else {
                        tmp[i->first] -= i->second;
                }
        }
        return tmp;
}
pol3v_t pol3v_t::operator*(const pol3v_t &x) const {
        polmap_t tmp;
        for (auto i = data.begin(); i != data.end(); ++i) {
                for (auto j = x.data.begin(); j != x.data.end(); ++j) {
                        if (tmp.find(i->first + j->first) == tmp.end()) {
                                tmp.insert(pol3v1_t(i->first + j->first, i->second * j->second));
                        } else {
                                tmp[i->first + j->first] += i->second * j->second;
                        }
                }
        }
        return tmp;
}
pol3v_t& pol3v_t::operator+=(const pol3v_t &x) {
        return *this = *this + x;
}
pol3v_t& pol3v_t::operator-=(const pol3v_t &x) {
        return *this = *this - x;
}
pol3v_t& pol3v_t::operator*=(const pol3v_t &x) {
        return *this = *this * x;
}
pol_t pol3v_t::subst(const pol_t &x, const pol_t &y) const {
        pol_t res;
        for (auto i = data.begin(), end = data.end(); i != end; ++i) {
                res += x.pow(i->first.x) * y.pow(i->first.y) * i->second;
        }
        return res;
}
pol3v_t pol3v_t::get_same_rand_pol() const {
        pol3v_t res = *this;
        for (auto i = res.data.begin(), end = res.data.end(); i != end; ++i) {
                i->second = get_rand_pol(i->second.get_deg(), false);
        }
        return res;
}
void pol3v_t::read(FILE *fin, pol_format_t format) {
        size_t count = 0;
        data.clear();
        switch (format)
        {
        case BINPR:
        {
                std::fread(&count, 1, sizeof(count), fin);
                if (!count) {
                        data.push_back(pol3v1_t());
                        dx = 0; dy = 0; dt = 0;
                }
                deg_t deg;
                for (size_t i = 0; i < count; ++i) {
                        std::fread(&(deg.key), sizeof(deg.key), 1, fin);
                        pol_t tmp;
                        tmp.read(fin, BINPR);
                        if (tmp) {
                                data.push_back(pol3v1_t(deg, tmp));
                                if (deg.x > dx) dx = deg.x;
                                if (deg.y > dy) dy = deg.y;
                                if (tmp.get_deg() > dt) dt = tmp.get_deg();
                        }
                }
                break;
        }
        case TEXTPR:
                std::fscanf(fin, "%zu", &count);
                if (!count) {
                        data.clear();
                        data.push_back(pol3v1_t());
                        dx = 0; dy = 0; dt = 0;
                } else {
                        for (size_t i = 0; i < count; ++i) {
                                u32_t v[2];
                                fscanf(fin, "%u%u", v, v + 1);
                                pol_t tmp;
                                tmp.read(fin, TEXTPR);
                                if (tmp) {
                                        data.push_back(pol3v1_t(deg_t(v[0], v[1]), tmp));
                                        if (v[0] > dx) dx = v[0];
                                        if (v[1] > dy) dy = v[1];
                                        if (tmp.get_deg() > dt) dt = tmp.get_deg();
                                }
                        }
                }
                break;
        case HTMLPR:
                break;
        default:
                break;
        }
}
void pol3v_t::write(FILE *fout, pol_format_t format, bool eol) const {
        size_t count = data.size();
        switch (format)
        {
        case pol::BINPR:
                std::fwrite(&count, 1, sizeof(count), fout);
                for (auto i = data.begin(), end = data.end(); i != end; ++i) {
                        std::fwrite(&(i->first.key), sizeof(i->first.key), 1, fout);
                        i->second.write(fout, BINPR);
                }
                break;
        case TEXTPR:
                std::fprintf(fout, "%zu\n", count);
                for (auto i = data.begin(), end = data.end(); i != end; ++i) {
                        fprintf(fout, "%u %u ", i->first.x, i->first.y);
                        i->second.write(fout, TEXTPR, true);
                }
                if (eol) {
                        fprintf(fout, "\n");
                }
                break;
        case pol::HTMLPR:
                if (!count) {
                        fprintf(fout, "0");
                } else {
                        auto i = data.rbegin();
                        if (i->first.x > 1) {
                                fprintf(fout, "x<sup>%u</sup>", i->first.x);
                        }
                        else if (i->first.x == 1) {
                                fprintf(fout, "x");
                        }
                        if (i->first.y > 1) {
                                fprintf(fout, "y<sup>%u</sup>", i->first.y);
                        }
                        else if (i->first.y == 1) {
                                fprintf(fout, "y");
                        }
                        fprintf(fout, "(");
                        i->second.write(fout, HTMLPR);
                        fprintf(fout, ")");
                        ++i;
                        for (auto end = data.rend(); i != end; ++i) {
                                fprintf(fout, " + ");
                                if (i->first.x > 1) {
                                        fprintf(fout, "x<sup>%u</sup>", i->first.x);
                                }
                                else if (i->first.x == 1) {
                                        fprintf(fout, "x");
                                }
                                if (i->first.y > 1) {
                                        fprintf(fout, "y<sup>%u</sup>", i->first.y);
                                }
                                else if (i->first.y == 1) {
                                        fprintf(fout, "y");
                                }
                                fprintf(fout, "(");
                                i->second.write(fout, HTMLPR);
                                fprintf(fout, ")");
                        }
                }
                if (eol) {
                        fprintf(fout, "<br>");
                }
                break;
        default:
                break;
        }
}

File::File() :
        file(NULL),
        opened(false),
        mode(READ),
        buf(0),
        pos(0),
        count(0)
{
}
File::File(FILE *_file, file_mode_t m) :
file(_file),
opened(false),
mode(m),
buf(0),
pos(0),
count(0)
{
}
File::File(const char *file_name, file_mode_t m) :
file(NULL),
opened(false),
mode(m),
buf(0),
pos(0),
count(0)
{
        if (!open(file_name, m)) {
                throw "Can't open the file";
        }
}
File::~File() {
        close();
}
bool File::open(const char *file_name, file_mode_t m) {
        if ((mode = m) == READ) {
                file = fopen(file_name, "rb");
        } else {
                file = fopen(file_name, "wb");
        }
        return opened = !!(file);
}
void File::close() {
        if (opened) {
                flush();
                fclose(file);
                opened = false;
                mode = READ;
        }
}
void File::flush() {
        if (mode == WRITE && count) {
                buf = (buf >> pos) & ((1ull << count) - 1);
                fwrite(&buf, 1, (count - 1) / 8 + 1, file);
        }
        count = 0;
        pos = 0;
        buf = 0;
}
size_t File::read(u61_t &block) {
        if (mode != READ || !opened) {
                throw "Incorrect read";
        }
        u64_t res = 0;
        size_t cur = 0;
        if (count) {
                res = (buf >> pos) & ((1ull << MODSIZE) - 1) & ((1ull << count) - 1);
                cur = count < MODSIZE ? count : MODSIZE;
        }
        if (cur < MODSIZE) {
                buf = 0;
                count = 8 * fread(&buf, 1, (MODSIZE - cur - 1) / 8 + 1, file);
                read_size += count / 8;
                res |= (buf << cur) & ((1ull << MODSIZE) - 1);
        }
        if (res >= MOD || (res < (1ull << (MODSIZE - 1)))) {
                res &= (1ull << (MODSIZE - 1)) - 1;
                if (count > MODSIZE - 1 - cur) {
                        count -= MODSIZE - 1 - cur;
                        pos = MODSIZE - 1 - cur;
                        cur = MODSIZE - 1;
                } else {
                        cur += count;
                        count = 0;
                }
        } else {
                count -= MODSIZE - cur;
                pos = MODSIZE - cur;
                cur = MODSIZE;
        }
        block = res;
        return cur;
}
size_t File::write(const u61_t &block, size_t block_size) {
        if (mode != WRITE || !opened) {
                throw "Incorrect write";
        }
        u64_t tmp = block;
        size_t size;
        if (tmp >= (1ull << (MODSIZE - 1))) {
                size = MODSIZE;
        } else {
                size = block_size;
        }
        if (!count) {
                buf = 0;
        }
        buf |= tmp << count;
        if (size + count >= 8 * sizeof(buf)) {
                fwrite(&buf, 1, sizeof(buf), file);
        }
        if (size + count > 8 *sizeof(buf)) {
                buf = tmp >> (sizeof(buf)* 8 - count);
        }
        count = (size + count) % (8 * sizeof(buf));
        return size;
}

random_t::random_t() :
        generator(std::time(NULL))
{
}
u61_t random_t::operator()() {
        return u64_t((generator() - 1.) / generator.max() * MOD);
}

pol_t pol::gcd(const pol_t &x, const pol_t &y) {
        pol_t a = x, b = y, q;
        while (q = a % b, q) {
                a = b;
                b = q;
        }
        return b.normalize();
}
pol_t pol::get_x() {
        pol_t res;
        res.change_degree(1);
        res[1] = 1;
        return res;
}

pol_t pol::get_rand_pol(u32_t deg, bool flag) {
        static random_t get_coef;
        pol_t res;
        res.change_degree(deg);
        //res[deg] = flag ? 1 : get_coef();
        while (!res(deg)) {
                res[deg] = get_coef();
        }
        for (u32_t i = 0; i < deg; ++i) {
        res[i] = get_coef();
    }
        return res;
}


pol3v_t pol::XXX_get_f(const u64_t max_deg, const u32_t key_deg) {
        polmap_t tmp;
        for (u32_t i = 0; i <= max_deg; ++i) {
        tmp.insert(pol3v1_t(deg_t(i, i), get_rand_pol(key_deg - 1)));
    }
        return tmp;
}

pol3v_t pol::XXX_get_mes(const u64_t max_deg, const u32_t key_deg, const u64_t size, const std::vector<u61_t> &m) {
        polmap_t tmp;
        pol_t tmp2;
        u64_t block_count = m.size();
        tmp2.change_degree(key_deg - 1);
        for (u32_t i = 0; i < max_deg; ++i) {
                for (u32_t j = 0; j < key_deg; ++j) {
                        if (i * key_deg + j < block_count) {
                                tmp2[j] = m[block_count - 1 - (i * key_deg + j)];
                        }
                        else {
                                tmp2(j) = 0;
                        }
                }
                tmp.insert(pol3v1_t(deg_t(i, i), tmp2));
        }
        tmp2.change_degree(0);
        tmp2[0] = size;
        tmp.insert(pol3v1_t(deg_t(u32_t(max_deg), u32_t(max_deg)), tmp2));
        return tmp;
}
void pol::XXX_get_fact(const vector_t &fact, u64_t deg, vector_t &res) {
        size_t num = fact.size();
        std::vector<std::list<pol_t>> tmp;
        tmp.resize(deg + 1);
        for (size_t i = 0; i < num; ++i) {
                u32_t pol_deg = fact[i].get_deg();
                for (auto j = tmp.rbegin(); j != tmp.rend(); ++j) {
                        for (auto it = j->begin(); it != j->end(); ++it) {
                                if (pol_deg + it->get_deg() <= deg) {
                                        tmp[pol_deg + it->get_deg()].push_back(fact[i] * *it);
                                }
                        }
                }
                if (pol_deg <= deg) {
                        tmp[pol_deg].push_back(fact[i]);
                }
        }
        res.clear();
        for (auto i = tmp[deg].begin(); i != tmp[deg].end(); ++i) {
                res.push_back(*i);
        }
}