English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give a new algorithm for performing the distinct-degree factorization of apolynomial P(x) over GF(2), using a multi-level blocking strategy. The coarsestlevel of blocking replaces GCD computations by multiplications, as suggested byPollard (1975), von zur Gathen and Shoup (1992), and others. The novelty of ourapproach is that a finer level of blocking replaces multiplications bysquarings, which speeds up the computation in GF(2)[x]/P(x) of certain intervalpolynomials when P(x) is sparse. As an application we give a fast algorithm tosearch 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 fullsearch. Naive algorithms cost O(r^2) per trinomial, thus O(r^3) to search overall trinomials of given degree r. Under a plausible assumption about thedistribution of factors of trinomials, the new algorithm has complexity O(r^2(log r)^{3/2}(log log r)^{1/2}) for the search over all trinomials of degree r.Our implementation achieves a speedup of greater than a factor of 560 over thenaive algorithm in the case r = 24036583 (a Mersenne exponent). Using ourprogram, we have found two new primitive trinomials of degree 24036583 overGF(2) (the previous record degree was 6972593).

A Multi-level Blocking Distinct Degree Factorization Algorithm