Changeset 7383:6b57fec5f439


Ignore:
Timestamp:
11/19/07 02:50:04 (5 years ago)
Author:
Martin Albrecht <malb@…>
Branch:
default
Message:

updated LLL documentation, added error check for fpLLL

Location:
sage
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • sage/libs/fplll/fplll.pyx

    r7126 r7383  
    176176        self._check_eta(eta) 
    177177        self._check_delta(delta) 
     178        cdef int ret = 0 
    178179 
    179180        cdef wrapper *w = wrapper_new(self._lattice, 0, eta, delta) 
    180181        _sig_on 
    181         w.LLL() 
     182        ret = w.LLL() 
    182183        _sig_off 
    183184        wrapper_delete(w) 
     185        if ret < 0: 
     186            raise RuntimeError, "fpLLL returned %d < 0"%ret 
     187         
    184188 
    185189    def proved(self, int precision=0, float eta=0.51, float delta=0.99, implementation=None): 
    … …  
    240244        cdef proved_mpfr *pmpfr 
    241245        cdef proved_dpe *pdpe 
     246        cdef int ret = 0  
    242247 
    243248        if implementation is None: 
    … …  
    247252           pdouble = proved_double_new(self._lattice, precision, eta, delta) 
    248253           _sig_on 
    249            pdouble.LLL() 
     254           ret = pdouble.LLL() 
    250255           _sig_off 
    251256           proved_double_delete(pdouble) 
    … …  
    253258           pdpe = proved_dpe_new(self._lattice, precision, <double>eta, <double>delta) 
    254259           _sig_on 
    255            pdpe.LLL() 
     260           ret = pdpe.LLL() 
    256261           _sig_off 
    257262           proved_dpe_delete(pdpe) 
    … …  
    259264           pmpfr = proved_mpfr_new(self._lattice, precision, eta, delta) 
    260265           _sig_on 
    261            pmpfr.LLL() 
     266           ret = pmpfr.LLL() 
    262267           _sig_off 
    263268           proved_mpfr_delete(pmpfr) 
     269 
     270        if ret < 0: 
     271            raise RuntimeError, "fpLLL returned %d < 0"%ret 
    264272 
    265273    def fast(self, int precision=0, float eta=0.51, float delta=0.99, implementation=None): 
    … …  
    312320 
    313321        cdef fast_double *pdouble 
     322        cdef int ret = 0 
    314323 
    315324        pdouble = fast_double_new(self._lattice, precision, eta, delta) 
    316325        _sig_on 
    317         pdouble.LLL() 
     326        ret = pdouble.LLL() 
    318327        _sig_off 
    319328        fast_double_delete(pdouble) 
     329 
     330        if ret < 0: 
     331            raise RuntimeError, "fpLLL returned %d < 0"%ret 
    320332 
    321333    def fast_early_red(self, int precision=0, float eta=0.51, float delta=0.99, implementation=None): 
    … …  
    373385        self._check_eta(eta) 
    374386        self._check_delta(delta) 
     387        cdef int ret = 0 
    375388 
    376389        cdef fast_early_red_double *pdouble 
    … …  
    378391        pdouble = fast_early_red_double_new(self._lattice, precision, eta, delta) 
    379392        _sig_on 
    380         pdouble.LLL() 
     393        ret = pdouble.LLL() 
    381394        _sig_off 
    382395        fast_early_red_double_delete(pdouble) 
     396 
     397        if ret < 0: 
     398            raise RuntimeError, "fpLLL returned %d < 0"%ret 
    383399 
    384400    def heuristic(self, int precision=0, float eta=0.51, float delta=0.99, implementation=None): 
    … …  
    433449        cdef heuristic_mpfr *pmpfr 
    434450        cdef heuristic_dpe *pdpe 
     451        cdef int ret = 0 
    435452 
    436453        if implementation is None: 
    … …  
    438455 
    439456        if implementation == "double": 
    440            pdouble = heuristic_double_new(self._lattice, precision, eta, delta) 
    441            _sig_on 
    442            pdouble.LLL() 
    443            _sig_off 
    444            heuristic_double_delete(pdouble) 
     457            pdouble = heuristic_double_new(self._lattice, precision, eta, delta) 
     458            _sig_on 
     459            ret = pdouble.LLL() 
     460            _sig_off 
     461            heuristic_double_delete(pdouble) 
    445462        elif implementation == "dpe": 
    446            pdpe = heuristic_dpe_new(self._lattice, precision, <double>eta, <double>delta) 
    447            _sig_on 
    448            pdpe.LLL() 
    449            _sig_off 
    450            heuristic_dpe_delete(pdpe) 
     463            pdpe = heuristic_dpe_new(self._lattice, precision, <double>eta, <double>delta) 
     464            _sig_on 
     465            ret = pdpe.LLL() 
     466            _sig_off 
     467            heuristic_dpe_delete(pdpe) 
    451468        elif implementation == "mpfr": 
    452            pmpfr = heuristic_mpfr_new(self._lattice, precision, eta, delta) 
    453            _sig_on 
    454            pmpfr.LLL() 
    455            _sig_off 
    456            heuristic_mpfr_delete(pmpfr) 
     469            pmpfr = heuristic_mpfr_new(self._lattice, precision, eta, delta) 
     470            _sig_on 
     471            ret = pmpfr.LLL() 
     472            _sig_off 
     473            heuristic_mpfr_delete(pmpfr) 
     474 
     475        if ret < 0: 
     476            raise RuntimeError, "fpLLL returned %d < 0"%ret 
     477 
    457478 
    458479    def heuristic_early_red(self, int precision=0, float eta=0.51, float delta=0.99, implementation=None): 
    … …  
    514535        cdef heuristic_early_red_mpfr *pmpfr 
    515536        cdef heuristic_early_red_dpe *pdpe 
     537        cdef int ret = 0  
    516538 
    517539        if implementation is None: 
    … …  
    521543           pdouble = heuristic_early_red_double_new(self._lattice, precision, eta, delta) 
    522544           _sig_on 
    523            pdouble.LLL() 
     545           ret = pdouble.LLL() 
    524546           _sig_off 
    525547           heuristic_early_red_double_delete(pdouble) 
    … …  
    527549           pdpe = heuristic_early_red_dpe_new(self._lattice, precision, <double>eta, <double>delta) 
    528550           _sig_on 
    529            pdpe.LLL() 
     551           ret = pdpe.LLL() 
    530552           _sig_off 
    531553           heuristic_early_red_dpe_delete(pdpe) 
    … …  
    533555           pmpfr = heuristic_early_red_mpfr_new(self._lattice, precision, eta, delta) 
    534556           _sig_on 
    535            pmpfr.LLL() 
     557           ret = pmpfr.LLL() 
    536558           _sig_off 
    537559           heuristic_early_red_mpfr_delete(pmpfr) 
    538560 
     561        if ret < 0: 
     562            raise RuntimeError, "fpLLL returned %d < 0"%ret 
    539563 
    540564def gen_intrel(int d, int b): 

  • sage/matrix/matrix_integer_dense.pyx

    r7099 r7383  
    15531553        self. 
    15541554 
     1555        A lattice is (delta, eta)-LLL-reduce if the two following 
     1556        conditions hold: 
     1557         
     1558        (a) For any $i>j$, we have $|mu_{i, j}| <= \eta$, 
     1559        (b) For any $i<d$, we have 
     1560        $\delta |b_i^*|^2 <= |b_{i + 1}^* + mu_{i + 1, i} b_{i + 1}^* |^2$, 
     1561 
    15551562        The lattice is returned as a matrix. Also the rank (and the 
    15561563        determinant) of self are cached if those are computed during 
    15571564        the reduction. 
    15581565 
    1559         More specifically, elementary row transformations are 
    1560         performed on a copy of self so that the non-zero rows of R 
    1561         form an LLL-reduced basis for the lattice spanned by the rows 
    1562         of self. The default reduction parameters are $\delta=3/4$ and 
    1563         $eta=0.501$. 
    1564  
    1565         For a basis reduced with parameter $\delta$, the squared 
    1566         length of the first non-zero basis vector is no more than 
    1567         $1/(\delta-1/4)^{r-1}$ times that of the shortest vector in 
    1568         the lattice. 
     1566        The default reduction parameters are $\delta=3/4$ and 
     1567        $eta=0.501$. The parameters $\delta$ and $\eta$ must satisfy: 
     1568        $0.25 < \delta <= 1.0$ and $0.5 <= \eta < sqrt(\delta)$. 
    15691569 
    15701570        If we can compute the determinant of self using this method, 
    … …  
    16081608            [ 2  1  0] 
    16091609            [-1  1  3] 
     1610 
     1611        We compute the extended GCD of a list of integers using LLL, 
     1612        this example is from the Magma handbook: 
     1613 
     1614        sage: Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449, \ 
     1615                    10230248, 709487, 68965012139, 972065, 864972271 ] 
     1616        sage: n = len(Q) 
     1617        sage: S = 100 
     1618        sage: X = Matrix(ZZ, n, n + 1) 
     1619        sage: for i in xrange(n): 
     1620        ...       X[i,i + 1] = 1 
     1621        sage: for i in xrange(n):  
     1622        ...       X[i,0] = S*Q[i] 
     1623        sage: L = X.LLL() 
     1624        sage: M = L[n-1].list()[1:] 
     1625        sage: M 
     1626        [-3, -1, 13, -1, -4, 2, 3, 4, 5, -1] 
     1627        sage: add([Q[i]*M[i] for i in range(n)]) 
     1628        -1 
    16101629             
    16111630        ALGORITHM: Uses NTL or fpLLL. 
Note: See TracChangeset for help on using the changeset viewer.