Main Page   Reference Manual   Compound List   File List  
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Friends

libecc::polynomial< m, k, k1, k2 > Class Template Reference

Polynomial representation of the Galois field F2m. More...

#include <polynomial.h>

Collaboration diagram for libecc::polynomial< m, k, k1, k2 >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef
Operator::bitsetExpression< m,
false, false,
Operator::bitsetXOR > 		xor_type
 The type of add and subtract expressions of polynomials (ie, p1 + p2).

Public Member Functions

 polynomial (void)
 polynomial (bitset_digit_t coefficients)
 polynomial (polynomial const &p)
 polynomial (bitset< m > const &coefficients)
 polynomial (std::string const &coefficients)
 polynomial (xor_type const &expression)
polynomial & operator= (polynomial const &p)
polynomial & operator= (bitset< m > const &coefficients)
polynomial & operator= (xor_type const &expression)
 polynomial (polynomial const &b, polynomial const &c)
polynomial & square (bitset_digit_t *tmpbuf) const
bool sqrt (void)
polynomial & operator+= (polynomial const &p)
polynomial & operator-= (polynomial const &p)
polynomial & operator*= (polynomial const &p)
polynomial & operator*= (typename polynomial< m, k, k1, k2 >::xor_type const &expr)
polynomial & operator/= (polynomial const &p)
polynomial & operator/= (typename polynomial< m, k, k1, k2 >::xor_type const &expr)
int trace (void) const
bitset< m > const & get_bitset (void) const
bitset< m > & get_bitset (void)

Static Public Member Functions

static polynomial const & unity (void)
static bitset< m > const & normal (void)

Static Public Attributes

static unsigned int const square_digits

Friends

xor_type operator+ (polynomial const &p1, polynomial const &p2)
xor_type operator- (polynomial const &p1, polynomial const &p2)
polynomial operator* (polynomial const &p1, polynomial const &p2)
bool operator* (polynomial< m, k, k1, k2 >::xor_type const &expr, polynomial< m, k, k1, k2 > const &p2)
bool operator* (polynomial< m, k, k1, k2 > const &p1, polynomial< m, k, k1, k2 >::xor_type const &expr)
polynomial operator/ (polynomial const &p1, polynomial const &p2)
bool operator/ (polynomial< m, k, k1, k2 >::xor_type const &expr, polynomial< m, k, k1, k2 > const &p2)
bool operator/ (polynomial< m, k, k1, k2 > const &p1, polynomial< m, k, k1, k2 >::xor_type const &expr)
bool operator== (polynomial const &p1, polynomial const &p2)
bool operator== (polynomial< m, k, k1, k2 >::xor_type const &expr, polynomial< m, k, k1, k2 > const &p2)
bool operator== (polynomial< m, k, k1, k2 > const &p1, polynomial< m, k, k1, k2 >::xor_type const &expr)
bool operator!= (polynomial const &p1, polynomial const &p2)
bool operator!= (polynomial< m, k, k1, k2 >::xor_type const &expr, polynomial< m, k, k1, k2 > const &p2)
bool operator!= (polynomial< m, k, k1, k2 > const &p1, polynomial< m, k, k1, k2 >::xor_type const &expr)
std::ostream & operator<< (std::ostream &os, polynomial const &p)
std::ostream & operator<< (std::ostream &os, polynomial< m, k, k1, k2 >::xor_type const &expr)

Detailed Description

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
class libecc::polynomial< m, k, k1, k2 >

Polynomial representation of the Galois field F2m.

This class represents a polynomial with binairy coefficients (0 or 1) for a finite field with the fixed reduction polynomial.

The reduction polynomial is either a trinomial (when k1 is 0), tm+tk+1, or a pentanomial, tm+tk+tk1+tk2+1.

See also:
Theory: Galois fields with cardinality 2m, the polynomial basis

Member Typedef Documentation

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
typedef Operator::bitsetExpression<m, false, false, Operator::bitsetXOR> libecc::polynomial< m, k, k1, k2 >::xor_type

The type of add and subtract expressions of polynomials (ie, p1 + p2).

