📄 algebra_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>Crypto++: algebra.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.2 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Compound List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Compound Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>algebra.cpp</h1><div class="fragment"><pre>00001 <span class="comment">// algebra.cpp - written and placed in the public domain by Wei Dai</span>00002 00003 <span class="preprocessor">#include "pch.h"</span>00004 00005 <span class="preprocessor">#include "algebra.h"</span>00006 <span class="preprocessor">#include "<a class="code" href="integer_8h.html">integer.h</a>"</span>00007 00008 <span class="preprocessor">#include <vector></span>00009 00010 NAMESPACE_BEGIN(CryptoPP)00011 00012 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_group.html">AbstractGroup<T>::Double</a>(<span class="keyword">const</span> Element &a)<span class="keyword"> const</span>00013 <span class="keyword"></span>{00014 <span class="keywordflow">return</span> Add(a, a);00015 }00016 00017 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_group.html">AbstractGroup<T>::Subtract</a>(<span class="keyword">const</span> Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00018 <span class="keyword"></span>{00019 <span class="comment">// make copy of a in case Inverse() overwrites it</span>00020 Element a1(a);00021 <span class="keywordflow">return</span> Add(a1, Inverse(b));00022 }00023 00024 <span class="keyword">template</span> <<span class="keyword">class</span> T> T& <a class="code" href="class_abstract_group.html">AbstractGroup<T>::Accumulate</a>(Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00025 <span class="keyword"></span>{00026 <span class="keywordflow">return</span> a = Add(a, b);00027 }00028 00029 <span class="keyword">template</span> <<span class="keyword">class</span> T> T& <a class="code" href="class_abstract_group.html">AbstractGroup<T>::Reduce</a>(Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00030 <span class="keyword"></span>{00031 <span class="keywordflow">return</span> a = Subtract(a, b);00032 }00033 00034 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_ring.html">AbstractRing<T>::Square</a>(<span class="keyword">const</span> Element &a)<span class="keyword"> const</span>00035 <span class="keyword"></span>{00036 <span class="keywordflow">return</span> Multiply(a, a);00037 }00038 00039 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_ring.html">AbstractRing<T>::Divide</a>(<span class="keyword">const</span> Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00040 <span class="keyword"></span>{00041 <span class="comment">// make copy of a in case MultiplicativeInverse() overwrites it</span>00042 Element a1(a);00043 <span class="keywordflow">return</span> Multiply(a1, MultiplicativeInverse(b));00044 }00045 00046 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_euclidean_domain.html">AbstractEuclideanDomain<T>::Mod</a>(<span class="keyword">const</span> Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00047 <span class="keyword"></span>{00048 Element q;00049 DivisionAlgorithm(result, q, a, b);00050 <span class="keywordflow">return</span> result;00051 }00052 00053 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> T& <a class="code" href="class_abstract_euclidean_domain.html">AbstractEuclideanDomain<T>::Gcd</a>(<span class="keyword">const</span> Element &a, <span class="keyword">const</span> Element &b)<span class="keyword"> const</span>00054 <span class="keyword"></span>{00055 Element g[3]={b, a};00056 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i0=0, i1=1, i2=2;00057 00058 <span class="keywordflow">while</span> (!Equal(g[i1], Identity()))00059 {00060 g[i2] = Mod(g[i0], g[i1]);00061 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> t = i0; i0 = i1; i1 = i2; i2 = t;00062 }00063 00064 <span class="keywordflow">return</span> result = g[i0];00065 }00066 00067 <span class="keyword">template</span> <<span class="keyword">class</span> T> <span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="class_quotient_ring.html">QuotientRing<T></a>::Element& <a class="code" href="class_quotient_ring.html">QuotientRing<T>::MultiplicativeInverse</a>(<span class="keyword">const</span> Element &a)<span class="keyword"> const</span>00068 <span class="keyword"></span>{00069 Element g[3]={m_modulus, a};00070 <span class="preprocessor">#ifdef __BCPLUSPLUS__</span>00071 <span class="preprocessor"></span> <span class="comment">// BC++50 workaround </span>00072 Element v[3];00073 v[0]=m_domain.Identity();00074 v[1]=m_domain.MultiplicativeIdentity();00075 <span class="preprocessor">#else</span>00076 <span class="preprocessor"></span> Element v[3]={m_domain.Identity(), m_domain.MultiplicativeIdentity()};00077 <span class="preprocessor">#endif</span>00078 <span class="preprocessor"></span> Element y;00079 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i0=0, i1=1, i2=2;00080 00081 <span class="keywordflow">while</span> (!Equal(g[i1], Identity()))00082 {00083 <span class="comment">// y = g[i0] / g[i1];</span>00084 <span class="comment">// g[i2] = g[i0] % g[i1];</span>00085 m_domain.DivisionAlgorithm(g[i2], y, g[i0], g[i1]);00086 <span class="comment">// v[i2] = v[i0] - (v[i1] * y);</span>00087 v[i2] = m_domain.Subtract(v[i0], m_domain.Multiply(v[i1], y));00088 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> t = i0; i0 = i1; i1 = i2; i2 = t;00089 }00090 00091 <span class="keywordflow">return</span> m_domain.IsUnit(g[i0]) ? m_domain.Divide(v[i0], g[i0]) : m_domain.Identity();00092 }00093 00094 <span class="keyword">template</span> <<span class="keyword">class</span> T> T <a class="code" href="class_abstract_group.html">AbstractGroup<T>::ScalarMultiply</a>(<span class="keyword">const</span> Element &base, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &exponent)<span class="keyword"> const</span>00095 <span class="keyword"></span>{00096 Element result;00097 SimultaneousMultiply(&result, base, &exponent, 1);00098 <span class="keywordflow">return</span> result;00099 }00100 00101 <span class="keyword">template</span> <<span class="keyword">class</span> T> T <a class="code" href="class_abstract_group.html">AbstractGroup<T>::CascadeScalarMultiply</a>(<span class="keyword">const</span> Element &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e1, <span class="keyword">const</span> Element &y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e2)<span class="keyword"> const</span>00102 <span class="keyword"></span>{00103 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> expLen = STDMAX(e1.<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>(), e2.<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>());00104 <span class="keywordflow">if</span> (expLen==0)00105 <span class="keywordflow">return</span> Identity();00106 00107 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));00108 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> tableSize = 1<<w;00109 std::vector<Element> powerTable(tableSize << w);00110 00111 powerTable[1] = x;00112 powerTable[tableSize] = y;00113 <span class="keywordflow">if</span> (w==1)00114 powerTable[3] = Add(x,y);00115 <span class="keywordflow">else</span>00116 {00117 powerTable[2] = Double(x);00118 powerTable[2*tableSize] = Double(y);00119 00120 <span class="keywordtype">unsigned</span> i, j;00121 00122 <span class="keywordflow">for</span> (i=3; i<tableSize; i+=2)00123 powerTable[i] = Add(powerTable[i-2], powerTable[2]);00124 <span class="keywordflow">for</span> (i=1; i<tableSize; i+=2)00125 <span class="keywordflow">for</span> (j=i+tableSize; j<(tableSize<<w); j+=tableSize)00126 powerTable[j] = Add(powerTable[j-tableSize], y);00127 00128 <span class="keywordflow">for</span> (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)00129 powerTable[i] = Add(powerTable[i-2*tableSize], powerTable[2*tableSize]);00130 <span class="keywordflow">for</span> (i=tableSize; i<(tableSize<<w); i+=2*tableSize)00131 <span class="keywordflow">for</span> (j=i+2; j<i+tableSize; j+=2)00132 powerTable[j] = Add(powerTable[j-1], x);00133 }00134 00135 Element result;00136 <span class="keywordtype">unsigned</span> power1 = 0, power2 = 0, prevPosition = expLen-1;00137 <span class="keywordtype">bool</span> firstTime = <span class="keyword">true</span>;00138 00139 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = expLen-1; i>=0; i--)00140 {00141 power1 = 2*power1 + e1.<a class="code" href="class_integer.html#_integerz41_5">GetBit</a>(i);00142 power2 = 2*power2 + e2.<a class="code" href="class_integer.html#_integerz41_5">GetBit</a>(i);00143 00144 <span class="keywordflow">if</span> (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)00145 {00146 <span class="keywordtype">unsigned</span> squaresBefore = prevPosition-i;00147 <span class="keywordtype">unsigned</span> squaresAfter = 0;00148 prevPosition = i;00149 <span class="keywordflow">while</span> ((power1 || power2) && power1%2 == 0 && power2%2==0)00150 {00151 power1 /= 2;00152 power2 /= 2;00153 squaresBefore--;00154 squaresAfter++;00155 }00156 <span class="keywordflow">if</span> (firstTime)00157 {00158 result = powerTable[(power2<<w) + power1];00159 firstTime = <span class="keyword">false</span>;00160 }00161 <span class="keywordflow">else</span>00162 {00163 <span class="keywordflow">while</span> (squaresBefore--)00164 result = Double(result);00165 <span class="keywordflow">if</span> (power1 || power2)00166 Accumulate(result, powerTable[(power2<<w) + power1]);00167 }00168 <span class="keywordflow">while</span> (squaresAfter--)00169 result = Double(result);00170 power1 = power2 = 0;00171 }⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -