Univariate polynomials with coefficients in GF(2^m) More...

#include <GFq_Polynomial.h>

Collaboration diagram for rssoft::gf::GFq_Polynomial:

Public Member Functions
	GFq_Polynomial (const GFq &_gf)
	GFq_Polynomial (const GFq &_gf, const unsigned int size, GFq_Element *gfe=NULL)
	GFq_Polynomial (const GFq &_gf, const std::vector< GFq_Element > &gfe)
	GFq_Polynomial (const GFq_Polynomial &polynomial)
	GFq_Polynomial (const GFq_Element &gfe)
	~GFq_Polynomial ()
void	init (const std::vector< GFq_Element > &_poly)
bool	is_valid () const
bool	is_zero () const
bool	is_one () const
unsigned int	deg () const
const GFq &	field () const
const std::vector< GFq_Element > &	get_poly () const
std::vector< GFq_Element > &	get_poly_for_update ()
void	get_poly_symbols (std::vector< GFq_Symbol > &symbols, unsigned int size=0) const
void	set_degree (const unsigned int &x)
GFq_Polynomial &	operator= (const GFq_Polynomial &polynomial)
GFq_Polynomial &	operator= (const GFq_Element &gfe)
GFq_Polynomial &	operator+= (const GFq_Polynomial &polynomial)
GFq_Polynomial &	operator+= (const GFq_Element &gfe)
GFq_Polynomial &	operator-= (const GFq_Polynomial &polynomial)
GFq_Polynomial &	operator-= (const GFq_Element &gfe)
GFq_Polynomial &	operator*= (const GFq_Polynomial &polynomial)
GFq_Polynomial &	operator*= (const GFq_Element &gfe)
GFq_Polynomial &	operator/= (const GFq_Polynomial &divisor)
GFq_Polynomial &	operator/= (const GFq_Element &gfe)
GFq_Polynomial &	operator%= (const GFq_Polynomial &divisor)
GFq_Polynomial &	operator%= (const unsigned int &power)
GFq_Polynomial &	operator^= (const int &n)
GFq_Polynomial &	operator<<= (const unsigned int &n)
GFq_Polynomial &	operator>>= (const unsigned int &n)
GFq_Element &	operator[] (const unsigned int &term)
GFq_Element	operator() (const GFq_Element &value)
GFq_Element	operator() (GFq_Symbol value)
const GFq_Element &	operator[] (const unsigned int &term) const
const GFq_Element	operator() (const GFq_Element &value) const
const GFq_Element	operator() (GFq_Symbol value) const
bool	operator== (const GFq_Polynomial &polynomial) const
bool	operator!= (const GFq_Polynomial &polynomial) const
GFq_Polynomial	derivative ()
GFq_Element	make_monic ()
void	rootChien (std::vector< GFq_Element > &roots)
void	set_alpha_format (bool _alpha_format)
Protected Attributes
const GFq &	gf
	Reference to the Galois Field of the coefficients.
std::vector< GFq_Element >	poly
	Coefficients vector.
bool	alpha_format
Friends
std::ostream &	operator<< (std::ostream &os, const GFq_Polynomial &polynomial)

Detailed Description

Univariate polynomials with coefficients in GF(2^m)

Constructor & Destructor Documentation

rssoft::gf::GFq_Polynomial::GFq_Polynomial ( const GFq & _gf )

Constructs a new polynomial with coefficients in the specified GF(2^m)

Parameters:

_gf	The coefficients GF(2^m)

                                             :
                gf(_gf), alpha_format(false)
{
        poly.clear();
}

rssoft::gf::GFq_Polynomial::GFq_Polynomial	(	const GFq &	_gf,
		const unsigned int	size,
		GFq_Element *	gfe = `NULL`
	)

Constructs a new polynomial with coefficients in the specified GF(2^m) with the specified coefficients

Parameters:

_gf	The coefficients GF(2^m)
size	The number of coefficients
gfe	Coefficients array in increasing powers of variable

                                                                                        :
                gf(_gf), alpha_format(false)
{
        if (gfe != NULL)
        {
                poly.assign(gfe, gfe + size);
        }
        else
        {
                poly.assign(size, GFq_Element(gf, 0));
        }
}

rssoft::gf::GFq_Polynomial::GFq_Polynomial	(	const GFq &	_gf,
		const std::vector< GFq_Element > &	gfe
	)

Constructs a new polynomial with coefficients in the specified GF(2^m) with the specified coefficients

Parameters:

_gf	The coefficients GF(2^m)
gfe	Coefficients vector in increasing powers of variable

                                                                                :
                gf(_gf),
                alpha_format(false),
                poly(gfe.begin(), gfe.end())
{
}

rssoft::gf::GFq_Polynomial::GFq_Polynomial ( const GFq_Polynomial & polynomial )

