Polynôme unitaire | EPFL Graph Search

En algèbre commutative, un polynôme unitaire, ou polynôme monique, est un polynôme non nul dont le coefficient dominant (le coefficient du terme de plus haut degré) est égal à 1. Un polynôme P est donc unitaire si et seulement s'il s'écrit sous la forme P= 1.X^n+p_{n-1}X^{n-1}+\cdots +p_1X+p_0. Propriétés *Sur les polynômes unitaires à coefficients dans un anneau commutatif A donné, la relation divise est une relation d'ordre partiel. *Si A est un corps, alors tout polynôme non nul est associé à un polynôme unitaire et un seul. En revanche, dans \Z[X], le polynôme P = 2X – 3 n'est associé à aucun polynôme unitaire. Lien externe Catégorie:Polynôme

Four-Variable Expanders Over The Prime Fields

Van Thang Pham, Adrian Claudiu Valculescu

Let F-p be a prime field of order p > 2, and let A be a set in F-p with very small size in terms of p. In this note, we show that the number of distinct cubic distances determined by points in A x A satisfies vertical bar(A - A)(3) + (A - A)(3 vertical bar) >> vertical bar A vertical bar(8/7), which improves a result due to Yazici, Murphy, Rudnev, and Shkredov. In addition, we investigate some new families of expanders in four and five variables. We also give an explicit exponent of a problem of Bukh and Tsimerman, namely, we prove that max {vertical bar A + A vertical bar, vertical bar f( A, A)vertical bar} >> vertical bar A vertical bar(6/5), where f(x, y) is a quadratic polynomial in F-p[x, y] that is not of the form g(alpha x + beta y) for some univariate polynomial g.

AMER MATHEMATICAL SOC2018

Deciding properties of number fields without factoring

Mohammad Amin Shokrollahi

The polynomial time algorithm of Lenstra, Lenstra, and Lovász [15] for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the problem of factoring polynomials over algebraic number fields, which is used itself as a major subroutine for several other algorithms. Although a theoretical breakthrough, algorithms based on factorization of polynomials are notoriously slow and hard to implement, with running times ranging between

O(n^12)

and

O(n^18)

depending on which variant of the lattice basis reduction is used. Here, n is an upper bound for the maximum of the degrees and the bit-lengths of the coefficients of the polynomials involved. On the other hand, in many situations one does not need the full power of factorization, so one may ask whether there exist faster algorithms in these cases. In this paper we develop more efficient Monte Carlo algorithms to decide certain properties of roots of integer polynomials, without factoring them. Such problems arise, e.g., when solving systems of algebraic equations. Our methods applied to this situation give thus information about the solutions of such systems of equations. Assuming the validity of the Extended Riemann Hypothesis, our algorithms run in time

O(n^6+?)

in worst case, though they usually terminate much faster if the input polynomials do not have the properties the algorithm is testing. Besides this substantial improvement in the running time, our algorithms have the advantage of being conceptually easy. Their building blocks are gcd- computations in polynomial rings over finite fields, and primality tests for integers. However, despite the simplicity of our algorithms, their analysis is involved and uses tools from algebraic and analytic number theory. Our methods yield polynomial time algorithms even in cases where the factorization method does not. We exhibit such an example by showing that the language consisting of pairs

(g, m)

where

g

is a monic irreducible polynomial such that all its roots are integral linear combinations of mth roots of unity, is in co-RP. Currently, we do not know of any deterministic polynomial time algorithm to decide this problem, even if we assume the validity of the Extended Riemann Hypothesis. We will also show that computing the minimal m such that

(g, m)

belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer

1997

Deciding properties of number fields without factoring

Mohammad Amin Shokrollahi

O(n^12)

and

O(n^18)

O(n^6+?)

(g, m)

where

g

(g, m)

belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer

1997