Discrete logarithm problem, popularly known as DLP has been the heart of many Public Key Infrastructures that are being used today. DLP belongs to the category of hard problems. Many ideas have been proposed to solve ...
详细信息
Discrete logarithm problem, popularly known as DLP has been the heart of many Public Key Infrastructures that are being used today. DLP belongs to the category of hard problems. Many ideas have been proposed to solve DLP. The best-known methods are Number Field Sieve (NFS) class algorithms. The Function Field Sieve (FFS) algorithm is one of the NFS class algorithms to solve DLP in an extension field, i.e. Galois field . This FFS involves three phases such as Function Sieving, Filtering, and Linear Algebra. Linear Algebra phase involves solving huge sparse matrices/system of linear equations. The most popular methods to solve sparse matrices are Lanczos and wiedemann method. Recently, wiedemann method got attention to solve the linear system of equations such as Ax = 0. This paper studies wiedemann algorithm to solve based on the factors of;since the DLP is defined over . The different cases considered in this paper are (1) is a prime of size less than n bits, (2) is a composite number with one factor of size more than n bits, and (3) is a composite number with more than one factors of n bits. The naive wiedemann is considered in case 1, paralleled version of Joux and Pierrot ["Nearly sparse linear algebra and application to discrete logarithms computation," preprint Contemporary Developments in Finite Fields and Applications, 2016.] is considered in case 2 and the client-server model along with the paralleled version of wiedemann for case 3. algorithms for all the three cases of solving are designed, analysed, experimented, and tested under the conditions based on density and size of matrices. The experiments are carried out on the matrices obtained from filtering step of FFS. The results are analysed and reported. From the results, it is shown that the communication cost between master and the slaves is to be considered and minimum density in the matrix is to be maintained in the previous step of linear algebra of FFS, i.e. filtering step to avoid trivial solutions
Solving large-scale sparse linear systems over GF(2) plays a key role in fluid mechanics, simulation and design of materials, petroleum seismic data processing, numerical weather prediction, computational electromagne...
详细信息
Solving large-scale sparse linear systems over GF(2) plays a key role in fluid mechanics, simulation and design of materials, petroleum seismic data processing, numerical weather prediction, computational electromagnetics, and numerical simulation of unclear explosions. Therefore, developing algorithms for this issue is a significant research topic. In this paper, we proposed a hyper-scale custom supercomputer architecture that matches specific data features to process the key procedure of block wiedemann algorithm and its parallel algorithm on the custom machine. To increase the computation, communication, and storage performance, four optimization strategies are proposed. This paper builds a performance model to evaluate the execution performance and power consumption for our custom machine. The model shows that the optimization strategies result in a considerable speedup, even three times faster than the fastest supercomputer, TH2, while consuming less power.
The main idea of the "black box"approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired resul...
详细信息
The main idea of the "black box"approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired result. Here good preconditioners will be used to ensure geometrical/algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We present new conditioners, including conditioners to preserve low displacement rank for Toeplitz-like matrices. We also provide new analyses of preconditioner performance and results on the relations among preconditioning problems and with linear algebra problems. Thus, improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields. (C) 2002 Elsevier Science Inc. All rights reserved.
Given a zero-dimensional ideal I subset of K([x(1), ..., x(n)] of degree D, the transformation of the ordering of its Grobner basis from DRL to LEX is a key step in polynomial system solving and turns out to be the bo...
详细信息
Given a zero-dimensional ideal I subset of K([x(1), ..., x(n)] of degree D, the transformation of the ordering of its Grobner basis from DRL to LEX is a key step in polynomial system solving and turns out to be the bottleneck of the whole solving process. Thus it is of crucial importance to design efficient algorithms to perform the change of ordering. The main contributions of this paper are several efficient methods for the change of ordering which take advantage of the sparsity of multiplication matrices in the classical FGLM algorithm. Combining all these methods, we propose a deterministic top-level algorithm that automatically detects which method to use depending on the input. As a by-product, we have a fast implementation that is able to handle ideals of degree over 60000. Such an implementation outperforms the MAGMA and SINGULAR ones, as shown by our experiments. First for the shape position case, two methods are designed based on the wiedemann algorithm: the first is probabilistic and its complexity to complete the change of ordering is O (D(N-1 +n log(D)(2))), where N1 is the number of nonzero entries of a multiplication matrix;the other is deterministic and computes the LEX Grinner basis of via Chinese Remainder Theorem. Then for the general case, the designed method is characterized by the Berlekamp-Massey-Sakata algorithm from Coding Theory to handle the multidimensional linearly recurring relations. Complexity analyses of all proposed methods are also provided. Furthermore, for generic polynomial systems, we present an explicit formula for the estimation of the sparsity of one main multiplication matrix, and prove that its construction is free. With the asymptotic analysis of such sparsity, we are able to show that for generic systems the complexity above becomes O (root 6/n pi D2+n-1/n). (C) 2016 Elsevier Ltd. All rights reserved.
Kaltofen has proposed a new approach in Kaltofen (1992) for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determ...
详细信息
Kaltofen has proposed a new approach in Kaltofen (1992) for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determinant as the constant term of the characteristic polynomial. For matrices over an abstract ring, by the results of Baur and Strassen (1983), the determinant algorithm, actually a straight-line program, leads to an algorithm with the same complexity for computing the adjoint of a matrix. However, the latter adjoint algorithm is obtained by the reverse mode of automatic differentiation, and hence is in some way not "explicit". We present an alternative (still closely related) algorithm for obtaining the adjoint that can be implemented directly, without resorting to an automatic transformation. The algorithm is deduced partly by applying program differentiation techniques "by hand" to Kaltofen's method, and is completely described. As a subproblem, we study the differentiation of the computation of minimum polynomials of linearly generated sequences, and we use a lazy polynomial evaluation mechanism for reducing the cost of Strassen's avoidance of divisions in our case. (C) 2010 Elsevier Ltd. All rights reserved.
Let I subset of K[x(1), ... , x(n)] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Grobner bases of I is crucial in polynomial s...
详细信息
ISBN:
(纸本)9781450306751
Let I subset of K[x(1), ... , x(n)] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Grobner bases of I is crucial in polynomial system solving. Through the algorithm FGLM, this task is classically tackled by linear algebra operations in K[x(1), ... , x(n)]/I. With recent progress on Grobner bases computations, this step turns out to be the bottleneck of the whole solving process. Our contribution is an algorithm that takes advantage of the sparsity structure of multiplication matrices appearing during the change of ordering. This sparsity structure arises even when the input polynomial system defining I is dense. As a by-product, we obtain an implementation which is able to manipulate 0-dimensional ideals over a prime field of degree greater than 30000. It outperforms the Magma/Singular/FGb implementations of FGLM. First, we investigate the particular but important shape position case. The obtained algorithm performs the change of ordering within a complexity O(D(N-1 + n log(D))), where N-1 is the number of nonzero entries of a multiplication matrix. This almost matches the complexity of computing the minimal polynomial of one multiplication matrix. Then, we address the general case and give corresponding complexity results. Our algorithm is dynamic in the sense that it selects automatically which strategy to use depending on the input. Its key ingredients are the wiedemann algorithm to handle 1-dimensional linear recurrence (for the shape position case), and the Berlekamp-Massey-Sakata algorithm from Coding Theory to handle multi-dimensional linearly recurring sequences in the general case.
We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo powers of word-size...
详细信息
ISBN:
(纸本)9781581132182
We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo powers of word-size primes. Consequently, the algorithm does not suffer from coefficient growth. We have implemented several variants of this algorithm (Elimination and/or Black-Box techniques) since practical performance depends strongly on the memory available. Our method has proven useful in algebraic topology for the computation of the homology of some large simplicial complexes.
暂无评论