Use the square-free factor instead of the full polynomial

[lvella]

For satisfiability applications, maintaining the same ideal as the input is not important. What is important is to maintain the same associated variety.

Calculating the square-free factor of a polynomial over a finite prime field is cheap (by using a square-free decomposition algorithm), and such factor is potentially a much simpler polynomial to process. The variety won't change if we replace a polynomial by its square-free component, so it can be done if we are not interested in that particular ideal.

I don't know how many non-square-free polynomials we will encounter in real world problems, but pending issue #2, it might be a good preprocessing step to replace each input polynomial by its square-free component.