- prime_count - needs the pc(#) option as well as pc(#,#)
- Do a GMP version of LMO prime_count. Possible versions:
- 32-bit main, 16-bit support
- 64-bit main, 32-bit support (using __uint64_t if necessary)
- 128-bit main, 64-bit support (gcc only)
- GMP main, 32-bit support (portable)
- GMP main, 64-bit support (mostly portable)
- nth_prime
- GMP SQUFOF could use a better implementation, though low priority since it
just isn't going to be the right algorithm for numbers > 2^64. Mainly what
it needs is to pay attention to the rounds argument. Perhaps race.
- Add Riemann R function
- Tune and improve SIMPQS for our uses. Check FLINT 2.3 for improvements.
- Write our own QS.
- The statics in ecm and QS won't play well with threading.
- ECPP: Perhaps more HCPs/WCPs could be loaded if needed?
- ECPP: Another idea is related to Atkin/Morain's EAS. When we have a large
number, we can process more Ds, delaying the downrun. We then use the
smallest q we found. Combine with lightened stage 1 factoring as above.
This drops our q sizes faster, at the expense of more up-front time.
I have this running, but for small numbers it doesn't matter much, and for
large numbers it just highlights how much nicer FAS would be.
- ECPP: All discriminants with D % 8 != 3 have been converted to Weber. We're
still left with lots of those D values. Figure out a different invariant
that will make smaller polynomials, along with a root conversion.
- ECPP: Add a fast BLS5 to downrun?
- Add BLS17 proof. Merge into BLS5 code since the end is the same.
- Add tests for proofs, similar to MPU t/23.
- Handle objects of type:
Math::GMP
Math::GMP::Fast
Math::GMPz
We should parse their mpz_t directly, do our processing, and output the
result as one of these types.
- Recognize Math::BigInt / Math::Pari objects. Shortcut validation.
Create results as new objects of their type.
- These functions should be added:
divisor_sum
legendre_phi
znlog
chinese
- Any fast primality pretest would be nice. I've tested:
- Colin Plumb's Euler Criterion test
- Fermat base 210, which is done in GMP's internal millerrabin.c.
None of these are faster on average than just doing BPSW.
- Partial range sieve, which we could use for next_prime or primes in
combination with BPSW.