flintlib / flint

FLINT (Fast Library for Number Theory)

FLINT (Fast Library for Number Theory)

Website: https://flintlib.org

Mailing list: https://groups.google.com/g/flint-devel

Overview

FLINT is a C library in support of computations in number theory. It's also a research project into algorithms in number theory. FLINT consists mainly of fast scalar and polynomial arithmetic, factorization and linear algebra over many basic rings (integers, rationals, reals, finite fields, number fields, p-adics). It includes some higher-level functionality for algebraic and analytic number theory.

FLINT 2, released in 2011 was a complete rewrite of FLINT 1.x from scratch. FLINT 3, released in 2023, incorporates the Arb, Antic, Calcium and Generic-Rings libraries, formerly developed separately.

Documentation

For FLINT's online documentation, see https://flintlib.org/doc/.

Building from source

This example assumes that GMP, MPFR and the GNU build system are already installed. To install them on a Ubuntu system, write

apt install libgmp-dev libmpfr-dev make autoconf libtool-bin

possibly with super-user privileges.

To download, bootstrap, configure and build everything, write

git clone https://github.com/flintlib/flint.git && cd flint
./bootstrap.sh
./configure                        # ./configure --help for more options
make
make check                         # optional
make install                       # optional
make examples                      # optional
cd doc && make html && cd ..       # optional: documentation

See FLINT's documentation for further instructions on how to build FLINT.

Authors

FLINT was started in 2007 by David Harvey and William Hart. Maintenance was later taken over solely by William Hart who remained in charge of the project until 2022. A large number of authors have contributed to FLINT over the years; for a complete list, see https://flintlib.org/authors.html or the AUTHORS file.

The current maintainers are:

• Fredrik Johansson ([email protected]) (project leader since 2022)
• Albin Ahlbäck ([email protected])

License

FLINT is distributed under LGPL (GNU Lesser General Public License) version 3 or later. See the COPYING.LESSER and COPYING files.

flint's Issues

Merge Arb into flint as a standard module

See title.

Test and merge Abhinav Baid's new n_gcd code.

Abhinav Baid has written a new n_gcd function which should be slightly faster than the old one on x86_64 and x86 due to the presence of cpu count_trailing_zeroes. This needs testing, comparing for speed and merging.

https://github.com/fandango-/number-theory/blob/master/flint_gcd.c

Improve rectangular matrix multiplication

nmod_mat_mul should be smarter when the matrices are highly unbalanced. We always want to break such products into smaller, approximately square blocks. For example, in Brent-Kung composition we have matrices of shape (n^0.5, n), and the blocks should be of size (n^0.5, n^0.5).

This improves access locality for basecase multiplication, and can reduce CPU efficiency as well (shorter dot products means fewer carries, meaning that in some cases 1 or 2 accumulator limbs can be used instead of 2 or 3), and it improves efficiency of Strassen. It also greatly reduces the extra temporary memory requirements (O(n) instead of O(n^1.5) in Brent-Kung).

When implementing this, one should be careful to get all the different cases right (i.e. in the multiplication (m, n) x (n, p), any one of them could be much larger than the others, or two of them could be larger than the third).

Allow to compile against mpir (without --enable-gmpcompat in mpir)

Distributions usually cannot enable gmpcompat in mpir since they need both installed at the same time. Enabling gmpcompat would cause file collision and is impossible to support sanely on distribution-level. That limits the user choice here effectively to gmp.

Make mpfr optional

It would be nice to be able to build flint without mpfr, obviously disabling functions which really require it in such instances.

Mathematically meaningful chapter headings in docs

The documentation currently has module name as chapter headings. This is somewhat unfriendly for new users who don't know what those modules do. The chapter headings should therefore be changed to mathematically meaningful headings with module names as subtitles.

Check slong is used for variables passed as params to _si functions

See title.

Macro for error condition and exception

We should use a macro for the pattern

if (cond)
{
printf("Exception (function_name): msg");
abort();
}

Example: fmpz_poly/divrem.c

Note that this use case is not quite the same as that of FLINT_ASSERT (which is intended for debug builds only).

Dependency (.d) files missing with GNU Make 3.80

I am on a Mac OS X 10.4 PPC machine, using GNU make 3.80. The basic problem is that in compiling some library extensions in Sage involving mwrank, compilation fails with

/usr/bin/ld: Undefined symbols:
_nmod_mat_clear referenced from libec expected to be defined in libflint.dylib
_nmod_mat_init referenced from libec expected to be defined in libflint.dylib
_nmod_mat_rref referenced from libec expected to be defined in libflint.dylib
collect2: error: ld returned 1 exit status
error: command 'g++' failed with exit status 1

