| dbo:abstract
|
- اختبار أولية عدد ما (بالإنجليزية: Primality test) هو خوارزمية هدفها تحديدُ إن كان عدد طبيعي ما أوليا أم لا. تستعمل هذه الخوارزميات في مجال التعمية وفي مجالات أخرى من الرياضيات. تختلف عن خوارزميات تحليل عدد صحيح إلى عوامل في كونها أنها لا تعطي قواسم العدد الذي نحن بصدد اختبار أوليته. خوارزميات تحليل عدد صحيح إلى عوامل، كما يدل على ذلك اسمها، تعطي قواسم هذا العدد. من حيث التعقد الحسابي، يعتقد أن تعميل عدد طبيعي هو معضلة صعبة، بينما اختبار أولية عدد، هو مقارنةً، معضلة سهلة حيث تعقد الوقت لخوارزميات اختبار أولية عدد هو بدلالة متعددة للحدود مدخلها طول العدد الذي يراد اختبار أوليته. بعض الاختبارات تبرهن على أن عدد ما هو أولى، بينما تبرهن بعضها أن عددا ما هو مؤلف. اختبار ميلر-رابن لأولية عدد ما مثال على ذلك. (ar)
- 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. Kromě algoritmů, které v případě úspěchu prokáží, že je číslo prvočíslem, jsou také algoritmy, které v případě úspěchu prokáží, že se jedná o složené číslo – takové se někdy označují testy složenosti a jejich zřejmě nejznámějším příkladem je oblíbený Millerův-Rabinův test prvočíselnosti. Testování prvočíselnosti je obecně možné v polynomiálním čase, 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í. (cs)
- 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). (ca)
- Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht. (de)
- 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. (eo)
- 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. (eu)
- Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. (fr)
- 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 de forma concluyente la hipótesis de un teorema cuya conclusión es que n es compuesto. Esto es, un test de primalidad solo conjetura que “ante la falta de certificación sobre la hipótesis de que n es compuesto podemos tener cierta confianza en que se trata de un número primo”. Esta definición supone un grado menor de confianza que lo que se denomina prueba de primalidad (o test verdadero de primalidad), que ofrece una seguridad matemática al respecto. (es)
- 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. (en)
- 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. (nl)
- 수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다. (ko)
- 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. Con la significativa eccezione del metodo delle curve ellittiche (noto come ECPP) e dell'algoritmo AKS, i test di primalità più efficienti oggi utilizzati sono probabilistici, nel senso che danno una risposta certa solo quando rispondono NO (ossia quando dicono che il numero è composto) mentre nel caso di risposta SÌ assicurano soltanto un limite inferiore alla probabilità che il numero sia primo. L'errore dei test può essere però reso piccolo a piacere. (it)
- 素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。 (ja)
- 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. (pl)
- 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 teste de Miller-Rabin, provam que um número é composto. Um dos primeiros testes de primalidade é o crivo de Eratóstenes. (pt)
- Вопрос определения того, является ли натуральное число простым, известен как проблема простоты. Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число , позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты.Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа , то это число может являться простым с определённой вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое даёт математически подтверждённый результат. (ru)
- 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. (sv)
- 素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。 (zh)
- Тест простоти — алгоритм перевірки, чи є дане число простим.Важливо наголосити на різниці між тестуванням простоти та факторизацією цілих чисел. Станом на 2009 рік, факторизація є обчислювально важкою проблемою, у той час як тестування простоти є порівняно простішим (має поліноміальну складність). (uk)
|
| rdfs:comment
|
- اختبار أولية عدد ما (بالإنجليزية: Primality test) هو خوارزمية هدفها تحديدُ إن كان عدد طبيعي ما أوليا أم لا. تستعمل هذه الخوارزميات في مجال التعمية وفي مجالات أخرى من الرياضيات. تختلف عن خوارزميات تحليل عدد صحيح إلى عوامل في كونها أنها لا تعطي قواسم العدد الذي نحن بصدد اختبار أوليته. خوارزميات تحليل عدد صحيح إلى عوامل، كما يدل على ذلك اسمها، تعطي قواسم هذا العدد. من حيث التعقد الحسابي، يعتقد أن تعميل عدد طبيعي هو معضلة صعبة، بينما اختبار أولية عدد، هو مقارنةً، معضلة سهلة حيث تعقد الوقت لخوارزميات اختبار أولية عدد هو بدلالة متعددة للحدود مدخلها طول العدد الذي يراد اختبار أوليته. بعض الاختبارات تبرهن على أن عدد ما هو أولى، بينما تبرهن بعضها أن عددا ما هو مؤلف. اختبار ميلر-رابن لأولية عدد ما مثال على ذلك. (ar)
- 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). (ca)
- Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht. (de)
- 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. (eo)
- 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. (eu)
- Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. (fr)
- 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. (en)
- 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. (nl)
- 수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다. (ko)
- 素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。 (ja)
- 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. (pl)
- Вопрос определения того, является ли натуральное число простым, известен как проблема простоты. Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число , позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты.Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа , то это число может являться простым с определённой вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое даёт математически подтверждённый результат. (ru)
- 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. (sv)
- 素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。 (zh)
- Тест простоти — алгоритм перевірки, чи є дане число простим.Важливо наголосити на різниці між тестуванням простоти та факторизацією цілих чисел. Станом на 2009 рік, факторизація є обчислювально важкою проблемою, у той час як тестування простоти є порівняно простішим (має поліноміальну складність). (uk)
- 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. (cs)
- 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 de forma concluyente la hipótesis de un teorema cuya conclusión es que n es compuesto. (es)
- 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. (it)
- 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 teste de Miller-Rabin, provam que um número é composto. (pt)
|
