Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2014, Volume 54, Number 1, Page 170
DOI: https://doi.org/10.7868/S0044466914010189
(Mi zvmmf9983)
 

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
Full-text PDF (95 kB) Citations (2)
References:
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
English version:
Computational Mathematics and Mathematical Physics, 2014, Volume 54, Issue 1, Pages 177–190
DOI: https://doi.org/10.1134/S0965542514010163
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: English
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
Citation in format AMSBIB
\Bibitem{UllKha14}
\by E.~Ullah, S.~A.~Khan
\paper Computing border bases using mutant strategies
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2014
\vol 54
\issue 1
\pages 170
\mathnet{http://mi.mathnet.ru/zvmmf9983}
\crossref{https://doi.org/10.7868/S0044466914010189}
\elib{https://elibrary.ru/item.asp?id=20991874}
\transl
\jour Comput. Math. Math. Phys.
\yr 2014
\vol 54
\issue 1
\pages 177--190
\crossref{https://doi.org/10.1134/S0965542514010163}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000332109500015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84894614467}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf9983
  • https://www.mathnet.ru/eng/zvmmf/v54/i1/p170
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Statistics & downloads:
    Abstract page:178
    Full-text PDF :70
    References:53
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024