Copy constructor

Parameters:

polynomial Reference of the polynomial to copy

                                                               :
                gf(polynomial.gf)
{
        poly = polynomial.poly;
        alpha_format = polynomial.alpha_format;
}

rssoft::gf::GFq_Polynomial::GFq_Polynomial ( const GFq_Element & gfe )

Constructs a zero degree polynomial with the given element as coefficient. The reference Galois Field is taken from the element

                                                     :
                gf(gfe.field()), alpha_format(false)
{
        poly.clear();
        poly.push_back(gfe);
}

rssoft::gf::GFq_Polynomial::~GFq_Polynomial ( ) [inline]

Destructor

        {
        }

Member Function Documentation

unsigned int rssoft::gf::GFq_Polynomial::deg ( ) const

Degree of the polynomial

{
        return static_cast<unsigned int>(poly.size() - 1);
}

GFq_Polynomial rssoft::gf::GFq_Polynomial::derivative ( )

Calculates the derivative of a polynomial

{
        if ((*this).poly.size() > 1)
        {
                GFq_Polynomial deriv(gf, deg());

                for (unsigned int i = 0; i < poly.size() - 1; i++)
                {
                        if (((i + 1) & 1) == 1) // odd power => (bX^n)' = nbX^(n-1) = bX^(n-1)
                        {
                                deriv.poly[i] = poly[i + 1];
                        }
                        else
                        {
                                deriv.poly[i] = 0; // even power => (bX^n)' = nbX^(n-1) = 0X^(n-1) = 0 (eliminated)
                        }
                }

                simplify(deriv);
                return deriv;
        }
        else
        {
                return GFq_Polynomial(gf, 0);
        }
}

Here is the call graph for this function:

const GFq & rssoft::gf::GFq_Polynomial::field ( ) const

Reference to the Galois Field of the coefficients of the polynomial

{
        return gf;
}

const std::vector< GFq_Element > & rssoft::gf::GFq_Polynomial::get_poly ( ) const

Gets a constant reference to the coefficients vector

{
        return poly;
}

std::vector< GFq_Element > & rssoft::gf::GFq_Polynomial::get_poly_for_update ( )

Gets a modifiable reference to the coefficients vector

{
        return poly;
}

void rssoft::gf::GFq_Polynomial::get_poly_symbols	(	std::vector< GFq_Symbol > &	symbols,
		unsigned int	size = `0`
	)		const `[inline]`

Gets the coefficients vector as symbols

    {
        symbols.resize((size == 0 ? poly.size() : size));
        std::transform(poly.begin(), poly.end(), symbols.begin(), gfq_element_to_symbol);
    }

Here is the call graph for this function:

void rssoft::gf::GFq_Polynomial::init ( const std::vector< GFq_Element > & _poly )

Initializes polynomial with a vector of coefficients in increasing power of variable

{
        poly = _poly;
}

bool rssoft::gf::GFq_Polynomial::is_one ( ) const

Tells if the polynomial is P(X)=1

{
        return ((poly.size() == 1) && (poly[0] == 1));
}

bool rssoft::gf::GFq_Polynomial::is_valid ( ) const

Tells if the polynomial has coefficients

{
        return (poly.size() > 0);
}

bool rssoft::gf::GFq_Polynomial::is_zero ( ) const

Tells if the polynomial has no coefficients or a null coefficient P(X)=0

{
        return (poly.size() == 0) || ((poly.size() == 1) && (poly[0] == 0));
}

GFq_Element rssoft::gf::GFq_Polynomial::make_monic ( )

Make this polynomial monic

Returns:: the leading coefficient by which all coefficients are divided

{
    GFq_Element lead_coeff = poly.back();
    std::vector<GFq_Element>::iterator it = poly.begin();
    
    for (; it != poly.end(); ++it)
    {
        *it /= lead_coeff;
    }
    
    return lead_coeff;
}

bool rssoft::gf::GFq_Polynomial::operator!= ( const GFq_Polynomial & polynomial ) const

