Index: sagePolynomialOperations.sage
===================================================================
--- sagePolynomialOperations.sage	(revision 76)
+++ sagePolynomialOperations.sage	(revision 77)
@@ -1,6 +1,6 @@
 load "/home/storres/recherche/arithmetique/pobysoPythonSage/src/sageSLZ/sageMatrixOperations.sage"
 
-def spo_polynomial_to_matrix(p, pRing, alpha, N, columnWidth=0):
+def spo_polynomial_to_matrix(p, pRing, alpha, N, columnsWidth=0):
     """
     From a (bivariate) polynomial and some other parameters build a matrix
     to be reduced by fpLLL.
@@ -11,6 +11,8 @@
     N:
     
     """
+    knownMonomials = []
+    protoMatrixRows = []
     pVariables = p.variables()
     iVariable = pVariables[0]
     tVariable = pVariables[1]
@@ -26,14 +28,16 @@
         # in, those in t necessary to be able to introduce
         # p. We arbitrary choose to introduce the highest degree monomial in i
         # with p. We also introduce all the mixed i^k * t^l monomials with
-        # k < p.degree(i) and l <= p.degree(t)
+        # k < p.degree(i) and l <= p.degree(t).
+        # Mixed terms introduction is necessary before we start "i shifts" in
+        # the next iteration.
         if pPower == 0:
             # iter1: power of i
             # Notice how i^pIdegree is excluded.
             for iPower in xrange(0, pIdegree): 
                 # iter5: power of t.
                 for tPower in xrange(0, pTdegree + 1):
-                    if columnWidth != 0:
+                    if columnsWidth != 0:
                         print "->", spo_expression_as_string(iPower, 
                                                              tPower, 
                                                              pPower, 
@@ -46,20 +50,163 @@
                                         polynomialAtPower 
                     pMonomials = currentPolynomial.monomials()
                     pCoefficients = currentPolynomial.coefficients()
-                    spo_add_polynomial_coeffs_to_matrix(pMonomials, pCoefficients, knownMonomials, protoMatrixRows, monomialLengthChars)
+                    spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                        pCoefficients, 
+                                                        knownMonomials, 
+                                                        protoMatrixRows, 
+                                                        columnsWidth)
                 # End iter5.
             # End for iter1.
             
