At present the file PrimeBase.txt contains all prime numbers below 106. This should suffice to
factorize all numbers up to 1012.
That is this distribution guarantees to find a solution for all DL-problems with prime moduli less than 1012,
provided that one exists.
Future versions of the distribution may extend the prime base and may use additional algorithms for factorization like the (p-1)-algorithm.
In the meantime you may exchange the prime base with your own PrimeBase.txt. All primes within this file should be separated through white spaces
and should be in ascending order. Since the prime numbers currently will be stored within a List[Int]
only primes below 231-1 are allowed.
All prime moduli up to 24096 will be accepted. Of course the program might not be able to factorize the group order fully. After the decomposition of all known primes the remaining factor could be too big for the computation of a discrete logarithmus by using BSGS or PollardRho. Consider task[id=9] from the batch. The prime factorization of the group order is 2·3·17·127·479309·1089764177. The last number 1089764177 is coincidentally prime but way to big to be referenced by the PrimeBase. After extracting of all known prime factors the remaining factor will be coprime to all the others, hence no problem for the Chinese Remainder Theorem. But the runtime complexity of the BSGS or rather the PollardRho-method is O(n1/2) and thus about 33011 computation steps will be needed to calculate a solution within this last group. The implementation had been able to compute an answer to this DL-problem on my computer within one and a half seconds. Now consider the disabled task[id=11] which has an order that exhibits 150666757763962484081 as prime factor. Hence this will take about one week. Because BSGS has also a space complexity of O(n1/2) your working memory will be probably exhausted during the process. PollardRho, however, has only a small memory footprint, therefore you would want to use it to compute this task. Now review task[id=12]. The remaining factor 66722510826044472645335077 isn't prime and hence PollardRho may run into problems when computing a solution. Take a look at task[id=7] to understand why this may so. The second last example (task[id=13) gives an illustration of the power of the Pohlig-Hellman algorithm. The equation
3x ≡ 5 (mod 38331277023003304069335415485024384542363849)
looks difficult. Clearly, no trivial solution does exist, but this distribution is able to find a solution within fractions of a second because all distinct primes within the factorization of the group order (23·1060194·3958513·611411) are sufficiently small.
Dependent on the given problems the JVM may need more thread stack size and/or heap size. The start scripts are presetted with 16MB or rather 1024MB.
