polynomi_8cpp-source.html

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

<a name="l00313"></a>00313         <span class="keywordflow">return</span> quotient;
<a name="l00314"></a>00314 }
<a name="l00315"></a>00315 
<a name="l00316"></a>00316 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00317"></a>00317 PolynomialOver&lt;T&gt; <a class="code" href="class_polynomial_over.html" title="represents single-variable polynomials over arbitrary rings">PolynomialOver&lt;T&gt;::Modulo</a>(<span class="keyword">const</span> PolynomialOver&lt;T&gt;&amp; t, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)<span class="keyword"> const</span>
<a name="l00318"></a>00318 <span class="keyword"></span>{
<a name="l00319"></a>00319         PolynomialOver&lt;T&gt; remainder, quotient;
<a name="l00320"></a>00320         <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...">Divide</a>(remainder, quotient, *<span class="keyword">this</span>, t, ring);
<a name="l00321"></a>00321         <span class="keywordflow">return</span> remainder;
<a name="l00322"></a>00322 }
<a name="l00323"></a>00323 
<a name="l00324"></a>00324 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00325"></a><a class="code" href="class_polynomial_over.html#1a24658cd38205e6a3edc607aaceedda">00325</a> PolynomialOver&lt;T&gt; <a class="code" href="class_polynomial_over.html#1a24658cd38205e6a3edc607aaceedda">PolynomialOver&lt;T&gt;::MultiplicativeInverse</a>(<span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)<span class="keyword"> const</span>
<a name="l00326"></a>00326 <span class="keyword"></span>{
<a name="l00327"></a>00327         <span class="keywordflow">return</span> <a class="code" href="class_polynomial_over.html#604beee6d397108b3334eaeb564b641a" title="the zero polynomial will return a degree of -1">Degree</a>(ring)==0 ? ring.MultiplicativeInverse(m_coefficients[0]) : ring.Identity();
<a name="l00328"></a>00328 }
<a name="l00329"></a>00329 
<a name="l00330"></a>00330 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00331"></a><a class="code" href="class_polynomial_over.html#bd97055ea77f4c511d84cbde55fee6a0">00331</a> <span class="keywordtype">bool</span> <a class="code" href="class_polynomial_over.html#bd97055ea77f4c511d84cbde55fee6a0">PolynomialOver&lt;T&gt;::IsUnit</a>(<span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)<span class="keyword"> const</span>
<a name="l00332"></a>00332 <span class="keyword"></span>{
<a name="l00333"></a>00333         <span class="keywordflow">return</span> <a class="code" href="class_polynomial_over.html#604beee6d397108b3334eaeb564b641a" title="the zero polynomial will return a degree of -1">Degree</a>(ring)==0 &amp;&amp; ring.IsUnit(m_coefficients[0]);
<a name="l00334"></a>00334 }
<a name="l00335"></a>00335 
<a name="l00336"></a>00336 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00337"></a><a class="code" href="class_polynomial_over.html#f2e687246fa4366712cc024e62c799a0">00337</a> std::istream&amp; <a class="code" href="class_polynomial_over.html#f2e687246fa4366712cc024e62c799a0">PolynomialOver&lt;T&gt;::Input</a>(std::istream &amp;in, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)
<a name="l00338"></a>00338 {
<a name="l00339"></a>00339         <span class="keywordtype">char</span> c;
<a name="l00340"></a>00340         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length = 0;
<a name="l00341"></a>00341         <a class="code" href="class_sec_block.html" title="a block of memory allocated using A">SecBlock&lt;char&gt;</a> str(length + 16);
<a name="l00342"></a>00342         <span class="keywordtype">bool</span> paren = <span class="keyword">false</span>;
<a name="l00343"></a>00343 
<a name="l00344"></a>00344         std::ws(in);
<a name="l00345"></a>00345 
<a name="l00346"></a>00346         <span class="keywordflow">if</span> (in.peek() == <span class="charliteral">'('</span>)
<a name="l00347"></a>00347         {
<a name="l00348"></a>00348                 paren = <span class="keyword">true</span>;
<a name="l00349"></a>00349                 in.get();
<a name="l00350"></a>00350         }
<a name="l00351"></a>00351 
<a name="l00352"></a>00352         <span class="keywordflow">do</span>
<a name="l00353"></a>00353         {
<a name="l00354"></a>00354                 in.read(&amp;c, 1);
<a name="l00355"></a>00355                 str[length++] = c;
<a name="l00356"></a>00356                 <span class="keywordflow">if</span> (length &gt;= str.<a class="code" href="class_sec_block.html#f5999bffe3193e62719cc0792b0282a7">size</a>())
<a name="l00357"></a>00357                         str.<a class="code" href="class_sec_block.html#8dea287fba8236b0979b52beece0ec1b" title="change size only if newSize &gt; current size. contents are preserved">Grow</a>(length + 16);
<a name="l00358"></a>00358         }
<a name="l00359"></a>00359         <span class="comment">// if we started with a left paren, then read until we find a right paren,</span>
<a name="l00360"></a>00360         <span class="comment">// otherwise read until the end of the line</span>
<a name="l00361"></a>00361         <span class="keywordflow">while</span> (in &amp;&amp; ((paren &amp;&amp; c != <span class="charliteral">')'</span>) || (!paren &amp;&amp; c != <span class="charliteral">'\n'</span>)));
<a name="l00362"></a>00362 
<a name="l00363"></a>00363         str[length-1] = <span class="charliteral">'\0'</span>;
<a name="l00364"></a>00364         *<span class="keyword">this</span> = PolynomialOver&lt;T&gt;(str, ring);
<a name="l00365"></a>00365 
<a name="l00366"></a>00366         <span class="keywordflow">return</span> in;
<a name="l00367"></a>00367 }
<a name="l00368"></a>00368 
<a name="l00369"></a>00369 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00370"></a><a class="code" href="class_polynomial_over.html#2c9b1f5f4bf5a748a1e811ea8b122d3c">00370</a> std::ostream&amp; <a class="code" href="class_polynomial_over.html#2c9b1f5f4bf5a748a1e811ea8b122d3c">PolynomialOver&lt;T&gt;::Output</a>(std::ostream &amp;out, <span class="keyword">const</span> <a class="code" href="class_polynomial_over.html#f87a6be38193e61c7aecb8c96510583e">Ring</a> &amp;ring)<span class="keyword"> const</span>
<a name="l00371"></a>00371 <span class="keyword"></span>{
<a name="l00372"></a>00372         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = <a class="code" href="class_polynomial_over.html#65c6004a42608f31008ff066f2eba3e2">CoefficientCount</a>(ring);
<a name="l00373"></a>00373         <span class="keywordflow">if</span> (i)
<a name="l00374"></a>00374         {
<a name="l00375"></a>00375                 <span class="keywordtype">bool</span> firstTerm = <span class="keyword">true</span>;
<a name="l00376"></a>00376 
<a name="l00377"></a>00377                 <span class="keywordflow">while</span> (i--)
<a name="l00378"></a>00378                 {
<a name="l00379"></a>00379                         <span class="keywordflow">if</span> (m_coefficients[i] != ring.Identity())
<a name="l00380"></a>00380                         {
<a name="l00381"></a>00381                                 <span class="keywordflow">if</span> (firstTerm)
<a name="l00382"></a>00382                                 {
<a name="l00383"></a>00383                                         firstTerm = <span class="keyword">false</span>;
<a name="l00384"></a>00384                                         <span class="keywordflow">if</span> (!i || !ring.Equal(m_coefficients[i], ring.MultiplicativeIdentity()))
<a name="l00385"></a>00385                                                 out &lt;&lt; m_coefficients[i];
<a name="l00386"></a>00386                                 }
<a name="l00387"></a>00387                                 <span class="keywordflow">else</span>
<a name="l00388"></a>00388                                 {
<a name="l00389"></a>00389                                         <a class="code" href="class_polynomial_over.html#2eb91afba2d1f0c11f78f5825ecd5408">CoefficientType</a> inverse = ring.Inverse(m_coefficients[i]);
<a name="l00390"></a>00390                                         std::ostringstream pstr, nstr;
<a name="l00391"></a>00391 
<a name="l00392"></a>00392                                         pstr &lt;&lt; m_coefficients[i];
<a name="l00393"></a>00393                                         nstr &lt;&lt; inverse;
<a name="l00394"></a>00394 
<a name="l00395"></a>00395                                         <span class="keywordflow">if</span> (pstr.str().size() &lt;= nstr.str().size())
<a name="l00396"></a>00396                                         {
<a name="l00397"></a>00397                                                 out &lt;&lt; <span class="stringliteral">" + "</span>; 
<a name="l00398"></a>00398                                                 <span class="keywordflow">if</span> (!i || !ring.Equal(m_coefficients[i], ring.MultiplicativeIdentity()))
<a name="l00399"></a>00399                                                         out &lt;&lt; m_coefficients[i];
<a name="l00400"></a>00400                                         }
<a name="l00401"></a>00401                                         <span class="keywordflow">else</span>
<a name="l00402"></a>00402                                         {
<a name="l00403"></a>00403                                                 out &lt;&lt; <span class="stringliteral">" - "</span>; 
<a name="l00404"></a>00404                                                 <span class="keywordflow">if</span> (!i || !ring.Equal(inverse, ring.MultiplicativeIdentity()))
<a name="l00405"></a>00405                                                         out &lt;&lt; inverse;
<a name="l00406"></a>00406                                         }
<a name="l00407"></a>00407                                 }
<a name="l00408"></a>00408 
<a name="l00409"></a>00409                                 <span class="keywordflow">switch</span> (i)
<a name="l00410"></a>00410                                 {
<a name="l00411"></a>00411                                 <span class="keywordflow">case</span> 0:
<a name="l00412"></a>00412                                         <span class="keywordflow">break</span>;
<a name="l00413"></a>00413                                 <span class="keywordflow">case</span> 1:
<a name="l00414"></a>00414                                         out &lt;&lt; <span class="stringliteral">"x"</span>;
<a name="l00415"></a>00415                                         <span class="keywordflow">break</span>;
<a name="l00416"></a>00416                                 <span class="keywordflow">default</span>:
<a name="l00417"></a>00417                                         out &lt;&lt; <span class="stringliteral">"x^"</span> &lt;&lt; i;
<a name="l00418"></a>00418                                 }
<a name="l00419"></a>00419                         }
<a name="l00420"></a>00420                 }
<a name="l00421"></a>00421         }
<a name="l00422"></a>00422         <span class="keywordflow">else</span>
<a name="l00423"></a>00423         {