nbtheory_8cpp-source.html

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

00597 {
00598         <span class="keywordflow">if</span> (p%4 == 3)
00599                 <span class="keywordflow">return</span> a_exp_b_mod_c(a, (p+1)/4, p);
00600 
00601         Integer q=p-1;
00602         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> r=0;
00603         <span class="keywordflow">while</span> (q.<a class="code" href="class_integer.html#_integerz41_14">IsEven</a>())
00604         {
00605                 r++;
00606                 q &gt;&gt;= 1;
00607         }
00608 
00609         Integer n=2;
00610         <span class="keywordflow">while</span> (Jacobi(n, p) != -1)
00611                 ++n;
00612 
00613         Integer y = a_exp_b_mod_c(n, q, p);
00614         Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
00615         Integer b = (x.Squared()%p)*a%p;
00616         x = a*x%p;
00617         Integer tempb, t;
00618 
00619         <span class="keywordflow">while</span> (b != 1)
00620         {
00621                 <span class="keywordtype">unsigned</span> m=0;
00622                 tempb = b;
00623                 <span class="keywordflow">do</span>
00624                 {
00625                         m++;
00626                         b = b.Squared()%p;
00627                         <span class="keywordflow">if</span> (m==r)
00628                                 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz37_10">Integer::Zero</a>();
00629                 }
00630                 <span class="keywordflow">while</span> (b != 1);
00631 
00632                 t = y;
00633                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i&lt;r-m-1; i++)
00634                         t = t.Squared()%p;
00635                 y = t.Squared()%p;
00636                 r = m;
00637                 x = x*t%p;
00638                 b = tempb*y%p;
00639         }
00640 
00641         assert(x.Squared()%p == a);
00642         <span class="keywordflow">return</span> x;
00643 }
00644 
00645 <span class="keywordtype">bool</span> SolveModularQuadraticEquation(Integer &amp;r1, Integer &amp;r2, <span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;b, <span class="keyword">const</span> Integer &amp;c, <span class="keyword">const</span> Integer &amp;p)
00646 {
00647         Integer D = (b.Squared() - 4*a*c) % p;
00648         <span class="keywordflow">switch</span> (Jacobi(D, p))
00649         {
00650         <span class="keywordflow">default</span>:
00651                 assert(<span class="keyword">false</span>);  <span class="comment">// not reached</span>
00652                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00653         <span class="keywordflow">case</span> -1:
00654                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00655         <span class="keywordflow">case</span> 0:
00656                 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
00657                 assert(((r1.<a class="code" href="class_integer.html#_integerz49_2">Squared</a>()*a + r1*b + c) % p).IsZero());
00658                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00659         <span class="keywordflow">case</span> 1:
00660                 Integer s = ModularSquareRoot(D, p);
00661                 Integer t = (a+a).InverseMod(p);
00662                 r1 = (s-b)*t % p;
00663                 r2 = (-s-b)*t % p;
00664                 assert(((r1.<a class="code" href="class_integer.html#_integerz49_2">Squared</a>()*a + r1*b + c) % p).IsZero());
00665                 assert(((r2.Squared()*a + r2*b + c) % p).IsZero());
00666                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00667         }
00668 }
00669 
00670 Integer ModularRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;dp, <span class="keyword">const</span> Integer &amp;dq,
00671                                         <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q, <span class="keyword">const</span> Integer &amp;u)
00672 {
00673         Integer p2 = ModularExponentiation((a % p), dp, p);
00674         Integer q2 = ModularExponentiation((a % q), dq, q);
00675         <span class="keywordflow">return</span> CRT(p2, p, q2, q, u);
00676 }
00677 
00678 Integer ModularRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;e,
00679                                         <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q)
00680 {
00681         Integer dp = EuclideanMultiplicativeInverse(e, p-1);
00682         Integer dq = EuclideanMultiplicativeInverse(e, q-1);
00683         Integer u = EuclideanMultiplicativeInverse(p, q);
00684         assert(!!dp &amp;&amp; !!dq &amp;&amp; !!u);
00685         <span class="keywordflow">return</span> ModularRoot(a, dp, dq, p, q, u);
00686 }
00687 
00688 <span class="comment">/*</span>
00689 <span class="comment">Integer GCDI(const Integer &amp;x, const Integer &amp;y)</span>
00690 <span class="comment">{</span>
00691 <span class="comment">        Integer a=x, b=y;</span>
00692 <span class="comment">        unsigned k=0;</span>
00693 <span class="comment"></span>
00694 <span class="comment">        assert(!!a &amp;&amp; !!b);</span>
00695 <span class="comment"></span>
00696 <span class="comment">        while (a[0]==0 &amp;&amp; b[0]==0)</span>
00697 <span class="comment">        {</span>
00698 <span class="comment">                a &gt;&gt;= 1;</span>
00699 <span class="comment">                b &gt;&gt;= 1;</span>
00700 <span class="comment">                k++;</span>
00701 <span class="comment">        }</span>
00702 <span class="comment"></span>
00703 <span class="comment">        while (a[0]==0)</span>
00704 <span class="comment">                a &gt;&gt;= 1;</span>
00705 <span class="comment"></span>
00706 <span class="comment">        while (b[0]==0)</span>
00707 <span class="comment">                b &gt;&gt;= 1;</span>
00708 <span class="comment"></span>
00709 <span class="comment">        while (1)</span>
00710 <span class="comment">        {</span>
00711 <span class="comment">                switch (a.Compare(b))</span>
00712 <span class="comment">                {</span>
00713 <span class="comment">                        case -1:</span>
00714 <span class="comment">                                b -= a;</span>
00715 <span class="comment">                                while (b[0]==0)</span>
00716 <span class="comment">                                        b &gt;&gt;= 1;</span>
00717 <span class="comment">                                break;</span>
00718 <span class="comment"></span>
00719 <span class="comment">                        case 0:</span>
00720 <span class="comment">                                return (a &lt;&lt;= k);</span>
00721 <span class="comment"></span>
00722 <span class="comment">                        case 1:</span>
00723 <span class="comment">                                a -= b;</span>
00724 <span class="comment">                                while (a[0]==0)</span>
00725 <span class="comment">                                        a &gt;&gt;= 1;</span>
00726 <span class="comment">                                break;</span>
00727 <span class="comment"></span>
00728 <span class="comment">                        default:</span>
00729 <span class="comment">                                assert(false);</span>
00730 <span class="comment">                }</span>
00731 <span class="comment">        }</span>
00732 <span class="comment">}</span>
00733 <span class="comment"></span>
00734 <span class="comment">Integer EuclideanMultiplicativeInverse(const Integer &amp;a, const Integer &amp;b)</span>
00735 <span class="comment">{</span>
00736 <span class="comment">        assert(b.Positive());</span>
00737 <span class="comment"></span>
00738 <span class="comment">        if (a.Negative())</span>
00739 <span class="comment">                return EuclideanMultiplicativeInverse(a%b, b);</span>
00740 <span class="comment"></span>
00741 <span class="comment">        if (b[0]==0)</span>
00742 <span class="comment">        {</span>
00743 <span class="comment">                if (!b || a[0]==0)</span>
00744 <span class="comment">                        return Integer::Zero();       // no inverse</span>
00745 <span class="comment">                if (a==1)</span>
00746 <span class="comment">                        return 1;</span>
00747 <span class="comment">                Integer u = EuclideanMultiplicativeInverse(b, a);</span>
00748 <span class="comment">                if (!u)</span>
00749 <span class="comment">                        return Integer::Zero();       // no inverse</span>
00750 <span class="comment">                else</span>
00751 <span class="comment">                        return (b*(a-u)+1)/a;</span>
00752 <span class="comment">        }</span>
00753 <span class="comment"></span>
00754 <span class="comment">        Integer u=1, d=a, v1=b, v3=b, t1, t3, b2=(b+1)&gt;&gt;1;</span>
00755 <span class="comment"></span>
00756 <span class="comment">        if (a[0])</span>
00757 <span class="comment">        {</span>
00758 <span class="comment">                t1 = Integer::Zero();</span>
00759 <span class="comment">                t3 = -b;</span>
00760 <span class="comment">        }</span>
00761 <span class="comment">        else</span>
00762 <span class="comment">        {</span>
00763 <span class="comment">                t1 = b2;</span>
00764 <span class="comment">                t3 = a&gt;&gt;1;</span>
00765 <span class="comment">        }</span>
00766 <span class="comment"></span>
00767 <span class="comment">        while (!!t3)</span>
00768 <span class="comment">        {</span>
00769 <span class="comment">                while (t3[0]==0)</span>
00770 <span class="comment">                {</span>
00771 <span class="comment">                        t3 &gt;&gt;= 1;</span>
00772 <span class="comment">                        if (t1[0]==0)</span>
00773 <span class="comment">                                t1 &gt;&gt;= 1;</span>
00774 <span class="comment">                        else</span>
00775 <span class="comment">                        {</span>
00776 <span class="comment">                                t1 &gt;&gt;= 1;</span>
00777 <span class="comment">                                t1 += b2;</span>
00778 <span class="comment">                        }</span>
00779 <span class="comment">                }</span>
00780 <span class="comment">                if (t3.Positive())</span>
00781 <span class="comment">                {</span>
00782 <span class="comment">                        u = t1;</span>
00783 <span class="comment">                        d = t3;</span>
00784 <span class="comment">                }</span>
00785 <span class="comment">                else</span>
00786 <span class="comment">                {</span>
00787 <span class="comment">                        v1 = b-t1;</span>
00788 <span class="comment">                        v3 = -t3;</span>
00789 <span class="comment">                }</span>
00790 <span class="comment">                t1 = u-v1;</span>
00791 <span class="comment">                t3 = d-v3;</span>
00792 <span class="comment">                if (t1.Negative())</span>
00793 <span class="comment">                        t1 += b;</span>
00794 <span class="comment">        }</span>
00795 <span class="comment">        if (d==1)</span>
00796 <span class="comment">                return u;</span>
00797 <span class="comment">        else</span>