search

hayguen / mlpolygen

a maximal-length polynomial generator for linear feedback shift registers
GNU General Public License v3.0
48 stars 5 forks source link

Alternative Polynomial Testing (performance improvement) #3

Open Vadimuh opened 2 years ago

Vadimuh commented 2 years ago

https://pastebin.com/uemgwKhN

hayguen commented 2 years ago

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

martin-zs commented 1 year ago

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 commented 1 year ago

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).