|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Multi-level Blocking Distinct Degree Factorization Algorithm | | Richard Brent
; Paul Zimmermann
; | | Date: |
24 Oct 2007 | | Abstract: | We give a new algorithm for performing the distinct-degree factorization of a
polynomial $P(x)$ over $GF(2)$, using a multi-level blocking strategy. The
coarsest level of blocking replaces GCD computations by multiplications, as
suggested by Pollard (1975), von zur Gathen and Shoup (1992), and others. The
novelty of our approach is that a finer level of blocking replaces
multiplications by squarings, which speeds up the computation in
$GF(2)[x]/P(x)$ of certain emph{interval polynomials} when $P(x)$ is sparse.
As an application we give a fast algorithm to search for all irreducible
trinomials $x^r + x^s + 1$ of degree $r$ over $GF(2)$, while producing a
certificate that can be checked in less time than the full search. Naive
algorithms cost $O(r^2)$ per trinomial, thus $O(r^3)$ to search over all
trinomials of given degree $r$. Under a plausible assumption about the
distribution of factors of trinomials, the new algorithm has complexity $O(r^2
(log r)^{3/2}(loglog r)^{1/2})$ for the search over all trinomials of degree
$r$. Our implementation achieves a speedup of greater than a factor % PZ:
changed ’’classical’’ into ’’naive’’ (also elsewhere - RPB) of 560 over the
naive algorithm in the case $r = 24036583$ (a Mersenne exponent). Using our
program, we have found two new primitive trinomials of degree 24036583 over
$GF(2)$ (the previous record degree was 6972593). | | Source: | arXiv, 0710.4410 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER