Add belt-che
agievich
| 1 |
/*
|
|
| 2 |
*******************************************************************************
|
|
| 3 |
\file gf2.c
|
|
| 4 |
\brief Binary fields
|
|
| 5 |
\project bee2 [cryptographic library]
|
|
| 6 |
\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}]
|
|
| 7 |
\created 2012.04.17
|
|
| 8 |
\version 2015.11.03
|
|
| 9 |
\license This program is released under the GNU General Public License
|
|
| 10 |
version 3. See Copyright Notices in bee2/info.h.
|
|
| 11 |
*******************************************************************************
|
|
| 12 |
*/
|
|
| 13 |
|
|
| 14 |
#include "bee2/core/blob.h" |
|
| 15 |
#include "bee2/core/mem.h" |
|
| 16 |
#include "bee2/core/stack.h" |
|
| 17 |
#include "bee2/core/util.h" |
|
| 18 |
#include "bee2/math/gf2.h" |
|
| 19 |
#include "bee2/math/pp.h" |
|
| 20 |
#include "bee2/math/ww.h" |
|
| 21 |
|
|
| 22 |
/*
|
|
| 23 |
*******************************************************************************
|
|
| 24 |
Ускоренные варианты ppRedTrinomial
|
|
| 25 |
|
|
| 26 |
Предварительно рассчитываются числа bm, wm, bk, wk.
|
|
| 27 |
|
|
| 28 |
gf2RedTrinomial0: bk == 0.
|
|
| 29 |
gf2RedTrinomial1: bk != 0.
|
|
| 30 |
*******************************************************************************
|
|
| 31 |
*/
|
|
| 32 |
|
|
| 33 |
typedef struct |
|
| 34 |
{
|
|
| 35 |
size_t m; /*< степень трехчлена */ |
|
| 36 |
size_t k; /*< степень среднего монома */ |
|
| 37 |
size_t l; /*< здесь должен быть 0 */ |
|
| 38 |
size_t l1; /*< здесь должен быть 0 */ |
|
| 39 |
size_t bm; /*< m % B_PER_W */ |
|
| 40 |
size_t wm; /*< m / B_PER_W */ |
|
| 41 |
size_t bk; /*< (m - k) % B_PER_W */ |
|
| 42 |
size_t wk; /*< (m - k) / B_PER_W */ |
|
| 43 |
} gf2_trinom_st; |
|
| 44 |
|
|
| 45 |
static void gf2RedTrinomial0(word a[], size_t n, const gf2_trinom_st* p) |
|
| 46 |
{
|
|
| 47 |
register word hi; |
|
| 48 |
// pre
|
|
| 49 |
ASSERT(wwIsValid(a, 2 * n)); |
|
| 50 |
ASSERT(memIsValid(p, sizeof(*p))); |
|
| 51 |
ASSERT(p->m % 8 != 0); |
|
| 52 |
ASSERT(p->m > p->k && p->k > 0); |
|
| 53 |
ASSERT(p->m - p->k >= B_PER_W); |
|
| 54 |
ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); |
|
| 55 |
ASSERT(p->m == p->wm * B_PER_W + p->bm); |
|
| 56 |
ASSERT(p->m == p->k + p->wk * B_PER_W + p->bk); |
|
| 57 |
ASSERT(n == W_OF_B(p->m)); |
|
| 58 |
ASSERT(p->bk == 0); |
|
| 59 |
// обработать старшие слова
|
|
| 60 |
n *= 2; |
|
| 61 |
while (--n > p->wm) |
|
| 62 |
{
|
|
| 63 |
hi = a[n]; |
|
| 64 |
a[n - p->wm - 1] ^= hi << (B_PER_W - p->bm); |
|
| 65 |
a[n - p->wm] ^= hi >> p->bm; |
|
| 66 |
a[n - p->wk] ^= hi; |
|
| 67 |
}
|
|
| 68 |
// слово, на которое попадает моном x^m
|
|
| 69 |
ASSERT(n == p->wm); |
|
| 70 |
hi = a[n] >> p->bm; |
|
| 71 |
a[0] ^= hi; |
|
| 72 |
hi <<= p->bm; |
|
| 73 |
a[n - p->wk] ^= hi; |
|
| 74 |
a[n] ^= hi; |
|
| 75 |
// очистка
|
|
| 76 |
hi = 0; |
|
| 77 |
}
|
|
| 78 |
|
|
| 79 | 1 |
static void gf2RedTrinomial1(word a[], size_t n, const gf2_trinom_st* p) |
| 80 |
{
|
|
| 81 |
register word hi; |
|
| 82 |
// pre
|
|
| 83 | 1 |
ASSERT(wwIsValid(a, 2 * n)); |
| 84 | 1 |
ASSERT(memIsValid(p, sizeof(*p))); |
| 85 | 1 |
ASSERT(p->m % 8 != 0); |
| 86 | 1 |
ASSERT(p->m > p->k && p->k > 0); |
| 87 | 1 |
ASSERT(p->m - p->k >= B_PER_W); |
| 88 | 1 |
ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); |
| 89 | 1 |
ASSERT(p->m == p->wm * B_PER_W + p->bm); |
| 90 | 1 |
ASSERT(p->m == p->k + p->wk * B_PER_W + p->bk); |
| 91 | 1 |
ASSERT(n == W_OF_B(p->m)); |
| 92 | 1 |
ASSERT(p->bk != 0); |
| 93 |
// обработать старшие слова
|
|
| 94 | 1 |
n *= 2; |
| 95 | 1 |
while (--n > p->wm) |
| 96 |
{
|
|
| 97 | 1 |
hi = a[n]; |
| 98 | 1 |
a[n - p->wm - 1] ^= hi << (B_PER_W - p->bm); |
| 99 | 1 |
a[n - p->wm] ^= hi >> p->bm; |
| 100 | 1 |
a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); |
| 101 | 1 |
a[n - p->wk] ^= hi >> p->bk; |
| 102 |
}
|
|
| 103 |
// слово, на которое попадает моном x^m
|
|
| 104 | 1 |
ASSERT(n == p->wm); |
| 105 | 1 |
hi = a[n] >> p->bm; |
| 106 | 1 |
a[0] ^= hi; |
| 107 | 1 |
hi <<= p->bm; |
| 108 | 1 |
if (p->wk < n) |
| 109 | 1 |
a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); |
| 110 | 1 |
a[n - p->wk] ^= hi >> p->bk; |
| 111 | 1 |
a[n] ^= hi; |
| 112 |
// очистка
|
|
| 113 | 1 |
hi = 0; |
| 114 |
}
|
|
| 115 |
|
|
| 116 |
/*
|
|
| 117 |
*******************************************************************************
|
|
| 118 |
Ускоренные варианты ppRedPentanomial
|
|
| 119 |
|
|
| 120 |
Предварительно рассчитываются числа bm, wm, bk, wk, wl, bl, wl1, bl1.
|
|
| 121 |
|
|
| 122 |
Набор (bm, bk, bl, bl1) не может быть нулевым -- соответствующий многочлен
|
|
| 123 |
не является неприводимым.
|
|
| 124 |
|
|
| 125 |
\todo 15 функций gf2RedPentanomial[bm|bk|bl|bl1].
|
|
| 126 |
*******************************************************************************
|
|
| 127 |
*/
|
|
| 128 |
|
|
| 129 |
typedef struct |
|
| 130 |
{
|
|
| 131 |
size_t m; /*< степень пятичлена */ |
|
| 132 |
size_t k; /*< степень старшего из средних мономов */ |
|
| 133 |
size_t l; /*< степень среднего из средних мономов */ |
|
| 134 |
size_t l1; /*< степень младшего из средних мономов */ |
|
| 135 |
size_t bm; /*< m % B_PER_W */ |
|
| 136 |
size_t wm; /*< m / B_PER_W */ |
|
| 137 |
size_t bk; /*< (m - k) % B_PER_W */ |
|
| 138 |
size_t wk; /*< (m - k) / B_PER_W */ |
|
| 139 |
size_t bl; /*< (m - l) % B_PER_W */ |
|
| 140 |
size_t wl; /*< (m - l) / B_PER_W */ |
|
| 141 |
size_t bl1; /*< (m - l1) % B_PER_W */ |
|
| 142 |
size_t wl1; /*< (m - l1) / B_PER_W */ |
|
| 143 |
} gf2_pentanom_st; |
|
| 144 |
|
|
| 145 | 1 |
static void gf2RedPentanomial(word a[], size_t n, const gf2_pentanom_st* p) |
| 146 |
{
|
|
| 147 |
register word hi; |
|
| 148 |
// pre
|
|
| 149 | 1 |
ASSERT(wwIsValid(a, 2 * n)); |
| 150 | 1 |
ASSERT(memIsValid(p, sizeof(*p))); |
| 151 | 1 |
ASSERT(p->m > p->k && p->k > p->l && p->l > p->l1 && p->l1 > 0); |
| 152 | 1 |
ASSERT(p->k < B_PER_W); |
| 153 | 1 |
ASSERT(p->m - p->k >= B_PER_W); |
| 154 | 1 |
ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); |
| 155 | 1 |
ASSERT(p->bl < B_PER_W && p->bl1 < B_PER_W); |
| 156 | 1 |
ASSERT(p->m == B_PER_W * p->wm + p->bm); |
| 157 | 1 |
ASSERT(p->m == p->k + B_PER_W * p->wk + p->bk); |
| 158 | 1 |
ASSERT(p->m == p->l + B_PER_W * p->wl + p->bl); |
| 159 | 1 |
ASSERT(p->m == p->l1 + B_PER_W * p->wl1 + p->bl1); |
| 160 | 1 |
ASSERT(n == W_OF_B(p->m)); |
| 161 |
// обрабатываем старшие слова
|
|
| 162 | 1 |
n *= 2; |
| 163 | 1 |
while (--n > p->wm) |
| 164 |
{
|
|
| 165 | 1 |
hi = a[n]; |
| 166 | 1 |
a[n - p->wm - 1] ^= p->bm ? hi << (B_PER_W - p->bm) : 0; |
| 167 | 1 |
a[n - p->wm] ^= hi >> p->bm; |
| 168 | 1 |
a[n - p->wl1 - 1] ^= p->bl1 ? hi << (B_PER_W - p->bl1) : 0; |
| 169 | 1 |
a[n - p->wl1] ^= hi >> p->bl1; |
| 170 | 1 |
a[n - p->wl - 1] ^= p->bl ? hi << (B_PER_W - p->bl) : 0; |
| 171 | 1 |
a[n - p->wl] ^= hi >> p->bl; |
| 172 | 1 |
a[n - p->wk - 1] ^= p->bk ? hi << (B_PER_W - p->bk) : 0; |
| 173 | 1 |
a[n - p->wk] ^= hi >> p->bk; |
| 174 |
}
|
|
| 175 |
// слово, на которое попадает моном x^m
|
|
| 176 | 1 |
ASSERT(n == p->wm); |
| 177 | 1 |
hi = a[n] >> p->bm; |
| 178 | 1 |
a[0] ^= hi; |
| 179 | 1 |
hi <<= p->bm; |
| 180 | 1 |
if (p->wl1 < n && p->bl1) |
| 181 |
a[n - p->wl1 - 1] ^= hi << (B_PER_W - p->bl1); |
|
| 182 | 1 |
a[n - p->wl1] ^= hi >> p->bl1; |
| 183 | 1 |
if (p->wl < n && p->bl) |
| 184 |
a[n - p->wl - 1] ^= hi << (B_PER_W - p->bl); |
|
| 185 | 1 |
a[n - p->wl] ^= hi >> p->bl; |
| 186 | 1 |
if (p->wk < n && p->bk) |
| 187 |
a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); |
|
| 188 | 1 |
a[n - p->wk] ^= hi >> p->bk; |
| 189 | 1 |
a[n] ^= hi; |
| 190 |
// очистка
|
|
| 191 | 1 |
hi = 0; |
| 192 |
}
|
|
| 193 |
|
|
| 194 |
/*
|
|
| 195 |
*******************************************************************************
|
|
| 196 |
Реализация интерфейсов qr_XXX_t
|
|
| 197 |
|
|
| 198 |
Если степень расширения m кратна B_PER_W, то модуль задается n + 1 словом,
|
|
| 199 |
а элементы поля -- n словами. Поэтому в функциях gf2From(), gf2Inv(),
|
|
| 200 |
gf2Div() случай m % B_PER_W == 0 обрабатывается особенным образом.
|
|
| 201 |
*******************************************************************************
|
|
| 202 |
*/
|
|
| 203 |
|
|
| 204 | 1 |
static bool_t gf2From(word b[], const octet a[], const qr_o* f, void* stack) |
| 205 |
{
|
|
| 206 | 1 |
ASSERT(gf2IsOperable(f)); |
| 207 | 1 |
wwFrom(b, a, f->no); |
| 208 | 1 |
return gf2IsIn(b, f); |
| 209 |
}
|
|
| 210 |
|
|
| 211 | 1 |
static void gf2To(octet b[], const word a[], const qr_o* f, void* stack) |
| 212 |
{
|
|
| 213 | 1 |
ASSERT(gf2IsOperable(f)); |
| 214 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 215 | 1 |
wwTo(b, f->no, a); |
| 216 |
}
|
|
| 217 |
|
|
| 218 |
static void gf2Add3(word c[], const word a[], const word b[], const qr_o* f) |
|
| 219 |
{
|
|
| 220 |
ASSERT(gf2IsOperable(f)); |
|
| 221 |
ASSERT(gf2IsIn(a, f)); |
|
| 222 |
ASSERT(gf2IsIn(b, f)); |
|
| 223 |
wwXor(c, a, b, f->n); |
|
| 224 |
}
|
|
| 225 |
|
|
| 226 |
static void gf2Neg2(word b[], const word a[], const qr_o* f) |
|
| 227 |
{
|
|
| 228 |
ASSERT(gf2IsOperable(f)); |
|
| 229 |
ASSERT(gf2IsIn(a, f)); |
|
| 230 |
wwCopy(b, a, f->n); |
|
| 231 |
}
|
|
| 232 |
|
|
| 233 |
static void gf2MulTrinomial0(word c[], const word a[], const word b[], |
|
| 234 |
const qr_o* f, void* stack) |
|
| 235 |
{
|
|
| 236 |
word* prod = (word*)stack; |
|
| 237 |
stack = prod + 2 * f->n; |
|
| 238 |
ASSERT(gf2IsOperable(f)); |
|
| 239 |
ASSERT(gf2IsIn(a, f)); |
|
| 240 |
ASSERT(gf2IsIn(b, f)); |
|
| 241 |
ppMul(prod, a, f->n, b, f->n, stack); |
|
| 242 |
gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params); |
|
| 243 |
wwCopy(c, prod, f->n); |
|
| 244 |
}
|
|
| 245 |
|
|
| 246 | 1 |
static size_t gf2MulTrinomial0_deep(size_t n) |
| 247 |
{
|
|
| 248 | 1 |
return ppMul_deep(n, n); |
| 249 |
}
|
|
| 250 |
|
|
| 251 | 1 |
static void gf2MulTrinomial1(word c[], const word a[], const word b[], |
| 252 |
const qr_o* f, void* stack) |
|
| 253 |
{
|
|
| 254 | 1 |
word* prod = (word*)stack; |
| 255 | 1 |
stack = prod + 2 * f->n; |
| 256 | 1 |
ASSERT(gf2IsOperable(f)); |
| 257 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 258 | 1 |
ASSERT(gf2IsIn(b, f)); |
| 259 | 1 |
ppMul(prod, a, f->n, b, f->n, stack); |
| 260 | 1 |
gf2RedTrinomial1(prod, f->n, (const gf2_trinom_st*)f->params); |
| 261 | 1 |
wwCopy(c, prod, f->n); |
| 262 |
}
|
|
| 263 |
|
|
| 264 | 1 |
static size_t gf2MulTrinomial1_deep(size_t n) |
| 265 |
{
|
|
| 266 | 1 |
return ppMul_deep(n, n); |
| 267 |
}
|
|
| 268 |
|
|
| 269 | 1 |
static void gf2MulPentanomial(word c[], const word a[], const word b[], |
| 270 |
const qr_o* f, void* stack) |
|
| 271 |
{
|
|
| 272 | 1 |
word* prod = (word*)stack; |
| 273 | 1 |
stack = prod + 2 * f->n; |
| 274 | 1 |
ASSERT(gf2IsOperable(f)); |
| 275 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 276 | 1 |
ASSERT(gf2IsIn(b, f)); |
| 277 | 1 |
ppMul(prod, a, f->n, b, f->n, stack); |
| 278 | 1 |
gf2RedPentanomial(prod, f->n, (const gf2_pentanom_st*)f->params); |
| 279 | 1 |
wwCopy(c, prod, f->n); |
| 280 |
}
|
|
| 281 |
|
|
| 282 | 1 |
static size_t gf2MulPentanomial_deep(size_t n) |
| 283 |
{
|
|
| 284 | 1 |
return ppMul_deep(n, n); |
| 285 |
}
|
|
| 286 |
|
|
| 287 |
static void gf2SqrTrinomial0(word b[], const word a[], const qr_o* f, |
|
| 288 |
void* stack) |
|
| 289 |
{
|
|
| 290 |
word* prod = (word*)stack; |
|
| 291 |
stack = prod + 2 * f->n; |
|
| 292 |
ASSERT(gf2IsOperable(f)); |
|
| 293 |
ASSERT(gf2IsIn(a, f)); |
|
| 294 |
ppSqr(prod, a, f->n, stack); |
|
| 295 |
gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params); |
|
| 296 |
wwCopy(b, prod, f->n); |
|
| 297 |
}
|
|
| 298 |
|
|
| 299 | 1 |
static size_t gf2SqrTrinomial0_deep(size_t n) |
| 300 |
{
|
|
| 301 | 1 |
return ppSqr_deep(n); |
| 302 |
}
|
|
| 303 |
|
|
| 304 | 1 |
static void gf2SqrTrinomial1(word b[], const word a[], const qr_o* f, |
| 305 |
void* stack) |
|
| 306 |
{
|
|
| 307 | 1 |
word* prod = (word*)stack; |
| 308 | 1 |
stack = prod + 2 * f->n; |
| 309 | 1 |
ASSERT(gf2IsOperable(f)); |
| 310 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 311 | 1 |
ppSqr(prod, a, f->n, stack); |
| 312 | 1 |
gf2RedTrinomial1(prod, f->n, (const gf2_trinom_st*)f->params); |
| 313 | 1 |
wwCopy(b, prod, f->n); |
| 314 |
}
|
|
| 315 |
|
|
| 316 | 1 |
static size_t gf2SqrTrinomial1_deep(size_t n) |
| 317 |
{
|
|
| 318 | 1 |
return ppSqr_deep(n); |
| 319 |
}
|
|
| 320 |
|
|
| 321 | 1 |
static void gf2SqrPentanomial(word b[], const word a[], const qr_o* f, |
| 322 |
void* stack) |
|
| 323 |
{
|
|
| 324 | 1 |
word* prod = (word*)stack; |
| 325 | 1 |
stack = prod + 2 * f->n; |
| 326 | 1 |
ASSERT(gf2IsOperable(f)); |
| 327 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 328 | 1 |
ppSqr(prod, a, f->n, stack); |
| 329 | 1 |
gf2RedPentanomial(prod, f->n, (const gf2_pentanom_st*)f->params); |
| 330 | 1 |
wwCopy(b, prod, f->n); |
| 331 |
}
|
|
| 332 |
|
|
| 333 | 1 |
static size_t gf2SqrPentanomial_deep(size_t n) |
| 334 |
{
|
|
| 335 | 1 |
return ppSqr_deep(n); |
| 336 |
}
|
|
| 337 |
|
|
| 338 | 1 |
static void gf2Inv(word b[], const word a[], const qr_o* f, void* stack) |
| 339 |
{
|
|
| 340 | 1 |
ASSERT(gf2IsOperable(f)); |
| 341 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 342 | 1 |
if (gf2Deg(f) % B_PER_W == 0) |
| 343 |
{
|
|
| 344 |
word* c = (word*)stack; |
|
| 345 |
stack = c + f->n + 1; |
|
| 346 |
ppInvMod(c, a, f->mod, f->n + 1, stack); |
|
| 347 |
ASSERT(c[f->n] == 0); |
|
| 348 |
wwCopy(b, c, f->n); |
|
| 349 |
}
|
|
| 350 |
else
|
|
| 351 | 1 |
ppInvMod(b, a, f->mod, f->n, stack); |
| 352 |
}
|
|
| 353 |
|
|
| 354 | 1 |
static size_t gf2Inv_deep(size_t n) |
| 355 |
{
|
|
| 356 | 1 |
return O_OF_W(n + 1) + ppInvMod_deep(n + 1); |
| 357 |
}
|
|
| 358 |
|
|
| 359 | 1 |
static void gf2Div(word b[], const word divident[], const word a[], |
| 360 |
const qr_o* f, void* stack) |
|
| 361 |
{
|
|
| 362 | 1 |
ASSERT(gf2IsOperable(f)); |
| 363 | 1 |
ASSERT(gf2IsIn(divident, f)); |
| 364 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 365 | 1 |
if (gf2Deg(f) % B_PER_W == 0) |
| 366 |
{
|
|
| 367 |
word* c = (word*)stack; |
|
| 368 |
stack = c + f->n + 1; |
|
| 369 |
ppDivMod(c, divident, a, f->mod, f->n + 1, stack); |
|
| 370 |
ASSERT(c[f->n] == 0); |
|
| 371 |
wwCopy(b, c, f->n); |
|
| 372 |
}
|
|
| 373 |
else
|
|
| 374 | 1 |
ppDivMod(b, divident, a, f->mod, f->n, stack); |
| 375 |
}
|
|
| 376 |
|
|
| 377 | 1 |
static size_t gf2Div_deep(size_t n) |
| 378 |
{
|
|
| 379 | 1 |
return O_OF_W(n + 1) + ppDivMod_deep(n + 1); |
| 380 |
}
|
|
| 381 |
|
|
| 382 |
/*
|
|
| 383 |
*******************************************************************************
|
|
| 384 |
Управление описанием поля
|
|
| 385 |
*******************************************************************************
|
|
| 386 |
*/
|
|
| 387 |
|
|
| 388 | 1 |
bool_t gf2Create(qr_o* f, const size_t p[4], void* stack) |
| 389 |
{
|
|
| 390 | 1 |
ASSERT(memIsValid(f, sizeof(qr_o))); |
| 391 | 1 |
ASSERT(memIsValid(p, 4 * sizeof(size_t))); |
| 392 |
// нормальный базис?
|
|
| 393 | 1 |
if (p[1] == 0) |
| 394 |
{
|
|
| 395 |
// todo: реализовать
|
|
| 396 |
return FALSE; |
|
| 397 |
}
|
|
| 398 |
// трехчлен?
|
|
| 399 | 1 |
else if (p[2] == 0) |
| 400 |
{
|
|
| 401 |
gf2_trinom_st* t; |
|
| 402 |
size_t n1; |
|
| 403 |
// нарушены соглашения?
|
|
| 404 | 1 |
if (p[2] != 0 || p[3] != 0) |
| 405 |
return FALSE; |
|
| 406 |
// нарушены условия функции ppRedTrinomial?
|
|
| 407 | 1 |
if (p[0] % 8 == 0 || p[1] >= p[0] || p[0] - p[1] < B_PER_W) |
| 408 |
return FALSE; |
|
| 409 |
// зафиксировать размерность
|
|
| 410 | 1 |
f->n = W_OF_B(p[0]); |
| 411 | 1 |
n1 = f->n + (p[0] % B_PER_W == 0); |
| 412 | 1 |
f->no = O_OF_B(p[0]); |
| 413 |
// сформировать mod
|
|
| 414 | 1 |
f->mod = (word*)f->descr; |
| 415 | 1 |
wwSetZero(f->mod, n1); |
| 416 | 1 |
wwSetBit(f->mod, p[0], 1); |
| 417 | 1 |
wwSetBit(f->mod, p[1], 1); |
| 418 | 1 |
wwSetBit(f->mod, 0, 1); |
| 419 |
// сформировать unity
|
|
| 420 | 1 |
f->unity = f->mod + n1; |
| 421 | 1 |
wwSetW(f->unity, f->n, 1); |
| 422 |
// сформировать params
|
|
| 423 | 1 |
f->params = (size_t*)(f->unity + f->n); |
| 424 | 1 |
t = (gf2_trinom_st*)f->params; |
| 425 | 1 |
t->m = p[0]; |
| 426 | 1 |
t->k = p[1]; |
| 427 | 1 |
t->l = t->l1 = 0; |
| 428 | 1 |
t->bm = p[0] % B_PER_W; |
| 429 | 1 |
t->wm = p[0] / B_PER_W; |
| 430 | 1 |
t->bk = (p[0] - p[1]) % B_PER_W; |
| 431 | 1 |
t->wk = (p[0] - p[1]) / B_PER_W; |
| 432 |
// настроить интерфейсы
|
|
| 433 | 1 |
f->from = gf2From; |
| 434 | 1 |
f->to = gf2To; |
| 435 | 1 |
f->add = gf2Add3; |
| 436 | 1 |
f->sub = gf2Add3; |
| 437 | 1 |
f->neg = gf2Neg2; |
| 438 | 1 |
f->mul = t->bk == 0 ? gf2MulTrinomial0 : gf2MulTrinomial1; |
| 439 | 1 |
f->sqr = t->bk == 0 ? gf2SqrTrinomial0 : gf2SqrTrinomial1; |
| 440 | 1 |
f->inv = gf2Inv; |
| 441 | 1 |
f->div = gf2Div; |
| 442 |
// заголовок
|
|
| 443 | 1 |
f->hdr.keep = sizeof(qr_o) + O_OF_W(n1 + f->n) + sizeof(gf2_trinom_st); |
| 444 | 1 |
f->hdr.p_count = 3; |
| 445 | 1 |
f->hdr.o_count = 0; |
| 446 |
// глубина стека
|
|
| 447 | 1 |
if (t->bk == 0) |
| 448 |
f->deep = utilMax(4, |
|
| 449 |
gf2MulTrinomial0_deep(f->n), |
|
| 450 |
gf2SqrTrinomial0_deep(f->n), |
|
| 451 |
gf2Inv_deep(f->n), |
|
| 452 |
gf2Div_deep(f->n)); |
|
| 453 |
else
|
|
| 454 | 1 |
f->deep = utilMax(4, |
| 455 |
gf2MulTrinomial1_deep(f->n), |
|
| 456 |
gf2SqrTrinomial1_deep(f->n), |
|
| 457 |
gf2Inv_deep(f->n), |
|
| 458 |
gf2Div_deep(f->n)); |
|
| 459 |
}
|
|
| 460 |
// пятичлен?
|
|
| 461 |
else
|
|
| 462 |
{
|
|
| 463 |
gf2_pentanom_st* t; |
|
| 464 |
size_t n1; |
|
| 465 |
// нарушены соглашения?
|
|
| 466 | 1 |
if (p[3] == 0) |
| 467 |
return FALSE; |
|
| 468 |
// нарушены условия функции ppRedPentanomial?
|
|
| 469 | 1 |
if (p[1] >= p[0] || p[2] >= p[1] || p[3] >= p[2] || p[3] == 0 || |
| 470 | 1 |
p[0] - p[1] < B_PER_W || p[1] >= B_PER_W) |
| 471 |
return FALSE; |
|
| 472 |
// зафиксировать размерность
|
|
| 473 | 1 |
f->n = W_OF_B(p[0]); |
| 474 | 1 |
n1 = f->n + (p[0] % B_PER_W == 0); |
| 475 | 1 |
f->no = O_OF_B(p[0]); |
| 476 |
// сформировать mod
|
|
| 477 | 1 |
f->mod = (word*)f->descr; |
| 478 | 1 |
wwSetZero(f->mod, n1); |
| 479 | 1 |
wwSetBit(f->mod, p[0], 1); |
| 480 | 1 |
wwSetBit(f->mod, p[1], 1); |
| 481 | 1 |
wwSetBit(f->mod, p[2], 1); |
| 482 | 1 |
wwSetBit(f->mod, p[3], 1); |
| 483 | 1 |
wwSetBit(f->mod, 0, 1); |
| 484 |
// сформировать unity
|
|
| 485 | 1 |
f->unity = f->mod + n1; |
| 486 | 1 |
wwSetW(f->unity, f->n, 1); |
| 487 |
// сформировать params
|
|
| 488 | 1 |
f->params = (size_t*)(f->unity + f->n); |
| 489 | 1 |
t = (gf2_pentanom_st*)f->params; |
| 490 | 1 |
t->m = p[0]; |
| 491 | 1 |
t->k = p[1]; |
| 492 | 1 |
t->l = p[2]; |
| 493 | 1 |
t->l1 = p[3]; |
| 494 | 1 |
t->bm = p[0] % B_PER_W; |
| 495 | 1 |
t->wm = p[0] / B_PER_W; |
| 496 | 1 |
t->bk = (p[0] - p[1]) % B_PER_W; |
| 497 | 1 |
t->wk = (p[0] - p[1]) / B_PER_W; |
| 498 | 1 |
t->bl = (p[0] - p[2]) % B_PER_W; |
| 499 | 1 |
t->wl = (p[0] - p[2]) / B_PER_W; |
| 500 | 1 |
t->bl1 = (p[0] - p[3]) % B_PER_W; |
| 501 | 1 |
t->wl1 = (p[0] - p[3]) / B_PER_W; |
| 502 |
// настроить интерфейсы
|
|
| 503 | 1 |
f->from = gf2From; |
| 504 | 1 |
f->to = gf2To; |
| 505 | 1 |
f->add = gf2Add3; |
| 506 | 1 |
f->sub = gf2Add3; |
| 507 | 1 |
f->neg = gf2Neg2; |
| 508 | 1 |
f->mul = gf2MulPentanomial; |
| 509 | 1 |
f->sqr = gf2SqrPentanomial; |
| 510 | 1 |
f->inv = gf2Inv; |
| 511 | 1 |
f->div = gf2Div; |
| 512 |
// заголовок
|
|
| 513 | 1 |
f->hdr.keep = sizeof(qr_o) + O_OF_W(n1 + f->n) + |
| 514 |
sizeof(gf2_pentanom_st); |
|
| 515 | 1 |
f->hdr.p_count = 3; |
| 516 | 1 |
f->hdr.o_count = 0; |
| 517 |
// глубина стека
|
|
| 518 | 1 |
f->deep = utilMax(4, |
| 519 |
gf2MulPentanomial_deep(f->n), |
|
| 520 |
gf2SqrPentanomial_deep(f->n), |
|
| 521 |
gf2Inv_deep(f->n), |
|
| 522 |
gf2Div_deep(f->n)); |
|
| 523 |
}
|
|
| 524 | 1 |
return TRUE; |
| 525 |
}
|
|
| 526 |
|
|
| 527 | 1 |
size_t gf2Create_keep(size_t m) |
| 528 |
{
|
|
| 529 | 1 |
const size_t n = W_OF_B(m); |
| 530 | 1 |
const size_t n1 = n + (m % B_PER_W == 0); |
| 531 | 1 |
return sizeof(qr_o) + O_OF_W(n1 + n) + |
| 532 | 1 |
utilMax(2, |
| 533 |
sizeof(gf2_trinom_st), |
|
| 534 |
sizeof(gf2_pentanom_st)); |
|
| 535 |
}
|
|
| 536 |
|
|
| 537 | 1 |
size_t gf2Create_deep(size_t m) |
| 538 |
{
|
|
| 539 | 1 |
const size_t n = W_OF_B(m); |
| 540 | 1 |
return utilMax(8, |
| 541 |
gf2MulTrinomial0_deep(n), |
|
| 542 |
gf2SqrTrinomial0_deep(n), |
|
| 543 |
gf2MulTrinomial1_deep(n), |
|
| 544 |
gf2SqrTrinomial1_deep(n), |
|
| 545 |
gf2MulPentanomial_deep(n), |
|
| 546 |
gf2SqrPentanomial_deep(n), |
|
| 547 |
gf2Inv_deep(n), |
|
| 548 |
gf2Div_deep(n)); |
|
| 549 |
}
|
|
| 550 |
|
|
| 551 | 1 |
bool_t gf2IsOperable(const qr_o* f) |
| 552 |
{
|
|
| 553 |
const size_t* p; |
|
| 554 |
size_t n1; |
|
| 555 | 1 |
if (!qrIsOperable(f) || |
| 556 | 1 |
!memIsValid(f->params, 4 * sizeof(size_t))) |
| 557 |
return FALSE; |
|
| 558 |
// проверить описание многочлена
|
|
| 559 | 1 |
p = (size_t*)f->params; |
| 560 | 1 |
if (p[0] <= p[1] || p[1] < p[2] || p[2] < p[3] || |
| 561 | 1 |
(p[2] > 0 && (p[1] == p[2] || p[2] == p[3] || p[3] == 0)) || |
| 562 | 1 |
f->n != W_OF_B(p[0]) || f->no != O_OF_B(p[0])) |
| 563 |
return FALSE; |
|
| 564 |
// проверить модуль
|
|
| 565 | 1 |
n1 = f->n + (p[0] % B_PER_W == 0); |
| 566 | 1 |
if (!wwIsValid(f->mod, n1) || f->mod[n1 - 1] == 0) |
| 567 |
return FALSE; |
|
| 568 |
// все нормально
|
|
| 569 | 1 |
return TRUE; |
| 570 |
}
|
|
| 571 |
|
|
| 572 | 1 |
bool_t gf2IsValid(const qr_o* f, void* stack) |
| 573 |
{
|
|
| 574 |
const size_t* p; |
|
| 575 | 1 |
if (!gf2IsOperable(f)) |
| 576 |
return FALSE; |
|
| 577 | 1 |
p = (const size_t*)f->params; |
| 578 | 1 |
if (p[1] > 0) |
| 579 |
{
|
|
| 580 |
// согласованность
|
|
| 581 | 1 |
const size_t n1 = f->n + (p[0] % B_PER_W == 0); |
| 582 | 1 |
word* mod = (word*)stack; |
| 583 | 1 |
wwSetZero(mod, n1); |
| 584 | 1 |
wwSetBit(mod, p[0], 1); |
| 585 | 1 |
wwSetBit(mod, p[1], 1); |
| 586 | 1 |
wwSetBit(mod, p[2], 1); |
| 587 | 1 |
wwSetBit(mod, p[3], 1); |
| 588 | 1 |
wwSetBit(mod, 0, 1); |
| 589 | 1 |
if (!wwEq(mod, f->mod, n1)) |
| 590 |
return FALSE; |
|
| 591 |
// неприводимость
|
|
| 592 | 1 |
return ppIsIrred(f->mod, n1, stack); |
| 593 |
}
|
|
| 594 |
return TRUE; |
|
| 595 |
}
|
|
| 596 |
|
|
| 597 | 1 |
size_t gf2IsValid_deep(size_t n) |
| 598 |
{
|
|
| 599 | 1 |
return O_OF_W(n + 1) + ppIsIrred_deep(n + 1); |
| 600 |
}
|
|
| 601 |
|
|
| 602 | 1 |
size_t gf2Deg(const qr_o* f) |
| 603 |
{
|
|
| 604 | 1 |
ASSERT(gf2IsOperable(f)); |
| 605 | 1 |
return ((size_t*)f->params)[0]; |
| 606 |
}
|
|
| 607 |
|
|
| 608 |
/*
|
|
| 609 |
*******************************************************************************
|
|
| 610 |
Дополнительные функции
|
|
| 611 |
|
|
| 612 |
В gf2QSolve() реализован алгоритм из раздела 6.7 ДСТУ 4145-2002.
|
|
| 613 |
*******************************************************************************
|
|
| 614 |
*/
|
|
| 615 |
|
|
| 616 | 1 |
bool_t gf2Tr(const word a[], const qr_o* f, void* stack) |
| 617 |
{
|
|
| 618 | 1 |
size_t m = gf2Deg(f); |
| 619 | 1 |
word* t = (word*)stack; |
| 620 | 1 |
stack = t + f->n; |
| 621 |
// pre
|
|
| 622 | 1 |
ASSERT(gf2IsOperable(f)); |
| 623 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 624 |
// t <- sum_{i = 0}^{m - 1} a^{2^i}
|
|
| 625 | 1 |
qrCopy(t, a, f); |
| 626 | 1 |
while (--m) |
| 627 |
{
|
|
| 628 | 1 |
qrSqr(t, t, f, stack); |
| 629 | 1 |
gf2Add2(t, a, f); |
| 630 |
}
|
|
| 631 |
// t == 0?
|
|
| 632 | 1 |
if (qrIsZero(t, f)) |
| 633 | 1 |
return FALSE; |
| 634 |
// t == 1?
|
|
| 635 | 1 |
ASSERT(qrIsUnity(t, f)); |
| 636 | 1 |
return TRUE; |
| 637 |
}
|
|
| 638 |
|
|
| 639 | 1 |
size_t gf2Tr_deep(size_t n, size_t f_deep) |
| 640 |
{
|
|
| 641 | 1 |
return O_OF_W(n) + f_deep; |
| 642 |
}
|
|
| 643 |
|
|
| 644 | 1 |
bool_t gf2QSolve(word x[], const word a[], const word b[], |
| 645 |
const qr_o* f, void* stack) |
|
| 646 |
{
|
|
| 647 | 1 |
size_t m = gf2Deg(f); |
| 648 | 1 |
word* t = (word*)stack; |
| 649 | 1 |
stack = t + f->n; |
| 650 |
// pre
|
|
| 651 | 1 |
ASSERT(gf2IsOperable(f)); |
| 652 | 1 |
ASSERT(gf2IsIn(a, f)); |
| 653 | 1 |
ASSERT(gf2IsIn(b, f)); |
| 654 | 1 |
ASSERT(x + f->n <= a || x >= a + f->n); |
| 655 | 1 |
ASSERT(m % 2); |
| 656 |
// a == 0?
|
|
| 657 | 1 |
if (qrIsZero(a, f)) |
| 658 |
{
|
|
| 659 |
// x <- b^{2^{m - 1}}
|
|
| 660 |
qrCopy(x, b, f); |
|
| 661 |
while (--m) |
|
| 662 |
qrSqr(x, x, f, stack); |
|
| 663 |
return TRUE; |
|
| 664 |
}
|
|
| 665 |
// a != 0, b == 0?
|
|
| 666 | 1 |
if (qrIsZero(b, f)) |
| 667 |
{
|
|
| 668 |
qrSetZero(x, f); |
|
| 669 |
return TRUE; |
|
| 670 |
}
|
|
| 671 |
// t <- ba^{-2}
|
|
| 672 | 1 |
qrSqr(t, a, f, stack); |
| 673 | 1 |
qrDiv(t, b, t, f, stack); |
| 674 |
// tr(t) == 1?
|
|
| 675 | 1 |
if (gf2Tr(t, f, stack)) |
| 676 | 1 |
return FALSE; |
| 677 |
// x <- htr(t) (полуслед)
|
|
| 678 | 1 |
qrCopy(x, t, f); |
| 679 | 1 |
m = (m - 1) / 2; |
| 680 | 1 |
while (m--) |
| 681 |
{
|
|
| 682 | 1 |
qrSqr(x, x, f, stack); |
| 683 | 1 |
qrSqr(x, x, f, stack); |
| 684 | 1 |
gf2Add2(x, t, f); |
| 685 |
}
|
|
| 686 |
// x <- x * a
|
|
| 687 | 1 |
qrMul(x, x, a, f, stack); |
| 688 |
// решение есть
|
|
| 689 | 1 |
return TRUE; |
| 690 |
}
|
|
| 691 |
|
|
| 692 | 1 |
size_t gf2QSolve_deep(size_t n, size_t f_deep) |
| 693 |
{
|
|
| 694 | 1 |
return O_OF_W(n) + f_deep; |
| 695 |
}
|
Read our documentation on viewing source code .