1v 1.0 -- 2-Dec-07 : 2 3 * First version of FLINT, includes fmpz_poly, fmpz and mpQS 4 5v 1.0.1 -- 7-Dec-07 : 6 7 * Fixed a bug in _fmpz_poly_maxbits1 on 32 bit machines, reported by Michael Abshoff and Carl Witty 8 * Removed some instances of u_int64_t and replaced them with uint64_t, reported by Michael Abshoff 9 * Replaced sys/types.h with stdint.h 10 * Added FLINT macros to documentation 11 * Corrected numerous typos in documentation 12 13v 1.0.2 -- 10-Dec-07 14 15 * Rewrote tuning code for integer multiplication functions, making it more robust and fixing a bug 16 which showed up on 32 bit machines (reported by Michael Abshoff and Jaap Spies). Factored the tuning 17 code out into a number of macros. 18 19v 1.0.3 -- 16-Dec-07 20 21 * Fixed a bug in the polynomial memory management code which caused a segfault 22 * Fixed a bug in the pseudo division code which caused a block overrun 23 24v 1.0.4 -- 04-Jan-08 25 26 * Fixed a bug in the bernoulli_zmod example program and associated polynomial zmod code which caused memory corruption. 27 * Fixed a bug in the fmpz-test code which manifested on 32 bit machines, reported by David Harvey. 28 * Fixed some bugs in the pari profiling code. 29 30v 1.0.5 -- 05-Jan-08 31 32 * Fixed some inline issues which cause problems because of the C99 inline rules (reported by David Harvey). 33 * Fixed a makefile issue reported (and solved) by David Harvey when *not* linking against NTL. 34 35v 1.0.6 -- 17-Jan-08 36 37 * Fixed an issue with FLINT_BIT_COUNT on certain machines (probably due to arithmetic shift issues) 38 39v 1.0.7 -- 22-Jan-08 40 41 * Made F_mpn_mul binary compatible with the way mpn_mul *operates* in practice. 42 43v 1.0.8 -- 15-Feb-08 44 45 * Fixed a bug in fmpz_poly_right_shift (reported by Kiran Kedlaya) 46 47v 1.0.9 -- 11-Mar-08 48 49 * Fixed a memory allocation bug in fmpz_poly_power 50 51v 1.0.10 -- 16-Jun-08: 52 53 * integer gcd (this just wraps the GMP gcd code) 54 * polynomial content 55 * convert to and from FLINT and NTL integers and polynomials 56 * get a coefficient of a polynomial efficiently as a read only mpz_t 57 * print polynomials in a prettified format with a specified variable 58 59v 1.0.11 -- 9-Jul-08 60 61 * Fixed a bug in z_ll_mod_precomp on ia64 (reported by Michael Abshoff and William Stein) 62 63v 1.0.12 -- 11-Jul-08 64 * Removed some Opteron tuning flags which cause illegal instruction errors on Pentium4 65 * Fixed numerous memory leaks in fmpz_poly test code 66 * Fixed memory leak in fmpz_poly_power_trunc_n 67 * Fixed major memory leaks in fmpz_poly_xgcd_modular 68 * Rewrote __fmpz_poly_mul_karatrunc_recursive and _fmpz_poly_mul_karatsuba_trunc to "prove code" and got rid of some dirty memory issues 69 * Fixed some potential illegal memory accesses to do with cache prefetching in fmpz_poly.c 70 71v 1.0.13 -- 13-Jul-08 72 * Fixed memory leaks and dirty memory issues in test code for numerous modules. 73 * Removed further issues with cache prefetching in mpn_extras.c 74 75v 1.0.14 -- 23-Sep-08 76 * Update long_extras and test code for the sake of new quadratic sieve (new functions in long_extras remain undocumented) 77 * Removed many bugs from tinyQS and mpQS and joined them into a single program for factoring integers 78 79v 1.0.15 -- 15-Oct-08 80 * Fixed a bug which causes a segfault when setting a coefficient of the zero polynomial to zero 81 * Fixed build bug in longlong.h on s390 platform 82 83v 1.0.16 -- 22-Oct-08 84 * Fixed a segfault when trying to truncate a polynomial to an longer length than it currently is, with the function fmpz_poly_truncate (reported by Craig Citro) 85 86v 1.0.17 -- 30-Nov-08 87 * Fixed a segfault caused by left shifting of polynomials with zero limbs allocated in division and pseudo division functions. 88 * Fixed a bound used in fmpz_gcd_modular to use a proven bound 89 * Fixed a bug in fmpz_poly-profile where the top bit of random coefficients of n bits was always set 90 91v 1.0.18 -- 05-Dec-08 92 * Fixed another bug in the fmpz_poly_set_coeff_* functions which resulted in dirty coefficients 93 94v 1.0.19 -- 12-Dec-08 95 * Fixed a bug in z_remove_precomp 96 97v 1.0.20 -- 13-Dec-08 98 * Fixed some bugs in conversion of zmod_poly's to and from strings 99 100v 1.0.21 -- 25-Dec-08 101 * Fixed the Christmas bug reported by Michael Abshoff which causes a test failure in fmpz_poly_gcd_modular and a hang in fmpz_poly_invmod_modular on 32 bit machines 102 103v 1.1.0 -- 21-Dec-08 (some of the following features were previewed in FLINT 1.0.11): 104 105 * integer gcd (this just wraps the GMP gcd code) 106 * polynomial content 107 * primitive part 108 * convert to and from FLINT and NTL integers and polynomials 109 * get a coefficient of a polynomial efficiently as a read only mpz_t 110 * print polynomials in a prettified format with a specified variable 111 * Sped up integer multiplication 112 * Convert to and from zmod_polys from fmpz_polys 113 * Chinese remainder for fmpz_polys 114 * Leading coeff macro 115 * Euclidean norm of polynomials 116 * Exact division testing of polynomials 117 * Polynomial GCD (subresultant, heuristic, modular) 118 * Modular inversion of polynomials 119 * Resultant 120 * XGCD (Pohst-Zassenhaus) 121 * Multimodular polynomial multiplication 122 * Rewritten karatsuba_trunc function 123 * Rewritten division functions 124 * Polynomial derivative 125 * Polynomial evaluation 126 * Polynomial composition 127 * Addition and subtraction of zmod_polys 128 * Sped up multiplication of zmod_polys 129 * Extended multiplication of zmod_polys to allow up to 63 bit moduli 130 * zmod_poly subpolynomials 131 * zmod_poly reverse 132 * Truncated multiplication for zmod_polys (left, right, classical and KS) 133 * Scalar multiplication 134 * Division for zmod_polys (divrem and div, classical, divide and conquer and newton) 135 * Series inversion for zmod_polys 136 * Series division for zmod_polys 137 * Resultant for zmod_polys 138 * GCD for zmod_polys including half-gcd 139 * Inversion modulo a polynomial for zmod_polys 140 * XGCD for zmod_polys 141 * Squarefree factorisation for zmod_polys 142 * Berlekamp factorisation for zmod_polys 143 * Irreducibility testing for zmod_polys 144 * Derivative for zmod_polys 145 * Middle product for zmod_polys (sped up newton division) 146 * addmod, submod and divmod for ulongs 147 * Sped up limb sized integer square root 148 * Partial factoring of ulongs 149 * z_randbits 150 * Pocklington-Lehmer primality testing 151 * BSPW pseudo-primality testing 152 * Fermat pseudo-primality testing 153 * Fast Legendre symbol computation 154 * Chinese remainder for fmpzs 155 * Square root with remainder for fmpzs 156 * Left and right shift for fmpzs 157 * Reduction modulo a ulong for fmpzs 158 * Montgomery redc, mulmod, divmod and mod for fmpzs 159 * Multimodular reduction and CRT for fmpzs 160 * fmpz_mulmod and fmpz_divmod 161 * fmpz_invert for inversion modulo an fmpz 162 * Dramatically sped up gcd for small fmpzs 163 * Computation of 1D, 2D and some 3D theta functions 164 * Example program for multiplying theta functions 165 * Test code now times test functions 166 * Quick and dirty timing function for profiler 167 * Tiny quadratic sieve for small one and two limb integers 168 * Completely rewritten self initialising multiple polynomial quadratic sieve 169 * Build fix for 64 bit OSX dylibs (reported by Michael Abshoff) 170 171v 1.1.1 -- 11-Feb-09 172 173 * Fixed bugs in _fmpz_poly_scalar_mul_fmpz, fmpz_poly_gcd_heuristic and fmpz_poly_gcd_subresultant and fixed bugs in test__fmpz_poly_scalar_div_fmpz, test_fmpz_poly_scalar_div_fmpz and test_fmpz_poly_scalar_div_mpz. 174 175v 1.1.2 -- 1-Mar-09 176 177 * Fixed some memory allocation slowdowns and bugs in fmpz_poly division and pseudo division functions (reported by William Stein). 178 179v 1.1.3 -- 1-Mar-09 180 181 * Inserted some missing return values in zmod_poly test code. 182 183v 1.2.0 -- 10-Mar-09 184 185 * made memory manager, fmpz and fmpz_poly threadsafe 186 * Code for running tests in parallel (not activated) 187 * Sped up fmpz_poly_scalar_div_ui/si when scalar is 1/-1 188 * Parallelise _fmpz_poly_mul_modular 189 * fmpz_mul_modular_packed to pack coefficients to the byte before running _fmpz_poly_mul_modular 190 * fmpz_poly_pseudo_rem_cohen (not documented) 191 * special case for leading coeff 1/-1 in fmpz_poly_pseudo_divrem_basecase 192 * removed a memory allocation bug which caused a massive slowdown in fmpz_poly_pseudo_divrem_basecase 193 * fmpz_poly_pseudo_rem_basecase (not documented) 194 * fmpz_poly_pseudo_rem (not asymptotically fast) 195 * fmpz_poly_signature (not asymptotically fast) 196 * basic fmpz_poly_is_squarefree function 197 * included zn_poly in trunk and made FLINT build zn_poly as part of its build process 198 * switched to using zn_poly for polynomial multiplication, newton inversion, scalar multiplication in zmod_poly 199 * Integer cube root of word sized integers 200 * Fibonacci pseudoprime test 201 * BSPW probable prime test 202 * n - 1 primality test 203 * Complete implementation of z_issquarefree 204 * Significantly improved the thetaproduct example program. 205 * Fixed bug in fmpz_poly_byte_pack which is triggered when trying to pack into fields a multiple of 8 bytes (could cause a segfault) 206 * Fixed a bug in fmpz_poly_pseudo_divrem (relied on an uninitialised poly to have length 0) 207 * Fixed bug in fmpz_multi_CRT_ui (could segfault) 208 * Fixed bug in fmpz_multi_mod_ui (could segfault) 209 * Fixed memory leak in zmod_poly_factor_squarefree 210 * Fixed memory leak in zmod_poly_from_string 211 212v 1.2.1 -- 14-Mar-09 213 214 * Removed some FLINT 2.0 code which was interfering with the build of the NTL-interface 215 * Removed an omp.h from fmpz_poly.c. 216 217v 1.2.2 -- 20-Mar-09 218 219 * Fixed a memory leak in zmod_poly_factor 220 * Fixed zmod_poly-profile build 221 222v 1.2.3 -- 31-Mar-09 223 224 * Fixed bugs in all fmpz_poly evaluation functions, identified by Burcin Erocal. 225 226v 1.2.4 -- 4-Apr-09 227 228 * Defined THREAD to be blank on Apple CC and __thread for thread local storage on other gcc's (where it's defined) 229 * #undef ulong in profiler.h where time.h and other system time headers are included (both reported by M. Abshoff) 230 231v 1.2.5 -- 18-Apr-09 232 233 * Upgraded to zn_poly-0.9 to avoid a serious error in squaring of large polynomials over Z/nZ 234 235v 1.3.0 -- 09-Jun-09 236 237 * Added new code for checking 2nd, 3rd and 5th roots 238 * Fixed a bug in z_factor 239 * Connected quadratic sieve for factoring large ulongs 240 * Added one line factor algorithm 241 * constructed best of breed factor algorithm 242 * Fixed termination conditions for z_intcuberoot and z_intfifthroot which were broken 243 * Added some code for special cases which cause infinite loops in cuberoot and fifthroot 244 * Went back to ceil(pow(n, 0.33333333)) and ceil(pow(n, 0.2)) for initial guesses in cube and fifth root functions as these were about 50% faster than sqrt(n) and sqrt(sqrt(n)) respectively. 245 * Added test code for z_intfifthroot 246 * Added test code for z_factor_235power 247 * Fixed some uninitialised data found by valgrind in intcuberoot and intfifthroot 248 * Fixed multiply defined PRIME_COUNT in long_extras-test 249 * Got rid of gotos in some functions in long_extras 250 * Knocked optimisation level back to -O2 because it miscompiles on sage.math 251 * Changed tables to use uint64_t's instead of ulongs which are not 64 bits on a 32 bit machine 252 * Only checked MAX_HOLF on 64 bit machine 253 * Changed MAX_SQUFOF to WORD(-1) 254 * Check constant 0x3FFFFFFFFUL only on a 64 bit machine 255 * Fixed a bug in z_oddprime_lt_4096 on 32 bit machines 256 * Fixed some TLS issues with Cygwin 257 * Fixed some typos in makefile 258 * Fixed a wrong path in fmpz.c 259 260v 1.4.0 -- 06-Jul-09 261 262 * Sped up zmod_poly division in case where operands are the same length 263 * Sped up zmod_poly division in case where operands have lengths differing by 1 264 * Fixed a bug in zmod_poly_gcd for polynomials of zero length 265 * Sped up zmod_poly_gcd considerably (both euclidean and half gcd) 266 * Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably 267 * Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast 268 * Made zmod_poly_resultant asymptotically fast 269 * Added optimised zmod_poly_rem function 270 * Fixed a divide by zero bug in zmod_poly_factor_berlekamp 271 * Added test code for z_factor_tinyQS and z_factor_HOLF 272 * Fixed many bugs in the z_factor code, tinyQS and mpQS 273 * Corrected numerous typos in the documentation and added missing descriptions 274 * Added F_mpz_cmp function 275 * Added documentation to the manual for the new F_mpz module 276 277v 1.5.0 -- 22-Sep-09 278 279 * Added multimodular reduction and CRT to F_mpz module 280 * Fixed some bugs in F_mpz module and numerous bugs in test code 281 * Added zmod_poly_compose 282 * Added zmod_poly_evaluate 283 * Added functions for reduced evaluation and composition to fmpz_poly module (contributed by Burcin Erocal) 284 * Fixed bugs in the primality tests in long_extras 285 * Removed all polynomial multimodular multiplication functions 286 * Added new thetaproduct code used in the 1 trillion triangles computation 287 * Fixed a severe bug in the fmpz_poly_pseudo_div function reported by Sebastian Pancratz 288 * Added fmpz_comb_temp_init/clear functions 289 * Fixed a normalisation buglet in fmpz_poly_pack_bytes 290 * Added F_mpz_pow_ui function (contributed by Andy Novocin) 291 * Fixed a severe bug in the FFT reported by William Stein and Mariah Lennox (fix contributed by David Harvey) 292 * Removed some memory leaks from F_mpz test code 293 * Fixed bug in zmod_poly_evaluate test code 294 295v 1.6.0 -- 24-Dec-10 296 297 Bugs: 298 ==== 299 300 * Fixed a memory leak in mpz_poly_to_string_pretty 301 * Fixed a bug inherited from an old version of fpLLL 302 * Makefile to respect CC and CXX 303 * Fixed bug in F_mpz_set_si 304 * Fixed bug in F_mpz_equal 305 * Most for loops to C90 standard (for easier MSVC porting) 306 * Better Cygwin support 307 * Fixed a bug in zmod_poly_resultant 308 * Fixed bug in F_mpz_mul_KS/2 309 * Fixed bug in tinyQS 310 * Worked around some known bugs in older GMP/MPIR's 311 312 Major new functionality 313 ======================= 314 * F_mpz_poly_factor_zassenhaus 315 * F_mpz_poly_factor (incl. fmpz_poly_factor wrapper) using new vH-N approach 316 (see the paper of van Hoeij and Novocin and the paper of van Hoeij, Novocin 317 and Hart) 318 * Implementation of new CLD bounds function for polynomial factors 319 (see the paper of van Hoeij, Novocin and Hart 320 * Restartable Hensel lifting 321 * Heuristic LLL implementations using doubles and mpfr 322 * LLL implementations optimised for knapsack lattices 323 * New (probably subquadratic) LLL implementation (ULLL) 324 * zmod_poly_factor_cantor_zassenhaus 325 * New F_mpz_mod_poly module for polynomials over Z/pZ for multiprec. p 326 327 Some of the other new functions added 328 ===================================== 329 330 F_mpz: 331 332 * F_mpz_gcd 333 * F_mpz_smod 334 * F_mpz_mod_preinv 335 * F_mpz_fdiv_qr 336 * F_mpz_get/set_mpfr/2exp 337 * F_mpz_sscanf 338 * F_mpz_set_d 339 340 F_mpz_poly: 341 342 * read F_mpz_poly to_string/from_string/fprint/print/fread/pretty 343 * F_mpz_poly_to/from_zmod_poly 344 * F_mpz_poly_scalar_div_exact 345 * F_mpz_poly_smod 346 * F_mpz_poly_derivative, F_mpz_poly_content, F_mpz_poly_eval_horner_d/2exp 347 * F_mpz_poly_scalar_abs 348 * F_mpz_poly_set_d_2exp 349 * F_mpz_poly_div/divrem 350 * F_mpz_poly_gcd 351 * F_mpz_poly_is_squarefree 352 * F_mpz_poly_factor_squarefree 353 * F_mpz_poly_mul_trunc_left 354 * F_mpz_poly_pseudo_div 355 * F_mpz_poly_set_coeff 356 * F_mpz_poly_pow_ui 357 * Inflation/deflation trick for factorisation 358 359 zmod_poly: 360 361 * Inflation/deflation trick for factorisation 362 363 mpz_mat: 364 365 * mpz_mat_from_string/to_string/fprint/fread/pretty 366 367 mpq_mat: 368 369 * mpq_mat_init/clear 370 * Gramm-schmidt Orthogonalisation 371 372 F_mpz_mat: 373 374 * F_mpz_mat_print/fprint/fread/pretty 375 * F_mpz_mat_mul_classical 376 * F_mpz_mat_max_bits/2 377 * F_mpz_mat_scalar_mul/div_2exp 378 * F_mpz_mat_col_equal 379 * F_mpz_mat_smod 380 * F_mpz_vec_scalar_product/norm 381 * F_mpz_vec_add/submul_ui/si/F_mpz/2exp 382 383 zmod_mat: 384 385 * classical multiplication 386 * strassen multiplication 387 * scalar multiplication 388 * zmod_mat_equal 389 * zmod_mat_add/sub 390 * zmod_mat_addmul_classical 391 392 d_mat: 393 394 * d_vec_norm, d_vec_scalar_product 395 396 mpfr_mat: 397 398 * mpfr_vec_scalar_product/norm 399 400v 2.0 -- 16 Jan 2011 401 N.B: FLINT 2 is a complete rewrite of flint from scratch 402 It includes the following modules: 403 404ulong_extras: (word sized integers and modular arithmetic) 405 * random numbers (randint, randbits, randprime, randint) 406 * powering 407 * reverse binary 408 * mod, divrem, mulmod all with precomputed inverses 409 * gcd, invgcd, xgcd 410 * jacobi symbols 411 * addmod, submod, invmod, powmod 412 * prime sieve, nextprime, prime-pi, nth-prime 413 * primality testing (small, binary search, Pocklington-Lehmer, Pseudosquare) 414 * probably prime tests (strong base-a, Fermat, Fibonacci, BPSW, Lucas) 415 * sqrt, sqrtrem, is-square, perfect-power (2,3,5) 416 * remove, is-squarefree 417 * factorisation (trial-range, trial, power (2,3,5), one-line, SQUFOF) 418 * Moebius mu, Euler phi 419 420fmpz: (memory managed multiple precision integers) 421 * memory management (init, clear) 422 * random numbers (randbits, randm) 423 * conversion to and from long, ulong, doubles, mpz's, strings 424 * read/write to file, stdin, stdout 425 * sizeinbase, bits, size, sgn, swap, set, zero 426 * cmp, cmp-ui, cmpabs, equal, is-zero, is-one 427 * neg, abs, add, add-ui, sub, sub-ui, mul, mul-si, mul-ui, mul-2exp 428 * addmul, addmul-ui, submul, submul-ui 429 * cdiv-q, cdiv-q-si, cdiv-q-ui 430 * fdiv-q, fdiv-q-si, fdiv-q-ui, fdiv-qr, fdiv-q-2exp 431 * tdiv-q, tdiv-q-si 432 * divexact, divexact-si, divexact-ui 433 * mod, mod-ui 434 * powering 435 * sqrt, sqrt-rem 436 * factorial 437 * gcd, invmod 438 * bit-pack, bit-unpack 439 * multimodular reduction, CRT 440 441fmpz_vec: (vectors over fmpz's) 442 * memory management (init, clear) 443 * random vectors 444 * max-bits, max-limbs 445 * read/write to file/stdin/stdout 446 * set, swap, zero, neg 447 * equal, is-zero 448 * sort 449 * add, sub 450 * scalar multiplication by fmpz, ulong, long, 2exp 451 * exact division by fmpz, long, ulong 452 * fdiv-q by fmpz, long, ulong, 2exp 453 * tdiv-q by fmpq, long, ulong 454 * addmul by fmpz, long, long by 2exp 455 * submul by fmpz, long, long by 2exp 456 * Gaussian content 457 458fmpz_poly: (polys over fmpz's) 459 * memory management (init, realloc, fit-length, clear) 460 * random polys 461 * normalise, set-length, truncate 462 * length, degree, max-limbs, max-bits 463 * set, set-si, set-ui, set-fmpz, set-str 464 * get-str, get-str-pretty 465 * zero, one, zero-coeffs 466 * swap, reverse 467 * get/set coeffs from fmpz, long, ulong 468 * get-coeff-ptr, lead 469 * equal, is-zero 470 * add, sub 471 * scalar multiplication by fmpz, long, ulong 472 * scalar addmul/submul by fmpz 473 * scalar fdiv by fmpz, long, ulong 474 * scalar tdiv by fmpz, long, ulong 475 * scalar divexact by fmpz, long, ulong 476 * bit pack, bit unpack 477 * multiplication (classical, karatsuba, KS) 478 * mullow (classical, karatsuba, KS) 479 * mulhigh (classical, karatsuba) 480 * middle product (classical) 481 * powering (small, binary exponent, binomial, multinomial, addition chains) 482 * truncated powering (binary exponent) 483 * shift left/right 484 * euclidean norm 485 * gcd (subresultant) 486 * resultant 487 * content, primitive part 488 * divrem (basecase, divide-and-conquer) 489 * div (basecase, divide-and-conquer) 490 * rem (basecase) 491 * invert series (basecase, Newton) 492 * div series 493 * pseudo divrem (basecase, divide-and-conquer, Cohen) 494 * rem (Cohen) 495 * div 496 * evaluate (Horner) at fmpz, mpq, a mod n 497 * composition (Horner, divide-and-conquer) 498 * signature 499 * read/write to file/stdin/stdout 500 501fmpq_poly: (polynomials over Q stored as poly over fmpz with fmpz denominator) 502 * memory management (init, realloc, fit-length, clear) 503 * random polys 504 * set-length, canonicalise, normalise, truncate 505 * is-canonical, length, degree 506 * reference to numerator, denominator 507 * set, set-si, set-ui, set-fmpz, set-mpz, set-mpq 508 * set-array-mpq, set-str 509 * get-str, get-str-pretty 510 * zero, neg, swap 511 * invert 512 * set coefficient to mpq, long, ulong, fmpz, mpz 513 * get coefficient as mpq 514 * equal, cmp, is-one, is-zero 515 * add, sub 516 * scalar multiplication by long, ulong, fmpz, mpq 517 * scalar division by fmpz, long, ulong, mpq 518 * multiplication, mullow 519 * powering 520 * shift left/right 521 * divrem, div, rem 522 * invert series (Newton iteration) 523 * divide series 524 * derivative 525 * evaluate at fmpz, mpq 526 * composition, scale by constant 527 * content, primitive part 528 * make-monic, is-monic 529 * is-squarefree 530 * read/write to file/stdin/stdout 531 532nmod_vec: (vectors over Z/nZ for n fitting in a machine word) 533 * memory management (init/clear) 534 * macros for efficient reduction of 1, 2 and 3 limb integers mod n 535 * macro for addmul mod n 536 * add/sub/neg individual coefficients mod n 537 * random vectors 538 * set, zero, swap 539 * reduce, max-bits 540 * equal 541 * add, sub, neg 542 * scalar multiplication by a value reduced mod n 543 * scalar addmul by a value reduced mod n 544 545nmod_poly: (polynomials over Z/nZ for n fitting in a machine word) 546 * memory management (init, realloc, fit-length, clear) 547 * random polys 548 * normalise, truncate 549 * length, degree, modulus, max-bits 550 * set, swap, zero, reverse 551 * get/set coefficients as ulongs, strings 552 * read/write to file, stdin, stdout 553 * equal, is-zero 554 * shift left/right 555 * add, sub, neg 556 * scalar multiplication by a value reduced mod n 557 * make-monic 558 * bit pack, bit unpack 559 * multiplication (classical, KS) 560 * mullow (classical, KS) 561 * mulhigh (classical) 562 * powering (binary exponent) 563 * pow-trunc (binary exponent) 564 * divrem (basecase, divide-and-conquer, Newton iteration) 565 * div (basecase, divide-and-conquer, Newton iteration) 566 * invert series (basecase, Newton iteration) 567 * divide series (Newton iteration) 568 * derivative 569 * evaluation at a value taken mod n 570 * composition (Horner, divide-and-conquer) 571 * gcd (euclidean) 572 573fmpz_mat: (matrices over fmpz's) 574 * memory management (init, clear) 575 * random matrices (bits, integer relations, simultaneous diophantine equations 576 NTRU-like, ajtai, permutation of rows and cols of a diagonal matrix, random 577 of given rank, random of given determinant, random elementary operations) 578 * set, init-set, swap, entry pointer 579 * write to file or stdout 580 * equal 581 * transpose 582 * multiplication (classical, multimodular) 583 * inverse 584 * determinant 585 * row reduce (Gaussian and Gauss-Jordan fraction-free elimination) 586 * rank 587 * solve Ax = b, solve AX = B 588 * fraction free LU decomposition 589 590nmod_mat: (matrices over Z/nZ for n fitting in a machine word) 591 * memory management (init, clear) 592 * random matrices (uniform, full, permutations of diagonal matrix, random of 593 given rank, random elementary operations) 594 * set, equal 595 * print to stdout 596 * add 597 * transpose 598 * multiplication (classical, Strassen, A*B^T) 599 * row reduction (Gaussian and Gauss-Jordan) 600 * determinant 601 * rank 602 * solve (Ax = b, AX = B, solve with precomputed LU) 603 * invert 604 605arith: (arithmetic functions) 606 * Bernoulli numbers 607 * Bernoulli polynomials 608 * primorials (product of primes up to n) 609 * harmonic numbers 610 * Stirling numbers 611 * Euler phi function 612 * Moebius mu function 613 * Sigma (sum of powers of divisors) 614 * Ramanujan tau function 615 616 617examples: (example programs) 618 * compute coefficients of q-series of Delta function 619 620mpfr_vec: (vectors over mpfr reals) 621 * memory management (init, clear) 622 * add 623 * set, zero 624 * scalar multiplication by mpfr, 2exp 625 * scalar product 626 627mpfr_mat: (matrices over mpfr reals) 628 * memory management (init, clear) 629 630v 2.1 -- 9 Mar 2011 631 632fmpz 633---- 634 * Simplified interface for fast multimodular reduction and CRT reconstruction 635 * Fixed segmentation fault in fmpz_multi_mod_ui when the input exceeds the product of the moduli 636 * Added simple incremental CRT functions (fmpz_CRT_ui, fmpz_CRT_ui_unsigned) to complement the existing fast ones 637 * Added example programs for CRT 638 * Added random number generators designed for testing modular code (fmpz_randtest_mod, fmpz_randtest_mod_signed) 639 * Added fmpz_fdiv_ui for remainder on division by an ulong 640 * Added fmpz_bin_uiui for computing binomial coefficients 641 * Added fmpz_mul2_uiui and fmpz_divexact2_uiui for multiplying or dividing an fmpz by a pair of ulongs (efficiently when their product fits in a single limb) 642 643fmpz_mat 644-------- 645 * Added utility functions for basic arithmetic and creating unit matrices 646 * Added multimodular determinant computation (certified or heuristic) 647 * Added support for computing right nullspaces (fmpz_mat_kernel). Fast only for small matrices. 648 * Some internal code cleanup and various small fixes 649 650nmod_mat 651-------- 652 * Faster Gaussian elimination for small moduli 653 * Faster determinants 654 * Faster matrix inversion and nonsingular solving 655 656nmod_poly 657--------- 658 * Added nmod_poly_integral for computing integrals 659 * Added fast square root and inverse square root of power series 660 * Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh) 661 * Made nmod_poly_inv_series_newton more memory efficient 662 663fmpq_poly 664--------- 665 * Added fmpq_poly_integral for computing integrals 666 * Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh) 667 668arith 669----- 670 * Made computation of vectors of Bernoulli numbers faster 671 * Added fast computation of single Bernoulli numbers 672 * Added a separate function for computing denominators of Bernoulli numbers 673 * Added fast computation of Bell numbers (vector and single) 674 * Added fast computation of Euler numbers (vector and single) 675 * Added fast computation of Euler polynomials 676 * Added fast computation of Swinnerton-Dyer polynomials 677 * Added fast computation of Legendre polynomials 678 * Added fast vector computation of the partition function 679 * Added fast vector computation of Landau's function 680 681ulong_extras 682------------ 683 * Added a function for computing factorials mod n 684 685build system 686------------ 687 * Added support for building static and shared libraries 688 * All object files and test/profile/example binaries now build in separate build directory 689 690documentation 691------------- 692 * Large number of corrections 693 694v 2.2 -- 4 Jun 2011 695 696fmpq (multiprecision rational numbers) 697-------------------------------------- 698 * Basic arithmetic functions 699 * Utility functions 700 * Rational reconstruction 701 * Functions for enumerating the rationals 702 703fmpq_mat (matrices over Q) 704-------------------------- 705 * Basic arithmetic functions 706 * Utility functions 707 * Fast multiplication 708 * Classical and fraction-free reduced row echelon form 709 * Determinants 710 * Fast non-singular solving 711 712fmpz_poly_mat (matrices over Z[x] 713--------------------------------- 714 * Basic arithmetic functions 715 * Utility functions 716 * Fraction-free row reduction and determinants 717 * Fast determinants (experimental) 718 719fmpz_mat 720-------- 721 * Added more utility functions (scalar multiplication, etc) 722 * Added Dixon's p-adic algorithm (used by fast nonsingular rational system 723 solving) 724 * Added reduced row echelon form 725 * Added conversions between fmpz_mat and nmod_mat 726 * Added CRT functions for fmpz_mats 727 * Faster matrix multiplication for small to medium dimensions 728 729longlong.h 730---------- 731 * Added x86 assembly macros for accumulating sums of two limb operands 732 733nmod_mat 734-------- 735 * Sped up arithmetic for moduli close to FLINT_BITS 736 737arith 738----- 739 * Changed interface of various functions to use new fmpq type 740 741fmpz 742---- 743 * Added fmpz_set_ui_mod 744 * Inlined fmpz_neg, fmpz_set_si, fmpz_set_ui for better performance 745 * Added fmpz_lcm 746 * Small performance improvement to fmpz_CRT_ui 747 748fmpz_vec 749-------- 750 * Added _fmpz_vec_lcm 751 752fmpz_poly_q (rational functions over Q, modeled as quotients of fmpz_polys) 753--------------------------------------------------------------------------- 754 * Basic arithmetic functions 755 * Conversion and IO functions 756 * Evaluation 757 758padic (p-adic numbers -- experimental) 759------------------------------------- 760 * Basic arithmetic 761 * Data conversion and IO 762 * Inverse and square root using Newton iteration 763 * Teichmuller lifts (not optimised) 764 * p-adic exponential function (not optimised) 765 766fmpz_poly 767--------- 768 * Added fmpz_poly_gcd_modular (and fmpz_poly_gcd wrapper) 769 * Added fmpz_poly_xgcd_modular (and fmpz_poly_xgcd wrapper) 770 * Added conversions between fmpz_poly and nmod_poly 771 * Added CRT functions 772 * Added multipoint evaluation and interpolation 773 774nmod_poly 775--------- 776 * Added nmod_poly_xgcd_euclidean (and nmod_poly_xgcd wrapper) 777 * nmod_poly_gcd wrapper 778 779mpn_extras 780---------- 781 * Added MPN_NORM and MPN_SWAP macros. 782 * Added mpn_gcd_full to remove some of the restrictions from the usual mpn_gcd 783 784build fixes 785------------ 786 * fixed make install to create nonexistent dirs (reported by Serge Torres) 787 * -L use /usr instead of /usr/local by default (reported by Serge Torres) 788 * guards for system headers because of flint's use of ulong 789 790v 2.3 -- 1 Jul 2012 791 792general 793------- 794 * many changes to the build system 795 * added NTL interface 796 * switched to custom memory allocation functions flint_malloc etc 797 * in addition to the entries below, fixed a large number of memory leaks, 798 problems with the test code, and bugs in corner cases of various functions 799 * added _fmpz_cleanup_mpz_content as an alternative to _fmpz_cleanup 800 * support MinGW32 801 * support Cygwin 802 * bugfix on ia64 803 * support sparc32/sparc64 804 * support OSX 805 * support Solaris, NetBSD, OpenBSD, etc (if bash, GNU Make present) 806 807ulong_extras 808------------ 809 * implemented the improved Lehman algorithm 810 * added n_jacobi_unsigned to allow n > WORD_MAX 811 * fixed n_sqrtmod for n > WORD_MAX 812 * fixed bug causing n_sqrtmod to hang 813 * added sublinear algorithm for computing factorials mod p 814 * added n_sqrtmod_primepow, n_sqrtmodn and associated functions for 815 computing square roots modulo composite integers 816 * fixed bugs in n_is_prime_pocklington 817 * fixed UWORD_MAX case in powmod and powmod2 818 * fixed problems with the random number generators 819 * fixed rare bug in n_mod_precomp 820 * fixed rare bug in n_is_prime_pseudosquare 821 822long_extras 823----------- 824 * added z_sizeinbase 825 826qsieve 827------ 828 * new module implementing a quadratic sieve for numbers up to two limbs 829 830fft 831--- 832 * new module providing an efficient Schoenhage-Strassen FFT 833 834longlong 835-------- 836 * added assembly code for ia64 and ARM 837 * fixed bug in fallback version of add_sssaaaaaa 838 839fmpz 840---- 841 * added fmpz_fib_ui 842 * added double precision natural logarithm 843 * added fmpz_val2 for 2-valuation 844 * added mul_2exp, div_2exp, cdiv_q_2exp, tdiv_q_2exp, fdiv_r, fdiv_r_2exp, 845 tdiv_ui, mul_tdiv_q_2exp 846 * added get_d/set_d 847 * added fmpz_divisible, divisible_si 848 * optimised fmpz_powm and fmpz_powm_ui 849 * added clog, clog_ui, flog, flog_ui for computing logarithms 850 * added abs_lbound_ui_2exp, ubound_ui_2exp 851 * added fmpz_rfac_ui and fmpz_rfac_uiui for rising factorials 852 * added functions to obtain read-only fmpz_t's from mpz_t's 853 * added fmpz_init_set, init_set_ui 854 * added fmpz_gcdinv 855 * added fmpz_is_square 856 * added fmpz_tstbit, setbit, clrbit, complement, combit, and, or, xor, popcnt 857 * added a sign flag for CRT instead of using separate methods 858 * fixed bugs in fmpz_sqrtmod 859 * fixed a bug in fmpz_bit_unpack that could cause corruption of the global 860 fmpz array when compiled in single mode 861 * fixed a bug in fmpz_sub_ui that could cause memory corruption 862 863fmpz_vec 864-------- 865 * added functions for obtaining the largest absolute value coefficient 866 * added functions for computing the sum and product of an integer vector 867 * made max_bits much faster 868 * added _fmpz_vec_mod_fmpz 869 * made randtest produce sparse output 870 871fmpz_poly 872--------- 873 * added fmpz_poly_sqr, fmpz_poly_sqrlow for squaring a polynomial 874 * added fmpz_poly_lcm 875 * made multipoint interpolation faster by using the Newton basis 876 * added a function for fast division by a linear polynomial 877 * added power series composition (classical and Brent-Kung) 878 * added power series reversion (classical, Newton, fast Lagrange) 879 * added a function for obtaining the largest absolute value coefficient 880 * fixed quadratic memory usage and stack overflow when performing 881 unbalanced division or pseudo division using the divconquer algorithm 882 * fixed a bug in poly_zero_coeffs 883 * fixed a bug in xgcd_modular 884 * allowing +/-1 in the constant term of power series inversion 885 * fixed aliasing bug in divrem 886 * added restartable Hensel lifting and associated utility functions 887 * fixed rem, which used to only call the basecase algorithm 888 * fixed pseudo_divrem, which used to only call the basecase algorithm 889 * implemented Schoenhage-Strassen multiplication (mul_SS, mullow_SS) 890 and enabled this by default 891 * fixed a bug in the heuristic GCD algorithm 892 * added functions for Newton basis conversion 893 * added functions for fast Taylor shift 894 * added fmpz_poly_sqrt implementing a basecase algorithm 895 * added scalar mul_2exp, fdiv_2exp, tdiv_2exp 896 * made randtest produce sparse output 897 * added fmpz_poly_equal_fmpz 898 * improved performance by always using basecase multiplication 899 when one polynomial is short 900 * improved algorithm selection for fmpz_poly_gcd 901 * fixed several bugs in gcd_modular 902 * improved performance of gcd_modular 903 904fmpz_poly_factor 905---------------- 906 * new module for factorisation of fmpz_polys 907 * added a naive implementation of the Zassenhaus algorithm 908 909fmpz_mod_poly 910------------- 911 * new module for polynomials modulo over Z/nZ for arbitrary-precision n 912 * multiplication, powering 913 * classical and divconquer division 914 * series inversion 915 * Euclidean GCD and XGCD 916 * invmod 917 * radix conversion 918 * divconquer composition 919 * GCD and division functions that test invertibility of the 920 leading coefficient 921 922fmpz_mat 923-------- 924 * added det_divisor for computing a random divisor of the determinant 925 * faster determinant computation using divisor trick 926 * faster determinant computation by using multimodular updates 927 * fixed n x 0 x m product not zeroing the result 928 * various interface improvements 929 * faster implementation of Cramer's rule for multiple right hand sides 930 * added fmpz_mat_fread and read 931 * added multi CRT/mod functions 932 * added trace 933 934fmpz_poly_mat 935------------- 936 * fixed n x 0 x m product not zeroing the result 937 * added inverse 938 * added rank computation 939 * added reduced row echelon form and nullspace computation 940 * added more utility functions 941 * added squaring and exponentiation 942 * added balanced product of a sequence of matrices 943 * added truncate, mullow, sqrlow, pow_trunc 944 * added trace 945 946fmpz_factor 947----------- 948 * new module providing interface for integer factorisation 949 * fast expansion of a factored integer 950 951fmpq 952---- 953 * cleaned up and improved performance of rational reconstruction code 954 * allow separate numerator and denominator bounds for rational 955 reconstruction 956 * added continued fraction expansion 957 * added functions for summation using binary splitting 958 * added fmpq_swap 959 * added fmpq_print, fmpq_get_str 960 * added fmpq_pow_si 961 * added functions to obtain read-only fmpq_t's from mpq_t's 962 * added fmpq_cmp 963 964fmpq_mat 965-------- 966 * fixed n x 0 x m product not zeroing the result 967 * added fmpq_mat_transpose 968 * added trace 969 970fmpq_poly 971--------- 972 * improved speed of multipoint interpolation using _fmpz_poly_div_root 973 * fmpq_poly: added power series composition (classical and Brent-Kung) 974 * fmpq_poly: added power series reversion (classical, Newton, fast Lagrange) 975 * fixed bug wherein set_array_mpq modified the input 976 * added gcd, xgcd, lcm, resultant 977 * added fmpq_poly_set_fmpq 978 * added fmpq_poly_get_slice, fmpq_poly_reverse 979 * fixed aliasing bug in divrem 980 * changed some functions to use FLINT scalar types instead of MPIR data types 981 * added fmpq_poly_get_numerator 982 983nmod_poly 984--------- 985 * implemented the half gcd algorithm for subquadratic gcd and xgcd 986 * added multipoint evaluation and interpolation 987 * added asymptotically fast multipoint evaluation and interpolation 988 * added a function for forming the product of linear factors 989 * added a function for fast division by a linear polynomial 990 * added power series composition (classical and Brent-Kung) 991 * added power series reversion (classical, Newton, fast Lagrange) 992 * added nmod_poly_mulmod, powmod and related functions 993 (ported from flint1) 994 * added squarefree, irreducibility tests (ported from flint1) 995 * added Berlekamp and Cantor-Zassenhaus factoring (ported from flint1) 996 * fixed quadratic memory usage and stack overflow when performing 997 unbalanced division using the divconquer algorithm 998 * added compose_series_divconquer 999 * added resultant 1000 * fixed aliasing bug in divrem 1001 * added rem functions 1002 * added divrem_q0, q1 for special cases of division 1003 * added functions for fast Taylor shift 1004 * added nmod_poly_sqrt 1005 * made fread read the modulus from the file 1006 * made randtest produce sparse output 1007 * fixed bug in xgcd_euclidean with scalar inputs 1008 1009nmod_vec 1010-------- 1011 * added functions and macros for computing dot products 1012 * made randtest produce sparse output 1013 1014nmod_mat 1015-------- 1016 * added addmul/submul functions 1017 * asymptotically fast solving of triangular systems 1018 * asymptotically fast LUP decomposition 1019 * asymptotically fast determinant and rank computation 1020 * asymptotically fast reduced row echelon form and nullspace 1021 * asymptotically fast nonsingular solving 1022 * asymptotically fast inverse 1023 * tidied some interfaces 1024 * fixed n x 0 x m product not zeroing the result 1025 * added trace 1026 * made multiplication faster for tiny moduli by means of bit packing 1027 1028nmod_poly_mat 1029------------- 1030 * new module for matrices over Z/nZ[x], with similar 1031 functionality as the fmpz_poly_mat module 1032 * determinant, rank, solving, reduced echelon form, nullspace 1033 * fraction-free Gaussian elimination 1034 * multiplication using bit packing 1035 * multiplication using evaluation-interpolation 1036 * determinant using evaluation-interpolation 1037 1038padic 1039----- 1040 * restructured and improved much of the code 1041 * added padic_log 1042 * improved log and exp using rectangular splitting 1043 * added asymptotically fast log and exp based on binary splitting 1044 1045perm 1046---- 1047 * added the perm module for permutation matrices 1048 * computing the parity of a permutation 1049 * inverting a permutation 1050 1051arith 1052----- 1053 * added generation of cyclotomic polynomials 1054 * added functions for evaluating Dedekind sums 1055 * fast computation of the partition function 1056 * added a function for factoring a Hardy-Ramanujan-Rademacher 1057 type exponential sum 1058 * added Chebyshev polynomials T and U 1059 * added computation of the minimal polynomial of cos(2pi/n) 1060 * added asymptotically fast high-precision approximation of zeta(n) 1061 * added asymptotically fast computation of Euler's constant 1062 * added new algorithms and functions for computing Bell numbers 1063 * fast computation of pi (adapting code written by Hanhong Xue) 1064 * added functions for computing the number of sum of squares 1065 representations of an integer 1066 * renamed functions to have an arith_ prefix 1067 1068v 2.4 -- 20 Nov 2013 1069 1070 * C++ expressions template wrapper 1071 * Fast factorisation of polynomials over Z/nZ 1072 * improved p-adics 1073 * polynomials/matrices over p-adics 1074 * qadics 1075 * Finite fields (small and large F_q), polynomials/matrices over F_q 1076 * Finite fields with Zech logarithm representation 1077 * Fast factorisation of polynomials over F_q 1078 * Faster Brent-Kung modular composition 1079 * New prime sieving code 1080 * Lambert-W function 1081 * Precomputed inverses for polynomials and large integers 1082 * Williams' P+1 integer factoring algorithm 1083 * Harvey's KS2/KS4 polynomial multiplication 1084 * Faster primality testing up to 64 bits 1085 * Support for Cygwin64 and MinGW64 1086 * Support for Clang 1087 * Support for GMP 1088 * Support for Boehm-Demers-Weiser GC 1089 * Support for flint extension modules 1090 1091v 2.4.2 -- 11 Mar 2014 1092 1093 * Fix bug in ARM assembly 1094 1095v 2.4.3 -- 01 Apr 2014 1096 1097 * Fix a linker issue on Mac OSX. 1098 1099v 2.4.4 -- fixed a severe bug in flint's primality code (n_is_prime() affecting n_factor()) 1100 1101v 2.4.5 -- fixed a severe bug in flint's fmpz_poly_gcd_heuristic, reported by 1102 Anton Mellit. 1103 1104v 2.5.0 -- 07 Aug 2015 1105 1106 * LLL (rational, Nguyen-Stehle, from Gram matrix, with_removal, Storjohann/ULLL) 1107 * Hermite normal form (naive, xgcd, Domich-Kannan-Trotter, Kannan-Bachem, Pernet-Stein) 1108 * Smith normal form (diagonal, Kannan-Bachem, Iliopoulos) 1109 * Paterson-Stockmeyer algorithm 1110 * modular resultant 1111 * hgcd resultant 1112 * polynomial discriminant 1113 * multithreaded multimodular Taylor shift 1114 * multithreaded Brent-Kung composition 1115 * multithreaded Kaltofen-Shoup distinct degree factorisation 1116 * multiplication based reduced row echelon form 1117 * place inline functions in library for foreign function interfaces 1118 * Primality tests for large integers (Pocklington, Morrison) 1119 * Probable prime tests for large integers (Lucas, Baillie-PSW, strong-psp, Brillhart-Lehmer-Selfridge) 1120 * CRT for large integers 1121 * Dixon algorithm for nullspace 1122 * Brent-Kung composition in irreducibility and distinct degree factorisation 1123 * floating point QR decomposition 1124 * Schwarz-Rutishauser Gram-Schmidt algorithm 1125 * Ogita-Rump-Oishi dot product 1126 * matrix window functions 1127 * MSVC support (Brian Gladman) 1128 * fast cube/nth-root (Newton, Kahan, magic number, Chebyshev) 1129 * Bodrato matrix squaring 1130 * matrix concatenation functions 1131 * matrix content 1132 * faster n_gcd 1133 * faster n_sqrtmod and fmpz_sqrtmod 1134 * additional functions for returning factor of modulus in polys over Z/nZ 1135 * Hadamard matrix construction 1136 * series addition/subtraction 1137 * faster prime_pi bounds 1138 * speedup creation of sparse polynomials 1139 * speedup n_isprime n_nextprime 1140 * speedup n_isprime_pocklington 1141 * speedups to fmpq_poly and fmpz_poly arithmetic 1142 * speedup polynomial irreducibility testing over Z/pZ 1143 * speedup of rank computation over ZZ 1144 * made CPimport compile time dependency only 1145 * teach flint_printf/sprintf about explicit width format specifiers 1146 * support relative paths in configure 1147 * library soname versioning 1148 * ARM64 patches 1149 * Support MSYS2 1150 * Progress towards supporting MIPS64 1151 * Fix a serious bug in fmpz_poly_signature 1152 1153v 2.5.1 -- 12 Aug 2015 1154 1155 * Fix some build bugs related to soname versioning and ldconfig 1156 * Fix issue with Windows MSVC build 1157 1158v 2.5.2 -- 13 Aug 2015 1159 1160 * Fix further issues with soname versioning and ldconfig 1161 * Fix a bug when using GMP instead of MPIR. 1162 1163v 2.6.0 -- 5 Jun 2020 1164 1165 * multivariate polynomials over most standard rings (sparse distributed) 1166 * APR-CL primality proving 1167 * elliptic curve integer factoring 1168 * minpoly and charpoly 1169 * improved quadratic sieve for integer factoring 1170 * embeddings of finite fields 1171 * pollard rho integer factoring 1172 * p+1 integer factoring 1173 * best of breed smooth integer factoring routine 1174 * best of breed general integer factoring routine 1175 * howell and strong echelon form 1176 * large speedups for solve and hence inverse over Z and Q 1177 * randprime and nextprime functions 1178 * pernet-stein HNF improvements 1179 * moller-granlund precomputed inverses 1180 * resultant_modular_div 1181 * fibonacci polynomials 1182 * exception mechanism/flint_abort 1183 * sqrt of series and polynomials 1184 * division of series over Z 1185 * power sums 1186 * improved base cases of various power series functions 1187 * ability to switch memory allocators 1188 * fast recurrence for Hermite polys 1189 * shifted Legendre polynomials 1190 * Laguerre polynomials 1191 * Gegenbauer polys 1192 * sphinx documentation 1193 * van hoeij with gradual feeding implementation of polynomial factoring over Z 1194 * perfect power detection 1195 * divisibility testing for polynomials 1196 * fast block based memory manager for bundling fmpz allocations 1197 * uniform random generation 1198 * CMake build system 1199 * linear algebra speedups when everything can be kept in longs 1200 * nmod module for integers mod (small) n 1201 * fmpz_mod_mat module for matrices over integers mod multiprecision n 1202 * kronecker product (tensor product) 1203 * random primitive polys (for finite fields) 1204 * thread pool implementation 1205 * threading of FFT for integer and polynomial multiplication over Z 1206 * threading of quadratic sieve for integer factoring 1207 * improved threading of factoring of polynomials mod p 1208 * threading for multivariate polynomial multiplication, division and GCD 1209 * threaded multiplication of matrices mod p 1210 * Berlekamp-Massey (nmod) 1211 * fmpz_mod module for integers mod multiprecision n 1212 * Pohlig-Hellman (discrete log) 1213 * farey_neighbours 1214 * remove openMP option 1215 * additional integer division variants 1216 * speed up mpn_mulmod_preinv 1217 * fft precaching 1218 * cyclotomic polynomial detection 1219 * polynomial root finding over finite fields 1220 * GMP 6.2 support 1221 * MPIR 3.0.0 support 1222 * many small speedups and additional convenience functions added 1223 1224v 2.6.1 -- 23 Jul 2020 1225 1226 * Fix issues on Debian major architectures 1227 * Fix numerous reported bugs (mpoly, fq_poly, mpn_mul_1, mod 2 code, etc.) 1228 1229v 2.6.2 -- 31 Jul 2020 1230 1231 * Fix for choice of generator in an fq finite field of degree one 1232 * Fix an incorrectly written test 1233 1234v 2.6.3 -- 12 Aug 2020 1235 1236 * Fix a bug in generator of finite field in characteristic 2 1237 * Allow Flint to work with GMP 6.1.2 and 6.2.0 interchangeably 1238 * Fix some old license headers 1239 12402.7.0 -- 18 Dec 2020 1241 1242 * Multivariate factorisation 1243 * Square root and square testing for finite fields 1244 * Square root and square testing for multivariates 1245 * Zassenhaus factoring speedups (incl. degree pruning) 1246 * Fast factorisation of cubic univariate polynomials 1247 * Add context objects to fmpz_mod_poly functions 1248 * Use BLAS for matrix multiplication over Z/nZ (small n) 1249 * Linear solving for non-square/singular matrices (can_solve) 1250 * Speed up factorisation over Z/nZ (for multiprecision n) 1251 12522.7.1 -- 18 Jan 2021 1253 1254 * Fix build bug due to missing test files 1255 * Fix bug in fmpz_mod_poly_factor when there are more than five factors 1256 * Fix issue when using MPIR 3.0.0 on Win64 with command line build 1257 * Fix bug in fmpz_mod_poly_div_series 1258 * Fix some broken asserts 1259 * Support standard GNU installation directories in CMake build 1260 * Fix stack overflow with ICC 1261 12622.8.0 -- 23 Jul 2021 1263 1264 * New fq_default module which combines existing finite fields 1265 * Speedups for linear algebra when using BLAS and/or threading 1266 * New series expansions with coefficients in QQ 1267 * Faster CRT 1268 * New fmpz_mod_mpoly module 1269 * Polynomial factoring improvements over ZZ 1270 * Fixed bugs in gmpcompat on Windows 1271 * Add fmpz_mat_can_solve_fflu and fmpz_mat_can_solve 1272 * Cleanup of the nmod_poly and nmod_poly_factor code 1273 * Implement nmod_mat_det_howell 1274 * Add fmpz_mod_poly_divides, fmpz_divides, n_divides, nmod_poly_divides 1275 * Interface for multiplying matrices by vectors and arrays 1276 * Nearest Euclidean division 1277 * Subresultant GCD 1278 * XGCD over ZZ with canonical Bezout coefficients 1279 * Add fmpz_mpoly resultant and discriminant 1280 * Add deprecations list 1281 * Add FLINT_SGN macro 1282 * Speedups for series computations 1283 * Switch to GitHub Actions for CI 1284 * Improve Taylor shift 1285 * Numerous bug fixes and speedups 1286 12872.8.1 -- 01 Oct 2021 1288 1289 * Numerous bug fixes 1290 * Adjust soname on android 1291 * Allow disabling of dependency tracking 1292 12932.8.2 -- 15 Oct 2021 1294 1295 * Fix an issue with --disable-dependency-tracking on some distributions 1296 12972.8.3 -- 03 Nov 2021 1298 1299 * Fix a serious bug in nmod_poly_xgcd_hgcd, nmod_poly_xgcd, fmpz_poly_xgcd_modular, fmpz_poly_xgcd, 1300 fmpq_poly_xgcd for polynomials of length >= 340. 1301 * Fix some copyright assignments 1302 * Fix some documentation errors 1303 13042.8.4 -- 17 Nov 2021 1305 1306 * Fix a serious big in fmpz_mod_poly_xgcd for polynomials of large length 1307 * Fix an assertion failure in fmpz_mat_solve_fflu (only relevant if asserts enabled) 1308 * Fix some bugs on 32 bit machines 1309 * Work around a compiler bug on Apple M1 1310 * Fix bug in nmod_mpoly_factor (returned 0 for some factorisations) 1311 * Fix some documentation build errors and some doc formatting issues 1312 1313