Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRoot optimization of polynomials in the number field sieve
194
0
0.0
(
0
)
Added by
Richard Brent
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.
rate research
Read More
We explore whether a root lattice may be similar to the lattice $mathscr O$ of integers of a number field $K$ endowed with the inner product $(x, y):={rm Trace}_{K/mathbb Q}(xcdottheta(y))$, where $theta$ is an involution of $K$. We classify all pairs $K$, $theta$ such that $mathscr O$ is similar to either an even root lattice or the root lattice $mathbb Z^{[K:mathbb Q]}$. We also classify all pairs $K$, $theta$ such that $mathscr O$ is a root lattice. In addition to this, we show that $mathscr O$ is never similar to a positive-definite even unimodular lattice of rank $leqslant 48$, in particular, $mathscr O$ is not similar to the Leech lattice. In appendix, we give a general cyclicity criterion for the primary components of the discriminant group of $mathscr O$.
Let $F(boldsymbol{x})$ be a diagonal integer-coefficient cubic form in $min{4,5,6}$ variables. Excluding rational lines if $m=4$, we bound the number of integral solutions $boldsymbol{x}in[-X,X]^m$ to $F(boldsymbol{x})=0$ by $O_{F,epsilon}(X^{3m/4 - 3/2 + epsilon})$, conditionally on an optimal large sieve inequality (in a specific range of parameters) for approximate Hasse-Weil $L$-functions of smooth hyperplane sections $F(boldsymbol{x})=boldsymbol{c}cdotboldsymbol{x}=0$ as $boldsymbol{c}inmathbb{Z}^m$ varies in natural boxes. When $m$ is even, these results were previously established conditionally under Hooleys Hypothesis HW. Our $ell^2$ large sieve approach requires that certain bad factors be roughly $1$ on average in $ell^2$, while the $ell^infty$ Hypothesis HW approach only required the bound in $ell^1$. Furthermore, the large sieve only accepts uniform vectors; yet our initially given vectors are only approximately uniform over $boldsymbol{c}$, due to variation in bad factors and in the archimedean component. Nonetheless, after some bookkeeping, partial summation, and Cauchy, the large sieve will still apply. In an appendix, we suggest a framework for non-diagonal cubics, up to Hessian issues.
We associate to every algebraic number field a hyperbolic surface lamination and an external fundamental group: the latter a generalization of the fundamental germ that necessarily contains external (not first order definable) elements. The external fundamental group of the rationals is a split extension of the absolute Galois group, that conjecturally contains a subgroup whose abelianization is isomorphic to the idele class group.
Most hypersurfaces in projective space are irreducible, and rather precise estimates are known for the probability that a random hypersurface over a finite field is reducible. This paper considers the parametrization of space curves by the appropriate Chow variety, and provides bounds on the probability that a random curve over a finite field is reducible.
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} are fixed. Our estimate holds without restrictions on the characteristic of Fq and asserts that V(d,s,bfs{a})=mu_d.q+mathcal{O}(1), where V(d,s,bfs{a}) is such an average cardinality, mu_d:=sum_{r=1}^d{(-1)^{r-1}}/{r!} and bfs{a}:=(a_{d-1},.., d_{d-s}). We provide an explicit upper bound for the constant underlying the mathcal{O}--notation in terms of d and s with good behavior. Our approach reduces the question to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. We show that the polynomials defining such complete intersections are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of the varieties under consideration, from which a suitable estimate on the number of Fq--rational points is established.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