Constructor & Destructor Documentation

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( void   )  [inline]

Construct an uninitialized field element.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( bitset_digit_t  coefficients  )  [inline, explicit]

Construct a polynomial of a low degree.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( polynomial< m, k, k1, k2 > const &  p  )  [inline]

Copy constructor.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( bitset< m > const &  coefficients  )  [inline, explicit]

Construct a polynomial with binairy coefficients given by the bitset coefficients.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( std::string const &  coefficients  )  [inline]

Construct a polynomial with binairy coefficients given by the hexadecimal value in the string coefficients.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
libecc::polynomial< m, k, k1, k2 >::polynomial ( xor_type const &  expression  )  [inline]

Construct a polynomial that is the sum of two other polynomials. This constructor is for implicit conversion in code like

 polynomial<m, k, k1, k2> p1("2"), p2("3");

 polynomial<m, k, k1, k2> p3 = p1 + p2;

Here this constructor is used to convert the xor_type (which is Operator::bitsetExpression<m, false, false, Operator::bitsetXOR>) returned by (p1 + p2) into a polynomial.

Note that because polynomial is a template, automatic conversion does unfortunately not happen. Code like

 polynomial<m, k, k1, k2> p4 = (p1 + p2) * p3;

needs an explicit operator*(xor_type, polynomial), for this code to compile (having just operator*(polynomial, polynomial) won't work).

Also note that code like

 polynomial<m, k, k1, k2> p5 = (p1 + p2) * (p3 + p4);

where the + may be a minus, and the * can be any binary operator, will not compile at all: it is not possible to determine the return type (a polynomial) from a call to operator*(xor_type, xor_type). Instead you have to split up the line or provide an explicit cast for one of the operands:

 polynomial<m, k, k1, k2> p5 = (p1 + p2) * polynomial<m, k, k1, k2>(p3 + p4);
template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
libecc::polynomial< m, k, k1, k2 >::polynomial ( polynomial< m, k, k1, k2 > const &  b,
polynomial< m, k, k1, k2 > const &  c 
)

Construct a polynomial x that is the solution to the quadratic equation x2 + b $\cdot$ x = c.

References libecc::bitset_base< N >::any(), libecc::polynomial< m, k, k1, k2 >::get_bitset(), libecc::bitset_base< N >::odd(), libecc::bitset_base< N >::reset(), libecc::bitset_base< N >::set(), libecc::polynomial< m, k, k1, k2 >::sqrt(), libecc::polynomial< m, k, k1, k2 >::square(), libecc::polynomial< m, k, k1, k2 >::square_digits, libecc::bitset_base< N >::test(), and libecc::polynomial< m, k, k1, k2 >::trace().

Member Function Documentation

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bitset<m> const& libecc::polynomial< m, k, k1, k2 >::get_bitset ( void   )  const [inline]

Return the underlaying bitset representing the coefficients.

Referenced by libecc::polynomial< m, k, k1, k2 >::operator/=(), libecc::polynomial< m, k, k1, k2 >::polynomial(), and libecc::polynomial< m, k, k1, k2 >::sqrt().

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bitset<m>& libecc::polynomial< m, k, k1, k2 >::get_bitset ( void   )  [inline]

Return the underlaying bitset representing the coefficients.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
static bitset<m> const& libecc::polynomial< m, k, k1, k2 >::normal ( void   )  [inline, static]

Returns the normal to the hyperplane existing of all elements with trace 0.

The returned value is a reference to a constant static. This function is extremely fast.

See also:
Cracking parameter a of the elliptic curve
template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
polynomial< m, k, k1, k2 > & libecc::polynomial< m, k, k1, k2 >::operator*= ( typename polynomial< m, k, k1, k2 >::xor_type const &  expr  )  [inline]

Multiply this polynomial by the sum of two polynomials.

For example,

 p1 *= p2 + p3;
See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
polynomial< m, k, k1, k2 > & libecc::polynomial< m, k, k1, k2 >::operator*= ( polynomial< m, k, k1, k2 > const &  p  )  [inline]

Multiply this polynomial with polynomial p.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial& libecc::polynomial< m, k, k1, k2 >::operator+= ( polynomial< m, k, k1, k2 > const &  p  )  [inline]

Add polynomial p to this polynomial.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial& libecc::polynomial< m, k, k1, k2 >::operator-= ( polynomial< m, k, k1, k2 > const &  p  )  [inline]

Subtract polynomial p from this polynomial. Has the same effect as adding it.

template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
polynomial< m, k, k1, k2 > & libecc::polynomial< m, k, k1, k2 >::operator/= ( polynomial< m, k, k1, k2 > const &  p  ) 

Devide this polynomial by polynomial p.

References libecc::bitset_base< N >::begin(), libecc::bitset_base< N >::flip(), libecc::polynomial< m, k, k1, k2 >::get_bitset(), libecc::bitset_base< N >::rbegin(), libecc::bitset_base< N >::test(), and libecc::bitset_base< N >::xor_with_zero_padded().

template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
polynomial< m, k, k1, k2 > & libecc::polynomial< m, k, k1, k2 >::operator/= ( typename polynomial< m, k, k1, k2 >::xor_type const &  expr  )  [inline]

Devide this polynomial by the sum of two polynomials.

For example,

 p1 /= p2 + p3;
See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
polynomial< m, k, k1, k2 > & libecc::polynomial< m, k, k1, k2 >::operator= ( xor_type const &  expression  )  [inline]

Add two polynomials and assign the result to this polynomial. This operator is used when doing p1 = p2 + p3;.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial& libecc::polynomial< m, k, k1, k2 >::operator= ( bitset< m > const &  coefficients  )  [inline]

Assignment operator, set the coefficients of this polynomial equal to coefficients.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial& libecc::polynomial< m, k, k1, k2 >::operator= ( polynomial< m, k, k1, k2 > const &  p  )  [inline]

Assignment operator, set this polynomial equal to p.

template<unsigned int m, unsigned int k, unsigned int k1, unsigned int k2>
bool libecc::polynomial< m, k, k1, k2 >::sqrt ( void   ) 

Calculate the square root of this polynomial.

Returns true if a solution was found. If m, k, k1 and k2 represent an irreducible polynomial (as it should for this to be a field) then a solution will always be found and this function will always return true.

References libecc::bitset_base< N >::clear(), libecc::bitset_base< N >::flip(), libecc::polynomial< m, k, k1, k2 >::get_bitset(), libecc::bitset_base< N >::reset(), libecc::bitset_base< N >::set(), libecc::polynomial< m, k, k1, k2 >::square(), and libecc::bitset_base< N >::test().

Referenced by libecc::polynomial< m, k, k1, k2 >::polynomial().

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial& libecc::polynomial< m, k, k1, k2 >::square ( bitset_digit_t *  tmpbuf  )  const

Calculate the square of this polynomial.

The result is written into tmpbuf which is returned, casted to a polynomial. Usage:

 libecc:polynomial<m, k, k1, k2> p1(init);
 libecc::bitset_digit_t p2buf[libecc:polynomial<m, k, k1, k2>::square_digits];
 libecc:polynomial<m, k, k1, k2>& p2 = p1.square(p2buf);        // p2 becomes the square of p1.

p2buf should not be destructed until the reference p2 will not be used anymore.

Referenced by libecc::polynomial< m, k, k1, k2 >::polynomial(), and libecc::polynomial< m, k, k1, k2 >::sqrt().

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
int libecc::polynomial< m, k, k1, k2 >::trace ( void   )  const [inline]

Returns the trace of this object.

The trace is either 0 or 1. If the trace is 0 then there will exist a polynomial y such that this object is equal to y + y2. Otherwise no such polynomial exists. This function is extremely fast (a few assembly instructions).

See also:
Theory: The trace of a field element

Referenced by libecc::polynomial< m, k, k1, k2 >::polynomial().

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
static polynomial const& libecc::polynomial< m, k, k1, k2 >::unity ( void   )  [inline, static]

Returns the multiplicative unity for the field (1).

Friends And Related Function Documentation

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator!= ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Compare two polynomials. Returns true when p1 != p2, false otherwise.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator!= ( polynomial< m, k, k1, k2 >::xor_type const &  expr,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Compare polynomial p2 with the result of expr (the result of an addition or subtraction).

For example: if (p1 + p3 != p2).

See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator!= ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 >::xor_type const &  expr 
) [friend]

Compare polynomial p1 with the result of expr (the result of an addition or subtraction).

For example: if (p1 != p2 + p3).

See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator* ( polynomial< m, k, k1, k2 >::xor_type const &  expr,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Multiply polynomial p2 with the result of expr (the result of an addition or subtraction).

For example: (p1 + p3) * p2.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator* ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 >::xor_type const &  expr 
) [friend]

Multiply polynomial p1 with the result of expr (the result of an addition or subtraction).

For example: p1 * (p2 + p3).

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial operator* ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Multiply polynomial p1 with polynomial p2.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
xor_type operator+ ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Prepare the addition of two polynomials.

Returns a dummy object with two pointers to the polynomials to be added. The addition does not take place until the final destination polynomial is known as well.

Note that it is not possible to write:

 p1 OP= p1 + p2 + p3;

There is a complicated reason for that. Instead, write

 polynomial<m,k> tmp(p2 + p3);
 p1 OP= p1 + tmp;

For example, when adding a whole series of polynomials you'd do:

 polynomial<m,k> result(p1 + p2);
 result += p3 + p4;
 result += p5 + p5;
 ...

Basically, it is not supported to add or substract a polynomial to or from a temporary that represents an addition or subtraction by itself.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
xor_type operator- ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Prepare the subtraction of two polynomials.

Returns a dummy object with two pointers to the polynomials to be subtracted. The subtraction does not take place until the final destination polynomial is known as well.

See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator/ ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 >::xor_type const &  expr 
) [friend]

