NDLI: Deterministic root finding in finite fields

Please wait, while we are loading the content...

Deterministic root finding in finite fields

Content Provider	ACM Digital Library
Author	De Feo, Luca Quisquater, Michaël Petit, Christophe
Abstract	Finding roots of polynomials with coefficients in a finite field is a special instance of the polynomial factorization problem. The most well known algorithm for factoring and root-finding is the Cantor-Zassenhaus algorithm. It is a Las Vegas algorithm with running time polynomial in both the polynomial degree and the field size. Its running time is quasi-optimal for the special case of root-finding. No deterministic polynomial time algorithm for these problems is known in general, however several deterministic algorithms are known for special instances, most notably when the characteristic of the finite field is small. The goal of this poster is to review the best deterministic algorithms for root-finding, in a systematic way. We present, in a unified way, four algorithms: • Berlekamp's Trace Algorithm [2] (BTA), • Moenk's Subgroup Refinement Method [7] (SRM), • Menezes, van Oorschot and Vanstone's Affine Refinement Method [5, 10] (ARM), and • Petit's Successive Resultants Algorithm [8] (SRA). It is the first time that these algorithms are presented together in a comprehensive way, and that they are rigorously analysed, implemented and compared to each other. In doing so, we obtain several new results: • We significantly improve the complexity ARM, matching that of BTA and SRA. • We highlight a profound duality relationship between ARM and SRA. • We show how to combine ARM with SRM to obtain a new algorithm, which always performs better, and of which ARM and SRM are special instances. The new algorithm considerably extends the range of finite fields for which deterministic polynomial time root-finding is possible. • We present several practical and asymptotic improvements to special instances of the algorithms. Part of these results were submitted in response to the call for papers of ISSAC '15, but were rejected. This poster corrects some minor imperfections, improves the asymptotic complexities of some algorithms, and presents a new algorithm not previously known.
Starting Page	87
Ending Page	89
Page Count	3
File Format	PDF
ISSN	19322240
DOI	10.1145/2850449.2850457
Journal	ACM Communications in Computer Algebra (ACCA)
Volume Number	49
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-02-05
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Deterministic root finding over finite fields using Graeffe transforms

Character Sums and Deterministic Polynomial Root Finding in Finite Fields

Finding Isomorphisms Between Finite Fields

Polynomial root-finding via structured matrices

Some results on finite fields

Irreducibility and Deterministic r-th Root Finding over Finite Fields

On sparse interpolation over finite fields

Recovering zeroes of hyperelliptic curves over finite fields

Some new almost difference sets via finite fields

Deterministic root finding in finite fields

Similar Documents

Deterministic root finding over finite fields using Graeffe transforms

Character Sums and Deterministic Polynomial Root Finding in Finite Fields

Finding Isomorphisms Between Finite Fields

Polynomial root-finding via structured matrices

Some results on finite fields

Irreducibility and Deterministic r-th Root Finding over Finite Fields

On sparse interpolation over finite fields

Recovering zeroes of hyperelliptic curves over finite fields

Some new almost difference sets via finite fields

Deterministic root finding in finite fields