search

PoslavskySV / rings

Rings: efficient JVM library for polynomial rings
https://rings.readthedocs.io
72 stars 10 forks source link

Inaccurate reference for SquareFreeFactorizationMusser? #72

Closed skirpichev closed 3 years ago

skirpichev commented 3 years ago

This code claims it's Musser's algorithm (a multivariate version), but it seems, it isn't.

Ring's references page quote [GeCL92] and [Muss71]. But the first one has only an univariate version. The second one has multivariate version (algorithm V on page 54), but it doesn't look like the implemented code (which seems to be an equivalent version, though).

My guess it that the implemented version follows the L.Bernardin's work (Factorization of multivariate polynomials over finite fields. Diplomarbeit, ETH Zurich, 1993), but I can't verify this.

PoslavskySV commented 3 years ago

Hi,

sorry for delay and thank you very much for the correction. You are absolutely right, the algorithm implemented in Rings follows Bernardin's work. I've made appropriate corrections to the docs.

Thanks!

With best wishes, Stanislav

skirpichev commented 3 years ago

I think, the reference is still wrong. The used in rings algorithm seems to be a modification of Musser's algorithm. The doctor thesis don't discuss this case in details and don't provide the algorithm itself. It references the Geddes et al book (Algorithms for Computer Algebra), where only univariate case provided and the mentioned above diplomarbeit.