v 1.0 -- 2-Dec-07 : * First version of FLINT, includes fmpz_poly, fmpz and mpQS v 1.0.1 -- 7-Dec-07 : * Fixed a bug in _fmpz_poly_maxbits1 on 32 bit machines, reported by Michael Abshoff and Carl Witty * Removed some instances of u_int64_t and replaced them with uint64_t, reported by Michael Abshoff * Replaced sys/types.h with stdint.h * Added FLINT macros to documentation * Corrected numerous typos in documentation v 1.0.2 -- 10-Dec-07 * Rewrote tuning code for integer multiplication functions, making it more robust and fixing a bug which showed up on 32 bit machines (reported by Michael Abshoff and Jaap Spies). Factored the tuning code out into a number of macros. v 1.0.3 -- 16-Dec-07 * Fixed a bug in the polynomial memory management code which caused a segfault * Fixed a bug in the pseudo division code which caused a block overrun v 1.0.4 -- 04-Jan-08 * Fixed a bug in the bernoulli_zmod example program and associated polynomial zmod code which caused memory corruption. * Fixed a bug in the fmpz-test code which manifested on 32 bit machines, reported by David Harvey. * Fixed some bugs in the pari profiling code. v 1.0.5 -- 05-Jan-08 * Fixed some inline issues which cause problems because of the C99 inline rules (reported by David Harvey). * Fixed a makefile issue reported (and solved) by David Harvey when *not* linking against NTL. v 1.0.6 -- 17-Jan-08 * Fixed an issue with FLINT_BIT_COUNT on certain machines (probably due to arithmetic shift issues) v 1.0.7 -- 22-Jan-08 * Made F_mpn_mul binary compatible with the way mpn_mul *operates* in practice. v 1.0.8 -- 15-Feb-08 * Fixed a bug in fmpz_poly_right_shift (reported by Kiran Kedlaya) v 1.0.9 -- 11-Mar-08 * Fixed a memory allocation bug in fmpz_poly_power v 1.0.10 -- 16-Jun-08: * integer gcd (this just wraps the GMP gcd code) * polynomial content * convert to and from FLINT and NTL integers and polynomials * get a coefficient of a polynomial efficiently as a read only mpz_t * print polynomials in a prettified format with a specified variable v 1.0.11 -- 9-Jul-08 * Fixed a bug in z_ll_mod_precomp on ia64 (reported by Michael Abshoff and William Stein) v 1.0.12 -- 11-Jul-08 * Removed some Opteron tuning flags which cause illegal instruction errors on Pentium4 * Fixed numerous memory leaks in fmpz_poly test code * Fixed memory leak in fmpz_poly_power_trunc_n * Fixed major memory leaks in fmpz_poly_xgcd_modular * Rewrote __fmpz_poly_mul_karatrunc_recursive and _fmpz_poly_mul_karatsuba_trunc to "prove code" and got rid of some dirty memory issues * Fixed some potential illegal memory accesses to do with cache prefetching in fmpz_poly.c v 1.0.13 -- 13-Jul-08 * Fixed memory leaks and dirty memory issues in test code for numerous modules. * Removed further issues with cache prefetching in mpn_extras.c v 1.0.14 -- 23-Sep-08 * Update long_extras and test code for the sake of new quadratic sieve (new functions in long_extras remain undocumented) * Removed many bugs from tinyQS and mpQS and joined them into a single program for factoring integers v 1.0.15 -- 15-Oct-08 * Fixed a bug which causes a segfault when setting a coefficient of the zero polynomial to zero * Fixed build bug in longlong.h on s390 platform v 1.0.16 -- 22-Oct-08 * 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) v 1.0.17 -- 30-Nov-08 * Fixed a segfault caused by left shifting of polynomials with zero limbs allocated in division and pseudo division functions. * Fixed a bound used in fmpz_gcd_modular to use a proven bound * Fixed a bug in fmpz_poly-profile where the top bit of random coefficients of n bits was always set v 1.0.18 -- 05-Dec-08 * Fixed another bug in the fmpz_poly_set_coeff_* functions which resulted in dirty coefficients v 1.0.19 -- 12-Dec-08 * Fixed a bug in z_remove_precomp v 1.0.20 -- 13-Dec-08 * Fixed some bugs in conversion of zmod_poly's to and from strings v 1.0.21 -- 25-Dec-08 * 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 v 1.1.0 -- 21-Dec-08 (some of the following features were previewed in FLINT 1.0.11): * integer gcd (this just wraps the GMP gcd code) * polynomial content * primitive part * convert to and from FLINT and NTL integers and polynomials * get a coefficient of a polynomial efficiently as a read only mpz_t * print polynomials in a prettified format with a specified variable * Sped up integer multiplication * Convert to and from zmod_polys from fmpz_polys * Chinese remainder for fmpz_polys * Leading coeff macro * Euclidean norm of polynomials * Exact division testing of polynomials * Polynomial GCD (subresultant, heuristic, modular) * Modular inversion of polynomials * Resultant * XGCD (Pohst-Zassenhaus) * Multimodular polynomial multiplication * Rewritten karatsuba_trunc function * Rewritten division functions * Polynomial derivative * Polynomial evaluation * Polynomial composition * Addition and subtraction of zmod_polys * Sped up multiplication of zmod_polys * Extended multiplication of zmod_polys to allow up to 63 bit moduli * zmod_poly subpolynomials * zmod_poly reverse * Truncated multiplication for zmod_polys (left, right, classical and KS) * Scalar multiplication * Division for zmod_polys (divrem and div, classical, divide and conquer and newton) * Series inversion for zmod_polys * Series division for zmod_polys * Resultant for zmod_polys * GCD for zmod_polys including half-gcd * Inversion modulo a polynomial for zmod_polys * XGCD for zmod_polys * Squarefree factorisation for zmod_polys * Berlekamp factorisation for zmod_polys * Irreducibility testing for zmod_polys * Derivative for zmod_polys * Middle product for zmod_polys (sped up newton division) * addmod, submod and divmod for ulongs * Sped up limb sized integer square root * Partial factoring of ulongs * z_randbits * Pocklington-Lehmer primality testing * BSPW pseudo-primality testing * Fermat pseudo-primality testing * Fast Legendre symbol computation * Chinese remainder for fmpzs * Square root with remainder for fmpzs * Left and right shift for fmpzs * Reduction modulo a ulong for fmpzs * Montgomery redc, mulmod, divmod and mod for fmpzs * Multimodular reduction and CRT for fmpzs * fmpz_mulmod and fmpz_divmod * fmpz_invert for inversion modulo an fmpz * Dramatically sped up gcd for small fmpzs * Computation of 1D, 2D and some 3D theta functions * Example program for multiplying theta functions * Test code now times test functions * Quick and dirty timing function for profiler * Tiny quadratic sieve for small one and two limb integers * Completely rewritten self initialising multiple polynomial quadratic sieve * Build fix for 64 bit OSX dylibs (reported by Michael Abshoff) v 1.1.1 -- 11-Feb-09 * 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. v 1.1.2 -- 1-Mar-09 * Fixed some memory allocation slowdowns and bugs in fmpz_poly division and pseudo division functions (reported by William Stein). v 1.1.3 -- 1-Mar-09 * Inserted some missing return values in zmod_poly test code. v 1.2.0 -- 10-Mar-09 * made memory manager, fmpz and fmpz_poly threadsafe * Code for running tests in parallel (not activated) * Sped up fmpz_poly_scalar_div_ui/si when scalar is 1/-1 * Parallelise _fmpz_poly_mul_modular * fmpz_mul_modular_packed to pack coefficients to the byte before running _fmpz_poly_mul_modular * fmpz_poly_pseudo_rem_cohen (not documented) * special case for leading coeff 1/-1 in fmpz_poly_pseudo_divrem_basecase * removed a memory allocation bug which caused a massive slowdown in fmpz_poly_pseudo_divrem_basecase * fmpz_poly_pseudo_rem_basecase (not documented) * fmpz_poly_pseudo_rem (not asymptotically fast) * fmpz_poly_signature (not asymptotically fast) * basic fmpz_poly_is_squarefree function * included zn_poly in trunk and made FLINT build zn_poly as part of its build process * switched to using zn_poly for polynomial multiplication, newton inversion, scalar multiplication in zmod_poly * Integer cube root of word sized integers * Fibonacci pseudoprime test * BSPW probable prime test * n - 1 primality test * Complete implementation of z_issquarefree * Significantly improved the thetaproduct example program. * 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) * Fixed a bug in fmpz_poly_pseudo_divrem (relied on an uninitialised poly to have length 0) * Fixed bug in fmpz_multi_CRT_ui (could segfault) * Fixed bug in fmpz_multi_mod_ui (could segfault) * Fixed memory leak in zmod_poly_factor_squarefree * Fixed memory leak in zmod_poly_from_string v 1.2.1 -- 14-Mar-09 * Removed some FLINT 2.0 code which was interfering with the build of the NTL-interface * Removed an omp.h from fmpz_poly.c. v 1.2.2 -- 20-Mar-09 * Fixed a memory leak in zmod_poly_factor * Fixed zmod_poly-profile build v 1.2.3 -- 31-Mar-09 * Fixed bugs in all fmpz_poly evaluation functions, identified by Burcin Erocal. v 1.2.4 -- 4-Apr-09 * Defined THREAD to be blank on Apple CC and __thread for thread local storage on other gcc's (where it's defined) * #undef ulong in profiler.h where time.h and other system time headers are included (both reported by M. Abshoff) v 1.2.5 -- 18-Apr-09 * Upgraded to zn_poly-0.9 to avoid a serious error in squaring of large polynomials over Z/nZ v 1.3.0 -- 09-Jun-09 * Added new code for checking 2nd, 3rd and 5th roots * Fixed a bug in z_factor * Connected quadratic sieve for factoring large ulongs * Added one line factor algorithm * constructed best of breed factor algorithm * Fixed termination conditions for z_intcuberoot and z_intfifthroot which were broken * Added some code for special cases which cause infinite loops in cuberoot and fifthroot * 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. * Added test code for z_intfifthroot * Added test code for z_factor_235power * Fixed some uninitialised data found by valgrind in intcuberoot and intfifthroot * Fixed multiply defined PRIME_COUNT in long_extras-test * Got rid of gotos in some functions in long_extras * Knocked optimisation level back to -O2 because it miscompiles on sage.math * Changed tables to use uint64_t's instead of ulongs which are not 64 bits on a 32 bit machine * Only checked MAX_HOLF on 64 bit machine * Changed MAX_SQUFOF to WORD(-1) * Check constant 0x3FFFFFFFFUL only on a 64 bit machine * Fixed a bug in z_oddprime_lt_4096 on 32 bit machines * Fixed some TLS issues with Cygwin * Fixed some typos in makefile * Fixed a wrong path in fmpz.c v 1.4.0 -- 06-Jul-09 * Sped up zmod_poly division in case where operands are the same length * Sped up zmod_poly division in case where operands have lengths differing by 1 * Fixed a bug in zmod_poly_gcd for polynomials of zero length * Sped up zmod_poly_gcd considerably (both euclidean and half gcd) * Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably * Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast * Made zmod_poly_resultant asymptotically fast * Added optimised zmod_poly_rem function * Fixed a divide by zero bug in zmod_poly_factor_berlekamp * Added test code for z_factor_tinyQS and z_factor_HOLF * Fixed many bugs in the z_factor code, tinyQS and mpQS * Corrected numerous typos in the documentation and added missing descriptions * Added F_mpz_cmp function * Added documentation to the manual for the new F_mpz module v 1.5.0 -- 22-Sep-09 * Added multimodular reduction and CRT to F_mpz module * Fixed some bugs in F_mpz module and numerous bugs in test code * Added zmod_poly_compose * Added zmod_poly_evaluate * Added functions for reduced evaluation and composition to fmpz_poly module (contributed by Burcin Erocal) * Fixed bugs in the primality tests in long_extras * Removed all polynomial multimodular multiplication functions * Added new thetaproduct code used in the 1 trillion triangles computation * Fixed a severe bug in the fmpz_poly_pseudo_div function reported by Sebastian Pancratz * Added fmpz_comb_temp_init/clear functions * Fixed a normalisation buglet in fmpz_poly_pack_bytes * Added F_mpz_pow_ui function (contributed by Andy Novocin) * Fixed a severe bug in the FFT reported by William Stein and Mariah Lennox (fix contributed by David Harvey) * Removed some memory leaks from F_mpz test code * Fixed bug in zmod_poly_evaluate test code v 1.6.0 -- 24-Dec-10 Bugs: ==== * Fixed a memory leak in mpz_poly_to_string_pretty * Fixed a bug inherited from an old version of fpLLL * Makefile to respect CC and CXX * Fixed bug in F_mpz_set_si * Fixed bug in F_mpz_equal * Most for loops to C90 standard (for easier MSVC porting) * Better Cygwin support * Fixed a bug in zmod_poly_resultant * Fixed bug in F_mpz_mul_KS/2 * Fixed bug in tinyQS * Worked around some known bugs in older GMP/MPIR's Major new functionality ======================= * F_mpz_poly_factor_zassenhaus * F_mpz_poly_factor (incl. fmpz_poly_factor wrapper) using new vH-N approach (see the paper of van Hoeij and Novocin and the paper of van Hoeij, Novocin and Hart) * Implementation of new CLD bounds function for polynomial factors (see the paper of van Hoeij, Novocin and Hart * Restartable Hensel lifting * Heuristic LLL implementations using doubles and mpfr * LLL implementations optimised for knapsack lattices * New (probably subquadratic) LLL implementation (ULLL) * zmod_poly_factor_cantor_zassenhaus * New F_mpz_mod_poly module for polynomials over Z/pZ for multiprec. p Some of the other new functions added ===================================== F_mpz: * F_mpz_gcd * F_mpz_smod * F_mpz_mod_preinv * F_mpz_fdiv_qr * F_mpz_get/set_mpfr/2exp * F_mpz_sscanf * F_mpz_set_d F_mpz_poly: * read F_mpz_poly to_string/from_string/fprint/print/fread/pretty * F_mpz_poly_to/from_zmod_poly * F_mpz_poly_scalar_div_exact * F_mpz_poly_smod * F_mpz_poly_derivative, F_mpz_poly_content, F_mpz_poly_eval_horner_d/2exp * F_mpz_poly_scalar_abs * F_mpz_poly_set_d_2exp * F_mpz_poly_div/divrem * F_mpz_poly_gcd * F_mpz_poly_is_squarefree * F_mpz_poly_factor_squarefree * F_mpz_poly_mul_trunc_left * F_mpz_poly_pseudo_div * F_mpz_poly_set_coeff * F_mpz_poly_pow_ui * Inflation/deflation trick for factorisation zmod_poly: * Inflation/deflation trick for factorisation mpz_mat: * mpz_mat_from_string/to_string/fprint/fread/pretty mpq_mat: * mpq_mat_init/clear * Gramm-schmidt Orthogonalisation F_mpz_mat: * F_mpz_mat_print/fprint/fread/pretty * F_mpz_mat_mul_classical * F_mpz_mat_max_bits/2 * F_mpz_mat_scalar_mul/div_2exp * F_mpz_mat_col_equal * F_mpz_mat_smod * F_mpz_vec_scalar_product/norm * F_mpz_vec_add/submul_ui/si/F_mpz/2exp zmod_mat: * classical multiplication * strassen multiplication * scalar multiplication * zmod_mat_equal * zmod_mat_add/sub * zmod_mat_addmul_classical d_mat: * d_vec_norm, d_vec_scalar_product mpfr_mat: * mpfr_vec_scalar_product/norm v 2.0 -- 16 Jan 2011 N.B: FLINT 2 is a complete rewrite of flint from scratch It includes the following modules: ulong_extras: (word sized integers and modular arithmetic) * random numbers (randint, randbits, randprime, randint) * powering * reverse binary * mod, divrem, mulmod all with precomputed inverses * gcd, invgcd, xgcd * jacobi symbols * addmod, submod, invmod, powmod * prime sieve, nextprime, prime-pi, nth-prime * primality testing (small, binary search, Pocklington-Lehmer, Pseudosquare) * probably prime tests (strong base-a, Fermat, Fibonacci, BPSW, Lucas) * sqrt, sqrtrem, is-square, perfect-power (2,3,5) * remove, is-squarefree * factorisation (trial-range, trial, power (2,3,5), one-line, SQUFOF) * Moebius mu, Euler phi fmpz: (memory managed multiple precision integers) * memory management (init, clear) * random numbers (randbits, randm) * conversion to and from long, ulong, doubles, mpz's, strings * read/write to file, stdin, stdout * sizeinbase, bits, size, sgn, swap, set, zero * cmp, cmp-ui, cmpabs, equal, is-zero, is-one * neg, abs, add, add-ui, sub, sub-ui, mul, mul-si, mul-ui, mul-2exp * addmul, addmul-ui, submul, submul-ui * cdiv-q, cdiv-q-si, cdiv-q-ui * fdiv-q, fdiv-q-si, fdiv-q-ui, fdiv-qr, fdiv-q-2exp * tdiv-q, tdiv-q-si * divexact, divexact-si, divexact-ui * mod, mod-ui * powering * sqrt, sqrt-rem * factorial * gcd, invmod * bit-pack, bit-unpack * multimodular reduction, CRT fmpz_vec: (vectors over fmpz's) * memory management (init, clear) * random vectors * max-bits, max-limbs * read/write to file/stdin/stdout * set, swap, zero, neg * equal, is-zero * sort * add, sub * scalar multiplication by fmpz, ulong, long, 2exp * exact division by fmpz, long, ulong * fdiv-q by fmpz, long, ulong, 2exp * tdiv-q by fmpq, long, ulong * addmul by fmpz, long, long by 2exp * submul by fmpz, long, long by 2exp * Gaussian content fmpz_poly: (polys over fmpz's) * memory management (init, realloc, fit-length, clear) * random polys * normalise, set-length, truncate * length, degree, max-limbs, max-bits * set, set-si, set-ui, set-fmpz, set-str * get-str, get-str-pretty * zero, one, zero-coeffs * swap, reverse * get/set coeffs from fmpz, long, ulong * get-coeff-ptr, lead * equal, is-zero * add, sub * scalar multiplication by fmpz, long, ulong * scalar addmul/submul by fmpz * scalar fdiv by fmpz, long, ulong * scalar tdiv by fmpz, long, ulong * scalar divexact by fmpz, long, ulong * bit pack, bit unpack * multiplication (classical, karatsuba, KS) * mullow (classical, karatsuba, KS) * mulhigh (classical, karatsuba) * middle product (classical) * powering (small, binary exponent, binomial, multinomial, addition chains) * truncated powering (binary exponent) * shift left/right * euclidean norm * gcd (subresultant) * resultant * content, primitive part * divrem (basecase, divide-and-conquer) * div (basecase, divide-and-conquer) * rem (basecase) * invert series (basecase, Newton) * div series * pseudo divrem (basecase, divide-and-conquer, Cohen) * rem (Cohen) * div * evaluate (Horner) at fmpz, mpq, a mod n * composition (Horner, divide-and-conquer) * signature * read/write to file/stdin/stdout fmpq_poly: (polynomials over Q stored as poly over fmpz with fmpz denominator) * memory management (init, realloc, fit-length, clear) * random polys * set-length, canonicalise, normalise, truncate * is-canonical, length, degree * reference to numerator, denominator * set, set-si, set-ui, set-fmpz, set-mpz, set-mpq * set-array-mpq, set-str * get-str, get-str-pretty * zero, neg, swap * invert * set coefficient to mpq, long, ulong, fmpz, mpz * get coefficient as mpq * equal, cmp, is-one, is-zero * add, sub * scalar multiplication by long, ulong, fmpz, mpq * scalar division by fmpz, long, ulong, mpq * multiplication, mullow * powering * shift left/right * divrem, div, rem * invert series (Newton iteration) * divide series * derivative * evaluate at fmpz, mpq * composition, scale by constant * content, primitive part * make-monic, is-monic * is-squarefree * read/write to file/stdin/stdout nmod_vec: (vectors over Z/nZ for n fitting in a machine word) * memory management (init/clear) * macros for efficient reduction of 1, 2 and 3 limb integers mod n * macro for addmul mod n * add/sub/neg individual coefficients mod n * random vectors * set, zero, swap * reduce, max-bits * equal * add, sub, neg * scalar multiplication by a value reduced mod n * scalar addmul by a value reduced mod n nmod_poly: (polynomials over Z/nZ for n fitting in a machine word) * memory management (init, realloc, fit-length, clear) * random polys * normalise, truncate * length, degree, modulus, max-bits * set, swap, zero, reverse * get/set coefficients as ulongs, strings * read/write to file, stdin, stdout * equal, is-zero * shift left/right * add, sub, neg * scalar multiplication by a value reduced mod n * make-monic * bit pack, bit unpack * multiplication (classical, KS) * mullow (classical, KS) * mulhigh (classical) * powering (binary exponent) * pow-trunc (binary exponent) * divrem (basecase, divide-and-conquer, Newton iteration) * div (basecase, divide-and-conquer, Newton iteration) * invert series (basecase, Newton iteration) * divide series (Newton iteration) * derivative * evaluation at a value taken mod n * composition (Horner, divide-and-conquer) * gcd (euclidean) fmpz_mat: (matrices over fmpz's) * memory management (init, clear) * random matrices (bits, integer relations, simultaneous diophantine equations NTRU-like, ajtai, permutation of rows and cols of a diagonal matrix, random of given rank, random of given determinant, random elementary operations) * set, init-set, swap, entry pointer * write to file or stdout * equal * transpose * multiplication (classical, multimodular) * inverse * determinant * row reduce (Gaussian and Gauss-Jordan fraction-free elimination) * rank * solve Ax = b, solve AX = B * fraction free LU decomposition nmod_mat: (matrices over Z/nZ for n fitting in a machine word) * memory management (init, clear) * random matrices (uniform, full, permutations of diagonal matrix, random of given rank, random elementary operations) * set, equal * print to stdout * add * transpose * multiplication (classical, Strassen, A*B^T) * row reduction (Gaussian and Gauss-Jordan) * determinant * rank * solve (Ax = b, AX = B, solve with precomputed LU) * invert arith: (arithmetic functions) * Bernoulli numbers * Bernoulli polynomials * primorials (product of primes up to n) * harmonic numbers * Stirling numbers * Euler phi function * Moebius mu function * Sigma (sum of powers of divisors) * Ramanujan tau function examples: (example programs) * compute coefficients of q-series of Delta function mpfr_vec: (vectors over mpfr reals) * memory management (init, clear) * add * set, zero * scalar multiplication by mpfr, 2exp * scalar product mpfr_mat: (matrices over mpfr reals) * memory management (init, clear) v 2.1 -- 9 Mar 2011 fmpz ---- * Simplified interface for fast multimodular reduction and CRT reconstruction * Fixed segmentation fault in fmpz_multi_mod_ui when the input exceeds the product of the moduli * Added simple incremental CRT functions (fmpz_CRT_ui, fmpz_CRT_ui_unsigned) to complement the existing fast ones * Added example programs for CRT * Added random number generators designed for testing modular code (fmpz_randtest_mod, fmpz_randtest_mod_signed) * Added fmpz_fdiv_ui for remainder on division by an ulong * Added fmpz_bin_uiui for computing binomial coefficients * 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) fmpz_mat -------- * Added utility functions for basic arithmetic and creating unit matrices * Added multimodular determinant computation (certified or heuristic) * Added support for computing right nullspaces (fmpz_mat_kernel). Fast only for small matrices. * Some internal code cleanup and various small fixes nmod_mat -------- * Faster Gaussian elimination for small moduli * Faster determinants * Faster matrix inversion and nonsingular solving nmod_poly --------- * Added nmod_poly_integral for computing integrals * Added fast square root and inverse square root of power series * Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh) * Made nmod_poly_inv_series_newton more memory efficient fmpq_poly --------- * Added fmpq_poly_integral for computing integrals * Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh) arith ----- * Made computation of vectors of Bernoulli numbers faster * Added fast computation of single Bernoulli numbers * Added a separate function for computing denominators of Bernoulli numbers * Added fast computation of Bell numbers (vector and single) * Added fast computation of Euler numbers (vector and single) * Added fast computation of Euler polynomials * Added fast computation of Swinnerton-Dyer polynomials * Added fast computation of Legendre polynomials * Added fast vector computation of the partition function * Added fast vector computation of Landau's function ulong_extras ------------ * Added a function for computing factorials mod n build system ------------ * Added support for building static and shared libraries * All object files and test/profile/example binaries now build in separate build directory documentation ------------- * Large number of corrections v 2.2 -- 4 Jun 2011 fmpq (multiprecision rational numbers) -------------------------------------- * Basic arithmetic functions * Utility functions * Rational reconstruction * Functions for enumerating the rationals fmpq_mat (matrices over Q) -------------------------- * Basic arithmetic functions * Utility functions * Fast multiplication * Classical and fraction-free reduced row echelon form * Determinants * Fast non-singular solving fmpz_poly_mat (matrices over Z[x] --------------------------------- * Basic arithmetic functions * Utility functions * Fraction-free row reduction and determinants * Fast determinants (experimental) fmpz_mat -------- * Added more utility functions (scalar multiplication, etc) * Added Dixon's p-adic algorithm (used by fast nonsingular rational system solving) * Added reduced row echelon form * Added conversions between fmpz_mat and nmod_mat * Added CRT functions for fmpz_mats * Faster matrix multiplication for small to medium dimensions longlong.h ---------- * Added x86 assembly macros for accumulating sums of two limb operands nmod_mat -------- * Sped up arithmetic for moduli close to FLINT_BITS arith ----- * Changed interface of various functions to use new fmpq type fmpz ---- * Added fmpz_set_ui_mod * Inlined fmpz_neg, fmpz_set_si, fmpz_set_ui for better performance * Added fmpz_lcm * Small performance improvement to fmpz_CRT_ui fmpz_vec -------- * Added _fmpz_vec_lcm fmpz_poly_q (rational functions over Q, modeled as quotients of fmpz_polys) --------------------------------------------------------------------------- * Basic arithmetic functions * Conversion and IO functions * Evaluation padic (p-adic numbers -- experimental) ------------------------------------- * Basic arithmetic * Data conversion and IO * Inverse and square root using Newton iteration * Teichmuller lifts (not optimised) * p-adic exponential function (not optimised) fmpz_poly --------- * Added fmpz_poly_gcd_modular (and fmpz_poly_gcd wrapper) * Added fmpz_poly_xgcd_modular (and fmpz_poly_xgcd wrapper) * Added conversions between fmpz_poly and nmod_poly * Added CRT functions * Added multipoint evaluation and interpolation nmod_poly --------- * Added nmod_poly_xgcd_euclidean (and nmod_poly_xgcd wrapper) * nmod_poly_gcd wrapper mpn_extras ---------- * Added MPN_NORM and MPN_SWAP macros. * Added mpn_gcd_full to remove some of the restrictions from the usual mpn_gcd build fixes ------------ * fixed make install to create nonexistent dirs (reported by Serge Torres) * -L use /usr instead of /usr/local by default (reported by Serge Torres) * guards for system headers because of flint's use of ulong v 2.3 -- 1 Jul 2012 general ------- * many changes to the build system * added NTL interface * switched to custom memory allocation functions flint_malloc etc * in addition to the entries below, fixed a large number of memory leaks, problems with the test code, and bugs in corner cases of various functions * added _fmpz_cleanup_mpz_content as an alternative to _fmpz_cleanup * support MinGW32 * support Cygwin * bugfix on ia64 * support sparc32/sparc64 * support OSX * support Solaris, NetBSD, OpenBSD, etc (if bash, GNU Make present) ulong_extras ------------ * implemented the improved Lehman algorithm * added n_jacobi_unsigned to allow n > WORD_MAX * fixed n_sqrtmod for n > WORD_MAX * fixed bug causing n_sqrtmod to hang * added sublinear algorithm for computing factorials mod p * added n_sqrtmod_primepow, n_sqrtmodn and associated functions for computing square roots modulo composite integers * fixed bugs in n_is_prime_pocklington * fixed UWORD_MAX case in powmod and powmod2 * fixed problems with the random number generators * fixed rare bug in n_mod_precomp * fixed rare bug in n_is_prime_pseudosquare long_extras ----------- * added z_sizeinbase qsieve ------ * new module implementing a quadratic sieve for numbers up to two limbs fft --- * new module providing an efficient Schoenhage-Strassen FFT longlong -------- * added assembly code for ia64 and ARM * fixed bug in fallback version of add_sssaaaaaa fmpz ---- * added fmpz_fib_ui * added double precision natural logarithm * added fmpz_val2 for 2-valuation * added mul_2exp, div_2exp, cdiv_q_2exp, tdiv_q_2exp, fdiv_r, fdiv_r_2exp, tdiv_ui, mul_tdiv_q_2exp * added get_d/set_d * added fmpz_divisible, divisible_si * optimised fmpz_powm and fmpz_powm_ui * added clog, clog_ui, flog, flog_ui for computing logarithms * added abs_lbound_ui_2exp, ubound_ui_2exp * added fmpz_rfac_ui and fmpz_rfac_uiui for rising factorials * added functions to obtain read-only fmpz_t's from mpz_t's * added fmpz_init_set, init_set_ui * added fmpz_gcdinv * added fmpz_is_square * added fmpz_tstbit, setbit, clrbit, complement, combit, and, or, xor, popcnt * added a sign flag for CRT instead of using separate methods * fixed bugs in fmpz_sqrtmod * fixed a bug in fmpz_bit_unpack that could cause corruption of the global fmpz array when compiled in single mode * fixed a bug in fmpz_sub_ui that could cause memory corruption fmpz_vec -------- * added functions for obtaining the largest absolute value coefficient * added functions for computing the sum and product of an integer vector * made max_bits much faster * added _fmpz_vec_mod_fmpz * made randtest produce sparse output fmpz_poly --------- * added fmpz_poly_sqr, fmpz_poly_sqrlow for squaring a polynomial * added fmpz_poly_lcm * made multipoint interpolation faster by using the Newton basis * added a function for fast division by a linear polynomial * added power series composition (classical and Brent-Kung) * added power series reversion (classical, Newton, fast Lagrange) * added a function for obtaining the largest absolute value coefficient * fixed quadratic memory usage and stack overflow when performing unbalanced division or pseudo division using the divconquer algorithm * fixed a bug in poly_zero_coeffs * fixed a bug in xgcd_modular * allowing +/-1 in the constant term of power series inversion * fixed aliasing bug in divrem * added restartable Hensel lifting and associated utility functions * fixed rem, which used to only call the basecase algorithm * fixed pseudo_divrem, which used to only call the basecase algorithm * implemented Schoenhage-Strassen multiplication (mul_SS, mullow_SS) and enabled this by default * fixed a bug in the heuristic GCD algorithm * added functions for Newton basis conversion * added functions for fast Taylor shift * added fmpz_poly_sqrt implementing a basecase algorithm * added scalar mul_2exp, fdiv_2exp, tdiv_2exp * made randtest produce sparse output * added fmpz_poly_equal_fmpz * improved performance by always using basecase multiplication when one polynomial is short * improved algorithm selection for fmpz_poly_gcd * fixed several bugs in gcd_modular * improved performance of gcd_modular fmpz_poly_factor ---------------- * new module for factorisation of fmpz_polys * added a naive implementation of the Zassenhaus algorithm fmpz_mod_poly ------------- * new module for polynomials modulo over Z/nZ for arbitrary-precision n * multiplication, powering * classical and divconquer division * series inversion * Euclidean GCD and XGCD * invmod * radix conversion * divconquer composition * GCD and division functions that test invertibility of the leading coefficient fmpz_mat -------- * added det_divisor for computing a random divisor of the determinant * faster determinant computation using divisor trick * faster determinant computation by using multimodular updates * fixed n x 0 x m product not zeroing the result * various interface improvements * faster implementation of Cramer's rule for multiple right hand sides * added fmpz_mat_fread and read * added multi CRT/mod functions * added trace fmpz_poly_mat ------------- * fixed n x 0 x m product not zeroing the result * added inverse * added rank computation * added reduced row echelon form and nullspace computation * added more utility functions * added squaring and exponentiation * added balanced product of a sequence of matrices * added truncate, mullow, sqrlow, pow_trunc * added trace fmpz_factor ----------- * new module providing interface for integer factorisation * fast expansion of a factored integer fmpq ---- * cleaned up and improved performance of rational reconstruction code * allow separate numerator and denominator bounds for rational reconstruction * added continued fraction expansion * added functions for summation using binary splitting * added fmpq_swap * added fmpq_print, fmpq_get_str * added fmpq_pow_si * added functions to obtain read-only fmpq_t's from mpq_t's * added fmpq_cmp fmpq_mat -------- * fixed n x 0 x m product not zeroing the result * added fmpq_mat_transpose * added trace fmpq_poly --------- * improved speed of multipoint interpolation using _fmpz_poly_div_root * fmpq_poly: added power series composition (classical and Brent-Kung) * fmpq_poly: added power series reversion (classical, Newton, fast Lagrange) * fixed bug wherein set_array_mpq modified the input * added gcd, xgcd, lcm, resultant * added fmpq_poly_set_fmpq * added fmpq_poly_get_slice, fmpq_poly_reverse * fixed aliasing bug in divrem * changed some functions to use FLINT scalar types instead of MPIR data types * added fmpq_poly_get_numerator nmod_poly --------- * implemented the half gcd algorithm for subquadratic gcd and xgcd * added multipoint evaluation and interpolation * added asymptotically fast multipoint evaluation and interpolation * added a function for forming the product of linear factors * added a function for fast division by a linear polynomial * added power series composition (classical and Brent-Kung) * added power series reversion (classical, Newton, fast Lagrange) * added nmod_poly_mulmod, powmod and related functions (ported from flint1) * added squarefree, irreducibility tests (ported from flint1) * added Berlekamp and Cantor-Zassenhaus factoring (ported from flint1) * fixed quadratic memory usage and stack overflow when performing unbalanced division using the divconquer algorithm * added compose_series_divconquer * added resultant * fixed aliasing bug in divrem * added rem functions * added divrem_q0, q1 for special cases of division * added functions for fast Taylor shift * added nmod_poly_sqrt * made fread read the modulus from the file * made randtest produce sparse output * fixed bug in xgcd_euclidean with scalar inputs nmod_vec -------- * added functions and macros for computing dot products * made randtest produce sparse output nmod_mat -------- * added addmul/submul functions * asymptotically fast solving of triangular systems * asymptotically fast LUP decomposition * asymptotically fast determinant and rank computation * asymptotically fast reduced row echelon form and nullspace * asymptotically fast nonsingular solving * asymptotically fast inverse * tidied some interfaces * fixed n x 0 x m product not zeroing the result * added trace * made multiplication faster for tiny moduli by means of bit packing nmod_poly_mat ------------- * new module for matrices over Z/nZ[x], with similar functionality as the fmpz_poly_mat module * determinant, rank, solving, reduced echelon form, nullspace * fraction-free Gaussian elimination * multiplication using bit packing * multiplication using evaluation-interpolation * determinant using evaluation-interpolation padic ----- * restructured and improved much of the code * added padic_log * improved log and exp using rectangular splitting * added asymptotically fast log and exp based on binary splitting perm ---- * added the perm module for permutation matrices * computing the parity of a permutation * inverting a permutation arith ----- * added generation of cyclotomic polynomials * added functions for evaluating Dedekind sums * fast computation of the partition function * added a function for factoring a Hardy-Ramanujan-Rademacher type exponential sum * added Chebyshev polynomials T and U * added computation of the minimal polynomial of cos(2pi/n) * added asymptotically fast high-precision approximation of zeta(n) * added asymptotically fast computation of Euler's constant * added new algorithms and functions for computing Bell numbers * fast computation of pi (adapting code written by Hanhong Xue) * added functions for computing the number of sum of squares representations of an integer * renamed functions to have an arith_ prefix v 2.4 -- 20 Nov 2013 * C++ expressions template wrapper * Fast factorisation of polynomials over Z/nZ * improved p-adics * polynomials/matrices over p-adics * qadics * Finite fields (small and large F_q), polynomials/matrices over F_q * Finite fields with Zech logarithm representation * Fast factorisation of polynomials over F_q * Faster Brent-Kung modular composition * New prime sieving code * Lambert-W function * Precomputed inverses for polynomials and large integers * Williams' P+1 integer factoring algorithm * Harvey's KS2/KS4 polynomial multiplication * Faster primality testing up to 64 bits * Support for Cygwin64 and MinGW64 * Support for Clang * Support for GMP * Support for Boehm-Demers-Weiser GC * Support for flint extension modules v 2.4.2 -- 11 Mar 2014 * Fix bug in ARM assembly v 2.4.3 -- 01 Apr 2014 * Fix a linker issue on Mac OSX. v 2.4.4 -- fixed a severe bug in flint's primality code (n_is_prime() affecting n_factor()) v 2.4.5 -- fixed a severe bug in flint's fmpz_poly_gcd_heuristic, reported by Anton Mellit. v 2.5.0 -- 07 Aug 2015 * LLL (rational, Nguyen-Stehle, from Gram matrix, with_removal, Storjohann/ULLL) * Hermite normal form (naive, xgcd, Domich-Kannan-Trotter, Kannan-Bachem, Pernet-Stein) * Smith normal form (diagonal, Kannan-Bachem, Iliopoulos) * Paterson-Stockmeyer algorithm * modular resultant * hgcd resultant * polynomial discriminant * multithreaded multimodular Taylor shift * multithreaded Brent-Kung composition * multithreaded Kaltofen-Shoup distinct degree factorisation * multiplication based reduced row echelon form * place inline functions in library for foreign function interfaces * Primality tests for large integers (Pocklington, Morrison) * Probable prime tests for large integers (Lucas, Baillie-PSW, strong-psp, Brillhart-Lehmer-Selfridge) * CRT for large integers * Dixon algorithm for nullspace * Brent-Kung composition in irreducibility and distinct degree factorisation * floating point QR decomposition * Schwarz-Rutishauser Gram-Schmidt algorithm * Ogita-Rump-Oishi dot product * matrix window functions * MSVC support (Brian Gladman) * fast cube/nth-root (Newton, Kahan, magic number, Chebyshev) * Bodrato matrix squaring * matrix concatenation functions * matrix content * faster n_gcd * faster n_sqrtmod and fmpz_sqrtmod * additional functions for returning factor of modulus in polys over Z/nZ * Hadamard matrix construction * series addition/subtraction * faster prime_pi bounds * speedup creation of sparse polynomials * speedup n_isprime n_nextprime * speedup n_isprime_pocklington * speedups to fmpq_poly and fmpz_poly arithmetic * speedup polynomial irreducibility testing over Z/pZ * speedup of rank computation over ZZ * made CPimport compile time dependency only * teach flint_printf/sprintf about explicit width format specifiers * support relative paths in configure * library soname versioning * ARM64 patches * Support MSYS2 * Progress towards supporting MIPS64 * Fix a serious bug in fmpz_poly_signature v 2.5.1 -- 12 Aug 2015 * Fix some build bugs related to soname versioning and ldconfig * Fix issue with Windows MSVC build v 2.5.2 -- 13 Aug 2015 * Fix further issues with soname versioning and ldconfig * Fix a bug when using GMP instead of MPIR. v 2.6.0 -- 5 Jun 2020 * multivariate polynomials over most standard rings (sparse distributed) * APR-CL primality proving * elliptic curve integer factoring * minpoly and charpoly * improved quadratic sieve for integer factoring * embeddings of finite fields * pollard rho integer factoring * p+1 integer factoring * best of breed smooth integer factoring routine * best of breed general integer factoring routine * howell and strong echelon form * large speedups for solve and hence inverse over Z and Q * randprime and nextprime functions * pernet-stein HNF improvements * moller-granlund precomputed inverses * resultant_modular_div * fibonacci polynomials * exception mechanism/flint_abort * sqrt of series and polynomials * division of series over Z * power sums * improved base cases of various power series functions * ability to switch memory allocators * fast recurrence for Hermite polys * shifted Legendre polynomials * Laguerre polynomials * Gegenbauer polys * sphinx documentation * van hoeij with gradual feeding implementation of polynomial factoring over Z * perfect power detection * divisibility testing for polynomials * fast block based memory manager for bundling fmpz allocations * uniform random generation * CMake build system * linear algebra speedups when everything can be kept in longs * nmod module for integers mod (small) n * fmpz_mod_mat module for matrices over integers mod multiprecision n * kronecker product (tensor product) * random primitive polys (for finite fields) * thread pool implementation * threading of FFT for integer and polynomial multiplication over Z * threading of quadratic sieve for integer factoring * improved threading of factoring of polynomials mod p * threading for multivariate polynomial multiplication, division and GCD * threaded multiplication of matrices mod p * Berlekamp-Massey (nmod) * fmpz_mod module for integers mod multiprecision n * Pohlig-Hellman (discrete log) * farey_neighbours * remove openMP option * additional integer division variants * speed up mpn_mulmod_preinv * fft precaching * cyclotomic polynomial detection * polynomial root finding over finite fields * GMP 6.2 support * MPIR 3.0.0 support * many small speedups and additional convenience functions added v 2.6.1 -- 23 Jul 2020 * Fix issues on Debian major architectures * Fix numerous reported bugs (mpoly, fq_poly, mpn_mul_1, mod 2 code, etc.) v 2.6.2 -- 31 Jul 2020 * Fix for choice of generator in an fq finite field of degree one * Fix an incorrectly written test v 2.6.3 -- 12 Aug 2020 * Fix a bug in generator of finite field in characteristic 2 * Allow Flint to work with GMP 6.1.2 and 6.2.0 interchangeably * Fix some old license headers 2.7.0 -- 18 Dec 2020 * Multivariate factorisation * Square root and square testing for finite fields * Square root and square testing for multivariates * Zassenhaus factoring speedups (incl. degree pruning) * Fast factorisation of cubic univariate polynomials * Add context objects to fmpz_mod_poly functions * Use BLAS for matrix multiplication over Z/nZ (small n) * Linear solving for non-square/singular matrices (can_solve) * Speed up factorisation over Z/nZ (for multiprecision n) 2.7.1 -- 18 Jan 2021 * Fix build bug due to missing test files * Fix bug in fmpz_mod_poly_factor when there are more than five factors * Fix issue when using MPIR 3.0.0 on Win64 with command line build * Fix bug in fmpz_mod_poly_div_series * Fix some broken asserts * Support standard GNU installation directories in CMake build * Fix stack overflow with ICC 2.8.0 -- 23 Jul 2021 * New fq_default module which combines existing finite fields * Speedups for linear algebra when using BLAS and/or threading * New series expansions with coefficients in QQ * Faster CRT * New fmpz_mod_mpoly module * Polynomial factoring improvements over ZZ * Fixed bugs in gmpcompat on Windows * Add fmpz_mat_can_solve_fflu and fmpz_mat_can_solve * Cleanup of the nmod_poly and nmod_poly_factor code * Implement nmod_mat_det_howell * Add fmpz_mod_poly_divides, fmpz_divides, n_divides, nmod_poly_divides * Interface for multiplying matrices by vectors and arrays * Nearest Euclidean division * Subresultant GCD * XGCD over ZZ with canonical Bezout coefficients * Add fmpz_mpoly resultant and discriminant * Add deprecations list * Add FLINT_SGN macro * Speedups for series computations * Switch to GitHub Actions for CI * Improve Taylor shift * Numerous bug fixes and speedups 2.8.1 -- 01 Oct 2021 * Numerous bug fixes * Adjust soname on android * Allow disabling of dependency tracking 2.8.2 -- 15 Oct 2021 * Fix an issue with --disable-dependency-tracking on some distributions 2.8.3 -- 03 Nov 2021 * Fix a serious bug in nmod_poly_xgcd_hgcd, nmod_poly_xgcd, fmpz_poly_xgcd_modular, fmpz_poly_xgcd, fmpq_poly_xgcd for polynomials of length >= 340. * Fix some copyright assignments * Fix some documentation errors 2.8.4 -- 17 Nov 2021 * Fix a serious bug in fmpz_mod_poly_xgcd for polynomials of large length * Fix an assertion failure in fmpz_mat_solve_fflu (only relevant if asserts enabled) * Fix some bugs on 32 bit machines * Work around a compiler bug on Apple M1 * Fix bug in nmod_mpoly_factor (returned 0 for some factorisations) * Fix some documentation build errors and some doc formatting issues 2.8.5 -- 25 Apr 2022 * Fix a serious bug in LLL