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, Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons, A note on quadratic residuosity and UP, Cryptographic key assignment schemes for any access control policy, 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}$, A randomized sublinear time parallel GCD algorithm for the EREW PRAM, Computing pairings using $x$-coordinates only, Bisection for genus 2 curves in odd characteristic, 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, Prime simplicity, Equivalence problems for circuits over sets of natural numbers, Efficient algorithms for sparse cyclotomic integer zero testing, On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's, Safer parameters for the Chor-Rivest cryptosystem, 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, Small Chvátal rank, 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$, On Models of a Nondeterministic Computation, Efficient, Robust and Constant-Round Distributed RSA Key Generation, 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, A deterministic version of Pollard’s $p-1$ algorithm, On the Average Distribution of Power Residues and Primitive Elements in Inversive and Nonlinear Recurring Sequences, The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences, Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2