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 |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum