An analytic approach to smooth polynomials over finite fields

DOI10.1007/BFB0054865MaRDI QIDQ3840165zbMATH OpenFDO

Authors Daniel Panario, X. Gourdon, Philippe Flajolet

Publication date 7 March 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054865

zbMATH Keywords

Dickman functionsdistribution of largest degreesfactors of a random polynomialJFM 56.0178.04

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Factorization (11Y05)

Review text

The Dickman function [\textit{K. Dickman}, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv Mat. Astr. Fys. 22, 1-14 (1930; JFM 50.0178.04)] describes the distribution of the largest prime divisor of a random integer. In the paper under review the authors use a variant of the Dickman function to investigate the distribution of the largest degree among the distinct irreducible factors of a random polynomial of fixed degree over a finite field. The same techniques are then used to study the joint distribution of the two largest degrees among the distinct factors. Knowledge of this distribution is useful in fine tuning the halting condition in various polynomial factorization algorithms. For the entire collection see [Zbl 0891.00022].

Recommendations

• On random polynomials over finite fields
• Degree distribution of the greatest common divisor of polynomials over 𝔽_q
• On the largest degree of an irreducible factor of a polynomial in \(\mathbb{F}_q[X]\)
• Polynomials over finite fields free from large and small degree irreducible factors

Cited in

(12)

• Birthday type attacks to the Naccache-Stern knapsack cryptosystem
• Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields
• On the enumeration of polynomials with prescribed factorization pattern
• Faster initial splitting for small characteristic composite extension degree fields
• Smoothness testing of polynomials over finite fields
• (EC)DSA lattice attacks based on Coppersmith's method
• The Function Field Sieve in the Medium Prime Case
• Smooth ideals in hyperelliptic function fields
• Square-free smooth polynomials in residue classes and generators of irreducible polynomials
• On the complexity formulae of the number field sieve and its variants
• Smooth polynomials with several prescribed coefficients
• Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity

This page was built for publication: An analytic approach to smooth polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840165)