






















We estimate the number $|\mathcal{A}_{\boldsymbolλ}|$ of elements on a nonlinear family $\mathcal{A}$ of monic polynomials of $\mathbb{F}_q[T]$ of degree $r$ having factorization pattern $\boldsymbolλ:=1^{λ_1}2^{λ_2}\cdots r^{λ_r}$. We show that $|\mathcal{A}_{\boldsymbolλ}|= \mathcal{T}(\boldsymbolλ)\,q^{r-m}+\mathcal{O}(q^{r-m-{1}/{2}})$, where $\mathcal{T}(\boldsymbolλ)$ is the proportion of elements of the symmetric group of $r$ elements with cycle pattern $\boldsymbolλ$ and $m$ is the codimension of $\mathcal{A}$. We provide explicit upper bounds for the constants underlying the $\mathcal{O}$--notation in terms of $\boldsymbolλ$ and $\mathcal{A}$ with "good" behavior. We also apply these results to analyze the average--case complexity of the classical factorization algorithm restricted to $\mathcal{A}$, showing that it behaves as good as in the general case.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。