TU Darmstadt / ULB / TUbiblio

PWXL: A Parallel Wiedemann-XL Algorithm for Solving Polynomial Equations over GF(2)

Mohamed, Wael Said Abd Elmageed ; Ding, Jintai ; Kleinjung, Thorsten ; Bulygin, Stanislav ; Buchmann, Johannes
Hrsg.: Cid, Carlos ; Faugere, Jean-Charles (2010)
PWXL: A Parallel Wiedemann-XL Algorithm for Solving Polynomial Equations over GF(2).
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

The XL algorithm is an algorithm for solving systems of multivariate polynomial equations over finite fields. XL expands the initial system by multiplying it with monomials below a certain degree. XL then linearizes the expanded system and solves the linear system by Gaussian elimination. Since the linear systems that have to be solved are sparse, the Wiedemann algorithm can be applied to reduce the high time and space complexity of Gaussian elimination. The main contribution of this paper is to show how PWXL, a combination of XL and a parallel Wiedemann solver, further reduces the time and space cost. When using n processors, the running time is divided by n and the linear system is distributed over memory of the n processors without the need to store in one place at any time of the computation. By using PWXL, we are able to solve an HFE system of univariate degree 4352 with 34 equations in 34 variables in almost 13 days using 16 processors, which was never done before by any known algebraic solver.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2010
Herausgeber: Cid, Carlos ; Faugere, Jean-Charles
Autor(en): Mohamed, Wael Said Abd Elmageed ; Ding, Jintai ; Kleinjung, Thorsten ; Bulygin, Stanislav ; Buchmann, Johannes
Art des Eintrags: Bibliographie
Titel: PWXL: A Parallel Wiedemann-XL Algorithm for Solving Polynomial Equations over GF(2)
Sprache: Englisch
Publikationsjahr: Juni 2010
Buchtitel: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography (SCC 2010)
Kurzbeschreibung (Abstract):

The XL algorithm is an algorithm for solving systems of multivariate polynomial equations over finite fields. XL expands the initial system by multiplying it with monomials below a certain degree. XL then linearizes the expanded system and solves the linear system by Gaussian elimination. Since the linear systems that have to be solved are sparse, the Wiedemann algorithm can be applied to reduce the high time and space complexity of Gaussian elimination. The main contribution of this paper is to show how PWXL, a combination of XL and a parallel Wiedemann solver, further reduces the time and space cost. When using n processors, the running time is divided by n and the linear system is distributed over memory of the n processors without the need to store in one place at any time of the computation. By using PWXL, we are able to solve an HFE system of univariate degree 4352 with 34 equations in 34 variables in almost 13 days using 16 processors, which was never done before by any known algebraic solver.

Freie Schlagworte: Secure Data
ID-Nummer: TUD-CS-2010-0116
Fachbereich(e)/-gebiet(e): LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
LOEWE > LOEWE-Zentren
20 Fachbereich Informatik
LOEWE
Hinterlegungsdatum: 30 Dez 2016 20:23
Letzte Änderung: 17 Mai 2018 13:02
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen