HAL - INRIA :: [inria-00188261, version 4] Faster Multiplication in GF(2)[x]

inria-00188261, version 4

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec acte</head>
<biblStruct type="inproceedings" xml:id="inria-00188261"><analytic>
<author><persName><forename>Richard</forename><surname>Brent</surname></persName>
<affiliation>
<orgName type="team">Mathematical Sciences Institute</orgName>
<country>AU</country>
<orgName type="institution">Mathematical Sciences Institute</orgName>
</affiliation>
</author>
<author><persName><forename>Pierrick</forename><surname>Gaudry</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs)</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Emmanuel</forename><surname>Thomé</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs)</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Paul</forename><surname>Zimmermann</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs)</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<title type="main" level="a">Faster Multiplication in GF(2)[x]</title></analytic><monogr><meeting>ANTS-VIII</meeting><imprint><publisher>Springer-Verlag</publisher><pubPlace><settlement>Banff</settlement><country>Canada</country></pubPlace><biblScope type="publicationDate">2008</biblScope><biblScope type="vol">5011</biblScope><biblScope type="pp">153-166</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-540-79456-1</idno><idno type="HALid">http://hal.inria.fr/inria-00188261/en/</idno><idno type="HALFile">http://hal.inria.fr/inria-00188261/PDF/gf2x.pdf</idno></biblStruct>
</listBibl>
</listBibl>

Faster Multiplication in GF(2)[x]

Richard Brent^a^, 1, Pierrick Gaudry (

) ², Emmanuel Thomé (

) ², Paul Zimmermann (

) ²

(2008)

Accès au texte intégral
PDF

ANTS-VIII 5011 (2008) 153-166

Lien vers texte intégral chez l'éditeur

Résumé : In this paper, we discuss an implementation of various algorithms for multiplying polynomials in GF(2)[x]: variants of the window methods, Karatsuba's, Toom-Cook's, Schoenhage's and Cantor's algorithms. For most of them, we propose improvements that lead to practical speedups.

a –	Australian National University
1 :	Mathematical Sciences Institute
	Mathematical Sciences Institute
2 :	CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs) (INRIA Lorraine - LORIA)
	CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

Domaine

Informatique/Algorithme et structure de données

DOI : 10.1007/978-3-540-79456-1

Versions disponibles :


inria-00188261, version 4
http://hal.inria.fr/inria-00188261/fr/
oai:hal.inria.fr:inria-00188261_v4
Contributeur : Pierrick Gaudry <>
Soumis le : Vendredi 7 Novembre 2008, 08:33:25
Dernière modification le : Jeudi 13 Novembre 2008, 21:49:38