Loading...
Please wait, while we are loading the content...
Similar Documents
Factoring polynomials and the knapsack problem.
| Content Provider | CiteSeerX |
|---|---|
| Author | Hoeij, Mark Van |
| Abstract | Although a polynomial time algorithm exists, the most commonly used algorithm for factoring a univariate polynomial f with integer coefficients is the Berlekamp-Zassenhaus algorithm which has a complexity that depends exponentially on n where n is the number of modular factors of f . This exponential time complexity is due to a combinatorial problem; the problem of choosing the right subset of these n factors. In this paper we reduce this combinatorial problem to a knapsack problem of a kind that can be solved with polynomial time algorithms such LLL or PSLQ. The result is a practical algorithm that can factor large polynomials even when n is large as well. 1 Introduction Let f be a polynomial of degree N with integer coefficients, f = N X i=0 a i x i where a i 2 ZZ. Assume that f is monic (i.e. aN = 1) and that f is square-free (no multiple roots), so the gcd of f and f 0 equals 1. Let p be a prime number and let F p = ZZ=(p) be the field with p elements. Let ZZ p ... |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Knapsack Problem Integer Coefficient Combinatorial Problem Prime Number Univariate Polynomial Polynomial Time Algorithm Exists Multiple Root Polynomial Time Algorithm Lll Berlekamp-zassenhaus Algorithm Exponential Time Complexity Practical Algorithm Introduction Let Right Subset Large Polynomial Modular Factor |
| Content Type | Text |
| Resource Type | Article |
