Alternative Polynomial Testing (performance improvement)

[Vadimuh]

https://pastebin.com/uemgwKhN

[hayguen]

example code is java .. and needs to be converted to C++ ..

[martin-zs]

I think the core idea is to use this precomputed lookup table** of prime fators for a insanely massive jump in processing speed for bits 1 to 1200 instead of brute forcing them with PrimeFactorizer.

** https://oeis.org/A001265/a001265.txt which in the java program is loaded as "mersenne_numbers_factors.txt"

[Vadimuh]

I think the core idea is to use this precomputed lookup table** of prime fators for a insanely massive jump in processing speed for bits 1 to 1200 instead of brute forcing them with PrimeFactorizer.

** https://oeis.org/A001265/a001265.txt which in the java program is loaded as "mersenne_numbers_factors.txt"

Hi martin. It's been a while since I looked at this, so I'm mainly going to be drawing from an email exchange I had with hayguen prior to opening this issue.
I didn't think much of how my code did prime factorization compared to the current implementation, though it might be something worth optimizing.

Hayguen's implementation uses matrix exponentation to detect cycles of given lengths, and has a runtime complexity of O(N^3 * log(N)) (ignoring the aspect of how many factors of 2^n - 1 to check again).
In contrast, my implementation tests maximality of the polynomials using the method described in the first answer to this question here: https://cs.stackexchange.com/questions/62759/check-if-a-given-polynomial-is-primitive
and has a runtime complexity of O(N^2 * log(N)) (once again, ignoring the aspect of how many factors of 2^n - 1 to check again).