Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q7243047> ?p ?o }
Showing triples 1 to 40 of
40
with 100 triples per page.
- Q7243047 subject Q7012332.
- Q7243047 abstract "In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. By "succinct", we usually mean that we wish for the proof to be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits).Primality certificates lead directly to proofs that problems such as primality testing and the complement of integer factorization lie in NP, the class of problems verifiable in polynomial time given a solution. These problems already trivially lie in co-NP. This was the first strong evidence that these problems are not NP-complete, since if they were it would imply NP = co-NP, a result widely believed to be false; in fact, this was the first demonstration of a problem in NP intersect co-NP not known (at the time) to be in P.Producing certificates for the complement problem, to establish that a number is composite, is straightforward; it suffices to give a nontrivial divisor. Standard probabilistic primality tests such as the Baillie-PSW primality test, the Fermat primality test, and the Miller-Rabin primality test also produce compositeness certificates in the event where the input is composite, but do not produce certificates for prime inputs.".
- Q7243047 wikiPageExternalLink Atkin-Goldwasser-Kilian-MorainCertificate.html.
- Q7243047 wikiPageExternalLink PrattCertificate.html.
- Q7243047 wikiPageExternalLink PrimalityCertificate.html.
- Q7243047 wikiPageExternalLink ppp.pdf.
- Q7243047 wikiPageExternalLink ppp.html.
- Q7243047 wikiPageExternalLink pratt.pdf.
- Q7243047 wikiPageWikiLink Q104752.
- Q7243047 wikiPageWikiLink Q11609.
- Q7243047 wikiPageWikiLink Q130762.
- Q7243047 wikiPageWikiLink Q1375963.
- Q7243047 wikiPageWikiLink Q1384912.
- Q7243047 wikiPageWikiLink Q1568194.
- Q7243047 wikiPageWikiLink Q181551.
- Q7243047 wikiPageWikiLink Q188295.
- Q7243047 wikiPageWikiLink Q1938391.
- Q7243047 wikiPageWikiLink Q207264.
- Q7243047 wikiPageWikiLink Q21198.
- Q7243047 wikiPageWikiLink Q215206.
- Q7243047 wikiPageWikiLink Q268493.
- Q7243047 wikiPageWikiLink Q269878.
- Q7243047 wikiPageWikiLink Q278986.
- Q7243047 wikiPageWikiLink Q294284.
- Q7243047 wikiPageWikiLink Q395.
- Q7243047 wikiPageWikiLink Q4249733.
- Q7243047 wikiPageWikiLink Q4846249.
- Q7243047 wikiPageWikiLink Q4848469.
- Q7243047 wikiPageWikiLink Q5365795.
- Q7243047 wikiPageWikiLink Q628036.
- Q7243047 wikiPageWikiLink Q7012332.
- Q7243047 wikiPageWikiLink Q737492.
- Q7243047 wikiPageWikiLink Q7917308.
- Q7243047 wikiPageWikiLink Q829546.
- Q7243047 wikiPageWikiLink Q864127.
- Q7243047 wikiPageWikiLink Q8789.
- Q7243047 wikiPageWikiLink Q955748.
- Q7243047 wikiPageWikiLink Q980224.
- Q7243047 comment "In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test.".
- Q7243047 label "Primality certificate".