- 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:
legendre_phi
znlog
- 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.
- Fermat base 2 also no faster than SPRP-2, though some claim it is.
mpz_t e, r; int composite;
mpz_init(e);
mpz_init_set_ui(r, 2); mpz_sub_ui(e, n, 1); mpz_powm(r, r, e, n);
composite = mpz_cmp_ui(r, 1) != 0;
mpz_clear(r); mpz_clear(e);
if (composite) return 0;
None of these are faster on average than just doing BPSW.
- merge the two frobenius tests. cp is faster, needs the deterministic
version, we should switch to the two input version (allow GMP), etc.
- New version of Pi code using Chudnovsky. See Pari.
- tests for sieve_primes.
speed up range sieving.
time mpu 'use bigint; my $n = 10**20; say join "\n",Math::Prime::Util::GMP::sieve_primes($n,$n+8e9,0);' >foo
takes ~35 minutes. NewPGen can do it in less than 4. At 10^22 it is closer.
- More efficient version of ramanujan_tau?
- Consider ranged ramanujan_tau. See:
https://cs.uwaterloo.ca/journals/JIS/VOL13/Lygeros/lygeros5.pdf
Where we could compute a number of hclassno values, then generate the
tau values. This might be more efficient.