Publication:4888749

Publication date: 19 August 1996

complexity; algorithms; roots; Jacobi symbol; probability theory; Hensel's lemma; greatest common divisors; elementary number theory; Legendre symbol; primality testing; analytic number theory; factoring of polynomials; algorithmic number theory; arithmetic of finite fields; arithmetic in residue class rings; number theoretical computations

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11Y16: Number-theoretic algorithms; complexity

11-02: Research exposition (monographs, survey articles) pertaining to number theory

11T06: Polynomials over finite fields

11Y40: Algebraic number theory computations

11-04: Software, source code, etc. for problems pertaining to number theory

11A05: Multiplicative structure; Euclidean algorithm; greatest common divisors

11A41: Primes

11Y05: Factorization

11Y11: Primality

11Yxx: Computational number theory

Related Items

Detecting perfect powers in essentially linear time, Determining the $2$-Sylow subgroup of an elliptic curve over a finite field, On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping, Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?, STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET, $(1+i)$-ary GCD computation in $\mathbb Z[i$ as an analogue to the binary GCD algorithm.], Factoring polynomials over special finite fields, Factoring polynomials over finite fields: A survey, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, The query complexity of order-finding, Partition bijections, a survey, Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring, Trace formulae for irreducible polynomials over $\mathbb F_P$ with minimal order roots in $\mathbb F_{P^q}$, Univariate polynomial factorization over finite fields, Transcendence of formal power series with rational coefficients, Primality test for numbers $M$ with a large power of 5 dividing $M^{4}-1$., The complexity of bisimilarity-checking for one-counter processes., On the iteration of certain quadratic maps over GF($p$)., Computing the cycles in the perfect shuffle permutation, Computational strategies for the Riemann zeta function, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Short vectors of planar lattices via continued fractions, On the security of RSA with primes sharing least-significant bits, Computing Hermite and Smith normal forms of triangular integer matrices, Approximate congruence in nearly linear time, DP lower bounds for equivalence-checking and model-checking of one-counter automata, Fast generation of prime numbers and secure public-key cryptographic parameters., On the density of normal bases in finite fields, Threshold data structures and coding theory, Factoring polynomials over global fields. I, Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers, On pseudorandomness in families of sequences derived from the Legendre symbol, Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem, New algorithms for generating Conway polynomials over finite fields, On the primality of $n! \pm 1$ and $2 \times 3 \times 5 \times \dotsm \times p \pm 1$, New integer representations as the sum of three cubes, Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA, On Faster Integer Calculations Using Non-arithmetic Primitives, On the Average Distribution of Power Residues and Primitive Elements in Inversive and Nonlinear Recurring Sequences, Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2