1 | |
---|
2 | |
---|
3 | #include <NTL/ZZX.h> |
---|
4 | |
---|
5 | #include <NTL/new.h> |
---|
6 | |
---|
7 | NTL_START_IMPL |
---|
8 | |
---|
9 | |
---|
10 | |
---|
11 | |
---|
12 | |
---|
13 | void conv(zz_pX& x, const ZZX& a) |
---|
14 | { |
---|
15 | conv(x.rep, a.rep); |
---|
16 | x.normalize(); |
---|
17 | } |
---|
18 | |
---|
19 | |
---|
20 | void conv(ZZX& x, const zz_pX& a) |
---|
21 | { |
---|
22 | conv(x.rep, a.rep); |
---|
23 | x.normalize(); |
---|
24 | } |
---|
25 | |
---|
26 | |
---|
27 | long CRT(ZZX& gg, ZZ& a, const zz_pX& G) |
---|
28 | { |
---|
29 | long n = gg.rep.length(); |
---|
30 | |
---|
31 | long p = zz_p::modulus(); |
---|
32 | |
---|
33 | ZZ new_a; |
---|
34 | mul(new_a, a, p); |
---|
35 | |
---|
36 | long a_inv; |
---|
37 | a_inv = rem(a, p); |
---|
38 | a_inv = InvMod(a_inv, p); |
---|
39 | |
---|
40 | long p1; |
---|
41 | p1 = p >> 1; |
---|
42 | |
---|
43 | ZZ a1; |
---|
44 | RightShift(a1, a, 1); |
---|
45 | |
---|
46 | long p_odd = (p & 1); |
---|
47 | |
---|
48 | long modified = 0; |
---|
49 | |
---|
50 | long h; |
---|
51 | ZZ ah; |
---|
52 | |
---|
53 | long m = G.rep.length(); |
---|
54 | |
---|
55 | long max_mn = max(m, n); |
---|
56 | |
---|
57 | gg.rep.SetLength(max_mn); |
---|
58 | |
---|
59 | ZZ g; |
---|
60 | long i; |
---|
61 | |
---|
62 | for (i = 0; i < n; i++) { |
---|
63 | if (!CRTInRange(gg.rep[i], a)) { |
---|
64 | modified = 1; |
---|
65 | rem(g, gg.rep[i], a); |
---|
66 | if (g > a1) sub(g, g, a); |
---|
67 | } |
---|
68 | else |
---|
69 | g = gg.rep[i]; |
---|
70 | |
---|
71 | h = rem(g, p); |
---|
72 | |
---|
73 | if (i < m) |
---|
74 | h = SubMod(rep(G.rep[i]), h, p); |
---|
75 | else |
---|
76 | h = NegateMod(h, p); |
---|
77 | |
---|
78 | h = MulMod(h, a_inv, p); |
---|
79 | if (h > p1) |
---|
80 | h = h - p; |
---|
81 | |
---|
82 | if (h != 0) { |
---|
83 | modified = 1; |
---|
84 | mul(ah, a, h); |
---|
85 | |
---|
86 | if (!p_odd && g > 0 && (h == p1)) |
---|
87 | sub(g, g, ah); |
---|
88 | else |
---|
89 | add(g, g, ah); |
---|
90 | } |
---|
91 | |
---|
92 | gg.rep[i] = g; |
---|
93 | } |
---|
94 | |
---|
95 | |
---|
96 | for (; i < m; i++) { |
---|
97 | h = rep(G.rep[i]); |
---|
98 | h = MulMod(h, a_inv, p); |
---|
99 | if (h > p1) |
---|
100 | h = h - p; |
---|
101 | |
---|
102 | modified = 1; |
---|
103 | mul(g, a, h); |
---|
104 | gg.rep[i] = g; |
---|
105 | } |
---|
106 | |
---|
107 | gg.normalize(); |
---|
108 | a = new_a; |
---|
109 | |
---|
110 | return modified; |
---|
111 | } |
---|
112 | |
---|
113 | long CRT(ZZX& gg, ZZ& a, const ZZ_pX& G) |
---|
114 | { |
---|
115 | long n = gg.rep.length(); |
---|
116 | |
---|
117 | const ZZ& p = ZZ_p::modulus(); |
---|
118 | |
---|
119 | ZZ new_a; |
---|
120 | mul(new_a, a, p); |
---|
121 | |
---|
122 | ZZ a_inv; |
---|
123 | rem(a_inv, a, p); |
---|
124 | InvMod(a_inv, a_inv, p); |
---|
125 | |
---|
126 | ZZ p1; |
---|
127 | RightShift(p1, p, 1); |
---|
128 | |
---|
129 | ZZ a1; |
---|
130 | RightShift(a1, a, 1); |
---|
131 | |
---|
132 | long p_odd = IsOdd(p); |
---|
133 | |
---|
134 | long modified = 0; |
---|
135 | |
---|
136 | ZZ h; |
---|
137 | ZZ ah; |
---|
138 | |
---|
139 | long m = G.rep.length(); |
---|
140 | |
---|
141 | long max_mn = max(m, n); |
---|
142 | |
---|
143 | gg.rep.SetLength(max_mn); |
---|
144 | |
---|
145 | ZZ g; |
---|
146 | long i; |
---|
147 | |
---|
148 | for (i = 0; i < n; i++) { |
---|
149 | if (!CRTInRange(gg.rep[i], a)) { |
---|
150 | modified = 1; |
---|
151 | rem(g, gg.rep[i], a); |
---|
152 | if (g > a1) sub(g, g, a); |
---|
153 | } |
---|
154 | else |
---|
155 | g = gg.rep[i]; |
---|
156 | |
---|
157 | rem(h, g, p); |
---|
158 | |
---|
159 | if (i < m) |
---|
160 | SubMod(h, rep(G.rep[i]), h, p); |
---|
161 | else |
---|
162 | NegateMod(h, h, p); |
---|
163 | |
---|
164 | MulMod(h, h, a_inv, p); |
---|
165 | if (h > p1) |
---|
166 | sub(h, h, p); |
---|
167 | |
---|
168 | if (h != 0) { |
---|
169 | modified = 1; |
---|
170 | mul(ah, a, h); |
---|
171 | |
---|
172 | if (!p_odd && g > 0 && (h == p1)) |
---|
173 | sub(g, g, ah); |
---|
174 | else |
---|
175 | add(g, g, ah); |
---|
176 | } |
---|
177 | |
---|
178 | gg.rep[i] = g; |
---|
179 | } |
---|
180 | |
---|
181 | |
---|
182 | for (; i < m; i++) { |
---|
183 | h = rep(G.rep[i]); |
---|
184 | MulMod(h, h, a_inv, p); |
---|
185 | if (h > p1) |
---|
186 | sub(h, h, p); |
---|
187 | |
---|
188 | modified = 1; |
---|
189 | mul(g, a, h); |
---|
190 | gg.rep[i] = g; |
---|
191 | } |
---|
192 | |
---|
193 | gg.normalize(); |
---|
194 | a = new_a; |
---|
195 | |
---|
196 | return modified; |
---|
197 | } |
---|
198 | |
---|
199 | |
---|
200 | |
---|
201 | |
---|
202 | /* Compute a = b * 2^l mod p, where p = 2^n+1. 0<=l<=n and 0<b<p are |
---|
203 | assumed. */ |
---|
204 | static void LeftRotate(ZZ& a, const ZZ& b, long l, const ZZ& p, long n) |
---|
205 | { |
---|
206 | if (l == 0) { |
---|
207 | if (&a != &b) { |
---|
208 | a = b; |
---|
209 | } |
---|
210 | return; |
---|
211 | } |
---|
212 | |
---|
213 | /* tmp := upper l bits of b */ |
---|
214 | static ZZ tmp; |
---|
215 | RightShift(tmp, b, n - l); |
---|
216 | /* a := 2^l * lower n - l bits of b */ |
---|
217 | trunc(a, b, n - l); |
---|
218 | LeftShift(a, a, l); |
---|
219 | /* a -= tmp */ |
---|
220 | sub(a, a, tmp); |
---|
221 | if (sign(a) < 0) { |
---|
222 | add(a, a, p); |
---|
223 | } |
---|
224 | } |
---|
225 | |
---|
226 | |
---|
227 | /* Compute a = b * 2^l mod p, where p = 2^n+1. 0<=p<b is assumed. */ |
---|
228 | static void Rotate(ZZ& a, const ZZ& b, long l, const ZZ& p, long n) |
---|
229 | { |
---|
230 | if (IsZero(b)) { |
---|
231 | clear(a); |
---|
232 | return; |
---|
233 | } |
---|
234 | |
---|
235 | /* l %= 2n */ |
---|
236 | if (l >= 0) { |
---|
237 | l %= (n << 1); |
---|
238 | } else { |
---|
239 | l = (n << 1) - 1 - (-(l + 1) % (n << 1)); |
---|
240 | } |
---|
241 | |
---|
242 | /* a = b * 2^l mod p */ |
---|
243 | if (l < n) { |
---|
244 | LeftRotate(a, b, l, p, n); |
---|
245 | } else { |
---|
246 | LeftRotate(a, b, l - n, p, n); |
---|
247 | SubPos(a, p, a); |
---|
248 | } |
---|
249 | } |
---|
250 | |
---|
251 | |
---|
252 | |
---|
253 | /* Fast Fourier Transform. a is a vector of length 2^l, 2^l divides 2n, |
---|
254 | p = 2^n+1, w = 2^r mod p is a primitive (2^l)th root of |
---|
255 | unity. Returns a(1),a(w),...,a(w^{2^l-1}) mod p in bit-reverse |
---|
256 | order. */ |
---|
257 | static void fft(vec_ZZ& a, long r, long l, const ZZ& p, long n) |
---|
258 | { |
---|
259 | long round; |
---|
260 | long off, i, j, e; |
---|
261 | long halfsize; |
---|
262 | ZZ tmp, tmp1; |
---|
263 | |
---|
264 | for (round = 0; round < l; round++, r <<= 1) { |
---|
265 | halfsize = 1L << (l - 1 - round); |
---|
266 | for (i = (1L << round) - 1, off = 0; i >= 0; i--, off += halfsize) { |
---|
267 | for (j = 0, e = 0; j < halfsize; j++, off++, e+=r) { |
---|
268 | /* One butterfly : |
---|
269 | ( a[off], a[off+halfsize] ) *= ( 1 w^{j2^round} ) |
---|
270 | ( 1 -w^{j2^round} ) */ |
---|
271 | /* tmp = a[off] - a[off + halfsize] mod p */ |
---|
272 | sub(tmp, a[off], a[off + halfsize]); |
---|
273 | if (sign(tmp) < 0) { |
---|
274 | add(tmp, tmp, p); |
---|
275 | } |
---|
276 | /* a[off] += a[off + halfsize] mod p */ |
---|
277 | add(a[off], a[off], a[off + halfsize]); |
---|
278 | sub(tmp1, a[off], p); |
---|
279 | if (sign(tmp1) >= 0) { |
---|
280 | a[off] = tmp1; |
---|
281 | } |
---|
282 | /* a[off + halfsize] = tmp * w^{j2^round} mod p */ |
---|
283 | Rotate(a[off + halfsize], tmp, e, p, n); |
---|
284 | } |
---|
285 | } |
---|
286 | } |
---|
287 | } |
---|
288 | |
---|
289 | /* Inverse FFT. r must be the same as in the call to FFT. Result is |
---|
290 | by 2^l too large. */ |
---|
291 | static void ifft(vec_ZZ& a, long r, long l, const ZZ& p, long n) |
---|
292 | { |
---|
293 | long round; |
---|
294 | long off, i, j, e; |
---|
295 | long halfsize; |
---|
296 | ZZ tmp, tmp1; |
---|
297 | |
---|
298 | for (round = l - 1, r <<= l - 1; round >= 0; round--, r >>= 1) { |
---|
299 | halfsize = 1L << (l - 1 - round); |
---|
300 | for (i = (1L << round) - 1, off = 0; i >= 0; i--, off += halfsize) { |
---|
301 | for (j = 0, e = 0; j < halfsize; j++, off++, e+=r) { |
---|
302 | /* One inverse butterfly : |
---|
303 | ( a[off], a[off+halfsize] ) *= ( 1 1 ) |
---|
304 | ( w^{-j2^round} -w^{-j2^round} ) */ |
---|
305 | /* a[off + halfsize] *= w^{-j2^round} mod p */ |
---|
306 | Rotate(a[off + halfsize], a[off + halfsize], -e, p, n); |
---|
307 | /* tmp = a[off] - a[off + halfsize] */ |
---|
308 | sub(tmp, a[off], a[off + halfsize]); |
---|
309 | |
---|
310 | /* a[off] += a[off + halfsize] mod p */ |
---|
311 | add(a[off], a[off], a[off + halfsize]); |
---|
312 | sub(tmp1, a[off], p); |
---|
313 | if (sign(tmp1) >= 0) { |
---|
314 | a[off] = tmp1; |
---|
315 | } |
---|
316 | /* a[off+halfsize] = tmp mod p */ |
---|
317 | if (sign(tmp) < 0) { |
---|
318 | add(a[off+halfsize], tmp, p); |
---|
319 | } else { |
---|
320 | a[off+halfsize] = tmp; |
---|
321 | } |
---|
322 | } |
---|
323 | } |
---|
324 | } |
---|
325 | } |
---|
326 | |
---|
327 | |
---|
328 | |
---|
329 | /* Multiplication a la Schoenhage & Strassen, modulo a "Fermat" number |
---|
330 | p = 2^{mr}+1, where m is a power of two and r is odd. Then w = 2^r |
---|
331 | is a primitive 2mth root of unity, i.e., polynomials whose product |
---|
332 | has degree less than 2m can be multiplied, provided that the |
---|
333 | coefficients of the product polynomial are at most 2^{mr-1} in |
---|
334 | absolute value. The algorithm is not called recursively; |
---|
335 | coefficient arithmetic is done directly.*/ |
---|
336 | |
---|
337 | void SSMul(ZZX& c, const ZZX& a, const ZZX& b) |
---|
338 | { |
---|
339 | long na = deg(a); |
---|
340 | long nb = deg(b); |
---|
341 | |
---|
342 | if (na <= 0 || nb <= 0) { |
---|
343 | PlainMul(c, a, b); |
---|
344 | return; |
---|
345 | } |
---|
346 | |
---|
347 | long n = na + nb; /* degree of the product */ |
---|
348 | |
---|
349 | |
---|
350 | /* Choose m and r suitably */ |
---|
351 | long l = NextPowerOfTwo(n + 1) - 1; /* 2^l <= n < 2^{l+1} */ |
---|
352 | long m2 = 1L << (l + 1); /* m2 = 2m = 2^{l+1} */ |
---|
353 | /* Bitlength of the product: if the coefficients of a are absolutely less |
---|
354 | than 2^ka and the coefficients of b are absolutely less than 2^kb, then |
---|
355 | the coefficients of ab are absolutely less than |
---|
356 | (min(na,nb)+1)2^{ka+kb} <= 2^bound. */ |
---|
357 | long bound = 2 + NumBits(min(na, nb)) + MaxBits(a) + MaxBits(b); |
---|
358 | /* Let r be minimal so that mr > bound */ |
---|
359 | long r = (bound >> l) + 1; |
---|
360 | long mr = r << l; |
---|
361 | |
---|
362 | /* p := 2^{mr}+1 */ |
---|
363 | ZZ p; |
---|
364 | set(p); |
---|
365 | LeftShift(p, p, mr); |
---|
366 | add(p, p, 1); |
---|
367 | |
---|
368 | /* Make coefficients of a and b positive */ |
---|
369 | vec_ZZ aa, bb; |
---|
370 | aa.SetLength(m2); |
---|
371 | bb.SetLength(m2); |
---|
372 | |
---|
373 | long i; |
---|
374 | for (i = 0; i <= deg(a); i++) { |
---|
375 | if (sign(a.rep[i]) >= 0) { |
---|
376 | aa[i] = a.rep[i]; |
---|
377 | } else { |
---|
378 | add(aa[i], a.rep[i], p); |
---|
379 | } |
---|
380 | } |
---|
381 | |
---|
382 | for (i = 0; i <= deg(b); i++) { |
---|
383 | if (sign(b.rep[i]) >= 0) { |
---|
384 | bb[i] = b.rep[i]; |
---|
385 | } else { |
---|
386 | add(bb[i], b.rep[i], p); |
---|
387 | } |
---|
388 | } |
---|
389 | |
---|
390 | /* 2m-point FFT's mod p */ |
---|
391 | fft(aa, r, l + 1, p, mr); |
---|
392 | fft(bb, r, l + 1, p, mr); |
---|
393 | |
---|
394 | /* Pointwise multiplication aa := aa * bb mod p */ |
---|
395 | ZZ tmp, ai; |
---|
396 | for (i = 0; i < m2; i++) { |
---|
397 | mul(ai, aa[i], bb[i]); |
---|
398 | if (NumBits(ai) > mr) { |
---|
399 | RightShift(tmp, ai, mr); |
---|
400 | trunc(ai, ai, mr); |
---|
401 | sub(ai, ai, tmp); |
---|
402 | if (sign(ai) < 0) { |
---|
403 | add(ai, ai, p); |
---|
404 | } |
---|
405 | } |
---|
406 | aa[i] = ai; |
---|
407 | } |
---|
408 | |
---|
409 | ifft(aa, r, l + 1, p, mr); |
---|
410 | |
---|
411 | /* Retrieve c, dividing by 2m, and subtracting p where necessary */ |
---|
412 | c.rep.SetLength(n + 1); |
---|
413 | for (i = 0; i <= n; i++) { |
---|
414 | ai = aa[i]; |
---|
415 | ZZ& ci = c.rep[i]; |
---|
416 | if (!IsZero(ai)) { |
---|
417 | /* ci = -ai * 2^{mr-l-1} = ai * 2^{-l-1} = ai / 2m mod p */ |
---|
418 | LeftRotate(ai, ai, mr - l - 1, p, mr); |
---|
419 | sub(tmp, p, ai); |
---|
420 | if (NumBits(tmp) >= mr) { /* ci >= (p-1)/2 */ |
---|
421 | negate(ci, ai); /* ci = -ai = ci - p */ |
---|
422 | } |
---|
423 | else |
---|
424 | ci = tmp; |
---|
425 | } |
---|
426 | else |
---|
427 | clear(ci); |
---|
428 | } |
---|
429 | } |
---|
430 | |
---|
431 | |
---|
432 | // SSRatio computes how much bigger the SS moduls must be |
---|
433 | // to accomodate the necessary roots of unity. |
---|
434 | // This is useful in determining algorithm crossover points. |
---|
435 | |
---|
436 | double SSRatio(long na, long maxa, long nb, long maxb) |
---|
437 | { |
---|
438 | if (na <= 0 || nb <= 0) return 0; |
---|
439 | |
---|
440 | long n = na + nb; /* degree of the product */ |
---|
441 | |
---|
442 | |
---|
443 | long l = NextPowerOfTwo(n + 1) - 1; /* 2^l <= n < 2^{l+1} */ |
---|
444 | long bound = 2 + NumBits(min(na, nb)) + maxa + maxb; |
---|
445 | long r = (bound >> l) + 1; |
---|
446 | long mr = r << l; |
---|
447 | |
---|
448 | return double(mr + 1)/double(bound); |
---|
449 | } |
---|
450 | |
---|
451 | void HomMul(ZZX& x, const ZZX& a, const ZZX& b) |
---|
452 | { |
---|
453 | if (&a == &b) { |
---|
454 | HomSqr(x, a); |
---|
455 | return; |
---|
456 | } |
---|
457 | |
---|
458 | long da = deg(a); |
---|
459 | long db = deg(b); |
---|
460 | |
---|
461 | if (da < 0 || db < 0) { |
---|
462 | clear(x); |
---|
463 | return; |
---|
464 | } |
---|
465 | |
---|
466 | long bound = 2 + NumBits(min(da, db)+1) + MaxBits(a) + MaxBits(b); |
---|
467 | |
---|
468 | |
---|
469 | ZZ prod; |
---|
470 | set(prod); |
---|
471 | |
---|
472 | long i, nprimes; |
---|
473 | |
---|
474 | zz_pBak bak; |
---|
475 | bak.save(); |
---|
476 | |
---|
477 | for (nprimes = 0; NumBits(prod) <= bound; nprimes++) { |
---|
478 | if (nprimes >= NumFFTPrimes) |
---|
479 | zz_p::FFTInit(nprimes); |
---|
480 | mul(prod, prod, FFTPrime[nprimes]); |
---|
481 | } |
---|
482 | |
---|
483 | |
---|
484 | ZZ coeff; |
---|
485 | ZZ t1; |
---|
486 | long tt; |
---|
487 | |
---|
488 | vec_ZZ c; |
---|
489 | |
---|
490 | c.SetLength(da+db+1); |
---|
491 | |
---|
492 | long j; |
---|
493 | |
---|
494 | for (i = 0; i < nprimes; i++) { |
---|
495 | zz_p::FFTInit(i); |
---|
496 | long p = zz_p::modulus(); |
---|
497 | |
---|
498 | div(t1, prod, p); |
---|
499 | tt = rem(t1, p); |
---|
500 | tt = InvMod(tt, p); |
---|
501 | mul(coeff, t1, tt); |
---|
502 | |
---|
503 | zz_pX A, B, C; |
---|
504 | |
---|
505 | conv(A, a); |
---|
506 | conv(B, b); |
---|
507 | mul(C, A, B); |
---|
508 | |
---|
509 | long m = deg(C); |
---|
510 | |
---|
511 | for (j = 0; j <= m; j++) { |
---|
512 | /* c[j] += coeff*rep(C.rep[j]) */ |
---|
513 | mul(t1, coeff, rep(C.rep[j])); |
---|
514 | add(c[j], c[j], t1); |
---|
515 | } |
---|
516 | } |
---|
517 | |
---|
518 | x.rep.SetLength(da+db+1); |
---|
519 | |
---|
520 | ZZ prod2; |
---|
521 | RightShift(prod2, prod, 1); |
---|
522 | |
---|
523 | for (j = 0; j <= da+db; j++) { |
---|
524 | rem(t1, c[j], prod); |
---|
525 | |
---|
526 | if (t1 > prod2) |
---|
527 | sub(x.rep[j], t1, prod); |
---|
528 | else |
---|
529 | x.rep[j] = t1; |
---|
530 | } |
---|
531 | |
---|
532 | x.normalize(); |
---|
533 | |
---|
534 | bak.restore(); |
---|
535 | } |
---|
536 | |
---|
537 | static |
---|
538 | long MaxSize(const ZZX& a) |
---|
539 | { |
---|
540 | long res = 0; |
---|
541 | long n = a.rep.length(); |
---|
542 | |
---|
543 | long i; |
---|
544 | for (i = 0; i < n; i++) { |
---|
545 | long t = a.rep[i].size(); |
---|
546 | if (t > res) |
---|
547 | res = t; |
---|
548 | } |
---|
549 | |
---|
550 | return res; |
---|
551 | } |
---|
552 | |
---|
553 | |
---|
554 | void mul(ZZX& c, const ZZX& a, const ZZX& b) |
---|
555 | { |
---|
556 | if (IsZero(a) || IsZero(b)) { |
---|
557 | clear(c); |
---|
558 | return; |
---|
559 | } |
---|
560 | |
---|
561 | if (&a == &b) { |
---|
562 | sqr(c, a); |
---|
563 | return; |
---|
564 | } |
---|
565 | |
---|
566 | long maxa = MaxSize(a); |
---|
567 | long maxb = MaxSize(b); |
---|
568 | |
---|
569 | long k = min(maxa, maxb); |
---|
570 | long s = min(deg(a), deg(b)) + 1; |
---|
571 | |
---|
572 | if (s == 1 || (k == 1 && s < 40) || (k == 2 && s < 20) || |
---|
573 | (k == 3 && s < 10)) { |
---|
574 | |
---|
575 | PlainMul(c, a, b); |
---|
576 | return; |
---|
577 | } |
---|
578 | |
---|
579 | if (s < 80 || (k < 30 && s < 150)) { |
---|
580 | KarMul(c, a, b); |
---|
581 | return; |
---|
582 | } |
---|
583 | |
---|
584 | |
---|
585 | if (maxa + maxb >= 40 && |
---|
586 | SSRatio(deg(a), MaxBits(a), deg(b), MaxBits(b)) < 1.75) |
---|
587 | SSMul(c, a, b); |
---|
588 | else |
---|
589 | HomMul(c, a, b); |
---|
590 | } |
---|
591 | |
---|
592 | |
---|
593 | void SSSqr(ZZX& c, const ZZX& a) |
---|
594 | { |
---|
595 | long na = deg(a); |
---|
596 | if (na <= 0) { |
---|
597 | PlainSqr(c, a); |
---|
598 | return; |
---|
599 | } |
---|
600 | |
---|
601 | long n = na + na; /* degree of the product */ |
---|
602 | |
---|
603 | |
---|
604 | long l = NextPowerOfTwo(n + 1) - 1; /* 2^l <= n < 2^{l+1} */ |
---|
605 | long m2 = 1L << (l + 1); /* m2 = 2m = 2^{l+1} */ |
---|
606 | long bound = 2 + NumBits(na) + 2*MaxBits(a); |
---|
607 | long r = (bound >> l) + 1; |
---|
608 | long mr = r << l; |
---|
609 | |
---|
610 | /* p := 2^{mr}+1 */ |
---|
611 | ZZ p; |
---|
612 | set(p); |
---|
613 | LeftShift(p, p, mr); |
---|
614 | add(p, p, 1); |
---|
615 | |
---|
616 | vec_ZZ aa; |
---|
617 | aa.SetLength(m2); |
---|
618 | |
---|
619 | long i; |
---|
620 | for (i = 0; i <= deg(a); i++) { |
---|
621 | if (sign(a.rep[i]) >= 0) { |
---|
622 | aa[i] = a.rep[i]; |
---|
623 | } else { |
---|
624 | add(aa[i], a.rep[i], p); |
---|
625 | } |
---|
626 | } |
---|
627 | |
---|
628 | |
---|
629 | /* 2m-point FFT's mod p */ |
---|
630 | fft(aa, r, l + 1, p, mr); |
---|
631 | |
---|
632 | /* Pointwise multiplication aa := aa * aa mod p */ |
---|
633 | ZZ tmp, ai; |
---|
634 | for (i = 0; i < m2; i++) { |
---|
635 | sqr(ai, aa[i]); |
---|
636 | if (NumBits(ai) > mr) { |
---|
637 | RightShift(tmp, ai, mr); |
---|
638 | trunc(ai, ai, mr); |
---|
639 | sub(ai, ai, tmp); |
---|
640 | if (sign(ai) < 0) { |
---|
641 | add(ai, ai, p); |
---|
642 | } |
---|
643 | } |
---|
644 | aa[i] = ai; |
---|
645 | } |
---|
646 | |
---|
647 | ifft(aa, r, l + 1, p, mr); |
---|
648 | |
---|
649 | ZZ ci; |
---|
650 | |
---|
651 | /* Retrieve c, dividing by 2m, and subtracting p where necessary */ |
---|
652 | c.rep.SetLength(n + 1); |
---|
653 | |
---|
654 | for (i = 0; i <= n; i++) { |
---|
655 | ai = aa[i]; |
---|
656 | ZZ& ci = c.rep[i]; |
---|
657 | if (!IsZero(ai)) { |
---|
658 | /* ci = -ai * 2^{mr-l-1} = ai * 2^{-l-1} = ai / 2m mod p */ |
---|
659 | LeftRotate(ai, ai, mr - l - 1, p, mr); |
---|
660 | sub(tmp, p, ai); |
---|
661 | if (NumBits(tmp) >= mr) { /* ci >= (p-1)/2 */ |
---|
662 | negate(ci, ai); /* ci = -ai = ci - p */ |
---|
663 | } |
---|
664 | else |
---|
665 | ci = tmp; |
---|
666 | } |
---|
667 | else |
---|
668 | clear(ci); |
---|
669 | } |
---|
670 | } |
---|
671 | |
---|
672 | void HomSqr(ZZX& x, const ZZX& a) |
---|
673 | { |
---|
674 | |
---|
675 | long da = deg(a); |
---|
676 | |
---|
677 | if (da < 0) { |
---|
678 | clear(x); |
---|
679 | return; |
---|
680 | } |
---|
681 | |
---|
682 | long bound = 2 + NumBits(da+1) + 2*MaxBits(a); |
---|
683 | |
---|
684 | |
---|
685 | ZZ prod; |
---|
686 | set(prod); |
---|
687 | |
---|
688 | long i, nprimes; |
---|
689 | |
---|
690 | zz_pBak bak; |
---|
691 | bak.save(); |
---|
692 | |
---|
693 | for (nprimes = 0; NumBits(prod) <= bound; nprimes++) { |
---|
694 | if (nprimes >= NumFFTPrimes) |
---|
695 | zz_p::FFTInit(nprimes); |
---|
696 | mul(prod, prod, FFTPrime[nprimes]); |
---|
697 | } |
---|
698 | |
---|
699 | |
---|
700 | ZZ coeff; |
---|
701 | ZZ t1; |
---|
702 | long tt; |
---|
703 | |
---|
704 | vec_ZZ c; |
---|
705 | |
---|
706 | c.SetLength(da+da+1); |
---|
707 | |
---|
708 | long j; |
---|
709 | |
---|
710 | for (i = 0; i < nprimes; i++) { |
---|
711 | zz_p::FFTInit(i); |
---|
712 | long p = zz_p::modulus(); |
---|
713 | |
---|
714 | div(t1, prod, p); |
---|
715 | tt = rem(t1, p); |
---|
716 | tt = InvMod(tt, p); |
---|
717 | mul(coeff, t1, tt); |
---|
718 | |
---|
719 | zz_pX A, C; |
---|
720 | |
---|
721 | conv(A, a); |
---|
722 | sqr(C, A); |
---|
723 | |
---|
724 | long m = deg(C); |
---|
725 | |
---|
726 | for (j = 0; j <= m; j++) { |
---|
727 | /* c[j] += coeff*rep(C.rep[j]) */ |
---|
728 | mul(t1, coeff, rep(C.rep[j])); |
---|
729 | add(c[j], c[j], t1); |
---|
730 | } |
---|
731 | } |
---|
732 | |
---|
733 | x.rep.SetLength(da+da+1); |
---|
734 | |
---|
735 | ZZ prod2; |
---|
736 | RightShift(prod2, prod, 1); |
---|
737 | |
---|
738 | for (j = 0; j <= da+da; j++) { |
---|
739 | rem(t1, c[j], prod); |
---|
740 | |
---|
741 | if (t1 > prod2) |
---|
742 | sub(x.rep[j], t1, prod); |
---|
743 | else |
---|
744 | x.rep[j] = t1; |
---|
745 | } |
---|
746 | |
---|
747 | x.normalize(); |
---|
748 | |
---|
749 | bak.restore(); |
---|
750 | } |
---|
751 | |
---|
752 | |
---|
753 | void sqr(ZZX& c, const ZZX& a) |
---|
754 | { |
---|
755 | if (IsZero(a)) { |
---|
756 | clear(c); |
---|
757 | return; |
---|
758 | } |
---|
759 | |
---|
760 | long maxa = MaxSize(a); |
---|
761 | |
---|
762 | long k = maxa; |
---|
763 | long s = deg(a) + 1; |
---|
764 | |
---|
765 | if (s == 1 || (k == 1 && s < 50) || (k == 2 && s < 25) || |
---|
766 | (k == 3 && s < 25) || (k == 4 && s < 10)) { |
---|
767 | |
---|
768 | PlainSqr(c, a); |
---|
769 | return; |
---|
770 | } |
---|
771 | |
---|
772 | if (s < 80 || (k < 30 && s < 150)) { |
---|
773 | KarSqr(c, a); |
---|
774 | return; |
---|
775 | } |
---|
776 | |
---|
777 | long mba = MaxBits(a); |
---|
778 | |
---|
779 | if (2*maxa >= 40 && |
---|
780 | SSRatio(deg(a), mba, deg(a), mba) < 1.75) |
---|
781 | SSSqr(c, a); |
---|
782 | else |
---|
783 | HomSqr(c, a); |
---|
784 | } |
---|
785 | |
---|
786 | |
---|
787 | void mul(ZZX& x, const ZZX& a, const ZZ& b) |
---|
788 | { |
---|
789 | ZZ t; |
---|
790 | long i, da; |
---|
791 | |
---|
792 | const ZZ *ap; |
---|
793 | ZZ* xp; |
---|
794 | |
---|
795 | if (IsZero(b)) { |
---|
796 | clear(x); |
---|
797 | return; |
---|
798 | } |
---|
799 | |
---|
800 | t = b; |
---|
801 | da = deg(a); |
---|
802 | x.rep.SetLength(da+1); |
---|
803 | ap = a.rep.elts(); |
---|
804 | xp = x.rep.elts(); |
---|
805 | |
---|
806 | for (i = 0; i <= da; i++) |
---|
807 | mul(xp[i], ap[i], t); |
---|
808 | } |
---|
809 | |
---|
810 | void mul(ZZX& x, const ZZX& a, long b) |
---|
811 | { |
---|
812 | long i, da; |
---|
813 | |
---|
814 | const ZZ *ap; |
---|
815 | ZZ* xp; |
---|
816 | |
---|
817 | if (b == 0) { |
---|
818 | clear(x); |
---|
819 | return; |
---|
820 | } |
---|
821 | |
---|
822 | da = deg(a); |
---|
823 | x.rep.SetLength(da+1); |
---|
824 | ap = a.rep.elts(); |
---|
825 | xp = x.rep.elts(); |
---|
826 | |
---|
827 | for (i = 0; i <= da; i++) |
---|
828 | mul(xp[i], ap[i], b); |
---|
829 | } |
---|
830 | |
---|
831 | |
---|
832 | |
---|
833 | |
---|
834 | void diff(ZZX& x, const ZZX& a) |
---|
835 | { |
---|
836 | long n = deg(a); |
---|
837 | long i; |
---|
838 | |
---|
839 | if (n <= 0) { |
---|
840 | clear(x); |
---|
841 | return; |
---|
842 | } |
---|
843 | |
---|
844 | if (&x != &a) |
---|
845 | x.rep.SetLength(n); |
---|
846 | |
---|
847 | for (i = 0; i <= n-1; i++) { |
---|
848 | mul(x.rep[i], a.rep[i+1], i+1); |
---|
849 | } |
---|
850 | |
---|
851 | if (&x == &a) |
---|
852 | x.rep.SetLength(n); |
---|
853 | |
---|
854 | x.normalize(); |
---|
855 | } |
---|
856 | |
---|
857 | void HomPseudoDivRem(ZZX& q, ZZX& r, const ZZX& a, const ZZX& b) |
---|
858 | { |
---|
859 | if (IsZero(b)) Error("division by zero"); |
---|
860 | |
---|
861 | long da = deg(a); |
---|
862 | long db = deg(b); |
---|
863 | |
---|
864 | if (da < db) { |
---|
865 | r = b; |
---|
866 | clear(q); |
---|
867 | return; |
---|
868 | } |
---|
869 | |
---|
870 | ZZ LC; |
---|
871 | LC = LeadCoeff(b); |
---|
872 | |
---|
873 | ZZ LC1; |
---|
874 | |
---|
875 | power(LC1, LC, da-db+1); |
---|
876 | |
---|
877 | long a_bound = NumBits(LC1) + MaxBits(a); |
---|
878 | |
---|
879 | LC1.kill(); |
---|
880 | |
---|
881 | long b_bound = MaxBits(b); |
---|
882 | |
---|
883 | zz_pBak bak; |
---|
884 | bak.save(); |
---|
885 | |
---|
886 | ZZX qq, rr; |
---|
887 | |
---|
888 | ZZ prod, t; |
---|
889 | set(prod); |
---|
890 | |
---|
891 | clear(qq); |
---|
892 | clear(rr); |
---|
893 | |
---|
894 | long i; |
---|
895 | long Qinstable, Rinstable; |
---|
896 | |
---|
897 | Qinstable = 1; |
---|
898 | Rinstable = 1; |
---|
899 | |
---|
900 | for (i = 0; ; i++) { |
---|
901 | zz_p::FFTInit(i); |
---|
902 | long p = zz_p::modulus(); |
---|
903 | |
---|
904 | |
---|
905 | if (divide(LC, p)) continue; |
---|
906 | |
---|
907 | zz_pX A, B, Q, R; |
---|
908 | |
---|
909 | conv(A, a); |
---|
910 | conv(B, b); |
---|
911 | |
---|
912 | if (!IsOne(LC)) { |
---|
913 | zz_p y; |
---|
914 | conv(y, LC); |
---|
915 | power(y, y, da-db+1); |
---|
916 | mul(A, A, y); |
---|
917 | } |
---|
918 | |
---|
919 | if (!Qinstable) { |
---|
920 | conv(Q, qq); |
---|
921 | mul(R, B, Q); |
---|
922 | sub(R, A, R); |
---|
923 | |
---|
924 | if (deg(R) >= db) |
---|
925 | Qinstable = 1; |
---|
926 | else |
---|
927 | Rinstable = CRT(rr, prod, R); |
---|
928 | } |
---|
929 | |
---|
930 | if (Qinstable) { |
---|
931 | DivRem(Q, R, A, B); |
---|
932 | t = prod; |
---|
933 | Qinstable = CRT(qq, t, Q); |
---|
934 | Rinstable = CRT(rr, prod, R); |
---|
935 | } |
---|
936 | |
---|
937 | if (!Qinstable && !Rinstable) { |
---|
938 | // stabilized...check if prod is big enough |
---|
939 | |
---|
940 | long bound1 = b_bound + MaxBits(qq) + NumBits(min(db, da-db)+1); |
---|
941 | long bound2 = MaxBits(rr); |
---|
942 | long bound = max(bound1, bound2); |
---|
943 | |
---|
944 | if (a_bound > bound) |
---|
945 | bound = a_bound; |
---|
946 | |
---|
947 | bound += 4; |
---|
948 | |
---|
949 | if (NumBits(prod) > bound) |
---|
950 | break; |
---|
951 | } |
---|
952 | } |
---|
953 | |
---|
954 | bak.restore(); |
---|
955 | |
---|
956 | q = qq; |
---|
957 | r = rr; |
---|
958 | } |
---|
959 | |
---|
960 | |
---|
961 | |
---|
962 | |
---|
963 | void HomPseudoDiv(ZZX& q, const ZZX& a, const ZZX& b) |
---|
964 | { |
---|
965 | ZZX r; |
---|
966 | HomPseudoDivRem(q, r, a, b); |
---|
967 | } |
---|
968 | |
---|
969 | void HomPseudoRem(ZZX& r, const ZZX& a, const ZZX& b) |
---|
970 | { |
---|
971 | ZZX q; |
---|
972 | HomPseudoDivRem(q, r, a, b); |
---|
973 | } |
---|
974 | |
---|
975 | void PlainPseudoDivRem(ZZX& q, ZZX& r, const ZZX& a, const ZZX& b) |
---|
976 | { |
---|
977 | long da, db, dq, i, j, LCIsOne; |
---|
978 | const ZZ *bp; |
---|
979 | ZZ *qp; |
---|
980 | ZZ *xp; |
---|
981 | |
---|
982 | |
---|
983 | ZZ s, t; |
---|
984 | |
---|
985 | da = deg(a); |
---|
986 | db = deg(b); |
---|
987 | |
---|
988 | if (db < 0) Error("ZZX: division by zero"); |
---|
989 | |
---|
990 | if (da < db) { |
---|
991 | r = a; |
---|
992 | clear(q); |
---|
993 | return; |
---|
994 | } |
---|
995 | |
---|
996 | ZZX lb; |
---|
997 | |
---|
998 | if (&q == &b) { |
---|
999 | lb = b; |
---|
1000 | bp = lb.rep.elts(); |
---|
1001 | } |
---|
1002 | else |
---|
1003 | bp = b.rep.elts(); |
---|
1004 | |
---|
1005 | ZZ LC = bp[db]; |
---|
1006 | LCIsOne = IsOne(LC); |
---|
1007 | |
---|
1008 | |
---|
1009 | vec_ZZ x; |
---|
1010 | |
---|
1011 | x = a.rep; |
---|
1012 | xp = x.elts(); |
---|
1013 | |
---|
1014 | dq = da - db; |
---|
1015 | q.rep.SetLength(dq+1); |
---|
1016 | qp = q.rep.elts(); |
---|
1017 | |
---|
1018 | if (!LCIsOne) { |
---|
1019 | t = LC; |
---|
1020 | for (i = dq-1; i >= 0; i--) { |
---|
1021 | mul(xp[i], xp[i], t); |
---|
1022 | if (i > 0) mul(t, t, LC); |
---|
1023 | } |
---|
1024 | } |
---|
1025 | |
---|
1026 | for (i = dq; i >= 0; i--) { |
---|
1027 | t = xp[i+db]; |
---|
1028 | qp[i] = t; |
---|
1029 | |
---|
1030 | for (j = db-1; j >= 0; j--) { |
---|
1031 | mul(s, t, bp[j]); |
---|
1032 | if (!LCIsOne) mul(xp[i+j], xp[i+j], LC); |
---|
1033 | sub(xp[i+j], xp[i+j], s); |
---|
1034 | } |
---|
1035 | } |
---|
1036 | |
---|
1037 | if (!LCIsOne) { |
---|
1038 | t = LC; |
---|
1039 | for (i = 1; i <= dq; i++) { |
---|
1040 | mul(qp[i], qp[i], t); |
---|
1041 | if (i < dq) mul(t, t, LC); |
---|
1042 | } |
---|
1043 | } |
---|
1044 | |
---|
1045 | |
---|
1046 | r.rep.SetLength(db); |
---|
1047 | for (i = 0; i < db; i++) |
---|
1048 | r.rep[i] = xp[i]; |
---|
1049 | r.normalize(); |
---|
1050 | } |
---|
1051 | |
---|
1052 | |
---|
1053 | void PlainPseudoDiv(ZZX& q, const ZZX& a, const ZZX& b) |
---|
1054 | { |
---|
1055 | ZZX r; |
---|
1056 | PlainPseudoDivRem(q, r, a, b); |
---|
1057 | } |
---|
1058 | |
---|
1059 | void PlainPseudoRem(ZZX& r, const ZZX& a, const ZZX& b) |
---|
1060 | { |
---|
1061 | ZZX q; |
---|
1062 | PlainPseudoDivRem(q, r, a, b); |
---|
1063 | } |
---|
1064 | |
---|
1065 | void div(ZZX& q, const ZZX& a, long b) |
---|
1066 | { |
---|
1067 | if (b == 0) Error("div: division by zero"); |
---|
1068 | |
---|
1069 | if (!divide(q, a, b)) Error("DivRem: quotient undefined over ZZ"); |
---|
1070 | } |
---|
1071 | |
---|
1072 | void div(ZZX& q, const ZZX& a, const ZZ& b) |
---|
1073 | { |
---|
1074 | if (b == 0) Error("div: division by zero"); |
---|
1075 | |
---|
1076 | if (!divide(q, a, b)) Error("DivRem: quotient undefined over ZZ"); |
---|
1077 | } |
---|
1078 | |
---|
1079 | static |
---|
1080 | void ConstDivRem(ZZX& q, ZZX& r, const ZZX& a, const ZZ& b) |
---|
1081 | { |
---|
1082 | if (b == 0) Error("DivRem: division by zero"); |
---|
1083 | |
---|
1084 | if (!divide(q, a, b)) Error("DivRem: quotient undefined over ZZ"); |
---|
1085 | |
---|
1086 | r = 0; |
---|
1087 | } |
---|
1088 | |
---|
1089 | static |
---|
1090 | void ConstRem(ZZX& r, const ZZX& a, const ZZ& b) |
---|
1091 | { |
---|
1092 | if (b == 0) Error("rem: division by zero"); |
---|
1093 | |
---|
1094 | r = 0; |
---|
1095 | } |
---|
1096 | |
---|
1097 | |
---|
1098 | |
---|
1099 | void DivRem(ZZX& q, ZZX& r, const ZZX& a, const ZZX& b) |
---|
1100 | { |
---|
1101 | long da = deg(a); |
---|
1102 | long db = deg(b); |
---|
1103 | |
---|
1104 | if (db < 0) Error("DivRem: division by zero"); |
---|
1105 | |
---|
1106 | if (da < db) { |
---|
1107 | r = a; |
---|
1108 | q = 0; |
---|
1109 | } |
---|
1110 | else if (db == 0) { |
---|
1111 | ConstDivRem(q, r, a, ConstTerm(b)); |
---|
1112 | } |
---|
1113 | else if (IsOne(LeadCoeff(b))) { |
---|
1114 | PseudoDivRem(q, r, a, b); |
---|
1115 | } |
---|
1116 | else if (LeadCoeff(b) == -1) { |
---|
1117 | ZZX b1; |
---|
1118 | negate(b1, b); |
---|
1119 | PseudoDivRem(q, r, a, b1); |
---|
1120 | negate(q, q); |
---|
1121 | } |
---|
1122 | else if (divide(q, a, b)) { |
---|
1123 | r = 0; |
---|
1124 | } |
---|
1125 | else { |
---|
1126 | ZZX q1, r1; |
---|
1127 | ZZ m; |
---|
1128 | PseudoDivRem(q1, r1, a, b); |
---|
1129 | power(m, LeadCoeff(b), da-db+1); |
---|
1130 | if (!divide(q, q1, m)) Error("DivRem: quotient not defined over ZZ"); |
---|
1131 | if (!divide(r, r1, m)) Error("DivRem: remainder not defined over ZZ"); |
---|
1132 | } |
---|
1133 | } |
---|
1134 | |
---|
1135 | void div(ZZX& q, const ZZX& a, const ZZX& b) |
---|
1136 | { |
---|
1137 | long da = deg(a); |
---|
1138 | long db = deg(b); |
---|
1139 | |
---|
1140 | if (db < 0) Error("div: division by zero"); |
---|
1141 | |
---|
1142 | if (da < db) { |
---|
1143 | q = 0; |
---|
1144 | } |
---|
1145 | else if (db == 0) { |
---|
1146 | div(q, a, ConstTerm(b)); |
---|
1147 | } |
---|
1148 | else if (IsOne(LeadCoeff(b))) { |
---|
1149 | PseudoDiv(q, a, b); |
---|
1150 | } |
---|
1151 | else if (LeadCoeff(b) == -1) { |
---|
1152 | ZZX b1; |
---|
1153 | negate(b1, b); |
---|
1154 | PseudoDiv(q, a, b1); |
---|
1155 | negate(q, q); |
---|
1156 | } |
---|
1157 | else if (divide(q, a, b)) { |
---|
1158 | |
---|
1159 | // nothing to do |
---|
1160 | |
---|
1161 | } |
---|
1162 | else { |
---|
1163 | ZZX q1; |
---|
1164 | ZZ m; |
---|
1165 | PseudoDiv(q1, a, b); |
---|
1166 | power(m, LeadCoeff(b), da-db+1); |
---|
1167 | if (!divide(q, q1, m)) Error("div: quotient not defined over ZZ"); |
---|
1168 | } |
---|
1169 | } |
---|
1170 | |
---|
1171 | void rem(ZZX& r, const ZZX& a, const ZZX& b) |
---|
1172 | { |
---|
1173 | long da = deg(a); |
---|
1174 | long db = deg(b); |
---|
1175 | |
---|
1176 | if (db < 0) Error("rem: division by zero"); |
---|
1177 | |
---|
1178 | if (da < db) { |
---|
1179 | r = a; |
---|
1180 | } |
---|
1181 | else if (db == 0) { |
---|
1182 | ConstRem(r, a, ConstTerm(b)); |
---|
1183 | } |
---|
1184 | else if (IsOne(LeadCoeff(b))) { |
---|
1185 | PseudoRem(r, a, b); |
---|
1186 | } |
---|
1187 | else if (LeadCoeff(b) == -1) { |
---|
1188 | ZZX b1; |
---|
1189 | negate(b1, b); |
---|
1190 | PseudoRem(r, a, b1); |
---|
1191 | } |
---|
1192 | else if (divide(a, b)) { |
---|
1193 | r = 0; |
---|
1194 | } |
---|
1195 | else { |
---|
1196 | ZZX r1; |
---|
1197 | ZZ m; |
---|
1198 | PseudoRem(r1, a, b); |
---|
1199 | power(m, LeadCoeff(b), da-db+1); |
---|
1200 | if (!divide(r, r1, m)) Error("rem: remainder not defined over ZZ"); |
---|
1201 | } |
---|
1202 | } |
---|
1203 | |
---|
1204 | long HomDivide(ZZX& q, const ZZX& a, const ZZX& b) |
---|
1205 | { |
---|
1206 | if (IsZero(b)) { |
---|
1207 | if (IsZero(a)) { |
---|
1208 | clear(q); |
---|
1209 | return 1; |
---|
1210 | } |
---|
1211 | else |
---|
1212 | return 0; |
---|
1213 | } |
---|
1214 | |
---|
1215 | if (IsZero(a)) { |
---|
1216 | clear(q); |
---|
1217 | return 1; |
---|
1218 | } |
---|
1219 | |
---|
1220 | if (deg(b) == 0) { |
---|
1221 | return divide(q, a, ConstTerm(b)); |
---|
1222 | } |
---|
1223 | |
---|
1224 | if (deg(a) < deg(b)) return 0; |
---|
1225 | |
---|
1226 | ZZ ca, cb, cq; |
---|
1227 | |
---|
1228 | content(ca, a); |
---|
1229 | content(cb, b); |
---|
1230 | |
---|
1231 | if (!divide(cq, ca, cb)) return 0; |
---|
1232 | |
---|
1233 | ZZX aa, bb; |
---|
1234 | |
---|
1235 | divide(aa, a, ca); |
---|
1236 | divide(bb, b, cb); |
---|
1237 | |
---|
1238 | if (!divide(LeadCoeff(aa), LeadCoeff(bb))) |
---|
1239 | return 0; |
---|
1240 | |
---|
1241 | if (!divide(ConstTerm(aa), ConstTerm(bb))) |
---|
1242 | return 0; |
---|
1243 | |
---|
1244 | zz_pBak bak; |
---|
1245 | bak.save(); |
---|
1246 | |
---|
1247 | ZZX qq; |
---|
1248 | |
---|
1249 | ZZ prod; |
---|
1250 | set(prod); |
---|
1251 | |
---|
1252 | clear(qq); |
---|
1253 | long res = 1; |
---|
1254 | long Qinstable = 1; |
---|
1255 | |
---|
1256 | |
---|
1257 | long a_bound = MaxBits(aa); |
---|
1258 | long b_bound = MaxBits(bb); |
---|
1259 | |
---|
1260 | |
---|
1261 | long i; |
---|
1262 | for (i = 0; ; i++) { |
---|
1263 | zz_p::FFTInit(i); |
---|
1264 | long p = zz_p::modulus(); |
---|
1265 | |
---|
1266 | if (divide(LeadCoeff(bb), p)) continue; |
---|
1267 | |
---|
1268 | zz_pX A, B, Q, R; |
---|
1269 | |
---|
1270 | conv(A, aa); |
---|
1271 | conv(B, bb); |
---|
1272 | |
---|
1273 | if (!Qinstable) { |
---|
1274 | conv(Q, qq); |
---|
1275 | mul(R, B, Q); |
---|
1276 | sub(R, A, R); |
---|
1277 | |
---|
1278 | if (deg(R) >= deg(B)) |
---|
1279 | Qinstable = 1; |
---|
1280 | else if (!IsZero(R)) { |
---|
1281 | res = 0; |
---|
1282 | break; |
---|
1283 | } |
---|
1284 | else |
---|
1285 | mul(prod, prod, p); |
---|
1286 | } |
---|
1287 | |
---|
1288 | if (Qinstable) { |
---|
1289 | if (!divide(Q, A, B)) { |
---|
1290 | res = 0; |
---|
1291 | break; |
---|
1292 | } |
---|
1293 | |
---|
1294 | Qinstable = CRT(qq, prod, Q); |
---|
1295 | } |
---|
1296 | |
---|
1297 | if (!Qinstable) { |
---|
1298 | // stabilized...check if prod is big enough |
---|
1299 | |
---|
1300 | long bound = b_bound + MaxBits(qq) + |
---|
1301 | NumBits(min(deg(bb), deg(qq)) + 1); |
---|
1302 | |
---|
1303 | if (a_bound > bound) |
---|
1304 | bound = a_bound; |
---|
1305 | |
---|
1306 | bound += 3; |
---|
1307 | |
---|
1308 | if (NumBits(prod) > bound) |
---|
1309 | break; |
---|
1310 | } |
---|
1311 | } |
---|
1312 | |
---|
1313 | bak.restore(); |
---|
1314 | |
---|
1315 | if (res) mul(q, qq, cq); |
---|
1316 | return res; |
---|
1317 | |
---|
1318 | } |
---|
1319 | |
---|
1320 | |
---|
1321 | long HomDivide(const ZZX& a, const ZZX& b) |
---|
1322 | { |
---|
1323 | if (deg(b) == 0) { |
---|
1324 | return divide(a, ConstTerm(b)); |
---|
1325 | } |
---|
1326 | else { |
---|
1327 | ZZX q; |
---|
1328 | return HomDivide(q, a, b); |
---|
1329 | } |
---|
1330 | } |
---|
1331 | |
---|
1332 | long PlainDivide(ZZX& qq, const ZZX& aa, const ZZX& bb) |
---|
1333 | { |
---|
1334 | if (IsZero(bb)) { |
---|
1335 | if (IsZero(aa)) { |
---|
1336 | clear(qq); |
---|
1337 | return 1; |
---|
1338 | } |
---|
1339 | else |
---|
1340 | return 0; |
---|
1341 | } |
---|
1342 | |
---|
1343 | if (deg(bb) == 0) { |
---|
1344 | return divide(qq, aa, ConstTerm(bb)); |
---|
1345 | } |
---|
1346 | |
---|
1347 | long da, db, dq, i, j, LCIsOne; |
---|
1348 | const ZZ *bp; |
---|
1349 | ZZ *qp; |
---|
1350 | ZZ *xp; |
---|
1351 | |
---|
1352 | |
---|
1353 | ZZ s, t; |
---|
1354 | |
---|
1355 | da = deg(aa); |
---|
1356 | db = deg(bb); |
---|
1357 | |
---|
1358 | if (da < db) { |
---|
1359 | return 0; |
---|
1360 | } |
---|
1361 | |
---|
1362 | ZZ ca, cb, cq; |
---|
1363 | |
---|
1364 | content(ca, aa); |
---|
1365 | content(cb, bb); |
---|
1366 | |
---|
1367 | if (!divide(cq, ca, cb)) { |
---|
1368 | return 0; |
---|
1369 | } |
---|
1370 | |
---|
1371 | |
---|
1372 | ZZX a, b, q; |
---|
1373 | |
---|
1374 | divide(a, aa, ca); |
---|
1375 | divide(b, bb, cb); |
---|
1376 | |
---|
1377 | if (!divide(LeadCoeff(a), LeadCoeff(b))) |
---|
1378 | return 0; |
---|
1379 | |
---|
1380 | if (!divide(ConstTerm(a), ConstTerm(b))) |
---|
1381 | return 0; |
---|
1382 | |
---|
1383 | long coeff_bnd = MaxBits(a) + (NumBits(da+1)+1)/2 + (da-db); |
---|
1384 | |
---|
1385 | bp = b.rep.elts(); |
---|
1386 | |
---|
1387 | ZZ LC; |
---|
1388 | LC = bp[db]; |
---|
1389 | |
---|
1390 | LCIsOne = IsOne(LC); |
---|
1391 | |
---|
1392 | xp = a.rep.elts(); |
---|
1393 | |
---|
1394 | dq = da - db; |
---|
1395 | q.rep.SetLength(dq+1); |
---|
1396 | qp = q.rep.elts(); |
---|
1397 | |
---|
1398 | for (i = dq; i >= 0; i--) { |
---|
1399 | if (!LCIsOne) { |
---|
1400 | if (!divide(t, xp[i+db], LC)) |
---|
1401 | return 0; |
---|
1402 | } |
---|
1403 | else |
---|
1404 | t = xp[i+db]; |
---|
1405 | |
---|
1406 | if (NumBits(t) > coeff_bnd) return 0; |
---|
1407 | |
---|
1408 | qp[i] = t; |
---|
1409 | |
---|
1410 | for (j = db-1; j >= 0; j--) { |
---|
1411 | mul(s, t, bp[j]); |
---|
1412 | sub(xp[i+j], xp[i+j], s); |
---|
1413 | } |
---|
1414 | } |
---|
1415 | |
---|
1416 | for (i = 0; i < db; i++) |
---|
1417 | if (!IsZero(xp[i])) |
---|
1418 | return 0; |
---|
1419 | |
---|
1420 | mul(qq, q, cq); |
---|
1421 | return 1; |
---|
1422 | } |
---|
1423 | |
---|
1424 | long PlainDivide(const ZZX& a, const ZZX& b) |
---|
1425 | { |
---|
1426 | if (deg(b) == 0) |
---|
1427 | return divide(a, ConstTerm(b)); |
---|
1428 | else { |
---|
1429 | ZZX q; |
---|
1430 | return PlainDivide(q, a, b); |
---|
1431 | } |
---|
1432 | } |
---|
1433 | |
---|
1434 | |
---|
1435 | long divide(ZZX& q, const ZZX& a, const ZZX& b) |
---|
1436 | { |
---|
1437 | long da = deg(a); |
---|
1438 | long db = deg(b); |
---|
1439 | |
---|
1440 | if (db <= 8 || da-db <= 8) |
---|
1441 | return PlainDivide(q, a, b); |
---|
1442 | else |
---|
1443 | return HomDivide(q, a, b); |
---|
1444 | } |
---|
1445 | |
---|
1446 | long divide(const ZZX& a, const ZZX& b) |
---|
1447 | { |
---|
1448 | long da = deg(a); |
---|
1449 | long db = deg(b); |
---|
1450 | |
---|
1451 | if (db <= 8 || da-db <= 8) |
---|
1452 | return PlainDivide(a, b); |
---|
1453 | else |
---|
1454 | return HomDivide(a, b); |
---|
1455 | } |
---|
1456 | |
---|
1457 | |
---|
1458 | |
---|
1459 | |
---|
1460 | |
---|
1461 | |
---|
1462 | |
---|
1463 | long divide(ZZX& q, const ZZX& a, const ZZ& b) |
---|
1464 | { |
---|
1465 | if (IsZero(b)) { |
---|
1466 | if (IsZero(a)) { |
---|
1467 | clear(q); |
---|
1468 | return 1; |
---|
1469 | } |
---|
1470 | else |
---|
1471 | return 0; |
---|
1472 | } |
---|
1473 | |
---|
1474 | if (IsOne(b)) { |
---|
1475 | q = a; |
---|
1476 | return 1; |
---|
1477 | } |
---|
1478 | |
---|
1479 | if (b == -1) { |
---|
1480 | negate(q, a); |
---|
1481 | return 1; |
---|
1482 | } |
---|
1483 | |
---|
1484 | long n = a.rep.length(); |
---|
1485 | vec_ZZ res(INIT_SIZE, n); |
---|
1486 | long i; |
---|
1487 | |
---|
1488 | for (i = 0; i < n; i++) { |
---|
1489 | if (!divide(res[i], a.rep[i], b)) |
---|
1490 | return 0; |
---|
1491 | } |
---|
1492 | |
---|
1493 | q.rep = res; |
---|
1494 | return 1; |
---|
1495 | } |
---|
1496 | |
---|
1497 | long divide(const ZZX& a, const ZZ& b) |
---|
1498 | { |
---|
1499 | if (IsZero(b)) return IsZero(a); |
---|
1500 | |
---|
1501 | if (IsOne(b) || b == -1) { |
---|
1502 | return 1; |
---|
1503 | } |
---|
1504 | |
---|
1505 | long n = a.rep.length(); |
---|
1506 | long i; |
---|
1507 | |
---|
1508 | for (i = 0; i < n; i++) { |
---|
1509 | if (!divide(a.rep[i], b)) |
---|
1510 | return 0; |
---|
1511 | } |
---|
1512 | |
---|
1513 | return 1; |
---|
1514 | } |
---|
1515 | |
---|
1516 | long divide(ZZX& q, const ZZX& a, long b) |
---|
1517 | { |
---|
1518 | if (b == 0) { |
---|
1519 | if (IsZero(a)) { |
---|
1520 | clear(q); |
---|
1521 | return 1; |
---|
1522 | } |
---|
1523 | else |
---|
1524 | return 0; |
---|
1525 | } |
---|
1526 | |
---|
1527 | if (b == 1) { |
---|
1528 | q = a; |
---|
1529 | return 1; |
---|
1530 | } |
---|
1531 | |
---|
1532 | if (b == -1) { |
---|
1533 | negate(q, a); |
---|
1534 | return 1; |
---|
1535 | } |
---|
1536 | |
---|
1537 | long n = a.rep.length(); |
---|
1538 | vec_ZZ res(INIT_SIZE, n); |
---|
1539 | long i; |
---|
1540 | |
---|
1541 | for (i = 0; i < n; i++) { |
---|
1542 | if (!divide(res[i], a.rep[i], b)) |
---|
1543 | return 0; |
---|
1544 | } |
---|
1545 | |
---|
1546 | q.rep = res; |
---|
1547 | return 1; |
---|
1548 | } |
---|
1549 | |
---|
1550 | long divide(const ZZX& a, long b) |
---|
1551 | { |
---|
1552 | if (b == 0) return IsZero(a); |
---|
1553 | if (b == 1 || b == -1) { |
---|
1554 | return 1; |
---|
1555 | } |
---|
1556 | |
---|
1557 | long n = a.rep.length(); |
---|
1558 | long i; |
---|
1559 | |
---|
1560 | for (i = 0; i < n; i++) { |
---|
1561 | if (!divide(a.rep[i], b)) |
---|
1562 | return 0; |
---|
1563 | } |
---|
1564 | |
---|
1565 | return 1; |
---|
1566 | } |
---|
1567 | |
---|
1568 | |
---|
1569 | |
---|
1570 | void content(ZZ& d, const ZZX& f) |
---|
1571 | { |
---|
1572 | ZZ res; |
---|
1573 | long i; |
---|
1574 | |
---|
1575 | clear(res); |
---|
1576 | for (i = 0; i <= deg(f); i++) { |
---|
1577 | GCD(res, res, f.rep[i]); |
---|
1578 | if (IsOne(res)) break; |
---|
1579 | } |
---|
1580 | |
---|
1581 | if (sign(LeadCoeff(f)) < 0) negate(res, res); |
---|
1582 | d = res; |
---|
1583 | } |
---|
1584 | |
---|
1585 | void PrimitivePart(ZZX& pp, const ZZX& f) |
---|
1586 | { |
---|
1587 | if (IsZero(f)) { |
---|
1588 | clear(pp); |
---|
1589 | return; |
---|
1590 | } |
---|
1591 | |
---|
1592 | ZZ d; |
---|
1593 | |
---|
1594 | content(d, f); |
---|
1595 | divide(pp, f, d); |
---|
1596 | } |
---|
1597 | |
---|
1598 | |
---|
1599 | static |
---|
1600 | void BalCopy(ZZX& g, const zz_pX& G) |
---|
1601 | { |
---|
1602 | long p = zz_p::modulus(); |
---|
1603 | long p2 = p >> 1; |
---|
1604 | long n = G.rep.length(); |
---|
1605 | long i; |
---|
1606 | long t; |
---|
1607 | |
---|
1608 | g.rep.SetLength(n); |
---|
1609 | for (i = 0; i < n; i++) { |
---|
1610 | t = rep(G.rep[i]); |
---|
1611 | if (t > p2) t = t - p; |
---|
1612 | conv(g.rep[i], t); |
---|
1613 | } |
---|
1614 | } |
---|
1615 | |
---|
1616 | |
---|
1617 | |
---|
1618 | void GCD(ZZX& d, const ZZX& a, const ZZX& b) |
---|
1619 | { |
---|
1620 | if (IsZero(a)) { |
---|
1621 | d = b; |
---|
1622 | if (sign(LeadCoeff(d)) < 0) negate(d, d); |
---|
1623 | return; |
---|
1624 | } |
---|
1625 | |
---|
1626 | if (IsZero(b)) { |
---|
1627 | d = a; |
---|
1628 | if (sign(LeadCoeff(d)) < 0) negate(d, d); |
---|
1629 | return; |
---|
1630 | } |
---|
1631 | |
---|
1632 | ZZ c1, c2, c; |
---|
1633 | ZZX f1, f2; |
---|
1634 | |
---|
1635 | content(c1, a); |
---|
1636 | divide(f1, a, c1); |
---|
1637 | |
---|
1638 | content(c2, b); |
---|
1639 | divide(f2, b, c2); |
---|
1640 | |
---|
1641 | GCD(c, c1, c2); |
---|
1642 | |
---|
1643 | ZZ ld; |
---|
1644 | GCD(ld, LeadCoeff(f1), LeadCoeff(f2)); |
---|
1645 | |
---|
1646 | ZZX g, h, res; |
---|
1647 | |
---|
1648 | ZZ prod; |
---|
1649 | set(prod); |
---|
1650 | |
---|
1651 | zz_pBak bak; |
---|
1652 | bak.save(); |
---|
1653 | |
---|
1654 | |
---|
1655 | long FirstTime = 1; |
---|
1656 | |
---|
1657 | long i; |
---|
1658 | for (i = 0; ;i++) { |
---|
1659 | zz_p::FFTInit(i); |
---|
1660 | long p = zz_p::modulus(); |
---|
1661 | |
---|
1662 | if (divide(LeadCoeff(f1), p) || divide(LeadCoeff(f2), p)) continue; |
---|
1663 | |
---|
1664 | zz_pX G, F1, F2; |
---|
1665 | zz_p LD; |
---|
1666 | |
---|
1667 | conv(F1, f1); |
---|
1668 | conv(F2, f2); |
---|
1669 | conv(LD, ld); |
---|
1670 | |
---|
1671 | GCD(G, F1, F2); |
---|
1672 | mul(G, G, LD); |
---|
1673 | |
---|
1674 | |
---|
1675 | if (deg(G) == 0) { |
---|
1676 | set(res); |
---|
1677 | break; |
---|
1678 | } |
---|
1679 | |
---|
1680 | if (FirstTime || deg(G) < deg(g)) { |
---|
1681 | FirstTime = 0; |
---|
1682 | conv(prod, p); |
---|
1683 | BalCopy(g, G); |
---|
1684 | } |
---|
1685 | else if (deg(G) > deg(g)) |
---|
1686 | continue; |
---|
1687 | else if (!CRT(g, prod, G)) { |
---|
1688 | PrimitivePart(res, g); |
---|
1689 | if (divide(f1, res) && divide(f2, res)) |
---|
1690 | break; |
---|
1691 | } |
---|
1692 | |
---|
1693 | } |
---|
1694 | |
---|
1695 | bak.restore(); |
---|
1696 | |
---|
1697 | mul(d, res, c); |
---|
1698 | if (sign(LeadCoeff(d)) < 0) negate(d, d); |
---|
1699 | } |
---|
1700 | |
---|
1701 | void trunc(ZZX& x, const ZZX& a, long m) |
---|
1702 | |
---|
1703 | // x = a % X^m, output may alias input |
---|
1704 | |
---|
1705 | { |
---|
1706 | if (m < 0) Error("trunc: bad args"); |
---|
1707 | |
---|
1708 | if (&x == &a) { |
---|
1709 | if (x.rep.length() > m) { |
---|
1710 | x.rep.SetLength(m); |
---|
1711 | x.normalize(); |
---|
1712 | } |
---|
1713 | } |
---|
1714 | else { |
---|
1715 | long n; |
---|
1716 | long i; |
---|
1717 | ZZ* xp; |
---|
1718 | const ZZ* ap; |
---|
1719 | |
---|
1720 | n = min(a.rep.length(), m); |
---|
1721 | x.rep.SetLength(n); |
---|
1722 | |
---|
1723 | xp = x.rep.elts(); |
---|
1724 | ap = a.rep.elts(); |
---|
1725 | |
---|
1726 | for (i = 0; i < n; i++) xp[i] = ap[i]; |
---|
1727 | |
---|
1728 | x.normalize(); |
---|
1729 | } |
---|
1730 | } |
---|
1731 | |
---|
1732 | |
---|
1733 | |
---|
1734 | void LeftShift(ZZX& x, const ZZX& a, long n) |
---|
1735 | { |
---|
1736 | if (n < 0) { |
---|
1737 | if (n < -NTL_MAX_LONG) Error("overflow in LeftShift"); |
---|
1738 | RightShift(x, a, -n); |
---|
1739 | return; |
---|
1740 | } |
---|
1741 | |
---|
1742 | if (n >= (1L << (NTL_BITS_PER_LONG-4))) |
---|
1743 | Error("overflow in LeftShift"); |
---|
1744 | |
---|
1745 | if (IsZero(a)) { |
---|
1746 | clear(x); |
---|
1747 | return; |
---|
1748 | } |
---|
1749 | |
---|
1750 | long m = a.rep.length(); |
---|
1751 | |
---|
1752 | x.rep.SetLength(m+n); |
---|
1753 | |
---|
1754 | long i; |
---|
1755 | for (i = m-1; i >= 0; i--) |
---|
1756 | x.rep[i+n] = a.rep[i]; |
---|
1757 | |
---|
1758 | for (i = 0; i < n; i++) |
---|
1759 | clear(x.rep[i]); |
---|
1760 | } |
---|
1761 | |
---|
1762 | |
---|
1763 | void RightShift(ZZX& x, const ZZX& a, long n) |
---|
1764 | { |
---|
1765 | if (n < 0) { |
---|
1766 | if (n < -NTL_MAX_LONG) Error("overflow in RightShift"); |
---|
1767 | LeftShift(x, a, -n); |
---|
1768 | return; |
---|
1769 | } |
---|
1770 | |
---|
1771 | long da = deg(a); |
---|
1772 | long i; |
---|
1773 | |
---|
1774 | if (da < n) { |
---|
1775 | clear(x); |
---|
1776 | return; |
---|
1777 | } |
---|
1778 | |
---|
1779 | if (&x != &a) |
---|
1780 | x.rep.SetLength(da-n+1); |
---|
1781 | |
---|
1782 | for (i = 0; i <= da-n; i++) |
---|
1783 | x.rep[i] = a.rep[i+n]; |
---|
1784 | |
---|
1785 | if (&x == &a) |
---|
1786 | x.rep.SetLength(da-n+1); |
---|
1787 | |
---|
1788 | x.normalize(); |
---|
1789 | } |
---|
1790 | |
---|
1791 | |
---|
1792 | void TraceVec(vec_ZZ& S, const ZZX& ff) |
---|
1793 | { |
---|
1794 | if (!IsOne(LeadCoeff(ff))) |
---|
1795 | Error("TraceVec: bad args"); |
---|
1796 | |
---|
1797 | ZZX f; |
---|
1798 | f = ff; |
---|
1799 | |
---|
1800 | long n = deg(f); |
---|
1801 | |
---|
1802 | S.SetLength(n); |
---|
1803 | |
---|
1804 | if (n == 0) |
---|
1805 | return; |
---|
1806 | |
---|
1807 | long k, i; |
---|
1808 | ZZ acc, t; |
---|
1809 | |
---|
1810 | S[0] = n; |
---|
1811 | |
---|
1812 | for (k = 1; k < n; k++) { |
---|
1813 | mul(acc, f.rep[n-k], k); |
---|
1814 | |
---|
1815 | for (i = 1; i < k; i++) { |
---|
1816 | mul(t, f.rep[n-i], S[k-i]); |
---|
1817 | add(acc, acc, t); |
---|
1818 | } |
---|
1819 | |
---|
1820 | negate(S[k], acc); |
---|
1821 | } |
---|
1822 | |
---|
1823 | } |
---|
1824 | |
---|
1825 | static |
---|
1826 | void EuclLength(ZZ& l, const ZZX& a) |
---|
1827 | { |
---|
1828 | long n = a.rep.length(); |
---|
1829 | long i; |
---|
1830 | |
---|
1831 | ZZ sum, t; |
---|
1832 | |
---|
1833 | clear(sum); |
---|
1834 | for (i = 0; i < n; i++) { |
---|
1835 | sqr(t, a.rep[i]); |
---|
1836 | add(sum, sum, t); |
---|
1837 | } |
---|
1838 | |
---|
1839 | if (sum > 1) { |
---|
1840 | SqrRoot(l, sum); |
---|
1841 | add(l, l, 1); |
---|
1842 | } |
---|
1843 | else |
---|
1844 | l = sum; |
---|
1845 | } |
---|
1846 | |
---|
1847 | |
---|
1848 | |
---|
1849 | static |
---|
1850 | long ResBound(const ZZX& a, const ZZX& b) |
---|
1851 | { |
---|
1852 | if (IsZero(a) || IsZero(b)) |
---|
1853 | return 0; |
---|
1854 | |
---|
1855 | ZZ t1, t2, t; |
---|
1856 | EuclLength(t1, a); |
---|
1857 | EuclLength(t2, b); |
---|
1858 | power(t1, t1, deg(b)); |
---|
1859 | power(t2, t2, deg(a)); |
---|
1860 | mul(t, t1, t2); |
---|
1861 | return NumBits(t); |
---|
1862 | } |
---|
1863 | |
---|
1864 | |
---|
1865 | |
---|
1866 | void resultant(ZZ& rres, const ZZX& a, const ZZX& b, long deterministic) |
---|
1867 | { |
---|
1868 | if (IsZero(a) || IsZero(b)) { |
---|
1869 | clear(rres); |
---|
1870 | return; |
---|
1871 | } |
---|
1872 | |
---|
1873 | zz_pBak zbak; |
---|
1874 | zbak.save(); |
---|
1875 | |
---|
1876 | ZZ_pBak Zbak; |
---|
1877 | Zbak.save(); |
---|
1878 | |
---|
1879 | long instable = 1; |
---|
1880 | |
---|
1881 | long bound = 2+ResBound(a, b); |
---|
1882 | |
---|
1883 | long gp_cnt = 0; |
---|
1884 | |
---|
1885 | ZZ res, prod; |
---|
1886 | |
---|
1887 | clear(res); |
---|
1888 | set(prod); |
---|
1889 | |
---|
1890 | |
---|
1891 | long i; |
---|
1892 | for (i = 0; ; i++) { |
---|
1893 | if (NumBits(prod) > bound) |
---|
1894 | break; |
---|
1895 | |
---|
1896 | if (!deterministic && |
---|
1897 | !instable && bound > 1000 && NumBits(prod) < 0.25*bound) { |
---|
1898 | |
---|
1899 | ZZ P; |
---|
1900 | |
---|
1901 | |
---|
1902 | long plen = 90 + NumBits(max(bound, NumBits(res))); |
---|
1903 | |
---|
1904 | do { |
---|
1905 | GenPrime(P, plen, 90 + 2*NumBits(gp_cnt++)); |
---|
1906 | } |
---|
1907 | while (divide(LeadCoeff(a), P) || divide(LeadCoeff(b), P)); |
---|
1908 | |
---|
1909 | ZZ_p::init(P); |
---|
1910 | |
---|
1911 | ZZ_pX A, B; |
---|
1912 | conv(A, a); |
---|
1913 | conv(B, b); |
---|
1914 | |
---|
1915 | ZZ_p t; |
---|
1916 | resultant(t, A, B); |
---|
1917 | |
---|
1918 | if (CRT(res, prod, rep(t), P)) |
---|
1919 | instable = 1; |
---|
1920 | else |
---|
1921 | break; |
---|
1922 | } |
---|
1923 | |
---|
1924 | |
---|
1925 | zz_p::FFTInit(i); |
---|
1926 | long p = zz_p::modulus(); |
---|
1927 | if (divide(LeadCoeff(a), p) || divide(LeadCoeff(b), p)) |
---|
1928 | continue; |
---|
1929 | |
---|
1930 | zz_pX A, B; |
---|
1931 | conv(A, a); |
---|
1932 | conv(B, b); |
---|
1933 | |
---|
1934 | zz_p t; |
---|
1935 | resultant(t, A, B); |
---|
1936 | |
---|
1937 | instable = CRT(res, prod, rep(t), p); |
---|
1938 | } |
---|
1939 | |
---|
1940 | rres = res; |
---|
1941 | |
---|
1942 | zbak.restore(); |
---|
1943 | Zbak.restore(); |
---|
1944 | } |
---|
1945 | |
---|
1946 | |
---|
1947 | |
---|
1948 | |
---|
1949 | void MinPolyMod(ZZX& gg, const ZZX& a, const ZZX& f) |
---|
1950 | |
---|
1951 | { |
---|
1952 | if (!IsOne(LeadCoeff(f)) || deg(f) < 1 || deg(a) >= deg(f)) |
---|
1953 | Error("MinPolyMod: bad args"); |
---|
1954 | |
---|
1955 | if (IsZero(a)) { |
---|
1956 | SetX(gg); |
---|
1957 | return; |
---|
1958 | } |
---|
1959 | |
---|
1960 | ZZ_pBak Zbak; |
---|
1961 | Zbak.save(); |
---|
1962 | zz_pBak zbak; |
---|
1963 | zbak.save(); |
---|
1964 | |
---|
1965 | long n = deg(f); |
---|
1966 | |
---|
1967 | long instable = 1; |
---|
1968 | |
---|
1969 | long gp_cnt = 0; |
---|
1970 | |
---|
1971 | ZZ prod; |
---|
1972 | ZZX g; |
---|
1973 | |
---|
1974 | clear(g); |
---|
1975 | set(prod); |
---|
1976 | |
---|
1977 | long bound = -1; |
---|
1978 | |
---|
1979 | long i; |
---|
1980 | for (i = 0; ; i++) { |
---|
1981 | if (deg(g) == n) { |
---|
1982 | if (bound < 0) |
---|
1983 | bound = 2+CharPolyBound(a, f); |
---|
1984 | |
---|
1985 | if (NumBits(prod) > bound) |
---|
1986 | break; |
---|
1987 | } |
---|
1988 | |
---|
1989 | if (!instable && |
---|
1990 | (deg(g) < n || |
---|
1991 | (deg(g) == n && bound > 1000 && NumBits(prod) < 0.75*bound))) { |
---|
1992 | |
---|
1993 | // guarantees 2^{-80} error probability |
---|
1994 | long plen = 90 + max( 2*NumBits(n) + NumBits(MaxBits(f)), |
---|
1995 | max( NumBits(n) + NumBits(MaxBits(a)), |
---|
1996 | NumBits(MaxBits(g)) )); |
---|
1997 | |
---|
1998 | ZZ P; |
---|
1999 | GenPrime(P, plen, 90 + 2*NumBits(gp_cnt++)); |
---|
2000 | ZZ_p::init(P); |
---|
2001 | |
---|
2002 | |
---|
2003 | ZZ_pX A, F, G; |
---|
2004 | conv(A, a); |
---|
2005 | conv(F, f); |
---|
2006 | conv(G, g); |
---|
2007 | |
---|
2008 | ZZ_pXModulus FF; |
---|
2009 | build(FF, F); |
---|
2010 | |
---|
2011 | ZZ_pX H; |
---|
2012 | CompMod(H, G, A, FF); |
---|
2013 | |
---|
2014 | if (IsZero(H)) |
---|
2015 | break; |
---|
2016 | |
---|
2017 | instable = 1; |
---|
2018 | } |
---|
2019 | |
---|
2020 | zz_p::FFTInit(i); |
---|
2021 | |
---|
2022 | zz_pX A, F; |
---|
2023 | conv(A, a); |
---|
2024 | conv(F, f); |
---|
2025 | |
---|
2026 | zz_pXModulus FF; |
---|
2027 | build(FF, F); |
---|
2028 | |
---|
2029 | zz_pX G; |
---|
2030 | MinPolyMod(G, A, FF); |
---|
2031 | |
---|
2032 | if (deg(G) < deg(g)) |
---|
2033 | continue; |
---|
2034 | |
---|
2035 | if (deg(G) > deg(g)) { |
---|
2036 | clear(g); |
---|
2037 | set(prod); |
---|
2038 | } |
---|
2039 | |
---|
2040 | instable = CRT(g, prod, G); |
---|
2041 | } |
---|
2042 | |
---|
2043 | gg = g; |
---|
2044 | |
---|
2045 | Zbak.restore(); |
---|
2046 | zbak.restore(); |
---|
2047 | } |
---|
2048 | |
---|
2049 | |
---|
2050 | void XGCD(ZZ& rr, ZZX& ss, ZZX& tt, const ZZX& a, const ZZX& b, |
---|
2051 | long deterministic) |
---|
2052 | { |
---|
2053 | ZZ r; |
---|
2054 | |
---|
2055 | resultant(r, a, b, deterministic); |
---|
2056 | |
---|
2057 | if (IsZero(r)) { |
---|
2058 | clear(rr); |
---|
2059 | return; |
---|
2060 | } |
---|
2061 | |
---|
2062 | zz_pBak bak; |
---|
2063 | bak.save(); |
---|
2064 | |
---|
2065 | long i; |
---|
2066 | long instable = 1; |
---|
2067 | |
---|
2068 | ZZ tmp; |
---|
2069 | ZZ prod; |
---|
2070 | ZZX s, t; |
---|
2071 | |
---|
2072 | set(prod); |
---|
2073 | clear(s); |
---|
2074 | clear(t); |
---|
2075 | |
---|
2076 | for (i = 0; ; i++) { |
---|
2077 | zz_p::FFTInit(i); |
---|
2078 | long p = zz_p::modulus(); |
---|
2079 | |
---|
2080 | if (divide(LeadCoeff(a), p) || divide(LeadCoeff(b), p) || divide(r, p)) |
---|
2081 | continue; |
---|
2082 | |
---|
2083 | zz_p R; |
---|
2084 | conv(R, r); |
---|
2085 | |
---|
2086 | zz_pX D, S, T, A, B; |
---|
2087 | conv(A, a); |
---|
2088 | conv(B, b); |
---|
2089 | |
---|
2090 | if (!instable) { |
---|
2091 | conv(S, s); |
---|
2092 | conv(T, t); |
---|
2093 | zz_pX t1, t2; |
---|
2094 | mul(t1, A, S); |
---|
2095 | mul(t2, B, T); |
---|
2096 | add(t1, t1, t2); |
---|
2097 | |
---|
2098 | if (deg(t1) == 0 && ConstTerm(t1) == R) |
---|
2099 | mul(prod, prod, p); |
---|
2100 | else |
---|
2101 | instable = 1; |
---|
2102 | } |
---|
2103 | |
---|
2104 | if (instable) { |
---|
2105 | XGCD(D, S, T, A, B); |
---|
2106 | |
---|
2107 | mul(S, S, R); |
---|
2108 | mul(T, T, R); |
---|
2109 | |
---|
2110 | tmp = prod; |
---|
2111 | long Sinstable = CRT(s, tmp, S); |
---|
2112 | long Tinstable = CRT(t, prod, T); |
---|
2113 | |
---|
2114 | instable = Sinstable || Tinstable; |
---|
2115 | } |
---|
2116 | |
---|
2117 | if (!instable) { |
---|
2118 | long bound1 = NumBits(min(deg(a), deg(s)) + 1) |
---|
2119 | + MaxBits(a) + MaxBits(s); |
---|
2120 | long bound2 = NumBits(min(deg(b), deg(t)) + 1) |
---|
2121 | + MaxBits(b) + MaxBits(t); |
---|
2122 | |
---|
2123 | long bound = 4 + max(NumBits(r), max(bound1, bound2)); |
---|
2124 | |
---|
2125 | if (NumBits(prod) > bound) |
---|
2126 | break; |
---|
2127 | } |
---|
2128 | } |
---|
2129 | |
---|
2130 | rr = r; |
---|
2131 | ss = s; |
---|
2132 | tt = t; |
---|
2133 | |
---|
2134 | bak.restore(); |
---|
2135 | } |
---|
2136 | |
---|
2137 | void NormMod(ZZ& x, const ZZX& a, const ZZX& f, long deterministic) |
---|
2138 | { |
---|
2139 | if (!IsOne(LeadCoeff(f)) || deg(a) >= deg(f) || deg(f) <= 0) |
---|
2140 | Error("norm: bad args"); |
---|
2141 | |
---|
2142 | if (IsZero(a)) { |
---|
2143 | clear(x); |
---|
2144 | return; |
---|
2145 | } |
---|
2146 | |
---|
2147 | resultant(x, f, a, deterministic); |
---|
2148 | } |
---|
2149 | |
---|
2150 | void TraceMod(ZZ& res, const ZZX& a, const ZZX& f) |
---|
2151 | { |
---|
2152 | if (!IsOne(LeadCoeff(f)) || deg(a) >= deg(f) || deg(f) <= 0) |
---|
2153 | Error("trace: bad args"); |
---|
2154 | |
---|
2155 | vec_ZZ S; |
---|
2156 | |
---|
2157 | TraceVec(S, f); |
---|
2158 | |
---|
2159 | InnerProduct(res, S, a.rep); |
---|
2160 | } |
---|
2161 | |
---|
2162 | |
---|
2163 | void discriminant(ZZ& d, const ZZX& a, long deterministic) |
---|
2164 | { |
---|
2165 | long m = deg(a); |
---|
2166 | |
---|
2167 | if (m < 0) { |
---|
2168 | clear(d); |
---|
2169 | return; |
---|
2170 | } |
---|
2171 | |
---|
2172 | ZZX a1; |
---|
2173 | ZZ res; |
---|
2174 | |
---|
2175 | diff(a1, a); |
---|
2176 | resultant(res, a, a1, deterministic); |
---|
2177 | if (!divide(res, res, LeadCoeff(a))) |
---|
2178 | Error("discriminant: inexact division"); |
---|
2179 | |
---|
2180 | m = m & 3; |
---|
2181 | if (m >= 2) |
---|
2182 | negate(res, res); |
---|
2183 | |
---|
2184 | d = res; |
---|
2185 | } |
---|
2186 | |
---|
2187 | |
---|
2188 | void MulMod(ZZX& x, const ZZX& a, const ZZX& b, const ZZX& f) |
---|
2189 | { |
---|
2190 | if (deg(a) >= deg(f) || deg(b) >= deg(f) || deg(f) == 0 || |
---|
2191 | !IsOne(LeadCoeff(f))) |
---|
2192 | Error("MulMod: bad args"); |
---|
2193 | |
---|
2194 | ZZX t; |
---|
2195 | mul(t, a, b); |
---|
2196 | rem(x, t, f); |
---|
2197 | } |
---|
2198 | |
---|
2199 | void SqrMod(ZZX& x, const ZZX& a, const ZZX& f) |
---|
2200 | { |
---|
2201 | if (deg(a) >= deg(f) || deg(f) == 0 || !IsOne(LeadCoeff(f))) |
---|
2202 | Error("MulMod: bad args"); |
---|
2203 | |
---|
2204 | ZZX t; |
---|
2205 | sqr(t, a); |
---|
2206 | rem(x, t, f); |
---|
2207 | } |
---|
2208 | |
---|
2209 | |
---|
2210 | |
---|
2211 | static |
---|
2212 | void MulByXModAux(ZZX& h, const ZZX& a, const ZZX& f) |
---|
2213 | { |
---|
2214 | long i, n, m; |
---|
2215 | ZZ* hh; |
---|
2216 | const ZZ *aa, *ff; |
---|
2217 | |
---|
2218 | ZZ t, z; |
---|
2219 | |
---|
2220 | |
---|
2221 | n = deg(f); |
---|
2222 | m = deg(a); |
---|
2223 | |
---|
2224 | if (m >= n || n == 0 || !IsOne(LeadCoeff(f))) |
---|
2225 | Error("MulByXMod: bad args"); |
---|
2226 | |
---|
2227 | if (m < 0) { |
---|
2228 | clear(h); |
---|
2229 | return; |
---|
2230 | } |
---|
2231 | |
---|
2232 | if (m < n-1) { |
---|
2233 | h.rep.SetLength(m+2); |
---|
2234 | hh = h.rep.elts(); |
---|
2235 | aa = a.rep.elts(); |
---|
2236 | for (i = m+1; i >= 1; i--) |
---|
2237 | hh[i] = aa[i-1]; |
---|
2238 | clear(hh[0]); |
---|
2239 | } |
---|
2240 | else { |
---|
2241 | h.rep.SetLength(n); |
---|
2242 | hh = h.rep.elts(); |
---|
2243 | aa = a.rep.elts(); |
---|
2244 | ff = f.rep.elts(); |
---|
2245 | negate(z, aa[n-1]); |
---|
2246 | for (i = n-1; i >= 1; i--) { |
---|
2247 | mul(t, z, ff[i]); |
---|
2248 | add(hh[i], aa[i-1], t); |
---|
2249 | } |
---|
2250 | mul(hh[0], z, ff[0]); |
---|
2251 | h.normalize(); |
---|
2252 | } |
---|
2253 | } |
---|
2254 | |
---|
2255 | void MulByXMod(ZZX& h, const ZZX& a, const ZZX& f) |
---|
2256 | { |
---|
2257 | if (&h == &f) { |
---|
2258 | ZZX hh; |
---|
2259 | MulByXModAux(hh, a, f); |
---|
2260 | h = hh; |
---|
2261 | } |
---|
2262 | else |
---|
2263 | MulByXModAux(h, a, f); |
---|
2264 | } |
---|
2265 | |
---|
2266 | static |
---|
2267 | void EuclLength1(ZZ& l, const ZZX& a) |
---|
2268 | { |
---|
2269 | long n = a.rep.length(); |
---|
2270 | long i; |
---|
2271 | |
---|
2272 | ZZ sum, t; |
---|
2273 | |
---|
2274 | clear(sum); |
---|
2275 | for (i = 0; i < n; i++) { |
---|
2276 | sqr(t, a.rep[i]); |
---|
2277 | add(sum, sum, t); |
---|
2278 | } |
---|
2279 | |
---|
2280 | abs(t, ConstTerm(a)); |
---|
2281 | mul(t, t, 2); |
---|
2282 | add(t, t, 1); |
---|
2283 | add(sum, sum, t); |
---|
2284 | |
---|
2285 | if (sum > 1) { |
---|
2286 | SqrRoot(l, sum); |
---|
2287 | add(l, l, 1); |
---|
2288 | } |
---|
2289 | else |
---|
2290 | l = sum; |
---|
2291 | } |
---|
2292 | |
---|
2293 | |
---|
2294 | long CharPolyBound(const ZZX& a, const ZZX& f) |
---|
2295 | // This computes a bound on the size of the |
---|
2296 | // coefficients of the characterstic polynomial. |
---|
2297 | // It use the relation characterization of the char poly as |
---|
2298 | // resultant_y(f(y), x-a(y)), and then interpolates this |
---|
2299 | // through complex primimitive (deg(f)+1)-roots of unity. |
---|
2300 | |
---|
2301 | { |
---|
2302 | if (IsZero(a) || IsZero(f)) |
---|
2303 | Error("CharPolyBound: bad args"); |
---|
2304 | |
---|
2305 | ZZ t1, t2, t; |
---|
2306 | EuclLength1(t1, a); |
---|
2307 | EuclLength(t2, f); |
---|
2308 | power(t1, t1, deg(f)); |
---|
2309 | power(t2, t2, deg(a)); |
---|
2310 | mul(t, t1, t2); |
---|
2311 | return NumBits(t); |
---|
2312 | } |
---|
2313 | |
---|
2314 | |
---|
2315 | void SetCoeff(ZZX& x, long i, long a) |
---|
2316 | { |
---|
2317 | if (a == 1) |
---|
2318 | SetCoeff(x, i); |
---|
2319 | else { |
---|
2320 | static ZZ aa; |
---|
2321 | conv(aa, a); |
---|
2322 | SetCoeff(x, i, aa); |
---|
2323 | } |
---|
2324 | } |
---|
2325 | |
---|
2326 | // vectors |
---|
2327 | |
---|
2328 | NTL_vector_impl(ZZX,vec_ZZX) |
---|
2329 | |
---|
2330 | NTL_eq_vector_impl(ZZX,vec_ZZX) |
---|
2331 | |
---|
2332 | NTL_io_vector_impl(ZZX,vec_ZZX) |
---|
2333 | |
---|
2334 | |
---|
2335 | |
---|
2336 | void CopyReverse(ZZX& x, const ZZX& a, long hi) |
---|
2337 | |
---|
2338 | // x[0..hi] = reverse(a[0..hi]), with zero fill |
---|
2339 | // input may not alias output |
---|
2340 | |
---|
2341 | { |
---|
2342 | long i, j, n, m; |
---|
2343 | |
---|
2344 | n = hi+1; |
---|
2345 | m = a.rep.length(); |
---|
2346 | |
---|
2347 | x.rep.SetLength(n); |
---|
2348 | |
---|
2349 | const ZZ* ap = a.rep.elts(); |
---|
2350 | ZZ* xp = x.rep.elts(); |
---|
2351 | |
---|
2352 | for (i = 0; i < n; i++) { |
---|
2353 | j = hi-i; |
---|
2354 | if (j < 0 || j >= m) |
---|
2355 | clear(xp[i]); |
---|
2356 | else |
---|
2357 | xp[i] = ap[j]; |
---|
2358 | } |
---|
2359 | |
---|
2360 | x.normalize(); |
---|
2361 | } |
---|
2362 | |
---|
2363 | void reverse(ZZX& x, const ZZX& a, long hi) |
---|
2364 | { |
---|
2365 | if (hi < -1) Error("reverse: bad args"); |
---|
2366 | |
---|
2367 | if (&x == &a) { |
---|
2368 | ZZX tmp; |
---|
2369 | CopyReverse(tmp, a, hi); |
---|
2370 | x = tmp; |
---|
2371 | } |
---|
2372 | else |
---|
2373 | CopyReverse(x, a, hi); |
---|
2374 | } |
---|
2375 | |
---|
2376 | void MulTrunc(ZZX& x, const ZZX& a, const ZZX& b, long n) |
---|
2377 | { |
---|
2378 | ZZX t; |
---|
2379 | mul(t, a, b); |
---|
2380 | trunc(x, t, n); |
---|
2381 | } |
---|
2382 | |
---|
2383 | void SqrTrunc(ZZX& x, const ZZX& a, long n) |
---|
2384 | { |
---|
2385 | ZZX t; |
---|
2386 | sqr(t, a); |
---|
2387 | trunc(x, t, n); |
---|
2388 | } |
---|
2389 | |
---|
2390 | |
---|
2391 | void NewtonInvTrunc(ZZX& c, const ZZX& a, long e) |
---|
2392 | { |
---|
2393 | ZZ x; |
---|
2394 | |
---|
2395 | if (ConstTerm(a) == 1) |
---|
2396 | x = 1; |
---|
2397 | else if (ConstTerm(a) == -1) |
---|
2398 | x = -1; |
---|
2399 | else |
---|
2400 | Error("InvTrunc: non-invertible constant term"); |
---|
2401 | |
---|
2402 | if (e == 1) { |
---|
2403 | conv(c, x); |
---|
2404 | return; |
---|
2405 | } |
---|
2406 | |
---|
2407 | static vec_long E; |
---|
2408 | E.SetLength(0); |
---|
2409 | append(E, e); |
---|
2410 | while (e > 1) { |
---|
2411 | e = (e+1)/2; |
---|
2412 | append(E, e); |
---|
2413 | } |
---|
2414 | |
---|
2415 | long L = E.length(); |
---|
2416 | |
---|
2417 | ZZX g, g0, g1, g2; |
---|
2418 | |
---|
2419 | |
---|
2420 | g.rep.SetMaxLength(e); |
---|
2421 | g0.rep.SetMaxLength(e); |
---|
2422 | g1.rep.SetMaxLength((3*e+1)/2); |
---|
2423 | g2.rep.SetMaxLength(e); |
---|
2424 | |
---|
2425 | conv(g, x); |
---|
2426 | |
---|
2427 | long i; |
---|
2428 | |
---|
2429 | for (i = L-1; i > 0; i--) { |
---|
2430 | // lift from E[i] to E[i-1] |
---|
2431 | |
---|
2432 | long k = E[i]; |
---|
2433 | long l = E[i-1]-E[i]; |
---|
2434 | |
---|
2435 | trunc(g0, a, k+l); |
---|
2436 | |
---|
2437 | mul(g1, g0, g); |
---|
2438 | RightShift(g1, g1, k); |
---|
2439 | trunc(g1, g1, l); |
---|
2440 | |
---|
2441 | mul(g2, g1, g); |
---|
2442 | trunc(g2, g2, l); |
---|
2443 | LeftShift(g2, g2, k); |
---|
2444 | |
---|
2445 | sub(g, g, g2); |
---|
2446 | } |
---|
2447 | |
---|
2448 | c = g; |
---|
2449 | } |
---|
2450 | |
---|
2451 | |
---|
2452 | void InvTrunc(ZZX& c, const ZZX& a, long e) |
---|
2453 | { |
---|
2454 | if (e < 0) Error("InvTrunc: bad args"); |
---|
2455 | |
---|
2456 | if (e == 0) { |
---|
2457 | clear(c); |
---|
2458 | return; |
---|
2459 | } |
---|
2460 | |
---|
2461 | if (e >= (1L << (NTL_BITS_PER_LONG-4))) |
---|
2462 | Error("overflow in InvTrunc"); |
---|
2463 | |
---|
2464 | NewtonInvTrunc(c, a, e); |
---|
2465 | } |
---|
2466 | |
---|
2467 | NTL_END_IMPL |
---|