TU Darmstadt / ULB / TUbiblio

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

Mohamed, Wael Said Abd Elmageed and Ding, Jintai and Kleinjung, Thorsten and Bulygin, Stanislav and Buchmann, Johannes
Cid, Carlos and Faugere, Jean-Charles (eds.) (2010):
PWXL: A Parallel Wiedemann-XL Algorithm for Solving Polynomial Equations over GF(2).
In: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography (SCC 2010), [Conference or Workshop Item]

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.

Item Type: Conference or Workshop Item
Erschienen: 2010
Editors: Cid, Carlos and Faugere, Jean-Charles
Creators: Mohamed, Wael Said Abd Elmageed and Ding, Jintai and Kleinjung, Thorsten and Bulygin, Stanislav and Buchmann, Johannes
Title: PWXL: A Parallel Wiedemann-XL Algorithm for Solving Polynomial Equations over GF(2)
Language: ["languages_typename_1" not defined]
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.

Title of Book: Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography (SCC 2010)
Uncontrolled Keywords: Secure Data
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
LOEWE > LOEWE-Zentren
20 Department of Computer Science
LOEWE
Date Deposited: 30 Dec 2016 20:23
Identification Number: TUD-CS-2010-0116
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item