A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Victor Shoup

doi:10.1145/120694.120697

A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Victor Shoup

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is "almost" quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic.

Original language	English (US)
Title of host publication	ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation
Editors	Stephen M. Watt
Publisher	Association for Computing Machinery
Pages	14-21
Number of pages	8
ISBN (Print)	0897914376, 9780897914376
DOIs	https://doi.org/10.1145/120694.120697
State	Published - Jun 1 1991
Event	1991 International Symposium on Symbolic and Algebraic Computation, ISSAC 1991 - Bonn, Germany Duration: Jul 15 1991 → Jul 17 1991

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other	1991 International Symposium on Symbolic and Algebraic Computation, ISSAC 1991
Country/Territory	Germany
City	Bonn
Period	7/15/91 → 7/17/91

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1145/120694.120697

Cite this

Shoup, V. (1991). A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In S. M. Watt (Ed.), ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (pp. 14-21). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/120694.120697

A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. / Shoup, Victor.
ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. ed. / Stephen M. Watt. Association for Computing Machinery, 1991. p. 14-21 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Shoup, V 1991, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. in SM Watt (ed.), ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, Association for Computing Machinery, pp. 14-21, 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC 1991, Bonn, Germany, 7/15/91. https://doi.org/10.1145/120694.120697

Shoup V. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In Watt SM, editor, ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. 1991. p. 14-21. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/120694.120697

Shoup, Victor. / A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. editor / Stephen M. Watt. Association for Computing Machinery, 1991. pp. 14-21 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

@inproceedings{92a9a5e3de234f35b1a3f735b6fb93a4,

title = "A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic",

abstract = "We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is {"}almost{"} quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic.",

author = "Victor Shoup",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC 1991 ; Conference date: 15-07-1991 Through 17-07-1991",

year = "1991",

month = jun,

day = "1",

doi = "10.1145/120694.120697",

language = "English (US)",

isbn = "0897914376",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery",

pages = "14--21",

editor = "Watt, {Stephen M.}",

booktitle = "ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation",

}

TY - GEN

T1 - A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

AU - Shoup, Victor

PY - 1991/6/1

Y1 - 1991/6/1

N2 - We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is "almost" quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic.

AB - We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is "almost" quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic.

UR - http://www.scopus.com/inward/record.url?scp=84971235488&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84971235488&partnerID=8YFLogxK

U2 - 10.1145/120694.120697

DO - 10.1145/120694.120697

M3 - Conference contribution

AN - SCOPUS:84971235488

SN - 0897914376

SN - 9780897914376

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 14

EP - 21

BT - ISSAC 1991 - Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation

A2 - Watt, Stephen M.

PB - Association for Computing Machinery

T2 - 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC 1991

Y2 - 15 July 1991 through 17 July 1991

ER -

A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this