| rdfs:comment
| - W teorii liczb, certyfikat pierwszości albo dowód pierwszości to zwięzły formalny dowód, że dana liczba jest pierwsza, który można szybko zweryfikować – w przeciwieństwie do czasochłonnego przeprowadzenia testu pierwszości. Istnienie certyfikatów pierwszości dowiodło, że problem znajdowania liczb pierwszych leży w klasie NP: problemów których rozwiązania można sprawdzić w czasie wielomianowym. (pl)
- En matemáticas y ciencias de la computación, un certificado de primalidad, prueba de primalidad o certeza de primalidad es una prueba formal y sucinta de que un número es primo. Los certificados de primalidad permiten verificar rápidamente la primalidad de un número sin tener que ejecutar un test de primalidad costoso o poco fiable. "Sucinta" generalmente significa que la prueba debe ser como máximo polinómica, con una cantidad de dígitos no desmesuradamente mayor que número en sí (por ejemplo, si el número tiene b bits, la prueba puede contener aproximadamente b2 bits). (es)
- 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. "Succinct" usually means that the proof should 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). (en)
- Na Ciência da Computação e na Matemática, o certificado de primalidade ou a prova de primalidade é uma prova sucinta e formal de que um número é primo. Certificados de primalidade permitem de maneira rápida checar a a primalidade de um número, sem ter que rodar um custoso e de difícil compreensão teste de primalidade. Por "sucinta" se quer referir ao que desejamos: que a prova seja no máximo polinomialmente maior que o número de dígitos do próprio número (por exemplo, se um número tem b bits, então a prova deve conter cerca de b2 bits). (pt)
- В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты. В теории сложности вычислений, как правило, подразумевается, что размер сертификата, как и время, необходимое для его проверки, полиномиально зависит от длины записи числа, то есть, от количества цифр в нём. (ru)
|
| has abstract
| - En matemáticas y ciencias de la computación, un certificado de primalidad, prueba de primalidad o certeza de primalidad es una prueba formal y sucinta de que un número es primo. Los certificados de primalidad permiten verificar rápidamente la primalidad de un número sin tener que ejecutar un test de primalidad costoso o poco fiable. "Sucinta" generalmente significa que la prueba debe ser como máximo polinómica, con una cantidad de dígitos no desmesuradamente mayor que número en sí (por ejemplo, si el número tiene b bits, la prueba puede contener aproximadamente b2 bits). Los certificados de primalidad conducen directamente a demostraciones de que problemas como los tests de primalidad y los complementos de factorización de enteros se encuentran en la categoría NP, la clase de problemas verificables en tiempo polinomial dada una solución. Estos problemas ya se encuentran trivialmente en la categoría co-NP. Esta fue la primera evidencia sólida de que estos problemas no son NP-completos, ya que si lo fueran, implicaría que NP es un subconjunto de co-NP, un resultado que se cree que es falso; de hecho, fue la primera demostración de un problema en NP intersección con co-NP que, en ese momento, no se sabía que estaba en P. Producir certificados para el problema del complemento, para establecer que un número es compuesto, es sencillo: basta con dar un divisor no trivial. Las pruebas estándar de primalidad probabilística como el test de primalidad Baillie-PSW, el test de primalidad de Fermat y el test de primalidad de Miller-Rabin también producen certificados de composición en el caso de que la entrada sea compuesta, pero no producen certificados para entradas primas. (es)
- 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. "Succinct" usually means that the proof should 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 that NP is subset of 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. (en)
- Na Ciência da Computação e na Matemática, o certificado de primalidade ou a prova de primalidade é uma prova sucinta e formal de que um número é primo. Certificados de primalidade permitem de maneira rápida checar a a primalidade de um número, sem ter que rodar um custoso e de difícil compreensão teste de primalidade. Por "sucinta" se quer referir ao que desejamos: que a prova seja no máximo polinomialmente maior que o número de dígitos do próprio número (por exemplo, se um número tem b bits, então a prova deve conter cerca de b2 bits). Certificados de primalidade conduzem diretamente a provas de que problemas como teste de primalidade e o complemento da fatoração de inteiros estarem na classe NP, a classe de problemas verificáveis em tempo polinomial dada uma determinada solução. Esses problemas já trivialmente estão em co-NP. Essa foi a primeira forte evidência para concluir que esses problemas não são NP-completos, pois se eles estivessem implicaria em NP = co-NP, um resultado que acredita-se ser falso. De fato, esta foi a primeira demonstração de um problema da classe NP que intersecta co-NP, não conhecida (até hoje), para a classe P. Produzir certificados para o problema do complemento, para estabelecer que um certo número é composto, é simples; se resume a dar um divisor não trivial. Padrões probabilísticos de testes de primalidade tais como e o teste de primalidade de Miller-Rabin também produzem certificados para os números compostos quando a entrada também é composta, mas não produz certificados para entradas quando estas são primos. (pt)
- W teorii liczb, certyfikat pierwszości albo dowód pierwszości to zwięzły formalny dowód, że dana liczba jest pierwsza, który można szybko zweryfikować – w przeciwieństwie do czasochłonnego przeprowadzenia testu pierwszości. Istnienie certyfikatów pierwszości dowiodło, że problem znajdowania liczb pierwszych leży w klasie NP: problemów których rozwiązania można sprawdzić w czasie wielomianowym. (pl)
- В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты. В теории сложности вычислений, как правило, подразумевается, что размер сертификата, как и время, необходимое для его проверки, полиномиально зависит от длины записи числа, то есть, от количества цифр в нём. Существование полиномиальных сертификатов простоты показывает, что такие задачи как проверка простоты и факторизация целых чисел принадлежат классу NP, так как по одному из эквивалентных определений данного класса это такие задачи, решение которых может быть проверено за полиномиальное время если будет дополнительно предоставлен сертификат. Кроме того, эти задачи лежат в классе co-NP, что следует из его определения как класса дополнений к задачам из NP — действительно, полиномиальным сертификатом того, что число является составным может быть любой его нетривиальный делитель. Таким образом, сертификаты простоты были одним из первых свидетельств того, что проверка простоты не является NP-полной задачей, так как если бы она была таковой, из этого бы следовало, что класс NP вложен в co-NP, что в свою очередь обычно[уточнить] считается[кем?] неверным. Кроме того, открытие полиномиальных сертификатов сделало проверку простоты первой задачей, про которую было известно, что она принадлежит как NP, так и co-NP, но про которую неизвестно, лежит ли она в классе P. С появлением теста Агравала — Каяла — Саксены в 2002 г., первого (и единственного на текущий момент[когда?]) детерминированного полиномиального теста простоты, было установлено, что задача всё же лежит в P. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)