Improve sign consistency in rational polynomial factorization

[real-or-random]

The placement of the minus sign when factoring multivariate polynomials over QQ lost consistency at some point between Sage 9.2 and 9.4.

Define a multivariate polynomial ring:

sage: R.<ax,bx,ay,by,Az,Bz,Ai,Bi> = PolynomialRing(QQ, 8, order='invlex')
sage: R
Multivariate Polynomial Ring in ax, bx, ay, by, Az, Bz, Ai, Bi over Rational Field

Then, in Sage 9.2:

sage: R((-2 * (bx - ax)) ^ 1).factor()
(2) * (-bx + ax)
sage: R((-2 * (bx - ax)) ^ 2).factor()
(4) * (-bx + ax)^2
sage: R((-2 * (bx - ax)) ^ 3).factor()
(8) * (-bx + ax)^3

while in Sage 9.4 or Sage 9.5:

sage: R((-2 * (bx - ax)) ^ 1).factor()
(-2) * (bx - ax)
sage: R((-2 * (bx - ax)) ^ 2).factor()
(4) * (-bx + ax)^2
sage: R((-2 * (bx - ax)) ^ 3).factor()
(8) * (-bx + ax)^3

This broke our code in

• sage: Fix incompatibility with sage 9.4 bitcoin-core/secp256k1#1068 (comment)

It would be good to output a canonical form. A natural choice seems to make the leading coefficient of each factor positive.

It may then also be good to document that the factors will be primitive.

The invlex monomial ordering is not the culprit: the inconsistency also occurs with lex (see one comment down at the GitHub link).

Component: factorization

Issue created by migration from https://trac.sagemath.org/ticket/33283

[real-or-random]

Description changed:

--- 
+++ 
@@ -35,6 +35,8 @@
 
 This broke our code in https://github.com/bitcoin-core/secp256k1/pull/1068#discussion_r796515727 .
 
-I think to would be good to output a canonical form. A natural choice seems to make the leading coefficient of each factor positive.
+I think to would be good to output a canonical form. A natural choice seems to make the leading coefficient of each factor positive. 
+
+It may then also be good to document that the factors will be primitive.
 
 Note that `invlex` is not the culprit here. We have an example this shows this inconsistency with `lex` (see the [GitHub](../wiki/GitHub) link, one comment further down).

[slel]

Description changed:

--- 
+++ 
@@ -1,14 +1,16 @@
-sage is not very consistent in the placement of the minus sign when factoring multivariate polynomials over QQ, and this has changed at some point between sage 9.2 and 9.4:
+The placement of the minus sign when factoring multivariate polynomials over `QQ` lost consistency at some point between Sage 9.2 and 9.4.
+
+Define a multivariate polynomial ring:
 
 ```
-$ sage
-┌────────────────────────────────────────────────────────────────────┐
-│ SageMath version 9.2, Release Date: 2020-10-24                     │
-│ Using Python 3.9.7. Type "help()" for help.                        │
-└────────────────────────────────────────────────────────────────────┘
-sage: R.<ax,bx,ay,by,Az,Bz,Ai,Bi> = PolynomialRing(QQ,8,order='invlex')
+sage: R.<ax,bx,ay,by,Az,Bz,Ai,Bi> = PolynomialRing(QQ, 8, order='invlex')
 sage: R
 Multivariate Polynomial Ring in ax, bx, ay, by, Az, Bz, Ai, Bi over Rational Field
+```
+
+Then, in Sage 9.2:
+
+```
 sage: R((-2 * (bx - ax)) ^ 1).factor()
 (2) * (-bx + ax)
 sage: R((-2 * (bx - ax)) ^ 2).factor()
@@ -16,13 +18,9 @@
 sage: R((-2 * (bx - ax)) ^ 3).factor()
 (8) * (-bx + ax)^3
 ```
+while in Sage 9.4 or Sage 9.5:
 
 ```
-┌────────────────────────────────────────────────────────────────────┐
-│ SageMath version 9.5, Release Date: 2022-01-30                     │
-│ Using Python 3.10.2. Type "help()" for help.                       │
-└────────────────────────────────────────────────────────────────────┘
-sage: R.<ax,bx,ay,by,Az,Bz,Ai,Bi> = PolynomialRing(QQ,8,order='invlex')
 sage: R((-2 * (bx - ax)) ^ 1).factor()
 (-2) * (bx - ax)
 sage: R((-2 * (bx - ax)) ^ 2).factor()
@@ -31,12 +29,12 @@
 (8) * (-bx + ax)^3
 ```
 
-(The second snippet is from 9.5 but we saw the same in 9.4.)
+This broke our code in
 
-This broke our code in https://github.com/bitcoin-core/secp256k1/pull/1068#discussion_r796515727 .
+- https://github.com/bitcoin-core/secp256k1/pull/1068#discussion_r796515727
 
-I think to would be good to output a canonical form. A natural choice seems to make the leading coefficient of each factor positive. 
+It would be good to output a canonical form. A natural choice seems to make the leading coefficient of each factor positive. 
 
 It may then also be good to document that the factors will be primitive.
 
-Note that `invlex` is not the culprit here. We have an example this shows this inconsistency with `lex` (see the [GitHub](../wiki/GitHub) link, one comment further down).
+The `invlex` monomial ordering is not the culprit: the inconsistency also occurs with `lex` (see one comment down at the GitHub link).