Low performance when factoring univariate polynomial

[algebrakit]

First of all: I am a very grateful user of this great library. Thank you for creating it!

I encountered a problem: Factoring the polynomial x^70+1 is extremely slow (25 seconds on my computer)

I found that increasing N_MODULAR_FACTORIZATION_TRIALS in UnivariateFactorization.java from 4 to 10 resolves the issue in my case. However, maybe this increased number is not suitable for all cases. In that case it is maybe wise to use some smarter heuristic to determine the number of attempts.

some ideas:

• allow more attempts if the current minimum of factors is high (in my case, this minimum was 30, causing 600k iterations in reconstructFactorsZ(). In that case it makes sense to try more than just 4 attempts)
• the complexity of FactorInGF (if this low, allow more attempts)
• a probability measure of how likely it is a much lower number of factors can be found. E.g. using the variation of the factors over the attempts)

[PoslavskySV]

Hi - Thank you for using Rings!

I just made a commit which tunes heuristics allowing more modular attempt and fixes this particular case. However there always will be cases when current algorithm will be very slow. The only robust solution is to switch to LLL-factorization for recombination part, which I hope I'll implement someday)

[algebrakit]

Thank you for updating, really appreciate it. I understand it doesn't guarantee all such factorization problems are now solved, but I think it will definitely reduce the likelihood of it happening again.

[abbyberkers]

@PoslavskySV could you upload a new release that includes these changes to the maven central repository?