gf2n_8cpp-source.html

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

00519                 u = u.<a class="code" href="class_polynomial_mod2.html#_polynomial_mod2z31_3">Squared</a>()%(*this);
00520                 <span class="keywordflow">if</span> (!<a class="code" href="class_polynomial_mod2.html#_polynomial_mod2z31_7">Gcd</a>(u+t, *<span class="keyword">this</span>).<a class="code" href="class_polynomial_mod2.html#_polynomial_mod2z31_4">IsUnit</a>())
00521                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00522         }
00523         <span class="keywordflow">return</span> <span class="keyword">true</span>;
00524 }
00525 
00526 <span class="comment">// ********************************************************</span>
00527 
00528 GF2NP::GF2NP(<span class="keyword">const</span> <a class="code" href="class_polynomial_mod2.html">PolynomialMod2</a> &amp;modulus)
00529         : <a class="code" href="class_quotient_ring.html">QuotientRing</a>&lt;<a class="code" href="class_euclidean_domain_of.html">EuclideanDomainOf</a>&lt;<a class="code" href="class_polynomial_mod2.html">PolynomialMod2</a>&gt; &gt;(<a class="code" href="class_euclidean_domain_of.html">EuclideanDomainOf</a>&lt;<a class="code" href="class_polynomial_mod2.html">PolynomialMod2</a>&gt;(), modulus), m(modulus.Degree()) 
00530 {
00531 }
00532 
00533 GF2NP::Element GF2NP::SquareRoot(<span class="keyword">const</span> Element &amp;a)<span class="keyword"> const</span>
00534 <span class="keyword"></span>{
00535         Element r = a;
00536         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=1; i&lt;m; i++)
00537                 r = <a class="code" href="class_square.html">Square</a>(r);
00538         <span class="keywordflow">return</span> r;
00539 }
00540 
00541 GF2NP::Element GF2NP::HalfTrace(<span class="keyword">const</span> Element &amp;a)<span class="keyword"> const</span>
00542 <span class="keyword"></span>{
00543         assert(m%2 == 1);
00544         Element h = a;
00545         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=1; i&lt;=(m-1)/2; i++)
00546                 h = Add(<a class="code" href="class_square.html">Square</a>(<a class="code" href="class_square.html">Square</a>(h)), a);
00547         <span class="keywordflow">return</span> h;
00548 }
00549 
00550 GF2NP::Element GF2NP::SolveQuadraticEquation(<span class="keyword">const</span> Element &amp;a)<span class="keyword"> const</span>
00551 <span class="keyword"></span>{
00552         <span class="keywordflow">if</span> (m%2 == 0)
00553         {
00554                 Element z, w;
00555                 <a class="code" href="class_random_pool.html">RandomPool</a> rng;
00556                 <span class="keywordflow">do</span>
00557                 {
00558                         Element p((<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;)rng, m);
00559                         z = PolynomialMod2::Zero();
00560                         w = p;
00561                         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=1; i&lt;=m-1; i++)
00562                         {
00563                                 w = <a class="code" href="class_square.html">Square</a>(w);
00564                                 z = Square(z);
00565                                 Accumulate(z, Multiply(w, a));
00566                                 Accumulate(w, p);
00567                         }
00568                 } <span class="keywordflow">while</span> (w.IsZero());
00569                 <span class="keywordflow">return</span> z;
00570         }
00571         <span class="keywordflow">else</span>
00572                 <span class="keywordflow">return</span> HalfTrace(a);
00573 }
00574 
00575 <span class="comment">// ********************************************************</span>
00576 
00577 GF2NT::GF2NT(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> t0, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> t1, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> t2)
00578         : <a class="code" href="class_g_f2_n_p.html">GF2NP</a>(<a class="code" href="class_polynomial_mod2.html">PolynomialMod2</a>::Trinomial(t0, t1, t2))
00579         , t0(t0), t1(t1)
00580         , result((word)0, m)
00581 {
00582         assert(t0 &gt; t1 &amp;&amp; t1 &gt; t2 &amp;&amp; t2==0);
00583 }
00584 
00585 <span class="keyword">const</span> GF2NT::Element&amp; GF2NT::MultiplicativeInverse(<span class="keyword">const</span> Element &amp;a)<span class="keyword"> const</span>
00586 <span class="keyword"></span>{
00587         <span class="keywordflow">if</span> (t0-t1 &lt; WORD_BITS)
00588                 <span class="keywordflow">return</span> GF2NP::MultiplicativeInverse(a);
00589 
00590         <a class="code" href="class_sec_block.html">SecWordBlock</a> T(m_modulus.reg.size() * 4);
00591         word *b = T;
00592         word *c = T+m_modulus.reg.size();
00593         word *f = T+2*m_modulus.reg.size();
00594         word *g = T+3*m_modulus.reg.size();
00595         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bcLen=1, fgLen=m_modulus.reg.size();
00596         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k=0;
00597 
00598         SetWords(T, 0, 3*m_modulus.reg.size());
00599         b[0]=1;
00600         assert(a.reg.size() &lt;= m_modulus.reg.size());
00601         CopyWords(f, a.reg, a.reg.size());
00602         CopyWords(g, m_modulus.reg, m_modulus.reg.size());
00603 
00604         <span class="keywordflow">while</span> (1)
00605         {
00606                 word t=f[0];
00607                 <span class="keywordflow">while</span> (!t)
00608                 {
00609                         ShiftWordsRightByWords(f, fgLen, 1);
00610                         <span class="keywordflow">if</span> (c[bcLen-1])
00611                                 bcLen++;
00612                         assert(bcLen &lt;= m_modulus.reg.size());
00613                         ShiftWordsLeftByWords(c, bcLen, 1);
00614                         k+=WORD_BITS;
00615                         t=f[0];
00616                 }
00617 
00618                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
00619                 <span class="keywordflow">while</span> (t%2 == 0)
00620                 {
00621                         t&gt;&gt;=1;
00622                         i++;
00623                 }
00624                 k+=i;
00625 
00626                 <span class="keywordflow">if</span> (t==1 &amp;&amp; CountWords(f, fgLen)==1)
00627                         <span class="keywordflow">break</span>;
00628 
00629                 <span class="keywordflow">if</span> (i==1)
00630                 {
00631                         ShiftWordsRightByBits(f, fgLen, 1);
00632                         t=ShiftWordsLeftByBits(c, bcLen, 1);
00633                 }
00634                 <span class="keywordflow">else</span>
00635                 {
00636                         ShiftWordsRightByBits(f, fgLen, i);
00637                         t=ShiftWordsLeftByBits(c, bcLen, i);
00638                 }
00639                 <span class="keywordflow">if</span> (t)
00640                 {
00641                         c[bcLen] = t;
00642                         bcLen++;
00643                         assert(bcLen &lt;= m_modulus.reg.size());
00644                 }
00645 
00646                 <span class="keywordflow">if</span> (f[fgLen-1]==0 &amp;&amp; g[fgLen-1]==0)
00647                         fgLen--;
00648 
00649                 <span class="keywordflow">if</span> (f[fgLen-1] &lt; g[fgLen-1])
00650                 {
00651                         std::swap(f, g);
00652                         std::swap(b, c);
00653                 }
00654 
00655                 XorWords(f, g, fgLen);
00656                 XorWords(b, c, bcLen);
00657         }
00658 
00659         <span class="keywordflow">while</span> (k &gt;= WORD_BITS)
00660         {
00661                 word temp = b[0];
00662                 <span class="comment">// right shift b</span>
00663                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i+1&lt;BitsToWords(m); i++)
00664                         b[i] = b[i+1];
00665                 b[BitsToWords(m)-1] = 0;
00666 
00667                 <span class="keywordflow">if</span> (t1 &lt; WORD_BITS)
00668                         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;WORD_BITS-t1; j++)
00669                                 temp ^= ((temp &gt;&gt; j) &amp; 1) &lt;&lt; (t1 + j);
00670                 <span class="keywordflow">else</span>
00671                         b[t1/WORD_BITS-1] ^= temp &lt;&lt; t1%WORD_BITS;
00672 
00673                 <span class="keywordflow">if</span> (t1 % WORD_BITS)
00674                         b[t1/WORD_BITS] ^= temp &gt;&gt; (WORD_BITS - t1%WORD_BITS);
00675 
00676                 <span class="keywordflow">if</span> (t0%WORD_BITS)
00677                 {
00678                         b[t0/WORD_BITS-1] ^= temp &lt;&lt; t0%WORD_BITS;
00679                         b[t0/WORD_BITS] ^= temp &gt;&gt; (WORD_BITS - t0%WORD_BITS);
00680                 }
00681                 <span class="keywordflow">else</span>
00682                         b[t0/WORD_BITS-1] ^= temp;
00683 
00684                 k -= WORD_BITS;
00685         }
00686 
00687         <span class="keywordflow">if</span> (k)
00688         {
00689                 word temp = b[0] &lt;&lt; (WORD_BITS - k);
00690                 ShiftWordsRightByBits(b, BitsToWords(m), k);
00691 
00692                 <span class="keywordflow">if</span> (t1 &lt; WORD_BITS)
00693                         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j&lt;WORD_BITS-t1; j++)