Lines Matching refs:ring
16 void PolynomialOver<T>::Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring)
20 m_coefficients[i] = ring.RandomElement(rng, parameter.m_coefficientParameter);
24 void PolynomialOver<T>::FromStr(const char *str, const Ring &ring)
35 coef = ring.MultiplicativeIdentity();
56 coef = ring.Inverse(coef);
58 SetCoefficient(power, coef, ring);
76 unsigned int PolynomialOver<T>::CoefficientCount(const Ring &ring) const
79 while (count && ring.Equal(m_coefficients[count-1], ring.Identity()))
86 typename PolynomialOver<T>::CoefficientType PolynomialOver<T>::GetCoefficient(unsigned int i, const Ring &ring) const
88 return (i < m_coefficients.size()) ? m_coefficients[i] : ring.Identity();
104 PolynomialOver<T>& PolynomialOver<T>::Accumulate(const PolynomialOver<T>& t, const Ring &ring)
106 unsigned int count = t.CoefficientCount(ring);
108 if (count > CoefficientCount(ring))
109 m_coefficients.resize(count, ring.Identity());
112 ring.Accumulate(m_coefficients[i], t.GetCoefficient(i, ring));
118 PolynomialOver<T>& PolynomialOver<T>::Reduce(const PolynomialOver<T>& t, const Ring &ring)
120 unsigned int count = t.CoefficientCount(ring);
122 if (count > CoefficientCount(ring))
123 m_coefficients.resize(count, ring.Identity());
126 ring.Reduce(m_coefficients[i], t.GetCoefficient(i, ring));
132 typename PolynomialOver<T>::CoefficientType PolynomialOver<T>::EvaluateAt(const CoefficientType &x, const Ring &ring) const
134 int degree = Degree(ring);
137 return ring.Identity();
142 result = ring.Multiply(result, x);
143 ring.Accumulate(result, m_coefficients[j]);
149 PolynomialOver<T>& PolynomialOver<T>::ShiftLeft(unsigned int n, const Ring &ring)
151 unsigned int i = CoefficientCount(ring) + n;
152 m_coefficients.resize(i, ring.Identity());
161 m_coefficients[i] = ring.Identity();
167 PolynomialOver<T>& PolynomialOver<T>::ShiftRight(unsigned int n, const Ring &ring)
169 unsigned int count = CoefficientCount(ring);
174 m_coefficients.resize(count-n, ring.Identity());
177 m_coefficients.resize(0, ring.Identity());
182 void PolynomialOver<T>::SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring)
185 m_coefficients.resize(i+1, ring.Identity());
190 void PolynomialOver<T>::Negate(const Ring &ring)
192 unsigned int count = CoefficientCount(ring);
194 m_coefficients[i] = ring.Inverse(m_coefficients[i]);
204 bool PolynomialOver<T>::Equals(const PolynomialOver<T>& t, const Ring &ring) const
206 unsigned int count = CoefficientCount(ring);
208 if (count != t.CoefficientCount(ring))
212 if (!ring.Equal(m_coefficients[i], t.m_coefficients[i]))
219 PolynomialOver<T> PolynomialOver<T>::Plus(const PolynomialOver<T>& t, const Ring &ring) const
222 unsigned int count = CoefficientCount(ring);
223 unsigned int tCount = t.CoefficientCount(ring);
227 PolynomialOver<T> result(ring, count);
230 result.m_coefficients[i] = ring.Add(m_coefficients[i], t.m_coefficients[i]);
238 PolynomialOver<T> result(ring, tCount);
241 result.m_coefficients[i] = ring.Add(m_coefficients[i], t.m_coefficients[i]);
250 PolynomialOver<T> PolynomialOver<T>::Minus(const PolynomialOver<T>& t, const Ring &ring) const
253 unsigned int count = CoefficientCount(ring);
254 unsigned int tCount = t.CoefficientCount(ring);
258 PolynomialOver<T> result(ring, count);
261 result.m_coefficients[i] = ring.Subtract(m_coefficients[i], t.m_coefficients[i]);
269 PolynomialOver<T> result(ring, tCount);
272 result.m_coefficients[i] = ring.Subtract(m_coefficients[i], t.m_coefficients[i]);
274 result.m_coefficients[i] = ring.Inverse(t.m_coefficients[i]);
281 PolynomialOver<T> PolynomialOver<T>::Inverse(const Ring &ring) const
283 unsigned int count = CoefficientCount(ring);
284 PolynomialOver<T> result(ring, count);
287 result.m_coefficients[i] = ring.Inverse(m_coefficients[i]);
293 PolynomialOver<T> PolynomialOver<T>::Times(const PolynomialOver<T>& t, const Ring &ring) const
295 if (IsZero(ring) || t.IsZero(ring))
298 unsigned int count1 = CoefficientCount(ring), count2 = t.CoefficientCount(ring);
299 PolynomialOver<T> result(ring, count1 + count2 - 1);
303 ring.Accumulate(result.m_coefficients[i+j], ring.Multiply(m_coefficients[i], t.m_coefficients[j]));
309 PolynomialOver<T> PolynomialOver<T>::DividedBy(const PolynomialOver<T>& t, const Ring &ring) const
312 Divide(remainder, quotient, *this, t, ring);
317 PolynomialOver<T> PolynomialOver<T>::Modulo(const PolynomialOver<T>& t, const Ring &ring) const
320 Divide(remainder, quotient, *this, t, ring);
325 PolynomialOver<T> PolynomialOver<T>::MultiplicativeInverse(const Ring &ring) const
327 return Degree(ring)==0 ? ring.MultiplicativeInverse(m_coefficients[0]) : ring.Identity();
331 bool PolynomialOver<T>::IsUnit(const Ring &ring) const
333 return Degree(ring)==0 && ring.IsUnit(m_coefficients[0]);
337 std::istream& PolynomialOver<T>::Input(std::istream &in, const Ring &ring)
364 *this = PolynomialOver<T>(str, ring);
370 std::ostream& PolynomialOver<T>::Output(std::ostream &out, const Ring &ring) const
372 unsigned int i = CoefficientCount(ring);
379 if (m_coefficients[i] != ring.Identity())
384 if (!i || !ring.Equal(m_coefficients[i], ring.MultiplicativeIdentity()))
389 CoefficientType inverse = ring.Inverse(m_coefficients[i]);
398 if (!i || !ring.Equal(m_coefficients[i], ring.MultiplicativeIdentity()))
404 if (!i || !ring.Equal(inverse, ring.MultiplicativeIdentity()))
424 out << ring.Identity();
430 void PolynomialOver<T>::Divide(PolynomialOver<T> &r, PolynomialOver<T> &q, const PolynomialOver<T> &a, const PolynomialOver<T> &d, const Ring &ring)
432 unsigned int i = a.CoefficientCount(ring);
433 const int dDegree = d.Degree(ring);
444 q.m_coefficients[i-dDegree] = ring.Divide(r.m_coefficients[i], d.m_coefficients[dDegree]);
446 ring.Reduce(r.m_coefficients[i-dDegree+j], ring.Multiply(q.m_coefficients[i-dDegree], d.m_coefficients[j]));
449 r.CoefficientCount(ring); // resize r.m_coefficients
515 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n)
519 Element t = ring.MultiplicativeIdentity();
522 t = ring.Multiply(t, ring.Subtract(x[i], x[j]));
523 w[i] = ring.MultiplicativeInverse(t);
528 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n)
536 a[n-1+i] = ring.Subtract(position, x[i]);
539 a[i-1] = ring.Multiply(a[2*i], a[2*i-1]);
541 a[0] = ring.MultiplicativeIdentity();
546 a[2*i+1] = ring.Multiply(a[i], a[2*i+1]);
547 a[2*i+2] = ring.Multiply(a[i], a[2*i+2]);
551 v[i] = ring.Multiply(a[n-1+i], w[i]);
555 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n)
557 Element result = ring.Identity();
559 ring.Accumulate(result, ring.Multiply(y[i], v[i]));