AlgorithmReducibleRecursionSearch.hpp

Go to the documentation of this file.

#ifndef MTTOOLBOX_ALGORITHM_REDUCIBLE_RECURSION_SEARCH_HPP
#define MTTOOLBOX_ALGORITHM_REDUCIBLE_RECURSION_SEARCH_HPP

#if defined(DEBUG)
#include <iostream>
#endif
#include <NTL/GF2X.h>
#include <NTL/GF2XFactoring.h>
#include <MTToolBox/util.hpp>
#include <MTToolBox/ReducibleGenerator.hpp>
#include <MTToolBox/AlgorithmPrimitivity.hpp>
#include <MTToolBox/period.hpp>

namespace MTToolBox {
    using namespace std;

    template<typename U, typename V = U>
    void calcCharacteristicPolynomial(RecursionSearchable<U, V> *rand,
                                      NTL::GF2X& poly);
    template<typename U, typename V = U>
    class AlgorithmReducibleRecursionSearch {
    public:
        AlgorithmReducibleRecursionSearch(ReducibleGenerator<U, V>& generator,
                                 AbstractGenerator<V>& bg) {
            rand = &generator;
            baseGenerator = &bg;
            count = 0;
        }

        bool start(int try_count) {
            long degree;
            long mexp = rand->getMexp();
            for (int i = 0; i < try_count; i++) {
                rand->setUpParam(*baseGenerator);
                rand->seed(getOne<U>());
#if defined(DEBUG)
                cout << "rand param:";
                cout << rand->getParamString() << endl;
#endif
                minpoly(poly, *rand);
                irreducible = poly;
                count++;
                if (deg(irreducible) < mexp) {
#if defined(DEBUG)
                    cout << "irrepoly deg = " << deg(irreducible)
                         << " skip" << endl;
#endif
                    continue;
                }
                bool hasFactor = hasFactorOfDegree(irreducible, mexp);
#if defined(DEBUG)
                cout << "has factor = " << hasFactor << endl;
#endif
                if (!hasFactor) {
#if defined(DEBUG)
                    cout << "not has factor of degree irrepoly deg = "
                         << deg(irreducible) << " skip" << endl;
#endif
                    continue;
                }
                degree = deg(irreducible);
                if (degree != mexp) {
#if defined(DEBUG)
                    cout << "degree:" << degree << "degree != mexp skip"
                         << endl;
#endif
                    continue;
                }
                return true;
            }
            return false;
        }

        const std::string getParamString() {
            return rand->getParamString();
        }

        const NTL::GF2X& getCharacteristicPolynomial() {
            return poly;
        }

        const NTL::GF2X& getIrreducibleFactor() const {
            return irreducible;
        }

        long getCount() const {
            return count;
        }

    private:
        ReducibleGenerator<U, V> *rand;
        AbstractGenerator<V> *baseGenerator;
        NTL::GF2X poly;
        NTL::GF2X irreducible;
        long count;

    };

    template<typename U, typename V = U>
    void calcCharacteristicPolynomial(ReducibleGenerator<U, V> *rand,
                                      NTL::GF2X& poly)
    {
#if defined(DEBUG)
        cout << "calcCharacteristicPolynomial start" << endl;
#endif
        int bitsize = bit_size<U>();
        NTL::GF2X minpol;
        NTL::GF2X lcmpoly = poly;
        int size = rand->bitSize();
        for (int i = 0; i < bitsize; i++) {
            if (deg(lcmpoly) == size) {
                poly = lcmpoly;
#if defined(DEBUG)
                cout << "calcCharacteristicPolynomial end" << endl;
#endif
                return;
            }
            minpoly(minpol, *rand, i);
            LCM(lcmpoly, lcmpoly, minpol);
        }
        poly = lcmpoly;
#if defined(DEBUG)
        cout << "calcCharacteristicPolynomial end" << endl;
#endif
    }
}
#endif // MTTOOLBOX_ALGORITHM_REDUCIBLE_RECURSION_SEARCH_HPP