nbtheory_8cpp-source.html

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

00798 <span class="comment">                return Integer::Zero();   // no inverse</span>
00799 <span class="comment">}</span>
00800 <span class="comment">*/</span>
00801 
00802 <span class="keywordtype">int</span> Jacobi(<span class="keyword">const</span> Integer &amp;aIn, <span class="keyword">const</span> Integer &amp;bIn)
00803 {
00804         assert(bIn.<a class="code" href="class_integer.html#_integerz41_15">IsOdd</a>());
00805 
00806         Integer b = bIn, a = aIn%bIn;
00807         <span class="keywordtype">int</span> result = 1;
00808 
00809         <span class="keywordflow">while</span> (!!a)
00810         {
00811                 <span class="keywordtype">unsigned</span> i=0;
00812                 <span class="keywordflow">while</span> (a.GetBit(i)==0)
00813                         i++;
00814                 a&gt;&gt;=i;
00815 
00816                 <span class="keywordflow">if</span> (i%2==1 &amp;&amp; (b%8==3 || b%8==5))
00817                         result = -result;
00818 
00819                 <span class="keywordflow">if</span> (a%4==3 &amp;&amp; b%4==3)
00820                         result = -result;
00821 
00822                 std::swap(a, b);
00823                 a %= b;
00824         }
00825 
00826         <span class="keywordflow">return</span> (b==1) ? result : 0;
00827 }
00828 
00829 Integer Lucas(<span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;pIn, <span class="keyword">const</span> Integer &amp;n)
00830 {
00831         <span class="keywordtype">unsigned</span> i = e.BitCount();
00832         <span class="keywordflow">if</span> (i==0)
00833                 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz37_12">Integer::Two</a>();
00834 
00835         <a class="code" href="class_montgomery_representation.html">MontgomeryRepresentation</a> m(n);
00836         Integer p=m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa3">ConvertIn</a>(pIn%n), two=m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa3">ConvertIn</a>(Integer::Two());
00837         Integer v=p, v1=m.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa7">Square</a>(p), two);
00838 
00839         i--;
00840         <span class="keywordflow">while</span> (i--)
00841         {
00842                 <span class="keywordflow">if</span> (e.GetBit(i))
00843                 {
00844                         <span class="comment">// v = (v*v1 - p) % m;</span>
00845                         v = m.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa6">Multiply</a>(v,v1), p);
00846                         <span class="comment">// v1 = (v1*v1 - 2) % m;</span>
00847                         v1 = m.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa7">Square</a>(v1), two);
00848                 }
00849                 <span class="keywordflow">else</span>
00850                 {
00851                         <span class="comment">// v1 = (v*v1 - p) % m;</span>
00852                         v1 = m.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa6">Multiply</a>(v,v1), p);
00853                         <span class="comment">// v = (v*v - 2) % m;</span>
00854                         v = m.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa7">Square</a>(v), two);
00855                 }
00856         }
00857         <span class="keywordflow">return</span> m.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa4">ConvertOut</a>(v);
00858 }
00859 
00860 <span class="comment">// This is Peter Montgomery's unpublished Lucas sequence evalutation algorithm.</span>
00861 <span class="comment">// The total number of multiplies and squares used is less than the binary</span>
00862 <span class="comment">// algorithm (see above).  Unfortunately I can't get it to run as fast as</span>
00863 <span class="comment">// the binary algorithm because of the extra overhead.</span>
00864 <span class="comment">/*</span>
00865 <span class="comment">Integer Lucas(const Integer &amp;n, const Integer &amp;P, const Integer &amp;modulus)</span>
00866 <span class="comment">{</span>
00867 <span class="comment">        if (!n)</span>
00868 <span class="comment">                return 2;</span>
00869 <span class="comment"></span>
00870 <span class="comment">#define f(A, B, C)      m.Subtract(m.Multiply(A, B), C)</span>
00871 <span class="comment">#define X2(A) m.Subtract(m.Square(A), two)</span>
00872 <span class="comment">#define X3(A) m.Multiply(A, m.Subtract(m.Square(A), three))</span>
00873 <span class="comment"></span>
00874 <span class="comment">        MontgomeryRepresentation m(modulus);</span>
00875 <span class="comment">        Integer two=m.ConvertIn(2), three=m.ConvertIn(3);</span>
00876 <span class="comment">        Integer A=m.ConvertIn(P), B, C, p, d=n, e, r, t, T, U;</span>
00877 <span class="comment"></span>
00878 <span class="comment">        while (d!=1)</span>
00879 <span class="comment">        {</span>
00880 <span class="comment">                p = d;</span>
00881 <span class="comment">                unsigned int b = WORD_BITS * p.WordCount();</span>
00882 <span class="comment">                Integer alpha = (Integer(5)&lt;&lt;(2*b-2)).SquareRoot() - Integer::Power2(b-1);</span>
00883 <span class="comment">                r = (p*alpha)&gt;&gt;b;</span>
00884 <span class="comment">                e = d-r;</span>
00885 <span class="comment">                B = A;</span>
00886 <span class="comment">                C = two;</span>
00887 <span class="comment">                d = r;</span>
00888 <span class="comment"></span>
00889 <span class="comment">                while (d!=e)</span>
00890 <span class="comment">                {</span>
00891 <span class="comment">                        if (d&lt;e)</span>
00892 <span class="comment">                        {</span>
00893 <span class="comment">                                swap(d, e);</span>
00894 <span class="comment">                                swap(A, B);</span>
00895 <span class="comment">                        }</span>
00896 <span class="comment"></span>
00897 <span class="comment">                        unsigned int dm2 = d[0], em2 = e[0];</span>
00898 <span class="comment">                        unsigned int dm3 = d%3, em3 = e%3;</span>
00899 <span class="comment"></span>
00900 <span class="comment">//                      if ((dm6+em6)%3 == 0 &amp;&amp; d &lt;= e + (e&gt;&gt;2))</span>
00901 <span class="comment">                        if ((dm3+em3==0 || dm3+em3==3) &amp;&amp; (t = e, t &gt;&gt;= 2, t += e, d &lt;= t))</span>
00902 <span class="comment">                        {</span>
00903 <span class="comment">                                // #1</span>
00904 <span class="comment">//                              t = (d+d-e)/3;</span>
00905 <span class="comment">//                              t = d; t += d; t -= e; t /= 3;</span>
00906 <span class="comment">//                              e = (e+e-d)/3;</span>
00907 <span class="comment">//                              e += e; e -= d; e /= 3;</span>
00908 <span class="comment">//                              d = t;</span>
00909 <span class="comment"></span>
00910 <span class="comment">//                              t = (d+e)/3</span>
00911 <span class="comment">                                t = d; t += e; t /= 3;</span>
00912 <span class="comment">                                e -= t;</span>
00913 <span class="comment">                                d -= t;</span>
00914 <span class="comment"></span>
00915 <span class="comment">                                T = f(A, B, C);</span>
00916 <span class="comment">                                U = f(T, A, B);</span>
00917 <span class="comment">                                B = f(T, B, A);</span>
00918 <span class="comment">                                A = U;</span>
00919 <span class="comment">                                continue;</span>
00920 <span class="comment">                        }</span>
00921 <span class="comment"></span>
00922 <span class="comment">//                      if (dm6 == em6 &amp;&amp; d &lt;= e + (e&gt;&gt;2))</span>
00923 <span class="comment">                        if (dm3 == em3 &amp;&amp; dm2 == em2 &amp;&amp; (t = e, t &gt;&gt;= 2, t += e, d &lt;= t))</span>
00924 <span class="comment">                        {</span>
00925 <span class="comment">                                // #2</span>
00926 <span class="comment">//                              d = (d-e)&gt;&gt;1;</span>
00927 <span class="comment">                                d -= e; d &gt;&gt;= 1;</span>
00928 <span class="comment">                                B = f(A, B, C);</span>
00929 <span class="comment">                                A = X2(A);</span>
00930 <span class="comment">                                continue;</span>
00931 <span class="comment">                        }</span>
00932 <span class="comment"></span>
00933 <span class="comment">//                      if (d &lt;= (e&lt;&lt;2))</span>
00934 <span class="comment">                        if (d &lt;= (t = e, t &lt;&lt;= 2))</span>
00935 <span class="comment">                        {</span>
00936 <span class="comment">                                // #3</span>
00937 <span class="comment">                                d -= e;</span>
00938 <span class="comment">                                C = f(A, B, C);</span>
00939 <span class="comment">                                swap(B, C);</span>
00940 <span class="comment">                                continue;</span>
00941 <span class="comment">                        }</span>
00942 <span class="comment"></span>
00943 <span class="comment">                        if (dm2 == em2)</span>
00944 <span class="comment">                        {</span>
00945 <span class="comment">                                // #4</span>
00946 <span class="comment">//                              d = (d-e)&gt;&gt;1;</span>
00947 <span class="comment">                                d -= e; d &gt;&gt;= 1;</span>
00948 <span class="comment">                                B = f(A, B, C);</span>
00949 <span class="comment">                                A = X2(A);</span>
00950 <span class="comment">                                continue;</span>
00951 <span class="comment">                        }</span>
00952 <span class="comment"></span>
00953 <span class="comment">                        if (dm2 == 0)</span>
00954 <span class="comment">                        {</span>
00955 <span class="comment">                                // #5</span>
00956 <span class="comment">                                d &gt;&gt;= 1;</span>
00957 <span class="comment">                                C = f(A, C, B);</span>
00958 <span class="comment">                                A = X2(A);</span>
00959 <span class="comment">                                continue;</span>
00960 <span class="comment">                        }</span>
00961 <span class="comment"></span>
00962 <span class="comment">                        if (dm3 == 0)</span>
00963 <span class="comment">                        {</span>
00964 <span class="comment">                                // #6</span>
00965 <span class="comment">//                              d = d/3 - e;</span>
00966 <span class="comment">                                d /= 3; d -= e;</span>
00967 <span class="comment">                                T = X2(A);</span>
00968 <span class="comment">                                C = f(T, f(A, B, C), C);</span>
00969 <span class="comment">                                swap(B, C);</span>
00970 <span class="comment">                                A = f(T, A, A);</span>
00971 <span class="comment">                                continue;</span>
00972 <span class="comment">                        }</span>
00973 <span class="comment"></span>
00974 <span class="comment">                        if (dm3+em3==0 || dm3+em3==3)</span>
00975 <span class="comment">                        {</span>
00976 <span class="comment">                                // #7</span>
00977 <span class="comment">//                              d = (d-e-e)/3;</span>
00978 <span class="comment">                                d -= e; d -= e; d /= 3;</span>
00979 <span class="comment">                                T = f(A, B, C);</span>
00980 <span class="comment">                                B = f(T, A, B);</span>
00981 <span class="comment">                                A = X3(A);</span>
00982 <span class="comment">                                continue;</span>
00983 <span class="comment">                        }</span>
00984 <span class="comment"></span>
00985 <span class="comment">                        if (dm3 == em3)</span>
00986 <span class="comment">                        {</span>
00987 <span class="comment">                                // #8</span>
00988 <span class="comment">//                              d = (d-e)/3;</span>
00989 <span class="comment">                                d -= e; d /= 3;</span>
00990 <span class="comment">                                T = f(A, B, C);</span>
00991 <span class="comment">                                C = f(A, C, B);</span>
00992 <span class="comment">                                B = T;</span>
00993 <span class="comment">                                A = X3(A);</span>
00994 <span class="comment">                                continue;</span>
00995 <span class="comment">                        }</span>
00996 <span class="comment"></s