Uni Passau

OPUS - Passau

Bibliographische Daten und PDF-Volltexte aus der Universität Passau
... die Wissenschaft der Hochschule sichtbar machen!

Home Suchen Melden Veröffentlichen Hilfe Kontakt
OPUS-Frontdoor

Ullah, Ehsan

New Techniques for Polynomial System Solving


Open Access: Freier Zugang zum Volltext!

pdf-Format:
Dokument 1.pdf (1.796 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Polynomlösung , Algebra , Lineare Algebra , Algorithmus
Freie Schlagwörter (Englisch): polynomial system solving , techniques , linear algebra , border bases , mutant strategies
Beteiligte Einrichtung: Sonstiger Autor der Fakultät für Informatik und Mathematik
Fakultät: Fakultät für Informatik und Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Kreuzer, Martin (Prof.Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 17.07.2012
Erstellungsjahr: 2012
Publikationsdatum: 25.07.2012
Kurzfassung auf Englisch: Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gröbner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm.

We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques.
Lizenz: Lizenz-Logo  Veröffentlichungsvertrag für Publikationen ohne Print on Demand


Lizenz

URN: http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26815
URL dieser Seite: http://www.opus-bayern.de/uni-passau/volltexte/2012/2681/


Home Suchen Melden Veröffentlichen Hilfe Kontakt
  OpenAccess logo   OAI2.0 logo   © Universitätsbibliothek Passau · Innstrasse 29 · 94032 Passau 
Tel. (0851) 509 1645 · Fax (0851) 509 1602 ·  Mail opus@uni-passau.de
22.10.10