|
This article is cited in 2 scientific papers (total in 2 papers)
Computing border bases using mutant strategies
E. Ullaha, S. A. Khanb a Fakultät für Informatik und Mathematik, Universität Passau, 94032 Passau, Germany
b Institute of Information Technology, Quaid-i-Azam University Islamabad, 45320 Pakistan
Abstract:
Border bases, a generalization of Gröbner bases, have actively been addressed during recent years due to their applicability to industrial problems. In cryptography and coding theory a useful application of border based is to solve zero-dimensional systems of polynomial equations over finite fields, which motivates us for developing optimizations of the algorithms that compute border bases. In 2006, Kehrein and Kreuzer formulated the Border Basis Algorithm (BBA), an algorithm which allows the computation of border bases that relate to a degree compatible term ordering. In 2007, J. Ding et al. introduced mutant strategies bases on finding special lower degree polynomials in the ideal. The mutant strategies aim to distinguish special lower degree polynomials (mutants) from the other polynomials and give them priority in the process of generating new polynomials in the ideal. In this paper we develop hybrid algorithms that use the ideas of J. Ding et al. involving the concept of mutants to optimize the Border Basis Algorithm for solving systems of polynomial equations over finite fields. In particular, we recall a version of the Border Basis Algorithm which is actually called the Improved Border Basis Algorithm and propose two hybrid algorithms, called MBBA and IMBBA. The new mutants variants provide us space efficiency as well as time efficiency. The efficiency of these newly developed hybrid algorithms is discussed using standard cryptographic examples.
Key words:
computing border basis, mutant strategy, order ideal, stable span.
Received: 14.01.2013 Revised: 06.04.2013
Citation:
E. Ullah, S. A. Khan, “Computing border bases using mutant strategies”, Zh. Vychisl. Mat. Mat. Fiz., 54:1 (2014), 170; Comput. Math. Math. Phys., 54:1 (2014), 177–190
Linking options:
https://www.mathnet.ru/eng/zvmmf9983 https://www.mathnet.ru/eng/zvmmf/v54/i1/p170
|
Statistics & downloads: |
Abstract page: | 159 | Full-text PDF : | 61 | References: | 42 |
|