Loading...
Please wait, while we are loading the content...
Similar Documents
Subquadratic-Time Factoring of Polynomials over Finite Fields (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kaltofen, Erich Shoup, Victor |
| Description | New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n 1:815 ). Previous algorithms required time \Theta(n 2+o(1) ). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field F q with q elements, the algorithms use O(n 1:815 log q) arithmetic operations in F q . The new "baby step/giant step" techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields. 1 Introduction In this paper, we present a new probabilistic approach for factoring univariate polynomials over finite fields. The resulting algorithms factor a polynomial of degree n over a finite field F q whose cardinality q is constant in time O(n 1:815 ). The best p... |
| File Format | |
| Journal | Math. Comp |
| Language | English |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Normal Base Time Theta Practical Algorithm Algorithm Factor Subquadratic-time Factoring Super-quadratic Asymptotic Running Time Finite Field New Algorithm Arithmetic Operation Constant Cardinality Previous Algorithm Algorithm Use New Probabilistic Approach Fast Matrix Multiplication Technique Univariate Polynomial Subquadratic-time Method New Probabilistic Algorithm |
| Content Type | Text |
| Resource Type | Article |
