###
**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), pp. 89-100, [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 |

Send an inquiry |

#### Options (only for editors)

View Item |