Sidef/Types/Number/PolynomialMod.pm untested

filter: Statementstmt 0.0% 0 / 660 Branchbran 0.0% 0 / 144 Conditioncond 0.0% 0 / 73 MC/DCmcdc 0.0% 0 / 43 Subroutinesub 0.0% 0 / 70 Podpod 0.0% 0 / 63 totaltotal 0.0% 0 / 1053 CC 73 SCAR 31.9
CC
73
Cov
0%
factor_exp
110.0
_poly_edf
72.0
add
42.0
CRAP 24.4
1 package Sidef::Types::Number::PolynomialMod;
2  
3 # References:
4 # Lecture 14, Week 8 (2hrs) - Towards polynomial factorization
5 # https://youtube.com/watch?v=KNyHz0eoAMA
6 #
7 # Lecture 15, Week 8, 1hr - Polynomial factorization
8 # https://youtube.com/watch?v=tMqKqsMb-Ro
9  
10 use utf8;
11 use 5.016;
12  
13 use List::Util qw();
14 use Scalar::Util qw();
15  
16 use parent qw(
17 Sidef::Types::Number::Polynomial
18 );
19  
20 use overload
21 q{bool} => sub { (@_) = ($_[0]); goto &__boolify__ },
22 q{""} => sub { (@_) = ($_[0]); goto &__stringify__ },
23 q{%{}} => \&to_poly,
24 q{${}} => \&Sidef::Types::Number::Polynomial::to_n,
25 q{0+} => \&Sidef::Types::Number::Polynomial::to_n;
26  
27 sub new {
28 my (undef, @args) = @_;
29  
30 my $mod = pop @args;
31  
32 if (Scalar::Util::reftype($mod) eq 'ARRAY') {
33 $mod = __PACKAGE__->SUPER::new($mod);
34 }
35  
36 if (scalar(@args) == 0 and ref($_[0]) eq __PACKAGE__) {
37 return $_[0]->eval($mod);
38 }
39  
40 my $poly;
41 if (scalar(@args) == 1 and ref($args[0]) eq 'Sidef::Types::Number::Polynomial') {
42 $poly = $args[0];
43 }
44 else {
45 $poly = __PACKAGE__->SUPER::new(@args);
46 }
47  
48 $poly = $poly->mod($mod)->lift;
49 bless [$poly, $mod];
50 }
51  
52 *call = \&new;
53  
54 sub with_value {
55 my ($self, $value) = @_;
56 __PACKAGE__->new(0 => $value, $self->[1]);
57 }
58  
59 sub to_poly {
60 $_[0][0];
61 }
62  
63 *lift = \&to_poly;
64  
65 sub modulus {
66 $_[0][1];
67 }
68  
69 sub __dump__ {
70 my ($x) = @_;
71 my $str = join('', $x->[0]->dump);
72 $str =~ s{^Polynomial}{PolynomialMod};
73 $str =~ s{\(\)}{\(0\)};
74 $str =~ s{\)\z}{, $x->[1])};
75 return $str;
76 }
77  
78 sub __boolify__ {
79 my ($x) = @_;
80 ($x->{0} // 0);
81 }
82  
83 sub __stringify__ {
84 my ($x, $method) = @_;
85 $method //= 'to_s';
86 $x->[0]->SUPER::__stringify__($method) . join('', " (mod ", ($x->[1] // '1'), ')');
87 }
88  
89 sub to_s {
90 my ($x) = @_;
91 Sidef::Types::String::String->new($x->__stringify__);
92 }
93  
94 *stringify = \&to_s;
95  
96 sub pretty {
97 my ($x) = @_;
98 Sidef::Types::String::String->new($x->__stringify__('pretty'));
99 }
100  
101 sub dump {
102 my ($x) = @_;
103 Sidef::Types::String::String->new($x->__dump__);
104 }
105  
106 sub derivative {
107 my ($x) = @_;
108 my $m = $x->[1];
109 $x = $x->[0];
110 __PACKAGE__->new((map { (Math::Prime::Util::GMP::subint($_, 1), $x->{$_}->mul(Sidef::Types::Number::Number::_set_int($_))->mod($m)) } CORE::keys(%$x)), $m);
111 }
112  
113 sub eval {
114 my ($x, $value) = @_;
115  
116 my $m = $x->[1];
117 $x = $x->[0];
118  
119 my @exponents = CORE::keys(%$x);
120 @exponents || return Sidef::Types::Number::Number::ZERO;
121  
122 # Evaluate via Horner's method (nested multiplication), visiting terms
123 # from the highest exponent down to the lowest. Between two consecutive
124 # exponents e_i > e_{i+1}, the accumulator is advanced by a single
125 # multiplication by value^(e_i - e_{i+1}) instead of computing
126 # value^e_{i+1} from scratch for every term independently, which turns
127 # O(n) independent modular exponentiations into O(n) much cheaper gap
128 # exponentiations (trivial -- a single multiply -- for the common case
129 # of consecutive or closely-spaced exponents).
130 @exponents = CORE::sort { $b <=> $a } @exponents;
131  
132 $value = $value->mod($m);
133  
134 my $prev_exp = CORE::shift(@exponents);
135 my $result = $x->{$prev_exp}->eval($value)->mod($m);
136  
137 foreach my $exp (@exponents) {
138 my $gap = Sidef::Types::Number::Number::_set_int(Math::Prime::Util::GMP::subint($prev_exp, $exp));
139 my $factor = Sidef::Types::Number::Mod->new($value, $m)->pow($gap)->lift;
140  
141 $result = $result->mul($factor)->add($x->{$exp}->eval($value))->mod($m);
142 $prev_exp = $exp;
143 }
144  
145 # Bring the accumulator down from the lowest nonzero exponent to x^0.
146 if ($prev_exp != 0) {
147 my $factor = Sidef::Types::Number::Mod->new($value, $m)->pow(Sidef::Types::Number::Number::_set_int($prev_exp))->lift;
148 $result = $result->mul($factor)->mod($m);
149 }
150  
151 return $result;
152 }
153  
154 sub binomial {
155 my ($n, $k) = @_;
156  
157 my $k_int = CORE::int($k);
158 my @terms;
159  
160 foreach my $i (0 .. $k_int - 1) {
161 push @terms, $n;
162 $n = $n->dec;
163 }
164  
165 @terms || return __PACKAGE__->new((0 => Sidef::Types::Number::Number::ONE), $n->[1]);
166  
167 my $prod = Sidef::Types::Number::Number::_binsplit(\@terms, \&Sidef::Types::Number::PolynomialMod::mul);
168 $prod->div($k->factorial);
169 }
170  
171 sub chinese {
172 my (@polynomials) = @_;
173  
174 my @moduli = map { $_->modulus } @polynomials;
175  
176 my $m = $moduli[0];
177 foreach my $i (1 .. $#moduli) {
178 $m = $m->lcm($moduli[$i]);
179 }
180  
181 my $c = __PACKAGE__->new($m);
182  
183 foreach my $i (0 .. $#polynomials) {
184 my $poly = $polynomials[$i];
185 my $n = $moduli[$i];
186 my $t = $m->div($n);
187 my $u = $t->mul($t->inv->mod($n));
188 $c = $c->add(__PACKAGE__->new($poly->lift, $m)->mul($u));
189 }
190  
191 return $c;
192 }
193  
194 sub add {
195 my ($x, $y) = @_;
196  
197 if (ref($y) eq __PACKAGE__ and $x->[1]->eq($y->[1])) {
198 my $m = $x->[1];
199 $x = $x->[0];
200 $y = $y->[0];
201 return
202 __PACKAGE__->new(
203 (
204 (map { $_ => (exists($y->{$_}) ? $x->{$_}->add($y->{$_})->mod($m) : $x->{$_}) } CORE::keys %$x),
205 (map { exists($x->{$_}) ? () : ($_ => $y->{$_}) } CORE::keys(%$y))
206 ),
207 $m
208 );
209 }
210  
211 my $m = $x->[1];
212 $x = $x->[0];
213  
214 if (not exists $x->{0}) {
215 return __PACKAGE__->new(0 => $y, %$x, $m);
216 }
217  
218 $y = $y->mod($m);
219  
220 __PACKAGE__->new((map { $_ => (($_ eq '0') ? $x->{$_}->add($y)->mod($m) : $x->{$_}) } CORE::keys(%$x)), $m);
221 }
222  
223 sub sub {
224 my ($x, $y) = @_;
225  
226 if (ref($y) eq __PACKAGE__ and $x->[1]->eq($y->[1])) {
227 my $m = $x->[1];
228 $x = $x->[0];
229 $y = $y->[0];
230 return
231 __PACKAGE__->new(
232 (
233 (map { $_ => (exists($y->{$_}) ? $x->{$_}->sub($y->{$_})->mod($m) : $x->{$_}) } CORE::keys %$x),
234 (map { exists($x->{$_}) ? () : ($_ => $y->{$_}->neg) } CORE::keys(%$y))
235 ),
236 $m
237 );
238 }
239  
240 my $m = $x->[1];
241 $x = $x->[0];
242  
243 if (not exists $x->{0}) {
244 return __PACKAGE__->new(0 => $y->neg, %$x, $m);
245 }
246  
247 $y = $y->mod($m);
248  
249 __PACKAGE__->new((map { $_ => (($_ eq '0') ? $x->{$_}->sub($y)->mod($m) : $x->{$_}) } CORE::keys(%$x)), $m);
250 }
251  
252 sub mul {
253 my ($x, $y) = @_;
254  
255 if (ref($y) eq __PACKAGE__ and $x->[1]->eq($y->[1])) {
256  
257 my $m = $x->[1];
258  
259 $x = $x->[0];
260 $y = $y->[0];
261  
262 my @keys_x = CORE::keys %$x;
263 my @keys_y = CORE::keys %$y;
264  
265 my %poly;
266 foreach my $key_x (@keys_x) {
267 foreach my $key_y (@keys_y) {
268  
269 my $coeff = $x->{$key_x}->mul($y->{$key_y})->mod($m);
270 my $key_z = Math::Prime::Util::GMP::addint($key_x, $key_y);
271  
272 if (exists $poly{$key_z}) {
273 $poly{$key_z} = $poly{$key_z}->add($coeff)->mod($m);
274 }
275 else {
276 $poly{$key_z} = $coeff;
277 }
278 }
279 }
280  
281 return __PACKAGE__->new(%poly, $m);
282 }
283  
284 $y = $y->mod($x->[1]);
285  
286 __PACKAGE__->new((map { $_ => $x->[0]{$_}->mul($y)->mod($x->[1]) } CORE::keys(%{$x->[0]})), $x->[1]);
287 }
288  
289 sub sqr {
290 my ($x) = @_;
291 $x->mul($x);
292 }
293  
294 sub divmod {
295 my ($x, $y) = @_;
296  
297 # Reference:
298 # https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division
299  
300 if ($x->[1]->ne($y->[1])) {
301 return (__PACKAGE__->new(Sidef::Types::Number::Number::nan(), Sidef::Types::Number::Number::nan()),
302 __PACKAGE__->new(Sidef::Types::Number::Number::nan()));
303 }
304  
305 my $m = $x->[1];
306  
307 my $x_mod = $x;
308 my $y_mod = $y;
309  
310 $x = $x->[0];
311 $y = $y->[0];
312  
313 my $deg_r = List::Util::max(CORE::keys(%$x)); # deg(x)
314 $deg_r // return (__PACKAGE__->new($m), __PACKAGE__->new($m));
315  
316 if ($deg_r > ~0) {
317 $deg_r = Math::GMPz::Rmpz_init_set_str("$deg_r", 10);
318 }
319  
320 my $deg_y = List::Util::max(CORE::keys(%$y)); # deg(y)
321 $deg_y // return (__PACKAGE__->new(0 => Sidef::Types::Number::Number::inf(), $m), __PACKAGE__->new($m));
322  
323 if ($deg_y > ~0) {
324 $deg_y = Math::GMPz::Rmpz_init_set_str("$deg_y", 10);
325 }
326  
327 my $q = __PACKAGE__->new($m);
328 my $r = $x_mod;
329 my $c = $y->{$deg_y}; # lc(y)
330  
331 # Calculate modular inverse of the leading coefficient of divisor
332 my $inv_c = $c->inv->mod($m);
333  
334 # If inverse does not exist (e.g. m is not prime), return NaN
335 if ($inv_c->is_nan) {
336 return (__PACKAGE__->new(Sidef::Types::Number::Number::nan(), Sidef::Types::Number::Number::nan()), __PACKAGE__->new($m));
337 }
338  
339 while ($deg_r >= $deg_y) {
340  
341 my $lc = $r->[0]{$deg_r}; # lc(r)
342  
343 # Fix: Use modular inverse multiplication instead of integer division
344 # t = lc(r) * inv(c) (mod m)
345 my $t = $lc->mul($inv_c)->mod($m);
346  
347 # s := t * x^(deg(r)−deg(y))
348 my $s = __PACKAGE__->new(Math::Prime::Util::GMP::subint($deg_r, $deg_y) => $t, $m);
349 $q = $q->add($s);
350 $r = $r->sub($s->mul($y_mod));
351  
352 # Find deg(r) for the new r
353 $deg_r = List::Util::max(CORE::keys(%{$r->[0]})) // last;
354  
355 if ($deg_r > ~0) {
356 $deg_r = Math::GMPz::Rmpz_init_set_str("$deg_r", 10);
357 }
358 }
359  
360 return ($q, $r);
361 }
362  
363 sub abs {
364 my ($x) = @_;
365 $x->mul($x->sgn);
366 }
367  
368 sub lcm {
369 my ($x, $y) = @_;
370 $x->mul($y)->abs->div($x->gcd($y));
371 }
372  
373 sub normalize_to_monic {
374 my ($x) = @_;
375 my $deg = join('', $x->degree);
376 return $x if $deg < 0;
377  
378 my $lc = $x->[0]{$deg};
379  
380 # Already monic
381 return $x if $lc->is_one;
382  
383 # Multiply polynomial by inv(lc)
384 my $inv = $lc->inv->mod($x->[1]);
385 return $x if $inv->is_nan; # Should not happen in field
386  
387 $x->mul($inv);
388 }
389  
390 sub gcd {
391 my ($x, $y) = @_;
392  
393 # Reference:
394 # https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclid's_algorithm
395  
396 my $r0 = $x;
397 my $r1 = $y;
398  
399 until ($r1->is_zero) {
400 my $r = $r0->mod($r1);
401 ($r0, $r1) = ($r1, $r);
402 }
403  
404 return $r0;
405 }
406  
407 sub monic_gcd {
408 my ($x, $y) = @_;
409 $x->gcd($y)->normalize_to_monic;
410 }
411  
412 sub gcdext {
413 my ($x, $y) = @_;
414  
415 # Reference:
416 # https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B%C3%A9zout's_identity_and_extended_GCD_algorithm
417  
418 if (ref($y) ne __PACKAGE__) {
419 $y = __PACKAGE__->new(0 => $y, $x->[1]);
420 }
421  
422 my $r0 = $x;
423 my $r1 = $y;
424  
425 my $s0 = Sidef::Types::Number::Number::ONE;
426 my $s1 = Sidef::Types::Number::Number::ZERO;
427 my $t0 = Sidef::Types::Number::Number::ZERO;
428 my $t1 = Sidef::Types::Number::Number::ONE;
429  
430 my $i = 1;
431 until ($r1->is_zero) {
432 my ($q, $r) = $r0->divmod($r1);
433 ($r0, $r1) = ($r1, $r);
434 ($s0, $s1) = ($s1, $s0->sub($q->mul($s1)));
435 ($t0, $t1) = ($t1, $t0->sub($q->mul($t1)));
436 ++$i;
437 }
438  
439 my $g = $r0;
440 my $u = $s0;
441 my $v = $t0;
442  
443 my $a1 = $t1->mul(Sidef::Types::Number::Number::MONE->ipow(Sidef::Types::Number::Number::_set_int($i - 1)));
444 my $b1 = $s1->mul(Sidef::Types::Number::Number::MONE->ipow(Sidef::Types::Number::Number::_set_int($i)));
445  
446 return ($g, $u, $v, $a1, $b1);
447 }
448  
449 sub idiv {
450 my ($x, $y) = @_;
451  
452 if (ref($y) ne __PACKAGE__) {
453 $y = __PACKAGE__->new(0 => $y, $x->[1]);
454 }
455  
456 my ($quot, $rem) = $x->divmod($y);
457 return $quot;
458 }
459  
460 # Probably not right?
461 *idiv_ceil = \&idiv;
462 *idiv_trunc = \&idiv;
463 *idiv_round = \&idiv;
464 *idiv_floor = \&idiv;
465  
466 sub div {
467 my ($x, $y) = @_;
468  
469 if (ref($y) eq __PACKAGE__ and $y->[1]->eq($x->[1])) {
470  
471 my ($quot, $rem) = $x->divmod($y);
472  
473 if ($rem->is_zero) {
474 return $quot;
475 }
476  
477 my $frac = Sidef::Types::Number::Fraction->new($quot->mul($y)->add($rem), $y);
478  
479 if ($frac->is_zero) {
480 return __PACKAGE__->new($x->[1]);
481 }
482  
483 return $frac;
484 }
485  
486 if ($y->is_zero) {
487 return __PACKAGE__->new((0 => Sidef::Types::Number::Number::inf()), $x->[1]);
488 }
489  
490 my $m = $x->[1];
491 $x = $x->[0];
492 $y = $y->mod($m);
493  
494 __PACKAGE__->new((map { $_ => $x->{$_}->div($y)->mod($m) } CORE::keys(%$x)), $m);
495 }
496  
497 sub neg {
498 my ($x) = @_;
499 __PACKAGE__->new((map { $_ => $x->{$_}->neg } CORE::keys %{$x->[0]}), $x->[1]);
500 }
501  
502 sub float {
503 my ($x) = @_;
504 __PACKAGE__->new((map { $_ => $x->{$_}->float } CORE::keys %{$x->[0]}), $x->[1]);
505 }
506  
507 sub rat {
508 my ($x) = @_;
509 __PACKAGE__->new((map { $_ => $x->{$_}->rat } CORE::keys %{$x->[0]}), $x->[1]);
510 }
511  
512 sub rat_approx {
513 my ($x) = @_;
514 __PACKAGE__->new((map { $_ => $x->{$_}->rat_approx } CORE::keys %{$x->[0]}), $x->[1]);
515 }
516  
517 sub floor {
518 my ($x) = @_;
519 __PACKAGE__->new((map { $_ => $x->{$_}->floor } CORE::keys %{$x->[0]}), $x->[1]);
520 }
521  
522 sub ceil {
523 my ($x) = @_;
524 __PACKAGE__->new((map { $_ => $x->{$_}->ceil } CORE::keys %{$x->[0]}), $x->[1]);
525 }
526  
527 sub round {
528 my ($x, $r) = @_;
529 __PACKAGE__->new((map { $_ => $x->{$_}->round($r) } CORE::keys %{$x->[0]}), $x->[1]);
530 }
531  
532 sub mod {
533 my ($x, $y) = @_;
534  
535 if (ref($y) eq __PACKAGE__ and $y->[1]->eq($x->[1])) {
536  
537 # mod(a, b) = a - b * floor(a/b)
538 # return $x->sub($y->mul($x->div($y)->floor));
539  
540 my ($quot, $rem) = $x->divmod($y);
541 return $rem;
542 }
543  
544 __PACKAGE__->new($x->[0], $y);
545 }
546  
547 #~ sub lift {
548 #~ my ($x) = @_;
549 #~ __PACKAGE__->new((map { $_ => $x->[0]{$_}->lift } CORE::keys %{$x->[0]}), $x->[1]);
550 #~ }
551  
552 sub inv {
553 my ($x) = @_;
554  
555 my $m = $x->[1]; # modulus polynomial (a Polynomial)
556 my $f = $x->lift; # residue polynomial (a plain Polynomial)
557  
558 if (ref($m) ne 'Sidef::Types::Number::Polynomial') {
559 return Sidef::Types::Number::Fraction->new(Sidef::Types::Number::Number::ONE, $x);
560 }
561  
562 # Run the extended Euclidean algorithm on the plain polynomials.
563 # Returns (g, u, v, ...) satisfying: u*f + v*m = g,
564 # with g normalised to monic by Polynomial::gcdext.
565 my ($g, $u) = $f->gcdext($m);
566  
567 # The inverse exists iff gcd(f, m) = 1.
568 # If g is not the constant polynomial 1, f is not invertible mod m.
569 $g->is_one
570 || return __PACKAGE__->new(0 => Sidef::Types::Number::Number::nan(), $m);
571  
572 # u*f ≡ 1 (mod m).
573 __PACKAGE__->new($u, $m);
574 }
575  
576 sub is_zero {
577 my ($x) = @_;
578 $x->eq(Sidef::Types::Number::Number::ZERO);
579 }
580  
581 sub is_one {
582 my ($x) = @_;
583 $x->eq(Sidef::Types::Number::Number::ONE);
584 }
585  
586 sub is_mone {
587 my ($x) = @_;
588 $x->eq(Sidef::Types::Number::Number::MONE);
589 }
590  
591 sub is_unit {
592 my ($x) = @_;
593 $x->inv->is_nan->not;
594 }
595  
596 sub inc {
597 my ($x) = @_;
598 __PACKAGE__->new(%{$x->[0]}, 0 => ($x->[0]{0} // Sidef::Types::Number::Number::ZERO)->inc, $x->[1]);
599 }
600  
601 sub dec {
602 my ($x) = @_;
603 __PACKAGE__->new(%{$x->[0]}, 0 => ($x->[0]{0} // Sidef::Types::Number::Number::ZERO)->dec, $x->[1]);
604 }
605  
606 sub pow {
607 my ($x, $n) = @_;
608  
609 my $m = $x->[1];
610  
611 my $negative_power = 0;
612  
613 if ($n->is_neg) {
614 $n = $n->abs;
615 $negative_power = 1;
616 }
617  
618 my $c = __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE, $m);
619  
620 foreach my $bit (reverse split(//, $n->as_bin)) {
621  
622 # c = (c*x)%m if bit
623 # x = (x*x)%m
624  
625 $c = $c->mul($x) if $bit;
626 $x = $x->mul($x);
627 }
628  
629 if ($negative_power) {
630 $c = $c->inv;
631 }
632  
633 return $c;
634 }
635  
636 sub cmp {
637 my ($x, $y) = @_;
638  
639 if (ref($x) eq ref($y)) {
640 my $mod_cmp = $x->[1]->cmp($y->[1]);
641  
642 $mod_cmp->is_zero
643 or return $mod_cmp;
644  
645 $x = $x->[0];
646 $y = $y->[0];
647 }
648 else {
649 $y = $y->mod($x->[1]);
650 $x = $x->[0];
651 }
652  
653 return $x->cmp($y);
654 }
655  
656 sub eq {
657 my ($x, $y) = @_;
658  
659 if (ref($x) eq ref($y)) {
660  
661 $x->[1]->eq($y->[1])
662 or return Sidef::Types::Bool::Bool::FALSE;
663  
664 $x = $x->[0];
665 $y = $y->[0];
666 }
667 else {
668 $y = $y->mod($x->[1]);
669 $x = $x->[0];
670 }
671  
672 return $x->eq($y);
673 }
674  
675 sub ne {
676 my ($x, $y) = @_;
677 $x->eq($y)->not;
678 }
679  
680 sub powmod {
681 my ($base, $exp, $poly_mod) = @_;
682  
683 my $p = $base->[1]; # scalar prime (Number)
684  
685 $base = $base->mod($poly_mod);
686  
687 my $result = __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE, $p);
688  
689 foreach my $bit (reverse split(//, $exp->as_bin)) {
690 $result = $result->mul($base)->mod($poly_mod) if $bit;
691 $base = $base->mul($base)->mod($poly_mod);
692 }
693  
694 return $result;
695 }
696  
697 sub _poly_clone {
698 my ($A) = @_;
699 return [map { Math::GMPz::Rmpz_init_set($_) } @$A];
700 }
701  
702 sub _poly_deg {
703 my ($A) = @_;
704 my $d = $#$A;
705 while ($d >= 0 && Math::GMPz::Rmpz_sgn($A->[$d]) == 0) { $d--; }
706 return $d;
707 }
708  
709 sub _poly_strip {
710 my ($A) = @_;
711 while (@$A && Math::GMPz::Rmpz_sgn($A->[-1]) == 0) { pop @$A; }
712 return $A;
713 }
714  
715 sub _poly_monic {
716 my ($A, $p) = @_;
717 my $d = _poly_deg($A);
718 return [] if $d < 0;
719 my $lc = $A->[$d];
720 if (Math::GMPz::Rmpz_cmp_ui($lc, 1) != 0) {
721 my $inv = Math::GMPz::Rmpz_init();
722 Math::GMPz::Rmpz_invert($inv, $lc, $p);
723 for my $i (0 .. $d) {
724 Math::GMPz::Rmpz_mul($A->[$i], $A->[$i], $inv);
725 Math::GMPz::Rmpz_mod($A->[$i], $A->[$i], $p);
726 }
727 }
728 return _poly_strip($A);
729 }
730  
731 sub _poly_add {
732 my ($A, $B, $p) = @_;
733 my @res;
734 my $max = @$A > @$B ? $#$A : $#$B;
735 my $zero = Math::GMPz::Rmpz_init();
736 for my $i (0 .. $max) {
737 my $v = Math::GMPz::Rmpz_init();
738 Math::GMPz::Rmpz_add($v, $i <= $#$A ? $A->[$i] : $zero, $i <= $#$B ? $B->[$i] : $zero);
739 Math::GMPz::Rmpz_mod($v, $v, $p);
740 push @res, $v;
741 }
742 return _poly_strip(\@res);
743 }
744  
745 sub _poly_sub {
746 my ($A, $B, $p) = @_;
747 my @res;
748 my $max = @$A > @$B ? $#$A : $#$B;
749 my $zero = Math::GMPz::Rmpz_init();
750 for my $i (0 .. $max) {
751 my $v = Math::GMPz::Rmpz_init();
752 Math::GMPz::Rmpz_sub($v, $i <= $#$A ? $A->[$i] : $zero, $i <= $#$B ? $B->[$i] : $zero);
753 Math::GMPz::Rmpz_mod($v, $v, $p);
754 push @res, $v;
755 }
756 return _poly_strip(\@res);
757 }
758  
759 sub _poly_mul {
760 my ($A, $B, $p) = @_;
761 my $da = _poly_deg($A);
762 my $db = _poly_deg($B);
763 return [] if $da < 0 || $db < 0;
764  
765 my @res = map { Math::GMPz::Rmpz_init() } 0 .. ($da + $db);
766 my $t = Math::GMPz::Rmpz_init();
767  
768 for my $i (0 .. $da) {
769 next if Math::GMPz::Rmpz_sgn($A->[$i]) == 0;
770 for my $j (0 .. $db) {
771 Math::GMPz::Rmpz_mul($t, $A->[$i], $B->[$j]);
772 Math::GMPz::Rmpz_add($res[$i + $j], $res[$i + $j], $t);
773 }
774 }
775 for my $r (@res) {
776 Math::GMPz::Rmpz_mod($r, $r, $p);
777 }
778 return _poly_strip(\@res);
779 }
780  
781 sub _poly_divmod {
782 my ($x, $y, $p) = @_;
783 my $dx = _poly_deg($x);
784 my $dy = _poly_deg($y);
785  
786 return ([], _poly_clone($x)) if $dx < $dy;
787  
788 my $r = _poly_clone($x);
789 my @q = map { Math::GMPz::Rmpz_init() } 0 .. ($dx - $dy);
790  
791 my $inv_lc = Math::GMPz::Rmpz_init();
792 Math::GMPz::Rmpz_invert($inv_lc, $y->[$dy], $p);
793 my $t = Math::GMPz::Rmpz_init();
794  
795 for (my $i = $dx ; $i >= $dy ; $i--) {
796 next if Math::GMPz::Rmpz_sgn($r->[$i]) == 0;
797  
798 Math::GMPz::Rmpz_mul($t, $r->[$i], $inv_lc);
799 Math::GMPz::Rmpz_mod($t, $t, $p);
800 Math::GMPz::Rmpz_set($q[$i - $dy], $t);
801  
802 for my $j (0 .. $dy) {
803 next if Math::GMPz::Rmpz_sgn($y->[$j]) == 0;
804 my $m = Math::GMPz::Rmpz_init();
805 Math::GMPz::Rmpz_mul($m, $t, $y->[$j]);
806 Math::GMPz::Rmpz_sub($r->[$i - $dy + $j], $r->[$i - $dy + $j], $m);
807 Math::GMPz::Rmpz_mod($r->[$i - $dy + $j], $r->[$i - $dy + $j], $p);
808 }
809 }
810 return (_poly_strip(\@q), _poly_strip($r));
811 }
812  
813 sub _poly_mod {
814 my ($x, $y, $p) = @_;
815 my ($q, $r) = _poly_divmod($x, $y, $p);
816 return $r;
817 }
818  
819 sub _poly_gcd {
820 my ($A, $B, $p) = @_;
821 my $r0 = _poly_clone($A);
822 my $r1 = _poly_clone($B);
823 while (_poly_deg($r1) >= 0) {
824 my $r = _poly_mod($r0, $r1, $p);
825 $r0 = $r1;
826 $r1 = $r;
827 }
828 return _poly_monic($r0, $p);
829 }
830  
831 sub _poly_derivative {
832 my ($A, $p) = @_;
833 my $d = _poly_deg($A);
834 return [] if $d < 1;
835 my @res;
836 for my $i (1 .. $d) {
837 my $v = Math::GMPz::Rmpz_init();
838 Math::GMPz::Rmpz_mul_ui($v, $A->[$i], $i);
839 Math::GMPz::Rmpz_mod($v, $v, $p);
840 push @res, $v;
841 }
842 return _poly_strip(\@res);
843 }
844  
845 sub _poly_powmod {
846 my ($base, $exp, $modpoly, $p) = @_;
847 my $res = [Math::GMPz::Rmpz_init_set_ui(1)];
848 my $B = _poly_mod($base, $modpoly, $p);
849  
850 my $e = Math::GMPz::Rmpz_init_set($exp);
851 while (Math::GMPz::Rmpz_sgn($e) > 0) {
852 if (Math::GMPz::Rmpz_tstbit($e, 0)) {
853 $res = _poly_mod(_poly_mul($res, $B, $p), $modpoly, $p);
854 }
855 $B = _poly_mod(_poly_mul($B, $B, $p), $modpoly, $p);
856 Math::GMPz::Rmpz_fdiv_q_2exp($e, $e, 1);
857 }
858 return $res;
859 }
860  
861 # ======================================================================
862 # Sub-algorithms for Factorization
863 # ======================================================================
864  
865 sub _poly_ddf {
866 my ($f, $p) = @_;
867 my $x_poly = [Math::GMPz::Rmpz_init(), Math::GMPz::Rmpz_init_set_ui(1)];
868 my $w = _poly_clone($x_poly);
869 my @factors;
870  
871 my $f_curr = _poly_clone($f);
872 my $deg_f = _poly_deg($f_curr);
873  
874 for my $k (1 .. $deg_f) {
875 $w = _poly_powmod($w, $p, $f_curr, $p);
876 my $diff = _poly_sub($w, $x_poly, $p);
877 my $gk = _poly_gcd($diff, $f_curr, $p);
878  
879 if (_poly_deg($gk) > 0) {
880 push @factors, [$k, $gk];
881 my ($q, $r) = _poly_divmod($f_curr, $gk, $p);
882 $f_curr = $q;
883 }
884 last if _poly_deg($f_curr) <= 0;
885 }
886  
887 if (_poly_deg($f_curr) > 0) {
888 push @factors, [_poly_deg($f_curr), $f_curr];
889 }
890 return @factors;
891 }
892  
893 sub _poly_edf {
894 my ($f, $d, $p, $p_sidef) = @_;
895 my $deg_f = _poly_deg($f);
896 return () if $deg_f <= 0;
897 return ($f) if $deg_f == $d;
898  
899 my $is_char2 = (Math::GMPz::Rmpz_cmp_ui($p, 2) == 0);
900 my $exp = Math::GMPz::Rmpz_init();
901  
902 if (!$is_char2) {
903 Math::GMPz::Rmpz_pow_ui($exp, $p, $d);
904 Math::GMPz::Rmpz_sub_ui($exp, $exp, 1);
905 Math::GMPz::Rmpz_fdiv_q_2exp($exp, $exp, 1);
906 }
907  
908 my $g;
909 for (1 .. 200) {
910 my @t;
911 for my $k (0 .. $deg_f - 1) {
912 my $c_sidef = $p_sidef->irand;
913 my $c = Sidef::Types::Number::Number::_any2mpz($$c_sidef);
914 push @t, Math::GMPz::Rmpz_init_set($c);
915 }
916 my $t_poly = _poly_strip(\@t);
917 next if _poly_deg($t_poly) < 0;
918  
919 my $h;
920 if ($is_char2) {
921 $h = _poly_mod($t_poly, $f, $p);
922 my $ti = _poly_clone($h);
923 for my $i (1 .. $d - 1) {
924 $ti = _poly_powmod($ti, $p, $f, $p);
925 $h = _poly_add($h, $ti, $p);
926 }
927 }
928 else {
929 my $t_pow = _poly_powmod($t_poly, $exp, $f, $p);
930 my $one = [Math::GMPz::Rmpz_init_set_ui(1)];
931 $h = _poly_sub($t_pow, $one, $p);
932 }
933  
934 $g = _poly_gcd($h, $f, $p);
935 last if _poly_deg($g) > 0 && _poly_deg($g) < $deg_f;
936 }
937  
938 return ($f) unless (defined($g) && _poly_deg($g) > 0 && _poly_deg($g) < $deg_f);
939  
940 my ($q, $r) = _poly_divmod($f, $g, $p);
941 return (__SUB__->($g, $d, $p, $p_sidef), __SUB__->($q, $d, $p, $p_sidef));
942 }
943  
944 sub factor_exp {
945 my ($original) = @_;
946  
947 my $p_sidef = $original->[1];
948 Sidef::Types::Number::Number::_valid(\$p_sidef);
949 my $p = Sidef::Types::Number::Number::_any2mpz($$p_sidef) // return Sidef::Types::Array::Array->new();
950  
951 # 1. Convert Sidef PolynomialMod into dense GMPz Array
952 my $hash = $original->[0];
953 my $deg_orig = List::Util::max(CORE::keys %$hash) // -1;
954 my @orig_poly;
955 for my $i (0 .. $deg_orig) {
956 if (exists $hash->{$i}) {
957 push @orig_poly, Math::GMPz::Rmpz_init_set(Sidef::Types::Number::Number::_any2mpz(${$hash->{$i}}));
958 }
959 else {
960 push @orig_poly, Math::GMPz::Rmpz_init();
961 }
962 }
963 my $orig_poly = _poly_strip(\@orig_poly);
964 $deg_orig = _poly_deg($orig_poly);
965  
966 # Handle leading coefficient
967 my $lc_sidef;
968 if ($deg_orig < 0) {
969 $lc_sidef = Sidef::Types::Number::Number::ZERO;
970 return Sidef::Types::Array::Array->new([Sidef::Types::Array::Array->new([$lc_sidef, Sidef::Types::Number::Number::ONE])]);
971 }
972 else {
973 $lc_sidef = Sidef::Types::Number::Number::_set_int($orig_poly->[$deg_orig]);
974 }
975  
976 # 2. Extract Monic and Squarefree part
977 my $f = _poly_monic(_poly_clone($orig_poly), $p);
978 my $df = _poly_derivative($f, $p);
979 if (_poly_deg($df) >= 0) {
980 my $sq = _poly_gcd($f, $df, $p);
981 if (_poly_deg($sq) > 0) {
982 my ($q, $r) = _poly_divmod($f, $sq, $p);
983 $f = _poly_monic($q, $p);
984 }
985 }
986  
987 # 3. Factorization Stages
988 my @ddf_groups = _poly_deg($f) <= 0 ? () : _poly_ddf($f, $p);
989  
990 my @irreducibles;
991 for my $pair (@ddf_groups) {
992 my ($d, $fk) = @$pair;
993 next if _poly_deg($fk) <= 0;
994 push @irreducibles, _poly_edf($fk, $d, $p, $p_sidef);
995 }
996  
997 # 4. Trial Division for Multiplicities
998 my $remainder = _poly_clone($orig_poly);
999 my @factors;
1000  
1001 for my $irred (@irreducibles) {
1002 my $e = 0;
1003 while (1) {
1004 my ($q, $r) = _poly_divmod($remainder, $irred, $p);
1005 last if _poly_deg($r) >= 0; # Remainder is NOT zero
1006 $e++;
1007 $remainder = $q;
1008 }
1009  
1010 if ($e > 0) {
1011  
1012 # Map dense array back to Sidef object
1013 my %h;
1014 for my $i (0 .. _poly_deg($irred)) {
1015 next if Math::GMPz::Rmpz_sgn($irred->[$i]) == 0;
1016 my $r = $irred->[$i];
1017 $h{$i} = bless(\$r, 'Sidef::Types::Number::Number');
1018 }
1019  
1020 my $irred_sidef = __PACKAGE__->new(%h, $p_sidef);
1021 push @factors, Sidef::Types::Array::Array->new([$irred_sidef, Sidef::Types::Number::Number::_set_int($e)]);
1022 }
1023 }
1024  
1025 my $arr = Sidef::Types::Array::Array->new(\@factors)->sort;
1026 $arr->unshift(Sidef::Types::Array::Array->new([$lc_sidef, Sidef::Types::Number::Number::ONE]));
1027  
1028 return $arr;
1029 }
1030  
1031 sub factor {
1032 my ($self) = @_;
1033 Sidef::Types::Array::Array->new([map { ($_->[0]) x CORE::int($_->[1]) } @{$self->factor_exp}]);
1034 }
1035  
1036 {
1037 no strict 'refs';
1038  
1039 foreach my $method (qw(ge gt lt le)) {
1040 *{__PACKAGE__ . '::' . $method} = sub {
1041 my ($x, $y) = @_;
1042 ($x->cmp($y) // return undef)->$method(Sidef::Types::Number::Number::ZERO);
1043 };
1044 }
1045  
1046 *{__PACKAGE__ . '::' . '/'} = \&div;
1047 *{__PACKAGE__ . '::' . '//'} = \&idiv;
1048 *{__PACKAGE__ . '::' . '÷'} = \&div;
1049 *{__PACKAGE__ . '::' . '*'} = \&mul;
1050 *{__PACKAGE__ . '::' . '%'} = \&mod;
1051 *{__PACKAGE__ . '::' . '+'} = \&add;
1052 *{__PACKAGE__ . '::' . '-'} = \&sub;
1053 *{__PACKAGE__ . '::' . '**'} = \&pow;
1054 *{__PACKAGE__ . '::' . '++'} = \&inc;
1055 *{__PACKAGE__ . '::' . '--'} = \&dec;
1056 *{__PACKAGE__ . '::' . '<'} = \&lt;
1057 *{__PACKAGE__ . '::' . '>'} = \&gt;
1058 *{__PACKAGE__ . '::' . '<=>'} = \&cmp;
1059 *{__PACKAGE__ . '::' . '<='} = \&le;
1060 *{__PACKAGE__ . '::' . '≤'} = \&le;
1061 *{__PACKAGE__ . '::' . '>='} = \&ge;
1062 *{__PACKAGE__ . '::' . '≥'} = \&ge;
1063 *{__PACKAGE__ . '::' . '=='} = \&eq;
1064 *{__PACKAGE__ . '::' . '!='} = \&ne;
1065 }
1066  
1067 1