| 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__ . '::' . '/'} = \÷ | ||
| 1047 | *{__PACKAGE__ . '::' . '//'} = \&idiv; | ||
| 1048 | *{__PACKAGE__ . '::' . '÷'} = \÷ | ||
| 1049 | *{__PACKAGE__ . '::' . '*'} = \&mul; | ||
| 1050 | *{__PACKAGE__ . '::' . '%'} = \&mod; | ||
| 1051 | *{__PACKAGE__ . '::' . '+'} = \&add; | ||
| 1052 | *{__PACKAGE__ . '::' . '-'} = \⊂ | ||
| 1053 | *{__PACKAGE__ . '::' . '**'} = \&pow; | ||
| 1054 | *{__PACKAGE__ . '::' . '++'} = \&inc; | ||
| 1055 | *{__PACKAGE__ . '::' . '--'} = \&dec; | ||
| 1056 | *{__PACKAGE__ . '::' . '<'} = \< | ||
| 1057 | *{__PACKAGE__ . '::' . '>'} = \> | ||
| 1058 | *{__PACKAGE__ . '::' . '<=>'} = \&cmp; | ||
| 1059 | *{__PACKAGE__ . '::' . '<='} = \≤ | ||
| 1060 | *{__PACKAGE__ . '::' . '≤'} = \≤ | ||
| 1061 | *{__PACKAGE__ . '::' . '>='} = \≥ | ||
| 1062 | *{__PACKAGE__ . '::' . '≥'} = \≥ | ||
| 1063 | *{__PACKAGE__ . '::' . '=='} = \&eq; | ||
| 1064 | *{__PACKAGE__ . '::' . '!='} = \≠ | ||
| 1065 | } | ||
| 1066 | |||
| 1067 | 1 |