-    else: # Next runs (p^1..p^alpha)
-        pass
-    
+        else: # pPower > 0: (p^1..p^alpha)
+            # This where we introduce the p^iPower * N^(alpha-iPower)
+            # polynomial.
+            # This step could technically be fused as the first iteration
+            # of the next loop (with iPower starting at 0).
+            # We set it apart for clarity.
+            if columnsWidth != 0:
+                print "->", spo_expression_as_string(0, 0, pPower, alpha)
+            currentPolynomial = polynomialAtPower * nAtPower
+            pMonomials = currentPolynomial.monomials()
+            pCoefficients = currentPolynomial.coefficients()
+            spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                pCoefficients, 
+                                                knownMonomials, 
+                                                protoMatrixRows, 
+                                                columnsWidth)
+            
+            # The i^iPower * p^pPower polynomials: they add i^k monomials to  
+            # p^pPower up to k < pIdegree * pPower. This only introduces i^k 
+            # monomials since mixed terms (that were introduced at a previous
+            # stage) are only shifted to already existing 
+            # ones. p^pPower is "shifted" to higher degrees in i as far as 
+            # possible, one step short of the degree in i of p^(pPower+1) .
+            # These "pure" i^k monomials can only show up with i multiplications.
+            for iPower in xrange(1, pIdegree):
+                print "->", spo_expression_as_string(iPower, 0, pPower, alpha)
+                currentExpression = i^iPower * nAtPower
+                currentPolynomial = P(currentExpression) * polynomialAtPower
+                pMonomials = currentPolynomial.monomials()
+                pCoefficients = currentPolynomial.coefficients()
+                spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                    pCoefficients, 
+                                                    knownMonomials, 
+                                                    protoMatrixRows, 
+                                                    columnsWidth)
+            # End for iPower
+            # We want now to introduce a t * p^pPower polynomial. But before
+            # that we must introduce some mixed monomials.
+            # This loop is no triggered before pPower == 2.
+            # It introduces a first set of mixed monomials.
+            for iPower in xrange(1, pPower):
+                tPower = pPower - iPower + 1
+                if columnsWidth != 0:
+                    print "->", spo_expression_as_string(iPower * pIdegree, 
+                                                         tPower, 
+                                                         0,  
+                                                         alpha)
+                currentExpression = i^(iPower * pIdegree) * t^tPower * nAtPower
+                currentPolynomial = P(currentExpression)
+                pMonomials = currentPolynomial.monomials()
+                pCoefficients = currentPolynomial.coefficients()
+                spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                    pCoefficients, 
+                                                    knownMonomials, 
+                                                    protoMatrixRows, 
+                                                    columnsWidth)
+            # End for iPower
+            # This is the main loop. It introduces:
+            # - the missing mixed monomials needed before the 
+            #   t * p^pPower * N^(alpha-pPower)  polynomial;
+            # - the t * p^pPower * N^(alpha-pPower) itself;
+            # - the missing mixed monomials needed before each of the 
+            #   i^k * t^l * p^pPower * N^(alpha-pPower) polynomials;
+            # - the i^k * t^l * p^pPower * N^(alpha-pPower) themselves.
+            for iShift in xrange(0, pIdegree):
+                # When pTdegree == 1, the following loop only introduces 
+                # a single new monomial.
+                #print "++++++++++"
+                for outerTpower in xrange(1, pTdegree + 1):
+                    # First one high i degree mixed monomial.
+                    iPower = iShift + pPower * pIdegree
+                    if columnsWidth != 0:
+                        print "->", spo_expression_as_string(iPower, 
+                                                             outerTpower,
+                                                             0,
+                                                             alpha)
+                    currentExpression = i^iPower * t^outerTpower * nAtPower
+                    currentPolynomial = P(currentExpression)
+                    pMonomials = currentPolynomial.monomials()
+                    pCoefficients = currentPolynomial.coefficients()
+                    spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                        pCoefficients, 
+                                                        knownMonomials, 
+                                                        protoMatrixRows, 
+                                                        columnsWidth)
+                    #print "+++++"
+
+                    # At iShift == 0, the following loop adds duplicate 
+                    # monomials, since no extra i^l * t^k is needed before 
+                    # introducing the  
+                    # i^iShift * t^outerPpower * p^pPower * N^(alpha-pPower) 
+                    # polynomial.
+                    # It introduces smaller i degree monomials than the
+                    # one(s) added previously (no pPower multiplication).
+                    # Here the exponent of t decreases as that of i increases.
+                    if iShift > 0:
+                        iPower = pIdegree + iShift
+                        for innerTpower in xrange(pPower, 1, -1):
+                            if columnsWidth != 0:
+                                print "->", spo_expression_as_string(iPower, 
+                                                                     innerTpower,
+                                                                     0,
+                                                                     alpha) 
+                            currentExpression = \
+                                    i^(iPower) * t^(innerTpower) * nAtPower
+                            currentPolynomial = P(currentExpression)
+                            pMonomials = currentPolynomial.monomials()
+                            pCoefficients = currentPolynomial.coefficients()
+                            spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                                pCoefficients, 
+                                                                knownMonomials, 
+                                                                protoMatrixRows, 
+                                                                columnsWidth)
+                            iPower += pIdegree
+                        # End for innerTpower
+                    # End of if iShift > 0
+                    # Eventually, the following section introduces the 
+                    # i^iShift * t^outerTpower * p^iPower * N^(alpha-iPower) 
+                    # polynomials.
+                    if columnsWidth != 0:
+                        print "->", spo_expression_as_string(iShift, 
+                                                             outerTpower,
+                                                             pPower,
+                                                             alpha)
+                    currentExpression = i^iShift * t^outerTpower * nAtPower
+                    currentPolynomial = P(currentExpression) * polynomialAtPower
+                    pMonomials = currentPolynomial.monomials()
+                    pCoefficients = currentPolynomial.coefficients()
+                    spo_add_polynomial_coeffs_to_matrix(pMonomials, 
+                                                        pCoefficients, 
+                                                        knownMonomials, 
+                                                        protoMatrixRows, 
+                                                        columnsWidth)
+                # End for outerTpower 
+                #print "++++++++++"
+
+
+            # End for iShift
+        polynomialAtPower *= p  
+        nAtPower /= N
+    # End for pPower loop
+    return protoMatrixRows
 # End spo_polynomial_to_matrix
 
 def spo_add_polynomial_coeffs_to_matrix(pMonomials, 
                                         pCoefficients, 
                                         knownMonomials, 
                                         protoMatrixRows, 
-                                        columnWidth=0):
+                                        columnsWidth=0):
     """
     For a given polynomial (under the form of monomials and coefficents lists),
     add the coefficients of the protoMatrix (a list of proto rows).
@@ -88,11 +235,11 @@
         for pmIdx in xrange(0, len(pMonomials)):
             knownMonomials.append(pMonomials[pmIdx])
             protoMatrixRowCoefficients.append(pCoefficients[pmIdx])
-            if columnWidth != 0:
+            if columnsWidth != 0:
                 monomialAsString = str(pCoefficients[pmIdx]) + " " + \
                                    str(pMonomials[pmIdx])
                 print monomialAsString, " " * \
-                      (columnWidth - len(monomialAsString)),
+                      (columnsWidth - len(monomialAsString)),
     # There are some known monomials. We search for them in pMonomials and 
     # add their coefficients to the proto matrix row.
     else: 
@@ -102,11 +249,11 @@
             try:
                 indexInPmonomials = \
                     pMonomials.index(knownMonomials[knownMonomialIndex])
-                if columnWidth != 0:
+                if columnsWidth != 0:
                     monomialAsString = str(pCoefficients[indexInPmonomials]) + \
                         " " + str(knownMonomials[knownMonomialIndex])
                     print monomialAsString, " " * \
-                        (columnWidth - len(monomialAsString)),
+                        (columnsWidth - len(monomialAsString)),
                 # Add the coefficient to the proto matrix row and delete the \
                 # known monomial from the current pMonomial list 
                 #(and the corresponding coefficient as well).
@@ -116,26 +263,26 @@
             # The knownMonomials element is not in pMonomials
             except ValueError:   
                 protoMatrixRowCoefficients.append(0)
-                if columnWidth != 0:
+                if columnsWidth != 0:
                     monomialAsString = "0" + " "+ \
                         str(knownMonomials[knownMonomialIndex])
                     print monomialAsString, " " * \
-                        (columnWidth - len(monomialAsString)),
+                        (columnsWidth - len(monomialAsString)),
         # End for knownMonomialKey loop. 
         # We now append the remaining monomials of pMonomials to knownMonomials 
         # and the corresponding coefficients to proto matrix row.
         for pmIdx in xrange(0, len(pMonomials)):
             knownMonomials.append(pMonomials[pmIdx])
             protoMatrixRowCoefficients.append(pCoefficients[pmIdx])
-            if columnWidth != 0:
+            if columnsWidth != 0:
                 monomialAsString = str(pCoefficients[pmIdx]) + " " \
                     + str(pMonomials[pmIdx])
                 print monomialAsString, " " * \
-                    (columnWidth - len(monomialAsString)),
+                    (columnsWidth - len(monomialAsString)),
         # End for pmIdx loop.
     # Add the new list row elements to the proto matrix.
     protoMatrixRows.append(protoMatrixRowCoefficients)
-    if columnWidth != 0:
+    if columnsWidth != 0:
         print    
 # End spo_add_polynomial_coeffs_to_matrix
 