{
        return !(*this == polynomial);
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator%= ( const GFq_Polynomial & divisor )

{
        const std::pair<GFq_Polynomial, GFq_Polynomial>& divres = div(*this, divisor);
        poly = divres.second.get_poly();
        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator%= ( const unsigned int & power )

{
        if (poly.size() >= power)
        {
                for (size_t i = poly.size(); i > power; i--)
                {
                        poly.pop_back();
                }
                //poly.resize(power);
        }

        simplify(*this);
        return *this;
}

Here is the call graph for this function:

GFq_Element rssoft::gf::GFq_Polynomial::operator() ( const GFq_Element & value )

{
        GFq_Element result(gf, 0);

        if (poly.size() > 0)
        {
                result = poly[poly.size() - 1];
                for (std::size_t i = poly.size() - 2; ((int) i) >= 0; i--)
                {
                        result = poly[i] + (result * value);
                }
                return result;
        }
        else
        {
                throw GF_Exception("Cannot evaluate invalid polynomial");
        }
}

GFq_Element rssoft::gf::GFq_Polynomial::operator() ( GFq_Symbol value )

{
        return (*this)(GFq_Element(gf, value));
}

const GFq_Element rssoft::gf::GFq_Polynomial::operator() ( const GFq_Element & value ) const

{
        GFq_Element result(gf, 0);

        if (poly.size() > 0)
        {
                result = poly[poly.size() - 1];
                for (std::size_t i = poly.size() - 2; static_cast<int>(i) >= 0; i--)
                {
                        result = poly[i] + (result * value);
                }
                return result;
        }
        else
        {
                throw GF_Exception("Cannot evaluate invalid polynomial");
        }
}

const GFq_Element rssoft::gf::GFq_Polynomial::operator() ( GFq_Symbol value ) const

{
        return (*this)(GFq_Element(gf, value));
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator*= ( const GFq_Polynomial & polynomial )

{
        if (gf == polynomial.gf)
        {
                GFq_Polynomial product(gf, deg() + polynomial.deg() + 1);

                for (unsigned int i = 0; i < poly.size(); i++)
                {
                        for (unsigned int j = 0; j < polynomial.poly.size(); j++)
                        {
                                product.poly[i + j] += poly[i] * polynomial.poly[j];
                        }
                }

                simplify(product);
                poly = product.poly;
        }

        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator*= ( const GFq_Element & gfe )

{
        if (gf == gfe.field())
        {
                for (unsigned int i = 0; i < poly.size(); i++)
                {
                        poly[i] *= gfe;
                }
        }

        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator+= ( const GFq_Polynomial & polynomial )

{
        if (gf == polynomial.gf)
        {
                if (poly.size() < polynomial.poly.size())
                {
                        unsigned int j = 0;
                        for (unsigned int i = 0; i < poly.size(); i++)
                        {
                                poly[i] += polynomial.poly[j++];
                        }

                        for (; j < polynomial.poly.size(); j++)
                        {
                                poly.push_back(polynomial.poly[j]);
                        }
                }
                else
                {
                        unsigned int i = 0;
                        for (unsigned int j = 0; j < polynomial.poly.size(); j++)
                        {
                                poly[i++] += polynomial.poly[j];
                        }
                }

                simplify(*this);
        }

        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator+= ( const GFq_Element & gfe )

{
        poly[0] += gfe;
        return *this;
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator-= ( const GFq_Polynomial & polynomial )

{
        return (*this += gfe);
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator-= ( const GFq_Element & gfe )

{
        poly[0] -= gfe;
        return *this;
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator/= ( const GFq_Polynomial & divisor )

{
        const std::pair<GFq_Polynomial, GFq_Polynomial>& divres = div(*this, divisor);
        poly = divres.first.get_poly();
        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator/= ( const GFq_Element & gfe )

{
        if (gf == gfe.field())
        {
                for (unsigned int i = 0; i < poly.size(); i++)
                {
                        poly[i] /= gfe;
                }
        }

        return *this;
}

Here is the call graph for this function:

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator<<= ( const unsigned int & n )

{
        if (poly.size() > 0)
        {
                std::size_t initial_size = poly.size();
                poly.resize(poly.size() + n, GFq_Element(gf, 1));
                std::copy(poly.rend() - initial_size, poly.rend(), poly.rbegin());
                std::fill(poly.begin(), poly.begin() + n, GFq_Element(gf, 0));
        }

        return *this;
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator= ( const GFq_Polynomial & polynomial )

{
        if (this == &polynomial)
        {
                return *this;
        }

        const_cast<GFq&>(gf) = polynomial.gf;
        poly = polynomial.poly;

        return *this;
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator= ( const GFq_Element & gfe )

{
        poly.clear();
        const_cast<GFq&>(gf) = gfe.field();
        poly.push_back(gfe);
        return *this;
}

Here is the call graph for this function:

bool rssoft::gf::GFq_Polynomial::operator== ( const GFq_Polynomial & polynomial ) const

{
        if (gf == polynomial.gf)
        {
                if (poly.size() != polynomial.poly.size())
                        return false;
                else
                {
                        for (unsigned int i = 0; i < poly.size(); i++)
                        {
                                if (poly[i] != polynomial.poly[i])
                                        return false;
                        }
                        return true;
                }
        }
        else
                return false;
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator>>= ( const unsigned int & n )

{
        if (n <= poly.size())
        {
                std::copy(poly.begin() + n, poly.end(), poly.begin());
                poly.erase(poly.end() - n, poly.end());
        }
        else
        {
                poly.clear();
        }
        return *this;
}

GFq_Element & rssoft::gf::GFq_Polynomial::operator[] ( const unsigned int & term )

{
        assert(term < poly.size());
        return poly[term];
}

const GFq_Element & rssoft::gf::GFq_Polynomial::operator[] ( const unsigned int & term ) const

{
        assert(term < poly.size());
        return poly[term];
}

GFq_Polynomial & rssoft::gf::GFq_Polynomial::operator^= ( const int & n )

{
    if (n == 0) // P^0 = 1
    {
        poly.clear();
        poly.push_back(GFq_Element(gf, 1)); 
    }
    else if (n > 1)
    {
        GFq_Polynomial result = *this;
        
        for (unsigned int i=0; i<n-1; i++)
        {
            result *= *this;
        }

        *this = result;
    }

        return *this;
}

void rssoft::gf::GFq_Polynomial::rootChien ( std::vector< GFq_Element > & roots )

Find non null roots of polynomial by Chien search. Basically this is an exhaustive search optimized for hardware implementation but is also interesting in software. Includes null root afterwards if constant coefficient is zero. see: http://www.stanford.edu/class/ee387/handouts/notes7.pdf

Parameters:

roots Vector of root field elements filled by the method

{
        std::vector<GFq_Element> wpoly(poly);
        const GFq_Element zero(gf,0);

        if (poly[0].is_zero())
        {
                roots.push_back(zero);
        }

        for (unsigned int i=0; i < gf.size(); i++)
        {
                GFq_Element sum = std::accumulate(wpoly.begin(), wpoly.end(), zero);

                if (sum.is_zero())
                {
                        roots.push_back(GFq_Element(gf,gf.alpha(i)));
                }

                for (unsigned int j=0; j<wpoly.size(); j++)
                {
                        wpoly[j] *= gf.alpha(j);
                }
        }
}

Here is the call graph for this function:

void rssoft::gf::GFq_Polynomial::set_alpha_format ( bool _alpha_format ) [inline]

Sets the output of coefficients in a power of alpha (printed a^i) ot binary representation

Parameters:

_alpha_format true: power of alpha representation. false: binary representation

        {
                alpha_format = _alpha_format;
        }

void rssoft::gf::GFq_Polynomial::set_degree ( const unsigned int & x )

Sets the degree of the polynomial. Truncates or extends with zeros the coefficients vector internally

{
        poly.resize(x - 1, GFq_Element(gf, 0));
}

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const GFq_Polynomial &	polynomial
	)		`[friend]`

Prints a polynomial to an output stream

{
        if (polynomial.deg() >= 0)
        {
                bool is_null = true;
                bool first_coeff = true;

                for (unsigned int i = 0; i < polynomial.poly.size(); i++)
                {
                        GFq_Symbol coeff = polynomial.poly[i].poly();

                        if (coeff != 0)
                        {
                                is_null = false;
                                os << ((!first_coeff) ? "+ " : "");

                                if (polynomial.alpha_format)
                                {
                                        GFq_Symbol log_alpha = polynomial.poly[i].index();

                                        if (log_alpha == 0)
                                        {
                                                if (i == 0)
                                                {
                                                        os << "1 ";
                                                }
                                                else
                                                {
                                                        os << "";
                                                }
                                        }
                                        else if (log_alpha == 1)
                                        {
                                                os << "a" << ((!first_coeff) ? "*" : " ");
                                        }
                                        else
                                        {
                                                os << "a^" << log_alpha << ((!first_coeff) ? "*" : " ");
                                        }
                                }
                                else
                                {
                                        if (coeff == 1)
                                        {
                                                if (i != 0)
                                                {
                                                        os << "";
                                                }
                                                else
                                                {
                                                        os << coeff << " ";
                                                }
                                        }
                                        else
                                        {
                                                os << coeff << ((!first_coeff) ? "*" : " ");
                                        }
                                }

                                if (i != 0)
                                {
                                        if (i == 1)
                                        {
                                                os << "X ";
                                        }
                                        else
                                        {
                                                os << "X^" << i << " ";
                                        }
                                }

                                first_coeff = false;
                        }
                }

                if (is_null)
                {
                        os << "0";
                }
        }

        return os;

}

Member Data Documentation

bool rssoft::gf::GFq_Polynomial::alpha_format [protected]

const GFq& rssoft::gf::GFq_Polynomial::gf [protected]

Reference to the Galois Field of the coefficients.

std::vector<GFq_Element> rssoft::gf::GFq_Polynomial::poly [protected]

Coefficients vector.

The documentation for this class was generated from the following files:

/shared/development/google_code/rssoft/library/lib/GFq_Polynomial.h
/shared/development/google_code/rssoft/library/lib/GFq_Polynomial.cpp

Public Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation