polynomi_8cpp-source.html

Crypto++是一个非常强大的密码学库,主要是功能全

00390                                         std::ostrstream pstr, nstr;
00391 
00392                                         pstr << m_coefficients[i];
00393                                         nstr << inverse;
00394 
00395                                         <span class="keywordflow">if</span> (pstr.pcount() &lt;= nstr.pcount())
00396                                         {
00397                                                 out &lt;&lt; <span class="stringliteral">" + "</span>; 
00398                                                 <span class="keywordflow">if</span> (!i || !ring.Equal(m_coefficients[i], ring.MultiplicativeIdentity()))
00399                                                         out &lt;&lt; m_coefficients[i];
00400                                         }
00401                                         <span class="keywordflow">else</span>
00402                                         {
00403                                                 out &lt;&lt; <span class="stringliteral">" - "</span>; 
00404                                                 <span class="keywordflow">if</span> (!i || !ring.Equal(inverse, ring.MultiplicativeIdentity()))
00405                                                         out &lt;&lt; inverse;
00406                                         }
00407                                 }
00408 
00409                                 <span class="keywordflow">switch</span> (i)
00410                                 {
00411                                 <span class="keywordflow">case</span> 0:
00412                                         <span class="keywordflow">break</span>;
00413                                 <span class="keywordflow">case</span> 1:
00414                                         out &lt;&lt; <span class="stringliteral">"x"</span>;
00415                                         <span class="keywordflow">break</span>;
00416                                 <span class="keywordflow">default</span>:
00417                                         out &lt;&lt; <span class="stringliteral">"x^"</span> &lt;&lt; i;
00418                                 }
00419                         }
00420                 }
00421         }
00422         <span class="keywordflow">else</span>
00423         {
00424                 out &lt;&lt; ring.Identity();
00425         }
00426         <span class="keywordflow">return</span> out;
00427 }
00428 
00429 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00430 <span class="keywordtype">void</span> <a class="code" href="class_polynomial_over.html#_polynomial_over_fixed_ringz63_17">PolynomialOver&lt;T&gt;::Divide</a>(<a class="code" href="class_polynomial_over.html">PolynomialOver&lt;T&gt;</a> &amp;r, <a class="code" href="class_polynomial_over.html">PolynomialOver&lt;T&gt;</a> &amp;q, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html">PolynomialOver&lt;T&gt;</a> &amp;a, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html">PolynomialOver&lt;T&gt;</a> &amp;d, <span class="keyword">const</span> Ring &amp;ring)
00431 {
00432         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = a.CoefficientCount(ring);
00433         <span class="keyword">const</span> <span class="keywordtype">int</span> dDegree = d.Degree(ring);
00434 
00435         <span class="keywordflow">if</span> (dDegree &lt; 0)
00436                 <span class="keywordflow">throw</span> DivideByZero();
00437 
00438         r = a;
00439         q.<a class="code" href="class_polynomial_over.html#_polynomial_overr0">m_coefficients</a>.resize(STDMAX(0, <span class="keywordtype">int</span>(i - dDegree)));
00440 
00441         <span class="keywordflow">while</span> (i &gt; (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)dDegree)
00442         {
00443                 --i;
00444                 q.<a class="code" href="class_polynomial_over.html#_polynomial_overr0">m_coefficients</a>[i-dDegree] = ring.Divide(r.<a class="code" href="class_polynomial_over.html#_polynomial_overr0">m_coefficients</a>[i], d.m_coefficients[dDegree]);
00445                 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=0; j&lt;=dDegree; j++)
00446                         ring.Reduce(r.<a class="code" href="class_polynomial_over.html#_polynomial_overr0">m_coefficients</a>[i-dDegree+j], ring.Multiply(q.<a class="code" href="class_polynomial_over.html#_polynomial_overr0">m_coefficients</a>[i-dDegree], d.m_coefficients[j]));
00447         }
00448 
00449         r.<a class="code" href="class_polynomial_over.html#_polynomial_over_fixed_ringz59_1">CoefficientCount</a>(ring);       <span class="comment">// resize r.m_coefficients</span>
00450 }
00451 
00452 <span class="comment">// ********************************************************</span>
00453 
00454 <span class="comment">// helper function for Interpolate() and InterpolateAt()</span>
00455 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00456 <span class="keywordtype">void</span> <a class="code" href="class_ring_of_polynomials_over.html">RingOfPolynomialsOver&lt;T&gt;::CalculateAlpha</a>(std::vector&lt;CoefficientType&gt; &amp;alpha, <span class="keyword">const</span> CoefficientType x[], <span class="keyword">const</span> CoefficientType y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
00457 <span class="keyword"></span>{
00458         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;n; ++j)
00459                 alpha[j] = y[j];
00460 
00461         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k=1; k&lt;n; ++k)
00462         {
00463                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=n-1; j&gt;=k; --j)
00464                 {
00465                         m_ring.Reduce(alpha[j], alpha[j-1]);
00466 
00467                         CoefficientType d = m_ring.Subtract(x[j], x[j-k]);
00468                         <span class="keywordflow">if</span> (!m_ring.IsUnit(d))
00469                                 <span class="keywordflow">throw</span> InterpolationFailed();
00470                         alpha[j] = m_ring.Divide(alpha[j], d);
00471                 }
00472         }
00473 }
00474 
00475 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00476 <a class="code" href="class_ring_of_polynomials_over.html">RingOfPolynomialsOver&lt;T&gt;</a>::Element <a class="code" href="class_ring_of_polynomials_over.html">RingOfPolynomialsOver&lt;T&gt;::Interpolate</a>(<span class="keyword">const</span> CoefficientType x[], <span class="keyword">const</span> CoefficientType y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
00477 <span class="keyword"></span>{
00478         assert(n &gt; 0);
00479 
00480         std::vector&lt;CoefficientType&gt; alpha(n);
00481         CalculateAlpha(alpha, x, y, n);
00482 
00483         std::vector&lt;CoefficientType&gt; coefficients((size_t)n, m_ring.Identity());
00484         coefficients[0] = alpha[n-1];
00485 
00486         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=n-2; j&gt;=0; --j)
00487         {
00488                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=n-j-1; i&gt;0; i--)
00489                         coefficients[i] = m_ring.Subtract(coefficients[i-1], m_ring.Multiply(coefficients[i], x[j]));
00490 
00491                 coefficients[0] = m_ring.Subtract(alpha[j], m_ring.Multiply(coefficients[0], x[j]));
00492         }
00493 
00494         <span class="keywordflow">return</span> <a class="code" href="class_polynomial_over.html">PolynomialOver&lt;T&gt;</a>(coefficients.begin(), coefficients.end());
00495 }
00496 
00497 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00498 <span class="keyword">typename</span> <a class="code" href="class_ring_of_polynomials_over.html">RingOfPolynomialsOver&lt;T&gt;</a>::CoefficientType <a class="code" href="class_ring_of_polynomials_over.html">RingOfPolynomialsOver&lt;T&gt;::InterpolateAt</a>(<span class="keyword">const</span> CoefficientType &amp;position, <span class="keyword">const</span> CoefficientType x[], <span class="keyword">const</span> CoefficientType y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
00499 <span class="keyword"></span>{
00500         assert(n &gt; 0);
00501 
00502         std::vector&lt;CoefficientType&gt; alpha(n);
00503         CalculateAlpha(alpha, x, y, n);
00504 
00505         CoefficientType result = alpha[n-1];
00506         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=n-2; j&gt;=0; --j)
00507         {
00508                 result = m_ring.Multiply(result, m_ring.Subtract(position, x[j]));
00509                 m_ring.Accumulate(result, alpha[j]);
00510         }
00511         <span class="keywordflow">return</span> result;
00512 }
00513 
00514 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Ring, <span class="keyword">class</span> Element&gt;
00515 <span class="keywordtype">void</span> PrepareBulkPolynomialInterpolation(<span class="keyword">const</span> Ring &amp;ring, Element *w, <span class="keyword">const</span> Element x[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
00516 {
00517         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i&lt;n; i++)
00518         {
00519                 Element t = ring.MultiplicativeIdentity();
00520                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;n; j++)
00521                         <span class="keywordflow">if</span> (i != j)
00522                                 t = ring.Multiply(t, ring.Subtract(x[i], x[j]));
00523                 w[i] = ring.MultiplicativeInverse(t);
00524         }
00525 }
00526 
00527 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Ring, <span class="keyword">class</span> Element&gt;
00528 <span class="keywordtype">void</span> PrepareBulkPolynomialInterpolationAt(<span class="keyword">const</span> Ring &amp;ring, Element *v, <span class="keyword">const</span> Element &amp;position, <span class="keyword">const</span> Element x[], <span class="keyword">const</span> Element w[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
00529 {
00530         assert(n &gt; 0);
00531 
00532         std::vector&lt;Element&gt; a(2*n-1);
00533         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00534 
00535         <span class="keywordflow">for</span> (i=0; i&lt;n; i++)
00536                 a[n-1+i] = ring.Subtract(position, x[i]);
00537 
00538         <span class="keywordflow">for</span> (i=n-1; i&gt;1; i--)
00539                 a[i-1] = ring.Multiply(a[2*i], a[2*i-1]);
00540 
00541         a[0] = ring.MultiplicativeIdentity();
00542 
00543         <span class="keywordflow">for</span> (i=0; i&lt;n-1; i++)
00544         {
00545                 std::swap(a[2*i+1], a[2*i+2]);
00546                 a[2*i+1] = ring.Multiply(a[i], a[2*i+1]);
00547                 a[2*i+2] = ring.Multiply(a[i], a[2*i+2]);
00548         }
00549 
00550         <span class="keywordflow">for</span> (i=0; i&lt;n; i++)
00551                 v[i] = ring.Multiply(a[n-1+i], w[i]);
00552 }
00553 
00554 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Ring, <span class="keyword">class</span> Element&gt;
00555 Element BulkPolynomialInterpolateAt(<span class="keyword">const</span> Ring &amp;ring, <span class="keyword">const</span> Element y[], <span class="keyword">const</span> Element v[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
00556 {
00557         Element result = ring.Identity();
00558         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i&lt;n; i++)
00559                 ring.Accumulate(result, ring.Multiply(y[i], v[i]));
00560         <span class="keywordflow">return</span> result;
00561 }
00562 
00563 <span class="comment">// ********************************************************</span>
00564 
00565 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keywordtype">int</span> instance&gt;
00566 <span class="keyword">const</span> <a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;</a> &amp;<a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;::Zero</a>()
00567 {
00568         <span class="keyword">static</span> <span class="keyword">const</span> <a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;</a> zero;
00569         <span class="keywordflow">return</span> zero;
00570 }
00571 
00572 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keywordtype">int</span> instance&gt;
00573 <span class="keyword">const</span> <a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;</a> &amp;<a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;::One</a>()
00574 {
00575         <span class="keyword">static</span> <span class="keyword">const</span> <a class="code" href="class_polynomial_over_fixed_ring.html">PolynomialOverFixedRing&lt;T, instance&gt;</a> one = fixedRing.MultiplicativeIdentity();
00576         <span class="keywordflow">return</span> one;
00577 }
00578 
00579 NAMESPACE_END
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Tue Jul 8 23:34:21 2003 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 > 
</a>1.3.2 </small></address>
</body>
</html>