我正在尝试在 GF(2^8) 中实现有效的乘法,这些元素最自然地以 numpy-thonic 方式表示为 uint8-numpy-values。因此,我实现了 GF-Arithmetics(在纯 Python 中,而不是 numpy 中)以构建 log-antilog-tables(我使用了一个随机生成器,9);特别是,我实现了一个(非numpy)Python-Function multGF
,它实现了GF-Multiplication,效果很好但速度很慢(因为它使用多项式模计算)。加速乘法的一个常见技巧是使用以下等式:
构建 log-antilog- uint8
-ndarrays 很容易执行如下:
gen = 9 ; K = [1] ; g = gen
for i in range(1,255):
K.append(g)
g = multGF(g,gen)
antilog = np.array(K, dtype='uint8')
log = np.full(256,0, dtype='uint8')
for i in range(255): log[antilog[i]] = i
但是,这是我的问题,如何以 numpy-thonic 的方式实现乘法?对数表和对数表的大小都是 255(不是 256;0 没有对数),指数必须以 255 为模,而不是 256 为模。我想出了以下恕我直言的非 numpy-thonic 解决方案:
def multGF2(a,b):
return antilog[(int(log[a]) + log[b]) % 255]
为了执行 mod-255-addition,我必须将 uint8-addition(自然地工作 mod-256)转换为 int-addtion。这既不优雅也不高效,我很确定,有更好的解决方案吗?
用于测试:这两个日志表都是数组:
log = [ nan 0 250 214 245 173 209 42 240 1 168 71 204 187 37 132 235 91
251 191 163 84 66 146 199 212 182 215 32 30 127 247 230 206 86 229
246 65 186 244 158 87 79 171 61 174 141 180 194 113 207 50 177 150
210 54 27 105 25 231 122 93 242 43 225 2 201 156 81 142 224 52
241 53 60 64 181 190 239 254 153 119 82 72 74 9 166 62 56 13
169 143 136 34 175 109 189 80 108 165 202 188 45 99 172 203 145 126
205 157 49 24 22 139 100 159 20 111 226 133 117 233 88 46 237 130
38 3 220 217 252 35 196 96 151 89 76 6 137 192 219 5 47 178
236 110 48 98 55 118 59 155 176 92 185 179 234 211 249 70 148 18
114 39 77 124 67 14 69 58 4 195 161 7 57 147 51 238 8 135
164 144 138 116 131 208 29 162 170 85 104 193 184 97 75 216 103 115
160 123 197 11 183 10 40 222 94 101 167 213 198 90 140 243 121 149
200 63 152 12 44 23 19 129 17 68 134 28 95 218 154 248 15 16
106 227 221 102 128 120 112 26 228 78 83 31 41 36 232 21 125 107
33 73 253 223]
antilog = [ 1 9 65 127 170 141 137 173 178 85 203 201 219 89 167 232 233 224
161 222 116 249 112 221 111 58 241 56 227 186 29 245 28 252 93 131
247 14 126 163 204 246 7 63 220 102 123 142 146 110 51 176 71 73
55 148 88 174 169 150 74 44 87 217 75 37 22 166 225 168 159 11
83 253 84 194 136 164 243 42 97 68 82 244 21 189 34 41 122 135
211 17 153 61 206 228 133 193 147 103 114 207 237 196 190 57 234 251
98 95 145 117 240 49 162 197 183 120 149 81 239 214 60 199 165 250
107 30 238 223 125 184 15 119 226 179 92 138 182 113 212 46 69 91
181 106 23 175 160 215 53 134 218 80 230 151 67 109 40 115 198 172
187 20 180 99 86 208 10 90 188 43 104 5 45 94 152 52 143 155
47 76 26 202 192 154 38 13 101 96 77 19 139 191 48 171 132 200
210 24 216 66 100 105 12 108 33 50 185 6 54 157 25 209 3 27
195 129 229 140 128 236 205 255 70 64 118 235 242 35 32 59 248 121
156 16 144 124 177 78 8 72 62 213 39 4 36 31 231 158 2 18
130 254 79 ]