bivpol.h 2.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
/* Common header file for the rrspace software

This file is part of the rrspace project.

This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 2.1 of the License, or (at your option) any
later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
details.

You should have received a copy of the GNU Lesser General Public License along
with this library; if not, write to the Free Software Foundation, Inc., 51
Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

*/

// class for bivariate polynomials over prime finite fields, written as
// univariate polynomials with polynomial coefficients.
// They are stored as a (d+1)-uplet (g_0,...,g_d) of univariate polynomials, i.e
// \sum_{i=0}^{d} g_i(X)*Y^i

#ifndef BIVPOL_H_
#define BIVPOL_H_

#include <NTL/ZZ_pX.h>
#include <vector>
#include <assert.h>
#include <iostream>

class BivPol {
 private:
  std::vector<NTL::ZZ_pX> coeffs;
 
 public:
  BivPol() {}
  BivPol(const std::vector<NTL::ZZ_pX>& _coeffs) : coeffs(_coeffs) {
    assert(coeffs.back() != NTL::ZZ_p(0));
  }

  std::size_t degree() const;
  std::size_t degree_y() const { return coeffs.size() - 1; }
  NTL::ZZ_pX coeff(std::size_t i) const { return coeffs[i]; }
  NTL::ZZ_pX LeadingCoeff() const { return coeffs[coeffs.size() - 1]; }
  bool IsZero() const;
  NTL::ZZ_pX mod_eval(const NTL::ZZ_pX& g, const NTL::ZZ_pX& modulus) const;
  BivPol diffY() const;

  friend std::istream& operator>>(std::istream&, BivPol&);
};

NTL::ZZ_pX
NewtonHenselStep(const BivPol& q, 
                 const NTL::ZZ_pX& s, 
                 const NTL::ZZ_pX& modulus);

// k steps of Newton-Hensel lifting
NTL::ZZ_pX
NewtonHensel(const BivPol& q, 
             const NTL::ZZ_pX& s, 
             const NTL::ZZ_pX& modulus, 
             std::size_t k);

std::ostream& operator<<(std::ostream&, const BivPol&);
std::ostream& PrintMagma(std::ostream&, const BivPol&);
std::istream& operator>>(std::istream&, BivPol&);

#endif