and then when we inspect Flint's package build, it turns out there are mysterious

../Makefile.subdirs:41: no file name for `-include'

which Bill Hart already has pointed out. All self-tests pass ('SAGE_CHECK=yes') so it's really just this issue of the linker not having the right symbols to link with because of these missing things earlier in compiling.

-include $(patsubst %, %.d, $(PROFS))

is the line in question, but other lines like this cause no problems, and it's only a few times that this particular line hiccups - lots of the .d files are produced and (presumably) included. (?)

See https://groups.google.com/forum/#!topic/sage-release/6Vh55hF7UXk for more details, and http://boxen.math.washington.edu/home/kcrisman/ for the Makefile, Makefile.subdirs, and log of flint 2.4.1.p0 within Sage.

Work out table of B1/B2 values to factor integers of a given size using factor_pp1

See title.

use indices into global array of mpz's for --with-gc option

See title.

Not sure if we can do this without suffering the evil pointer-changed-while-holding-on-to-it bugs again, though.

Document WORD/UWORD macros

Our code_conventions.txt does not seem to discuss the WORD/UWORD macros. It should.

fmpq_poly_print_pretty is broken

(x + 1)/3 prints as x + 1/3. Reported by Hans Schoenemann.

Top level tests run sequentially even when make -j is used

Dan Grayson reports that some tests are run sequentially even when make -j is used.

Modules are also tested one after the other. It's not clear if this should be changed.

Use indices into global array of mpz's for --with-gc option

Can we do this without the evil your-pointer-silently-got-invalidated bugs though?

Port David Harvey's Schoenhage/Nussbaumer code from zn_poly

See title.

Remove dependency on gmake

See title.

Use n_factor_pp1 in n_factor

Using p+1 cleverly should speed up factorisation of integers close to 64 bits.

./configure ignores LDFLAGS

We need to pass the proper rpath options to the linker, for example by:

export LDFLAGS="-L${FLINT_DIR}/lib -Wl,-rpath=${FLINT_DIR}/lib -L${GMP_DIR}/lib -Wl,-rpath=${GMP_DIR}/lib -L${MPFR_DIR}/lib -Wl,-rpath=${MPFR_DIR}/lib"

But the LDFLAGS variable gets ignored, unlike autotools. So we then need to patch the final .so library manually with patchelf. See hashdist/hashstack#232.

The solution is to allow the user to specify LDFLAGS, just like you allow the user to specify CFLAGS.

This bug applies to Arb as well (flintlib/arb#3).

Memory usage in flint tests should not exceed 400000 where possible

Dan Grayson has noted that some flint tests use more than 400 mb (?) of memory, and that this makes testing in small virtual machines difficult. We should at least offer an option to turn off parts of tests which will exceed this, and cut the usage in others, where possible. This is quite reasonable.

0^0 consistency

The ulong_extras powmod functions don't define 0^0 = 1. They should be fixed to be consistent with all other powering functions (some changes to the test code are required).

Allow relative paths for extension modules

This would be convenient for the user, and it would make it easier to bundle flint together with several extension packages.

flint-2.4.3.pdf incorrectly describes fmpz_mat_fflu() subroutine

2nd parameter to fmpz_mat_fflu() is of type fmpz_t. However .pdf says that it is fmpz_poly_t

I don't put patch in here because GitHub Flavored Markdown turns patches into garbage

Unused code in nmod_mat/lu_recursive.c

As of ver 2.4.3 subroutine nmod_mat_lu_recursive() contains unused var A1, and code to initialize and clear it

I suggest removing A1 var definition and three lines accessing the var:

66c66

< nmod_mat_t A0, A1, A00, A01, A10, A11;

nmod_mat_t A0, A00, A01, A10, A11;

85d84
< nmod_mat_window_init(A1, A, 0, n1, m, n);
93d91
< nmod_mat_window_clear(A1);
144d141
< nmod_mat_window_clear(A1);

link with 'blas' instead of 'openblas'?

Hello,

if it is possible, I would like that flint links with lblas instead of lopenblas. (in 'configure')
If the user wants to link with openblas, his environment should be configured that way,
that there is libblas.xx pointing to libopenblas.xxx

The arguments for this change is that since blas//lapack is used by many libraries, it is probably smarter to configure its usage once for all by adjusting the environment, see below:

There are various ways to manage the environment variables. In computer centers this is/was usually done by using the 'modules' tool, http://modules.sourceforge.net/

In Ubuntu/Debian it is recently supported to install multiple implementations/versions for the same library and select a default by using the command update-alternatives, see https://wiki.debian.org/DebianScience/LinearAlgebraLibraries

feature request: make check in parallel

it seems that Flint builds in parallel using e.g. make -j4,
is that safe?

definitely not working perfectly is make -j4 check, since the output gets scrambled.
Is it possible to fix that?

Maybe 'GNU parallel' could be useful, but I'm not sure about this.

Support ICC

See title.

Balance product tree in fmpz_mod_poly and nmod_poly

Balancing the product tree can give an improvement (perhaps 20%?) in fast multipoint evaluation.

One should be careful not to not slow the current code down when the tree already is close to balanced or when the tree is small.

Integrate JP's dense p-adics modulus code with Sebastian's sparse modulus code

See title.

make install with extensions fails

I get an error running "make install" with extensions:

/bin/sh: 1: [: /home/fredrik/src/arb/bernoulli.h: unexpected operator

with the shell changed to /bin/bash:

/bin/bash: line 0: [: too many arguments

The problem appears to be this:

$(AT)if [ ! -z $(EXT_HEADERS) ]; then
cp $(EXT_HEADERS) $(DESTDIR)$(PREFIX)/include/flint;
fi

It works if one removes the first and third lines.

Documentation of probable prime testing

The n_is_probableprime_bpsw and by extension n_is_probableprime functions are now known to guarantee primality up to 2^64. The documentation does not reflect this.

Speed up trial division in fmpz_factor

Two ideas:

1. use precomputed inverses
2. use the GCD trick (precompute a huge primorial and compute the GCD of the integer with that)

Some investigation is needed to determine the best strategy.

Out of tree builds

See title.

Test for broken compilers

See title.

Bug in flint_sprintf

Ashish Kedia reports:

I was writing a few codes to understand the nmod_math module. I faced a weird trouble while doing so. The nmod_mat_print_pretty function (which prints a matrix) turned out to be the culprit.

Expected Output for a Matrix=
<2 x 2 integer matrix mod 1000000007>
[ 607560423 841602215]
[ 755434942 20]

Output Obtained from the function=
<2 x 2 integer matrix mod 1000000007>
[%%10lu %%10lu]
[%%10lu %%10lu]

I immediately understood that the problem was in format string parsing. I looked at the source code of the nmod_mat_print_pretty function. I then realized that the problem was in the flint_sprintf. Consider these 2 cases =

//Let width be 10
flint_sprintf(fmt, "%%%dlu",width);
printf("%s\n",fmt); //Outputs "%%10lu" (quotes for clarity)

sprintf(fmt, "%%%dlu",width);
printf("%s\n",fmt); //Outputs "%10lu" (quotes for clarity)

So the flint_sprintf method is parsing the format string wrongly. The solution is a pretty small change in the flint_sprintf function.
Also there is a nice trick which can be used to overcome this problem in the nmod_mat_print_pretty function, we change line number 48 from flint_sprintf(fmt,"%%%dlu",width); to flint_sprintf(fmt, "%c%dlu",'%',width); which will achieve the desired result without any change in the flint_sprintf file.

Document bug : renamed functions

袁轶君 Reports

I find something wrong with the document of flint. In the pdf doc of FLINT 2.4.3, the special 
function of fmpz (chapter 18.16), some functions are missing! For example, the function 
"void fmpz_euler_phi ( fmpz_t res , const fmpz_t n)" 
described in document can't be found in any of the header file. I have found 
"void arith_euler_phi(fmpz_t res, const fmpz_t n)" 
in the header arith.h and it is described in chapter 55.9. I believe these function are not 
the same one. Several other functions are suffering the same problem.

Thoughts on the API

I am currently using flint for a small fun crypto project which involves a lot of polynomial arithmetic, modulus stuff and euclidean algorithm.

There are a few things in the flint API that confuses me. Please bear with me in case I was just too stupid to figure out something:

• a lot of functions are void without any indication if they succeeded or not... I have to check the parameters I passed or wait for a segfault in order to figure out what just happened
• it seems most functions don't do any checking on the parameters they use... so you get a segfault instead somewhere in the middle of the code, when the function tries to dereference null-pointers
• although the allocation of polynomials is pretty smart, it also makes it extremely difficult to implement some algorithms that expect trailing 0-coefficients (NOT null-pointers!)... this makes me check for both... is it a null pointer? if it is not, is it a null-coefficient?
• It's not clear to me whether it is safe to access some structs directly. E.g. it gets a bit weird if you have to operate a lot on polynomial coefficients and have to use fmpz_poly_get_coeff_ptr() in a hundred places
• the meaning of "get" is confusing in a lot of functions
• for modular reduction I ended up calling fmpz_poly_get_nmod_poly() and fmpz_poly_set_nmod_poly_unsigned() directly after it in most of the cases, maybe a convenience function here would be a thing to consider in case I don't really need the nmod_poly data type?

But what bothers me most is the error handling. Did I miss a section in the manual and there is some sort of global variable I can check? Or is this just a design decision of debugging segfaults instead of functions returning error codes?

Anyway, probably the most advanced library in this field. Pretty awesome.

Implement APRCL

Possibly adapt the version in Yafu.

Provide SONAME and proper symlinks

There are a lot of reasons why this is important
http://tldp.org/HOWTO/Program-Library-HOWTO/shared-libraries.html

Document need for absolute paths for extensions

John Cremona reports:

In the instructions for using extension modules on page 15 of the
reference manual, I suggest saying explitly that absolute paths to the
location of the extension modulu should be given. I used something
like ../../xyz the first time and that does not work, presumably
because that exact string is passed down to subdirectories where it no
longer works. If I made that mistake , others might also. I hope.

provide a pkg-config file

Pkg-config files (foo.pc) are common interfaces to libraries. These are portable across distributions and platforms and standardize accessing your lib via build systems.
In addition, this also solves some trouble when statically linking such libs, since the dependency libs are put in the "Libs.private" variable (or Requires.private if those libs also have .pc files). Since these are generated at build time, the information is reliable (e.g. Libs.private will reflect whether flint was built with or without gc/ntl/blas support).

check http://people.freedesktop.org/~dbn/pkg-config-guide.html

I might be able to send a pull request for this too, but would need to investigate this a little bit more.

Use BLAS for matrix multiplication

We should use BLAS for matrix multiplication when available.

The easiest way to take advantage of BLAS would be to just call it in nmod_mat_mul.

We probably also want a separate module for matrices mod n < (2^53)^(1/2) implemented using doubles in a BLAS compatible format, though, to avoid double (ha!) conversions, i.e. to do fmpz_mat -> doubles directly instead of fmpz_mat -> nmod_mat -> doubles.

fmpz_zero() assigns zero twice

fmpz_zero() when called with a big number assigns zero twice: once in _fmpz_demote() and once by itself.

I offer a patch, to fix the problem (can't sleep at night when my program works slower than it could)

--- fmpz.h      2014-04-01 03:48:29.000000000 +0400
+++ fmpz-m.h    2014-04-17 18:36:53.312158379 +0400
@@ -270,8 +270,9 @@
 static __inline__
 void fmpz_zero(fmpz_t f)
 {
-   _fmpz_demote(f);
+   if (COEFF_IS_MPZ(*f)) 
+       _fmpz_clear_mpz(*f);
 }

Versioning the shared library? Binary backwards compatibility guarantees?

Hi there,
I am working on packaging flint 2.4 for Fink (a Mac OS X package manager). Doing that, I noticed that your custom build system builds a dynamic library that is not setting a compatibility_version.

Now, I can workaround that, e.g. by manually relinking the .dylib file. But the fact that the library is not versioned in any meaningful way immediately raises the question whether newer versions of the flint shared library will be backwards compatible on the ABI / binary level. E.g. is an executable linked against Flint 2.0 supposed to work when the shared library is upgraded to 2.4?

My hope is yes... but I couldn't find anything directly talking about this, nor any indirect hints (which in other projects are taken care of by library versioning -- which in turn of course is highly platform specific, which is why GNU libtool comes in handy for that).

Anyway: This is quite important to know for packaging purposes, as it affects how to package things: Do I make a flint2 package which is going to cover all 2.x release of flint? Or do I call it flint24 and then when 2.5 comes out, call that 2.5, to make sure I can install both versions in parallel (necessary to keep already compiled binaries working)? Or is compatibility possibly even broken by minor releases (e.g. 2.4.2 might or might not be binary backwards compatible)? In that case, I would probably only ship a static library.

Any pointers on this appreciated. Sorry if you cover this topic elsewhere and I missed it, in that case I would be grateful if you were to point me to the relevant discussion(s).

n_isprime() returning true for composites!!!

Dana Jacobsen reports that 2007193456621 is prime according to n_isprime(). It's composite!

There are many other failures.

Dana writes

is_prime.c:  if (n < UWORD(10000000000000000))  return n_is_probabprime(n);

in is_probabprime.c, it:
  - is not <= 1
  - is not = 2
  - is not even
  - is not a perfect 235 power
  - is not > 10000000000000000
  - is >= 1122004669633
  - is a strong probable prime to bases 2, 3, 7, 61, 24251
  - is not = 46856248255981
  - returns 1

The last test in is_probabprime.c claims that the bases 2, 3, 7, 61, 24251 are correct 
for all n between 1122004669633 and 10000000000000000 except the number 
46856248255981 (with 235 perfect powers and evens removed).  This isn't right.

As another example, the following code:

  mp_limb_t n;
  for (n = 2744715551500; n < 2744715551600; n++)
    if (n_is_prime(n))
      printf("%lu\n", n);

prints:

2744715551519
2744715551537
2744715551551
2744715551569
2744715551581

when I run it using FLINT 2.4.3 or 2.4.1.  The last number is composite.  This goes away 
if I use n_is_probabprime_BPSW(n) instead.

Fredrik writes

This was listed as a proven test on
http://primes.utm.edu/prove/prove2_3.html in 2006-2008, which
attributed it to Charles Greathouse. In fact, I clearly recall that I
implemented it in SymPy based on that page, and I guess Bill might
have done the same with FLINT...

So I suppose n_is_probabprime should be fixed by changing the constant in

#if FLINT64
    if (n >= UWORD(10000000000000000)) return n_is_probabprime_BPSW(n);
#endif

to 1122004669633, and removing the (2,3,7,61,24251) test?

It probably wouldn't hurt to improve our test code to check a list of
composites known to pass various SPRP tests.

FLINT test fails against GMP 6

Due to changes in GMP 6.0.0 specification, t-invmod test fails

The function mpz_invert now considers any number invertible in Z/1Z

(according to release notes https://gmplib.org/gmp6.0.html)

I suggest that either

1. t-invmod test be rewritten
2. FLINT documentation includes warning against using GMP 6

For 2nd salvation, I offer a patch

--- flint-manual.tex    2014-04-01 03:48:29.000000000 +0400
+++ flint-manual-m.tex  2014-04-09 09:33:05.894036023 +0400
@@ -300,7 +300,7 @@
 GNU toolchain, however it is specially optimised for x86 (32 and 64 bit)
 machines. There is also limited optimisation for ARM and ia64 machines. As
 of version 2.0, FLINT required GCC version 2.96 or later, either MPIR
-(2.6.0 or later) or GMP (5.1.1 or later), and MPFR 3.0.0 or later.
+(2.6.0 or later) or GMP (5.1.1 or later 5.1.*), and MPFR 3.0.0 or later.
 It is also required that the platform
 provide a \code{uint64_t} type if a native 64 bit type is not available.
 Full C99 compliance is \textbf{not} required.

Fix n_prime_pi_bounds and n_is_oddprime_binary for small input

n_prime_pi_bounds divides by zero if you pass n = 0 or 1. Another problem with the function is that it relies on floating-point arithmetic (there is probably a model of Bulgarian wristwatch on which the rounding goes the wrong way).

Here's a possible replacement:

extern const unsigned char FLINT_PRIME_PI_ODD_LOOKUP[];

void n_prime_pi_bounds(ulong *lo, ulong *hi, mp_limb_t n)
{
    if (n < FLINT_PRIME_PI_ODD_LOOKUP_CUTOFF)
    {
        if (n < 3)
            *lo = *hi = (n == 2);
        else
            *lo = *hi = FLINT_PRIME_PI_ODD_LOOKUP[(n-1)/2];
    }
    else
    {
        /* 14/10 < 1/log(2)*/
        *lo = (n / (10 * FLINT_CLOG2(n))) * 14;
        /* 19/10 > 1.25506/log(2) */
        *hi = (n / (10 * FLINT_FLOG2(n)) + 1) * 19;
    }
}

This change breaks n_is_oddprime_binary, however (test fails at d = 139). There is probably an off-by-one error in the way that function uses the starting bounds, making it fails when the bounds are exact.

fmpz_mod_poly_gcd_hgcd(_f) functions not implemented

see title

Optimise space for remainders

Either make _fmpz_mod_poly_rem not write to upper coeffs of remainder or fix multipoint evaluation code so it has more space to put remainders (make consistent across poly modules)

--enable-cxx on MinGW64 build failure

The makefile tries to touch flintxx/test/t-*.c but there are no .c files in the directory.

Either we need to add a t-dummy.c of make it deal differently with flintxx/test.