polynomi_8cpp-source.html

著名的密码库Crypto++的文档 C++语言的杰作。程序员必备。

<a name="l00424"></a>00424                 out &lt;&lt; ring.Identity();
<a name="l00425"></a>00425         }
<a name="l00426"></a>00426         <span class="keywordflow">return</span> out;
<a name="l00427"></a>00427 }
<a name="l00428"></a>00428 
<a name="l00429"></a>00429 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00430"></a>00430 <span class="keywordtype">void</span> <a class="code" href="class_polynomial_over.html#e4e0b0beb7bfab492d6f7343630c2df9" title="calculate r and q such that (a == d*q + r) &amp;&amp; (0 &lt;= degree of r &lt; degree...">PolynomialOver&lt;T&gt;::Divide</a>(PolynomialOver&lt;T&gt; &amp;r, PolynomialOver&lt;T&gt; &amp;q, <span class="keyword">const</span> PolynomialOver&lt;T&gt; &amp;a, <span class="keyword">const</span> PolynomialOver&lt;T&gt; &amp;d, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)
<a name="l00431"></a>00431 {
<a name="l00432"></a>00432         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = a.<a class="code" href="class_polynomial_over.html#65c6004a42608f31008ff066f2eba3e2">CoefficientCount</a>(ring);
<a name="l00433"></a>00433         <span class="keyword">const</span> <span class="keywordtype">int</span> dDegree = d.<a class="code" href="class_polynomial_over.html#604beee6d397108b3334eaeb564b641a" title="the zero polynomial will return a degree of -1">Degree</a>(ring);
<a name="l00434"></a>00434 
<a name="l00435"></a>00435         <span class="keywordflow">if</span> (dDegree &lt; 0)
<a name="l00436"></a>00436                 <span class="keywordflow">throw</span> DivideByZero();
<a name="l00437"></a>00437 
<a name="l00438"></a>00438         r = a;
<a name="l00439"></a>00439         q.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>.resize(STDMAX(0, <span class="keywordtype">int</span>(i - dDegree)));
<a name="l00440"></a>00440 
<a name="l00441"></a>00441         <span class="keywordflow">while</span> (i &gt; (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)dDegree)
<a name="l00442"></a>00442         {
<a name="l00443"></a>00443                 --i;
<a name="l00444"></a>00444                 q.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[i-dDegree] = ring.Divide(r.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[i], d.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[dDegree]);
<a name="l00445"></a>00445                 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=0; j&lt;=dDegree; j++)
<a name="l00446"></a>00446                         ring.Reduce(r.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[i-dDegree+j], ring.Multiply(q.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[i-dDegree], d.<a class="code" href="class_polynomial_over.html#d669c6670fb313273a4d245eeddb82dc">m_coefficients</a>[j]));
<a name="l00447"></a>00447         }
<a name="l00448"></a>00448 
<a name="l00449"></a>00449         r.<a class="code" href="class_polynomial_over.html#65c6004a42608f31008ff066f2eba3e2">CoefficientCount</a>(ring);       <span class="comment">// resize r.m_coefficients</span>
<a name="l00450"></a>00450 }
<a name="l00451"></a>00451 
<a name="l00452"></a>00452 <span class="comment">// ********************************************************</span>
<a name="l00453"></a>00453 
<a name="l00454"></a>00454 <span class="comment">// helper function for Interpolate() and InterpolateAt()</span>
<a name="l00455"></a>00455 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00456"></a><a class="code" href="class_ring_of_polynomials_over.html#b80f9ffd1ebb119d125718f31d1ef170">00456</a> <span class="keywordtype">void</span> <a class="code" href="class_ring_of_polynomials_over.html#b80f9ffd1ebb119d125718f31d1ef170">RingOfPolynomialsOver&lt;T&gt;::CalculateAlpha</a>(std::vector&lt;CoefficientType&gt; &amp;alpha, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#2eb91afba2d1f0c11f78f5825ecd5408">CoefficientType</a> x[], <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#2eb91afba2d1f0c11f78f5825ecd5408">CoefficientType</a> y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
<a name="l00457"></a>00457 <span class="keyword"></span>{
<a name="l00458"></a>00458         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;n; ++j)
<a name="l00459"></a>00459                 alpha[j] = y[j];
<a name="l00460"></a>00460 
<a name="l00461"></a>00461         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k=1; k&lt;n; ++k)
<a name="l00462"></a>00462         {
<a name="l00463"></a>00463                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=n-1; j&gt;=k; --j)
<a name="l00464"></a>00464                 {
<a name="l00465"></a>00465                         <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Reduce(alpha[j], alpha[j-1]);
<a name="l00466"></a>00466 
<a name="l00467"></a>00467                         <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> d = <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Subtract(x[j], x[j-k]);
<a name="l00468"></a>00468                         <span class="keywordflow">if</span> (!<a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.IsUnit(d))
<a name="l00469"></a>00469                                 <span class="keywordflow">throw</span> <a class="code" href="class_ring_of_polynomials_over_1_1_interpolation_failed.html">InterpolationFailed</a>();
<a name="l00470"></a>00470                         alpha[j] = <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Divide(alpha[j], d);
<a name="l00471"></a>00471                 }
<a name="l00472"></a>00472         }
<a name="l00473"></a>00473 }
<a name="l00474"></a>00474 
<a name="l00475"></a>00475 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00476"></a><a class="code" href="class_ring_of_polynomials_over.html#5f36bbd09c0b766a2dd794b63028adf6">00476</a> <span class="keyword">typename</span> <a class="code" href="class_ring_of_polynomials_over.html" title="Ring of polynomials over another ring.">RingOfPolynomialsOver&lt;T&gt;::Element</a> <a class="code" href="class_ring_of_polynomials_over.html#5f36bbd09c0b766a2dd794b63028adf6">RingOfPolynomialsOver&lt;T&gt;::Interpolate</a>(<span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> x[], <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
<a name="l00477"></a>00477 <span class="keyword"></span>{
<a name="l00478"></a>00478         assert(n &gt; 0);
<a name="l00479"></a>00479 
<a name="l00480"></a>00480         std::vector&lt;CoefficientType&gt; alpha(n);
<a name="l00481"></a>00481         <a class="code" href="class_ring_of_polynomials_over.html#b80f9ffd1ebb119d125718f31d1ef170">CalculateAlpha</a>(alpha, x, y, n);
<a name="l00482"></a>00482 
<a name="l00483"></a>00483         std::vector&lt;CoefficientType&gt; coefficients((<span class="keywordtype">size_t</span>)n, <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Identity());
<a name="l00484"></a>00484         coefficients[0] = alpha[n-1];
<a name="l00485"></a>00485 
<a name="l00486"></a>00486         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=n-2; j&gt;=0; --j)
<a name="l00487"></a>00487         {
<a name="l00488"></a>00488                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=n-j-1; i&gt;0; i--)
<a name="l00489"></a>00489                         coefficients[i] = <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Subtract(coefficients[i-1], <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Multiply(coefficients[i], x[j]));
<a name="l00490"></a>00490 
<a name="l00491"></a>00491                 coefficients[0] = <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Subtract(alpha[j], <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Multiply(coefficients[0], x[j]));
<a name="l00492"></a>00492         }
<a name="l00493"></a>00493 
<a name="l00494"></a>00494         <span class="keywordflow">return</span> PolynomialOver&lt;T&gt;(coefficients.begin(), coefficients.end());
<a name="l00495"></a>00495 }
<a name="l00496"></a>00496 
<a name="l00497"></a>00497 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00498"></a><a class="code" href="class_ring_of_polynomials_over.html#3f5e10426b55fffebbc5b1f9b6646b45">00498</a> <span class="keyword">typename</span> <a class="code" href="class_ring_of_polynomials_over.html" title="Ring of polynomials over another ring.">RingOfPolynomialsOver&lt;T&gt;::CoefficientType</a> <a class="code" href="class_ring_of_polynomials_over.html#3f5e10426b55fffebbc5b1f9b6646b45">RingOfPolynomialsOver&lt;T&gt;::InterpolateAt</a>(<span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> &amp;position, <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> x[], <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> y[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
<a name="l00499"></a>00499 <span class="keyword"></span>{
<a name="l00500"></a>00500         assert(n &gt; 0);
<a name="l00501"></a>00501 
<a name="l00502"></a>00502         std::vector&lt;CoefficientType&gt; alpha(n);
<a name="l00503"></a>00503         <a class="code" href="class_ring_of_polynomials_over.html#b80f9ffd1ebb119d125718f31d1ef170">CalculateAlpha</a>(alpha, x, y, n);
<a name="l00504"></a>00504 
<a name="l00505"></a>00505         <a class="code" href="class_ring_of_polynomials_over.html#d481c398f3ffa1af06ffa30d71c68659">CoefficientType</a> <a class="code" href="class_abstract_euclidean_domain.html#f1314f064e73c560b3d31982c4e26404">result</a> = alpha[n-1];
<a name="l00506"></a>00506         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j=n-2; j&gt;=0; --j)
<a name="l00507"></a>00507         {
<a name="l00508"></a>00508                 result = <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Multiply(result, <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Subtract(position, x[j]));
<a name="l00509"></a>00509                 <a class="code" href="class_ring_of_polynomials_over.html#18dc9d8b05fbd86b93845c8710c59d74">m_ring</a>.Accumulate(result, alpha[j]);
<a name="l00510"></a>00510         }
<a name="l00511"></a>00511         <span class="keywordflow">return</span> result;
<a name="l00512"></a>00512 }
<a name="l00513"></a>00513 
<a name="l00514"></a>00514 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Ring, <span class="keyword">class</span> Element&gt;
<a name="l00515"></a><a class="code" href="polynomi_8h.html#7eea79e03a897e65e9b488ab6667ba32">00515</a> <span class="keywordtype">void</span> PrepareBulkPolynomialInterpolation(<span class="keyword">const</span> Ring &amp;ring, <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> *w, <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> x[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
<a name="l00516"></a>00516 {
<a name="l00517"></a>00517         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i&lt;n; i++)
<a name="l00518"></a>00518         {
<a name="l00519"></a>00519                 <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> t = ring.MultiplicativeIdentity();
<a name="l00520"></a>00520                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;n; j++)
<a name="l00521"></a>00521                         <span class="keywordflow">if</span> (i != j)
<a name="l00522"></a>00522                                 t = ring.Multiply(t, ring.Subtract(x[i], x[j]));
<a name="l00523"></a>00523                 w[i] = ring.<a class="code" href="class_polynomial_over.html#1a24658cd38205e6a3edc607aaceedda">MultiplicativeInverse</a>(t);
<a name="l00524"></a>00524         }
<a name="l00525"></a>00525 }
<a name="l00526"></a>00526 
<a name="l00527"></a>00527 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Ring, <span class="keyword">class</span> Element&gt;
<a name="l00528"></a><a class="code" href="polynomi_8h.html#f2825233f78e39db435891d165423709">00528</a> <span class="keywordtype">void</span> PrepareBulkPolynomialInterpolationAt(<span class="keyword">const</span> Ring &amp;ring, <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> *v, <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> &amp;position, <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> x[], <span class="keyword">const</span> <a class="code" href="class_ring_of_polynomials_over.html#5a9d435f7f8d004e1da6d46f16717704">Element</a> w[], <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
<a name="l00529"></a>00529 {
<a name="l00530"></a>00530         assert(n &gt; 0);
<a name="l00531"></a>00531 
<a name="l00532"></a>00532         std::vector&lt;Eleme