Devide polynomial p1 by the result of expr (the result of an addition or subtraction).

For example: p1 / (p2 + p3).

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
polynomial operator/ ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Devide polynomial p1 by polynomial p2.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator/ ( polynomial< m, k, k1, k2 >::xor_type const &  expr,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Devide polynomial the result of expr, the result of an addition or subtraction, by polynomial p2.

For example: (p1 + p3) / p2.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
std::ostream& operator<< ( std::ostream &  os,
polynomial< m, k, k1, k2 > const &  p 
) [friend]

Write the binary coefficients of the polynomial p to os.

For example, an output string 1001101 means t6 + t3 + t2 + 1.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
std::ostream& operator<< ( std::ostream &  os,
polynomial< m, k, k1, k2 >::xor_type const &  expr 
) [friend]

Write the binary coefficients of the result of expr (the result of an addition or subtraction) to os.

See also:
operator<<(std::ostream&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator== ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Compare two polynomials. Returns true when p1 == p2, false otherwise.

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator== ( polynomial< m, k, k1, k2 >::xor_type const &  expr,
polynomial< m, k, k1, k2 > const &  p2 
) [friend]

Compare polynomial p2 with the result of expr (the result of an addition or subtraction).

For example: if (p1 + p3 == p2).

See also:
operator+(polynomial const&, polynomial const&)
template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
bool operator== ( polynomial< m, k, k1, k2 > const &  p1,
polynomial< m, k, k1, k2 >::xor_type const &  expr 
) [friend]

Compare polynomial p1 with the result of expr (the result of an addition or subtraction).

For example: if (p1 == p2 + p3).

See also:
operator+(polynomial const&, polynomial const&)

Member Data Documentation

template<unsigned int m, unsigned int k, unsigned int k1 = 0, unsigned int k2 = 0>
unsigned int const libecc::polynomial< m, k, k1, k2 >::square_digits [static]

Number of digits needed for temporary buffer used to calculate a square.

Referenced by libecc::polynomial< m, k, k1, k2 >::polynomial().

Copyright © 2002-2008 Carlo Wood.  All rights reserved.