| Functions | Implemented |
|---|---|
| Factorization | Rho, P-1, P+1, Elliptic Curve examples |
| Arithmetic and Number theoretic functions | Prime decomposition, totient function, sigma functions, primality test, Meissel formula for counting primes, Jacobi Symbol |
| Analytic NT functions | Gamma function, approximation for large values, Riemann-Siegel formula for Z(t) |
| Sieves | Eratosthenes, Atkin sieves |
| Combinatorics | Integer Partitions, Partition counting, Permutation, lexicographically ordered permutations, permutation rank, parity. |
BSD 2-clause “Simplified” License
mvn clean install
mvn test
Factoring a BigInteger The following uses the Pollard-rho method of factorization:
ArrayList<BigInteger> list = Factorizor.factor(new BigInteger("909077759200010102032010201"), Factorizor.FactorMethod.RHO);
will return
967, 9819889267, 95734388625509
Pollard P-1 method is also implemented:
ArrayList<BigInteger> list2 = Factorizor.factor(new BigInteger("425624900000909000001111317911"), Factorizor.FactorMethod.PMO);
returns
571, 62818373, 11865997022428766417
Factorizor also includes a P+1 factorization algorithm implementation.
Euler Totient of a BigInteger
Euler totient is defined Totient
BigInteger tot = Totient.totient(new BigInteger("425624"));
returns
209920
Calculating number of primes less than a given float (or BigDecimal)
int q = PrimeCount.pi(1000000f);
returns
78498
This uses the Meissel formula to calculate pi(x). It will probably choke on values much larger than 10 million though.
Calculate Lexicographically ordered permutations of list of objects (which implement Comparable)
ArrayList<Character[]> permutations = PermutationsGeneric.getLexicographicPermutations(new Character[]{'a', 'b', 'c'});
This returns six permutations:
```
{'a','b','c'}
{'a','c','b'}
{'b','a','c'}
{'b','c','a'}
{'c','a','b'}
{'c','b','a'}
```