A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

AttributesValues
type
label
  • Primtalstest
  • Teste de primalidade
  • Test de primalité
  • Primality test
  • Test de primalitat
  • اختبار أولية عدد ما
  • 素性测试
  • Test prvočíselnosti
  • Test pierwszości
  • Тест простоти
  • Test de primalidad
  • Primeca provo
  • 素数判定
  • Тест простоты
  • Priemgetaltest
  • Test di primalità
  • Zenbaki lehenen test
  • Primzahltest
comment
  • La qüestió de determinar si un nombre donat n és primer es coneix com el problema de la primalitat. Un test de primalitat, test de primeritat (o revisió de primalitat) és un algorisme que, donat un nombre d'entrada n, no aconsegueix la hipòtesi que n és compost. Per tant, un test de primalitat només afirma que "davant de la falta de verificació de la hipòtesi: n és compost, es pot tenir certa de què es tracta d'un nombre primer". Aquesta definició implica un grau menor de confiança que amb una (o test verdader de primalitat), que n'ofereix la seguretat matemàtica (confiança=1).
  • Een priemgetaltest is een algoritme dat bepaalt of een gegeven getal al dan niet priem is. Een dergelijke test wordt onder andere gebruikt in de cryptografie. Het verschil tussen een priemgetaltest en ontbinding in priemfactoren is dat een priemgetaltest niet noodzakelijk priemfactoren geeft, maar alleen zegt of het gegeven getal wel of niet priem is. Ontbinding in priemfactoren geeft uiteraard wel deze factoren. Het is eenvoudiger om te bepalen of een getal wel of niet priem is (aan de hand van een priemgetaltest) dan wat de priemfactoren zijn. Sommige priemgetaltests bewijzen dat een getal priem is, terwijl andere bewijzen dat een getal samengesteld is. Deze tests zouden we daarom beter samengesteldheidstests kunnen noemen.
  • 素性测试或素数判定,是檢驗一個給定的整數是否為質數的测试。
  • A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
  • Ett primtalstest är en algoritm som avgör huruvida ett givet heltal n är ett primtal, det vill säga inte delbart med något heltal förutom 1 och n självt. Att avgöra huruvida ett tal är primt är beräkningsmässigt betydligt enklare än att faktorisera det. Denna skillnad ligger till grund för krypteringsalgoritmer som exempelvis RSA.
  • Вопрос определения того, является ли натуральное число простым, известен как проблема простоты. Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число , позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты.Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа , то это число может являться простым с определённой вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое даёт математически подтверждённый результат.
  • Um teste de primalidade é um algoritmo para determinar se um dado número inteiro é primo. Este tipo de teste é usado em áreas da matemática como a criptografia. Diferentemente da fatoração de inteiros, os testes de primalidade geralmente não fornecem os fatores primos, indicando apenas se o número fornecido é ou não primo. O problema da fatoração é computacionalmente difícil, enquanto que os testes de primalidade são comparativamente mais fáceis (o tempo de execução é polinomial no tamanho dos dados de entrada). Alguns testes de primalidade provam que um número é primo, enquanto que outros, como o provam que um número é composto.
  • اختبار أولية عدد ما (بالإنجليزية: Primality test) هو خوارزمية من أجل تحديد إن كان عدد طبيعي ما أوليا أم لا.
  • La cuestión de la determinación de si un número n dado es primo es conocida como el problema de la primalidad. Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.
  • Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier.
  • Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht.
  • Test prvočíselnosti je algoritmus z oboru teorie čísel, kterým lze určit, zda je zadané přirozené číslo prvočíslem. Obvykle přitom tuto otázku zodpoví, aniž by přímo našel prvočíselný rozklad (to je považováno za podstatně náročnější úlohu), a často se jedná o pravděpodobnostní algoritmy či algoritmy použitelné jen na určitý druh čísel. Testování prvočíselnosti je obecně možné v , což bylo prokázáno objevením v roce 2002. Jedná se ovšem o asymptotickou složitost, při praktickém použití svou rychlostí silně zaostává a jsou často upřednostňovány jiné algoritmy, byť třeba pravděpodobnostní.
  • Тест простоти — алгоритм перевірки, чи є дане число простим.Важливо наголосити на різниці між тестуванням простоти та факторизацією цілих чисел. Станом на 2009 рік, факторизація є обчислювально важкою проблемою, в той час як тестування простоти є порівняно простішим (має поліноміальну складність).
  • Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero: quest'ultima operazione è infatti generalmente più lunga e complessa.
  • Test pierwszości – algorytm określający, czy dana liczba jest pierwsza, czy złożona. Nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili (2011 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.
  • Zenbaki lehenen testa algoritmo bat da, n zenbakia emanik lehena den edo ez jakiteko erabiltzen dena. Zenbaki lehenen testarekin n zenbakia konposatua dela dioen hipotesia egiaztatzea lortzen ez bada, lehena izango dela ondorioztatzen da, konfiantza-maila jakin batekin. Bereizi behar dira zenbaki lehenen testak emandako emaitzaren konfidantza-maila eta zenbaki lehenen froga (edo zenbaki lehenen egiazko testa) egitean lortutakoarena, azken hori froga izanik erantzuna erabateko segurtasun matematikoaz ematen delako.
  • 素数判定(そすうはんてい)とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する(クラスPに含まれる)素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された(AKS素数判定法)。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。
  • Primeca provo estas algoritmo por kontroli ĉu eniga nombro estas primo aŭ komponigita. Noto ke estas grava diferenco inter provo de primeco kaj entjera faktorigo. Kiel en 2008, faktorigo estas kompute peza problemo, sed primeca provo estas kompare facila.
owl:sameAs
Alternative Linked Data Views: Sponger | iSPARQL | ODE     Raw Data in: CXML | CSV | RDF ( N-Triples N3/Turtle JSON XML ) | OData ( Atom JSON )    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] This material is Open Knowledge Creative Commons License Valid XHTML + RDFa
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
OpenLink Virtuoso version 06.01.3127, on Linux (x86_64-pc-linux-gnu), Standard Edition
Copyright © 2009-2011 OpenLink Software