scientific article; zbMATH DE number 918133

Publication date: 19 August 1996

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Polynomials over finite fields (11T06) Algebraic number theory computations (11Y40) Software, source code, etc. for problems pertaining to number theory (11-04) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Primes (11A41) Factorization (11Y05) Primality (11Y11) Computational number theory (11Yxx)

Related Items

COMPUTING THE DIMENSION OF IDEALS IN GROUP ALGEBRAS, WITH AN APPLICATION TO CODING THEORY ⋮ Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝 ⋮ The State Complexity of Lexicographically Smallest Words and Computing Successors ⋮ Cocks IBE Scheme ⋮ Two compact incremental prime sieves ⋮ Asymptotic existence results for primitive completely normal elements in extensions of Galois fields ⋮ A Conjecture on Primes in Arithmetic Progressions and Geometric Intervals ⋮ Unnamed Item ⋮ LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD ⋮ On the number of distinct functional graphs of affine-linear transformations over finite fields ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ Small Chvátal rank ⋮ Average $r$-rank Artin conjecture ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ New algorithms for generating Conway polynomials over finite fields ⋮ Determining the $2$-Sylow subgroup of an elliptic curve over a finite field ⋮ Dirichlet’s proof of the three-square theorem: An algorithmic perspective ⋮ DENSITY AND DISTRIBUTION OF PRIMES ⋮ On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping ⋮ Fast algorithms for solving equations of degree $\le 4$ in some finite fields ⋮ Unnamed Item ⋮ Counting with Probabilistic and Ultrametric Finite Automata ⋮ Computing Primitively-Rooted Squares and Runs in Partial Words ⋮ Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations ⋮ On the Order of Power Series and the Sum of Square Roots Problem ⋮ Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm ⋮ On module unique-SVP and NTRU ⋮ Computers as a novel mathematical reality. III: Mersenne numbers and sums of divisors ⋮ A DYNAMICAL SYSTEM PROOF OF NIVEN’S THEOREM AND ITS EXTENSIONS ⋮ On the Solution of the Equation $n = ak + bp_k$ by Means of an Iterative Method ⋮ Counting roots for polynomials modulo prime powers ⋮ Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages ⋮ As easy as $\mathbb {Q}$: Hilbert’s Tenth Problem for subrings of the rationals and number fields ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Exponentially Long Orbits in Hopfield Neural Networks ⋮ NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA ⋮ On Faster Integer Calculations Using Non-arithmetic Primitives ⋮ Coordination Problems in Ad Hoc Radio Networks ⋮ Authentic Quantum Nonces ⋮ Faster Polynomial Multiplication via Discrete Fourier Transforms ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ Explicit Burgess bound for composite moduli ⋮ $(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 ⋮ On the primality of $n! \pm 1$ and $2 \times 3 \times 5 \times \dotsm \times p \pm 1$ ⋮ Detecting perfect powers in essentially linear time ⋮ Three‐Phase Barker Arrays ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ An O(M(n) logn) Algorithm for the Jacobi Symbol ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ On the Average Distribution of Power Residues and Primitive Elements in Inversive and Nonlinear Recurring Sequences ⋮ Computing the $\ell $-power torsion of an elliptic curve over a finite field ⋮ Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know? ⋮ The Sheldon Conjecture ⋮ STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET ⋮ Unary coded PSPACE-complete languages in $\mathrm{ASPACE}(\log\log n)$ ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ On Models of a Nondeterministic Computation ⋮ The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences ⋮ Stabilizer states and Clifford operations for systems of arbitrary dimensions and modular arithmetic ⋮ Randomized polynomial-time root counting in prime power rings ⋮ Efficient, Robust and Constant-Round Distributed RSA Key Generation ⋮ Tabulation of cubic function fields via polynomial binary cubic forms ⋮ Unnamed Item ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ Taking roots over high extensions of finite fields ⋮ New integer representations as the sum of three cubes ⋮ Unnamed Item ⋮ Computation of Fermat’s pseudoprimes (Dedicated to the Memory of Professor Leetsch C. Hsu) ⋮ Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2 ⋮ Constructing Carmichael numbers through improved subset-product algorithms ⋮ Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields ⋮ Isomorphism between circulants and Cartesian products of cycles ⋮ Sparse univariate polynomials with many roots over finite fields ⋮ Shortest division chains in unique factorization domains ⋮ Hypergeometric groups and dynamics on $K3$ surfaces ⋮ Factoring multi-power RSA moduli with primes sharing least or most significant bits ⋮ Decision procedures for flat array properties ⋮ Lower bounds for the maximum of the Riemann zeta function along vertical lines ⋮ 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 ⋮ DP lower bounds for equivalence-checking and model-checking of one-counter automata ⋮ Multi-dimensional Kronecker sequences with a small number of gap lengths ⋮ The computational complexity of calculating partition functions of optimal medians with Hamming distance ⋮ A linear-time algorithm for the orbit problem over cyclic groups ⋮ A reduction of semigroup DLP to classic DLP ⋮ Fast generation of prime numbers and secure public-key cryptographic parameters. ⋮ Partition bijections, a survey ⋮ Factoring RSA moduli with primes sharing bits in the middle ⋮ Safer parameters for the Chor-Rivest cryptosystem ⋮ Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring ⋮ Root repulsion and faster solving for very sparse polynomials over $p$-adic fields ⋮ Lower bounds on words separation: are there short identities in transformation semigroups? ⋮ The query complexity of order-finding ⋮ Computing zeta functions of large polynomial systems over finite fields ⋮ Univariate polynomial factorization over finite fields ⋮ String cadences ⋮ Computing primitively-rooted squares and runs in partial words ⋮ Property testing for cyclic groups and beyond ⋮ Algorithmic complexity of proper labeling problems ⋮ Estimation of a finite population mean under random nonresponse using kernel weights ⋮ Optimal constraints aggregation method for ILP ⋮ Holographic algorithms: from art to science ⋮ Halving for the 2-Sylow subgroup of genus 2 curves over binary fields ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Faster $p$-adic feasibility for certain multivariate sparse polynomials ⋮ On the number of $N$-free elements with prescribed trace ⋮ Primality test for numbers $M$ with a large power of 5 dividing $M^{4}-1$. ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Unambiguous finite automata over a unary alphabet ⋮ On primitivity of sets of matrices ⋮ Free $W^*$-dynamical systems from $p$-adic number fields and the Euler totient function ⋮ Fast equality test for straight-line compressed strings ⋮ Amount of nonconstructivity in deterministic finite automata ⋮ On the tightness of forward-secure signature reductions ⋮ Binary trees as a computational framework ⋮ On the iteration of certain quadratic maps over GF($p$). ⋮ On Euler products with smaller than one exponents ⋮ Good reduction of Puiseux series and applications ⋮ Finite primitive permutation groups and regular cycles of their elements. ⋮ Secure sealed-bid online auctions using discreet cryptographic proofs ⋮ Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series ⋮ On the density of normal bases in finite fields ⋮ Circulant graphs and GCD and LCM of subsets ⋮ Factoring polynomials over global fields. I ⋮ Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers ⋮ Rational curves over generalized complex numbers ⋮ The Kronecker-Vahlen theorem fails in real quadratic norm-Euclidean fields ⋮ On pseudorandomness in families of sequences derived from the Legendre symbol ⋮ Threshold data structures and coding theory ⋮ The complexity of synchronizing Markov decision processes ⋮ Fixed argument pairing inversion on elliptic curves ⋮ Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces ⋮ Trace formulae for irreducible polynomials over $\mathbb F_P$ with minimal order roots in $\mathbb F_{P^q}$ ⋮ On the security of RSA with primes sharing least-significant bits ⋮ Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem ⋮ 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 ⋮ What are the longest ropes on the unit sphere? ⋮ New number-theoretic cryptographic primitives ⋮ A randomized sublinear time parallel GCD algorithm for the EREW PRAM ⋮ Identity testing and interpolation from high powers of polynomials of large degree over finite fields ⋮ Fast matrix decomposition in $\mathbb F_2$ ⋮ Counting walks with large steps in an orthant ⋮ Subquadratic-time algorithms for normal bases ⋮ Computing pairings using $x$-coordinates only ⋮ An application of free probability to arithmetic functions ⋮ Computing Hermite and Smith normal forms of triangular integer matrices ⋮ Bisection and squares in genus 2 ⋮ Determinisability of unary weighted automata over the rational numbers ⋮ Arithmeticity and hidden symmetries of fully augmented pretzel link complements ⋮ Bisection for genus 2 curves in odd characteristic ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Transcendence of formal power series with rational coefficients ⋮ On the index of the Diffie-Hellman mapping ⋮ Computing the cycles in the perfect shuffle permutation ⋮ Some connections between discrepancy, finite gap properties, and pair correlations ⋮ Computational strategies for the Riemann zeta function ⋮ Random self-reducibility of ideal-SVP via Arakelov random walks ⋮ Squares and primitivity in partial words ⋮ Hardness of approximation for knapsack problems ⋮ Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number ⋮ The Rabin cryptosystem revisited ⋮ Short vectors of planar lattices via continued fractions ⋮ Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients ⋮ Systems of rank one, explicit Rokhlin towers, and covering numbers ⋮ Cryptanalysis of RSA with a small parameter revisited ⋮ Mosaics of combinatorial designs for information-theoretic security ⋮ Approximate congruence in nearly linear time