Every Prime Has a Succinct Certificate
From MaRDI portal
Publication:4077450
DOI10.1137/0204018zbMath0316.68031OpenAlexW2045664183MaRDI QIDQ4077450
Publication date: 1975
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/533ba306dbd8e4f483372d177d898ef4963c9a02
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Primality (11Y11)
Related Items
Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, On the complexity of the parity argument and other inefficient proofs of existence, Certifying Irreducibility in $${\mathbb Z}[x$$], Locating \(P\)/poly optimally in the extended low hierarchy, On hardness of one-way functions, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, Fast generation of prime numbers and secure public-key cryptographic parameters., The complexity of mean payoff games on graphs, Minimum disclosure proofs of knowledge, Dominoes and the complexity of subclasses of logical theories, The generation of random numbers that are probably prime, The complexity of computing the permanent, Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Prime chains and Pratt trees, Fast verification, testing, and generation of large primes, A bi-directional extensible interface between Lean and Mathematica, The complexity of mean payoff games, Some consequences of cryptographical conjectures for S 2 1 and EF, Certifying giant nonprimes, On the complexity of computational problems associated with simple stochastic games, Discrete extremal problems, Poisson-Dirichlet branching random walks, Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?, Recent developments in primality testing, Some observations on the probabilistic algorithms and NP-hard problems, The influence of computers in the development of number theory, Knottedness is in NP, modulo GRH, Two remarks on iterates of Euler's totient function, An appraisal of computational complexity for operations researchers, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, Classroom Notes, Classroom Notes, Classroom Notes, Aristotle, Boole, and Categories, Elliptic Curves and Primality Proving, Self-witnessing polynomial-time complexity and prime factorization, The Lucas-Pratt primality tree, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Riemann's hypothesis and tests for primality, Complexity of some problems in Petri nets, NP-complete decision problems for binary quadratics, The computational complexity of recognizing permutation functions, Construction of logarithm tables for Galois Fields, Pairing inversion for finding discrete logarithms, Efficient search for rationals, On hiding information from an oracle, Computational complexity, Newton polytopes, and Schubert polynomials, P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP, Prime-number algorithm for public-key systems, The relative complexity of NP search problems, $$P\mathop{ =}\limits^{?}NP$$, DEHN FUNCTION AND LENGTH OF PROOFS, A Proposal for Broad Spectrum Proof Certificates, Non-standard finite fields over \(I\Delta_0+\Omega_1\), Complexity questions in number theory, On values taken by the largest prime factor of shifted primes, Optimal information retrieval when queries are not random, New NP-hard and NP-complete polynomial and integer divisibility problems, On total functions, existence theorems and computational complexity
