Révision 279

pobysoPythonSage/src/sageSLZ/sageSLZ.sage (revision 279)
483 483 
        else:
484 484 
            #print l2Norm.n() , ">", nAtAlpha
485 485 
            pass
486 
        # End if
487 
    # End for.
486 488 
    if len(ccReducedPolynomialsList) < 2: # Insufficient reduction.
487 489 
        print "Less than 2 Coppersmith condition compliant vectors."
488 490 
        print "Extra reduction starting..."
489 
        reducedMatrix = reducedMatrixStep1.LLL(algorithm='fpLLL:wrapper')
490 
        ### If uncommented, the following statement avoids performing
491 
        #   an actual LLL reduction. This allows for demonstrating
492 
        #   the behavior of our pseudo-reduction alone.
493 
        #return ()
494 
    else:
491 
        reducedMatrixStep2 = reducedMatrixStep1.LLL(algorithm='fpLLL:wrapper')
492 
        ## Create a fresh reduced polynomials list.
493 
        ccReducedPolynomialsList = []
494 
        for row in reducedMatrixStep2.rows():
495 
            l2Norm = row.norm(2)
496 
            if (l2Norm * monomialsCountSqrt) < nAtAlpha:
497 
                #print (l2Norm * monomialsCountSqrt).n()
498 
                #print l2Norm.n()
499 
                ccReducedPolynomial = \
500 
                    slz_compute_reduced_polynomial(row,
501 
                                                   knownMonomials,
502 
                                                   iVariable,
503 
                                                   iBound,
504 
                                                   tVariable,
505 
                                                   tBound)
506 
                if not ccReducedPolynomial is None:
507 
                    ccReducedPolynomialsList.append(ccReducedPolynomial)
508 
        # End for.
509 
    else: # At least 2 small norm enough vectors from reducedMatrixStep2.
495 510 
        print "First step of reduction afforded enough vectors"
496 
        return ccReducedPolynomialsList
511 
    return ccReducedPolynomialsList
497 512 
    #print ccReducedPolynomialsList
498 513 
    ## Check again the Coppersmith condition for each row and build the reduced
499 514 
    #  polynomials.
......
2740 2755 
                                           matToReduce.ncols(),
2741 2756 
                                           matToReduce.nrows())
2742 2757 
    """
2743 
    # Random matrix elements in {-1,0,1}.
2744 
    matProjector = slz_random_proj_pm1(matToReduce.ncols(),
2745 
                                       matToReduce.nrows())
2746 
    matProjected = matToReduce * matProjector
2747 
    ## Build the argument matrix for LLL in such a way that the transformation
2748 
    #  matrix is also returned. This matrix is obtained at almost no extra
2749 
    # cost. An identity matrix must be appended to
2750 
    #  the left of the initial matrix. The transformation matrix will
2751 
    # will be recovered at the same location from the returned matrix .
2752 
    idMat = identity_matrix(matProjected.nrows())
2753 
    augmentedMatToReduce = idMat.augment(matProjected)
2754 
    reducedProjMat = \
2755 
        augmentedMatToReduce.LLL(algorithm='fpLLL:wrapper')
2758 
    reductionOK = False
2759 
    while not reductionOK:
2760 
        # Random matrix elements in {-1,0,1}.
2761 
        matProjector = slz_random_proj_pm1(matToReduce.ncols(),
2762 
                                           matToReduce.nrows())
2763 
        matProjected = matToReduce * matProjector
2764 
        ## Build the argument matrix for LLL in such a way that the
2765 
        #  transformationmatrix is also returned. This matrix is obtained
2766 
        #  at almost no extra cost. An identity matrix must be appended to
2767 
        #  the left of the initial matrix. The transformation matrix will
2768 
        # will be recovered at the same location from the returned matrix .
2769 
        idMat = identity_matrix(matProjected.nrows())
2770 
        augmentedMatToReduce = idMat.augment(matProjected)
2771 
        try:
2772 
            reducedProjMat = \
2773 
                augmentedMatToReduce.LLL(algorithm='fpLLL:wrapper')
2774 
            reductionOK = True
2775 
        except ValueError:
2776 
            print "Problem with projected matrix."
2777 
    # Enb while not reduction OK
2778 
    #
2756 2779 
    ## Recover the transformation matrix (the left part of the reduced matrix).
2757 2780 
    #  We discard the reduced matrix itself.
2758 2781 
    transMat = reducedProjMat.submatrix(0,

Formats disponibles : Unified diff