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 0
static void gf2RedTrinomial0(word a[], size_t n, const gf2_trinom_st* p)
46
{
47
	register word hi;
48
	// pre
49 0
	ASSERT(wwIsValid(a, 2 * n));
50 0
	ASSERT(memIsValid(p, sizeof(*p)));
51 0
	ASSERT(p->m % 8 != 0);
52 0
	ASSERT(p->m > p->k && p->k > 0);
53 0
	ASSERT(p->m - p->k >= B_PER_W);
54 0
	ASSERT(p->bm < B_PER_W && p->bk < B_PER_W);
55 0
	ASSERT(p->m == p->wm * B_PER_W + p->bm);
56 0
	ASSERT(p->m == p->k + p->wk * B_PER_W + p->bk);
57 0
	ASSERT(n == W_OF_B(p->m));
58 0
	ASSERT(p->bk == 0);
59
	// обработать старшие слова
60 0
	n *= 2;
61 0
	while (--n > p->wm)
62
	{
63 0
		hi = a[n];
64 0
		a[n - p->wm - 1] ^= hi << (B_PER_W - p->bm);
65 0
		a[n - p->wm] ^= hi >> p->bm;
66 0
		a[n - p->wk] ^= hi;
67
	}
68
	// слово, на которое попадает моном x^m
69 0
	ASSERT(n == p->wm);
70 0
	hi = a[n] >> p->bm;
71 0
	a[0] ^= hi;
72 0
	hi <<= p->bm;
73 0
	a[n - p->wk] ^= hi;
74 0
	a[n] ^= hi;
75
	// очистка
76 0
	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 0
		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 0
		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 0
		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 0
static void gf2Add3(word c[], const word a[], const word b[], const qr_o* f)
219
{
220 0
	ASSERT(gf2IsOperable(f));
221 0
	ASSERT(gf2IsIn(a, f));
222 0
	ASSERT(gf2IsIn(b, f));
223 0
	wwXor(c, a, b, f->n);
224
}
225

226 0
static void gf2Neg2(word b[], const word a[], const qr_o* f)
227
{
228 0
	ASSERT(gf2IsOperable(f));
229 0
	ASSERT(gf2IsIn(a, f));
230 0
	wwCopy(b, a, f->n);
231
}
232

233 0
static void gf2MulTrinomial0(word c[], const word a[], const word b[], 
234
	const qr_o* f, void* stack)
235
{
236 0
	word* prod = (word*)stack;
237 0
	stack = prod + 2 * f->n;
238 0
	ASSERT(gf2IsOperable(f));
239 0
	ASSERT(gf2IsIn(a, f));
240 0
	ASSERT(gf2IsIn(b, f));
241 0
	ppMul(prod, a, f->n, b, f->n, stack);
242 0
	gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params);
243 0
	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 0
static void gf2SqrTrinomial0(word b[], const word a[], const qr_o* f, 
288
	void* stack)
289
{
290 0
	word* prod = (word*)stack;
291 0
	stack = prod + 2 * f->n;
292 0
	ASSERT(gf2IsOperable(f));
293 0
	ASSERT(gf2IsIn(a, f));
294 0
	ppSqr(prod, a, f->n, stack);
295 0
	gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params);
296 0
	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 0
		word* c = (word*)stack;
345 0
		stack = c + f->n + 1;
346 0
		ppInvMod(c, a, f->mod, f->n + 1, stack);
347 0
		ASSERT(c[f->n] == 0);
348 0
		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 0
		word* c = (word*)stack;
368 0
		stack = c + f->n + 1;
369 0
		ppDivMod(c, divident, a, f->mod, f->n + 1, stack);
370 0
		ASSERT(c[f->n] == 0);
371 0
		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 0
		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 0
			return FALSE;
406
		// нарушены условия функции ppRedTrinomial?
407 1
		if (p[0] % 8 == 0 || p[1] >= p[0] || p[0] - p[1] < B_PER_W)
408 0
			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 0
			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 0
			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 0
			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 0
		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 0
		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 0
		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 0
		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 0
			return FALSE;
591
		// неприводимость
592 1
		return ppIsIrred(f->mod, n1, stack);
593
	}
594 0
	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 0
		qrCopy(x, b, f);
661 0
		while (--m)
662 0
			qrSqr(x, x, f, stack);
663 0
		return TRUE;
664
	}
665
	// a != 0, b == 0?
666 1
	if (qrIsZero(b, f))
667
	{
668 0
		qrSetZero(x, f);
669 0
		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 .

Loading