| dbo:abstract
|
- اختبار ميلر ورابين لأولية عدد ما (بالإنجليزية: Miller–Rabin primality test) هو اختبار احتمالي لمعرفة إذا ما كان العدد أوليّاً: وهو خوارزمية تحدد فيما إذا كان العدد المعطى من المحتمل أن يكون أوليًا ، على غرار اختبار فيرمات لأولية عدد ما . لهذا الاختبار أهمية تاريخية في البحث عن اختبار الأولية الحتمية في مجال تعقيد الوقت، حيث لا يزال متغيره الاحتمالي مستخدمًا على نطاق واسع في الممارسة، كواحد من أبسط وأسرع الاختبارات المعروفة. اقترح هذا الاختبار عام 1976، نسخة ميلر من اختبار الحتمية، لكن صحتها تعتمد على فرضية ريمان المعممة غير المثبتة. عدلها مايكل رابين للحصول على خوارزمية عشوائية غير مشروطة عام 1980. (ar)
- El test de primalitat de Miller-Rabin o test de primalitat de Rabin-Miller és un test de primalitat, és a dir un algorisme que determina si un nombre donat és un ,De forma similar al test de primalitat de Fermat i el test de primalitat de Solovay-Strassen. En la seva versió original, deguda a Gary L. Miller, era un , però el determinisme es basa en la que no està demostrada; En Michael O. Rabin el va modificar per a obtenir un . (ca)
- Millerův-Rabinův test prvočíselnosti je jedním z testů prvočíselnosti, tedy z algoritmů rozhodujících, zda je dané číslo prvočíslo. Je podobný Fermatovu testu prvočíselnosti a . Původní verze vyvinutá byla deterministická, ovšem závisela na nedokázané zobecněné Riemannově hypotéze. Michael O. Rabin na jejím základě vyvinul verzi pravděpodobnostní, která na ničem nedokázaném nezávisí. (cs)
- Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test (kurz MRT) ist ein probabilistischer Primzahltest und damit ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie. Der MRT erhält als Eingabe eine ungerade natürliche Zahl , von der man wissen will, ob sie prim ist, und eine weitere Zahl und gibt entweder „zusammengesetzt“ oder „wahrscheinlich prim“ aus. Ist prim, so lautet die Ausgabe immer „wahrscheinlich prim“. Anderenfalls wird in den meisten Fällen „zusammengesetzt“ ausgegeben, aber für manche Paare mit zusammengesetztem ist die Ausgabe trotzdem „wahrscheinlich prim“. Oft wird zufällig gewählt, der MRT zählt in dieser Form zur Klasse der Monte-Carlo-Algorithmen. Durch wiederholtes Testen mit verschiedenen kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt des MRT, bei denen durch geeignete Wahl der ein Irrtum ausgeschlossen wird. Der MRT ist nach Gary L. Miller und Michael O. Rabin benannt. John L. Selfridge hat diesen Test schon 1974 verwendet, bevor Rabin ihn 1976 veröffentlichte. Daher rührt der alternative Name Miller-Selfridge-Rabin-Test. Der MRT funktioniert ähnlich wie der Solovay-Strassen-Test, ist diesem allerdings in allen Aspekten überlegen. Er ist schneller, seine Irrtumswahrscheinlichkeit ist geringer, und alle Paare ,, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt. (de)
- El test de primalidad de Miller-Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trataba de un algoritmo determinista, pero basado en la no demostrada hipótesis generalizada de Riemann; Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados. (es)
- The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. Gary L. Miller discovered the test in 1976; Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980. (en)
- En mathématiques, le test de primalité de Miller-Rabin est un test de primalité probabiliste, de type Monte Carlo : étant donné un nombre entier, il donne une réponse oui/non pour conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablement premier. La probabilité qu'un nombre déclaré premier par l'algorithme soit en réalité composé peut être rendue aussi faible que souhaité, en fonction des paramètres d'entrées de l'algorithme. En cela il est analogue au test de primalité de Solovay-Strassen, mais toujours plus efficace que ce dernier. Sa version originale, due à Gary L. Miller, est déterministe, mais ce déterminisme dépend de l'hypothèse de Riemann généralisée (qui n'est pas démontrée) ; Michael Rabin l'a modifiée pour obtenir un algorithme probabiliste inconditionnel. Le test de Miller-Rabin est très utilisé en cryptographie asymétrique pour engendrer les grands nombres premiers nécessaires pour le chiffrement RSA, et pour beaucoup des utilisations du chiffrement El Gamal ou de l'échange de clés Diffie-Hellman. (fr)
- 밀러-라빈 소수판별법(Miller-Rabin primality test)은 입력으로 주어진 수가 소수인지 아닌지 판별하는 알고리즘이다. 라빈-밀러 소수판별법(Rabin-Miller primality test)이라고도 한다. 의 원래 알고리즘은 일반 리만 가설에 기반한 결정론적 알고리즘이었는데, 미하엘 라빈이 확률적 알고리즘으로 변경했다. (ko)
- De Miller-Rabin-priemgetaltest of Rabin-Miller-priemgetaltest is een priemgetaltest: een algoritme dat bepaalt of een gegeven getal priem is of niet. Het is vergelijkbaar met de priemtest van Fermat en de Solovay-Strassen-priemgetaltest, die net als de Miller-Rabin-priemgetaltest veelal worden gebruikt in de cryptografie. De originele versie van deze test is gemaakt door en is deterministisch. Het deterministische deel van deze test is echter afhankelijk van de nog onbewezen Riemann-hypothese. Michael O. Rabin heeft de test veranderd tot een probabilistische test, die nergens van afhankelijk is en altijd werkt. (nl)
- ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。 (ja)
- Il test di primalità di Miller-Rabin è un test di primalità, ossia un algoritmo per determinare se un numero intero è primo. La sua versione originale, dovuta a , è deterministica, ma dipende dall'ipotesi di Riemann generalizzata, un'importante congettura matematica tuttora aperta. L'algoritmo è stato successivamente modificato da Michael Rabin che ne ha ottenuto una versione simile al test di Fermat e al . (it)
- O teste Miller-Rabin (por Gary Miller e Michael Rabin) é um teste probabilístico da primitividade de um dado número n. Se um número n não passar pelo teste, n com certeza é um número composto (ou seja, não-primo). Se o número passar no teste, ele é primo, com uma probabilidade, sendo que denomina o conjunto de todos números primos. A margem de erro pode ser diminuída arbitrariamente, aplicando-se o teste várias vezes ao mesmo número n. O teste é parecido com o teste , portanto sua margem de erro é bem menor. A importância desse algoritmo se deve à criptografia assimétrica, onde a necessidade de uma grande quantidade de números primos grandes é vital para a segurança dos algoritmos. Tais números são tão grandes que testes não probabilísticos como o da simples divisão por números primos menores que o número gerado ou o tabelamento de todos os números primos são impraticáveis. É importante dizer que o teste Miller-Rabin, ou Rabin-Miller, como as vezes também é chamado, não dá indícios sobre a fatoração no número n. Devido suas caraterísticas, esse teste é o mais utilizado para o teste da primalidade. (pt)
- Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел. (ru)
- Test Millera-Rabina – test pierwszości, czyli algorytm określający czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas . Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci. (pl)
- 米勒-拉賓質數判定法（英語：Miller–Rabin primality test）是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。1976年，卡内基梅隆大学的计算机系教授首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，於1980年，由以色列耶路撒冷希伯來大學的迈克尔·拉宾教授作出修改，提出了不依赖于该假设的随机化算法。 (zh)
- Тест простоти Міллера — Рабіна або тест Міллера – Рабіна — це тест простоти: алгоритм, який визначає чи є надане число простим. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену узагальнену гіпотезу Рімана; Міхаель Рабін змінив її, щоб отримати безумовний імовірнісний алгоритм. (uk)
|
| rdfs:comment
|
- El test de primalitat de Miller-Rabin o test de primalitat de Rabin-Miller és un test de primalitat, és a dir un algorisme que determina si un nombre donat és un ,De forma similar al test de primalitat de Fermat i el test de primalitat de Solovay-Strassen. En la seva versió original, deguda a Gary L. Miller, era un , però el determinisme es basa en la que no està demostrada; En Michael O. Rabin el va modificar per a obtenir un . (ca)
- Millerův-Rabinův test prvočíselnosti je jedním z testů prvočíselnosti, tedy z algoritmů rozhodujících, zda je dané číslo prvočíslo. Je podobný Fermatovu testu prvočíselnosti a . Původní verze vyvinutá byla deterministická, ovšem závisela na nedokázané zobecněné Riemannově hypotéze. Michael O. Rabin na jejím základě vyvinul verzi pravděpodobnostní, která na ničem nedokázaném nezávisí. (cs)
- El test de primalidad de Miller-Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trataba de un algoritmo determinista, pero basado en la no demostrada hipótesis generalizada de Riemann; Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados. (es)
- 밀러-라빈 소수판별법(Miller-Rabin primality test)은 입력으로 주어진 수가 소수인지 아닌지 판별하는 알고리즘이다. 라빈-밀러 소수판별법(Rabin-Miller primality test)이라고도 한다. 의 원래 알고리즘은 일반 리만 가설에 기반한 결정론적 알고리즘이었는데, 미하엘 라빈이 확률적 알고리즘으로 변경했다. (ko)
- De Miller-Rabin-priemgetaltest of Rabin-Miller-priemgetaltest is een priemgetaltest: een algoritme dat bepaalt of een gegeven getal priem is of niet. Het is vergelijkbaar met de priemtest van Fermat en de Solovay-Strassen-priemgetaltest, die net als de Miller-Rabin-priemgetaltest veelal worden gebruikt in de cryptografie. De originele versie van deze test is gemaakt door en is deterministisch. Het deterministische deel van deze test is echter afhankelijk van de nog onbewezen Riemann-hypothese. Michael O. Rabin heeft de test veranderd tot een probabilistische test, die nergens van afhankelijk is en altijd werkt. (nl)
- ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。 (ja)
- Il test di primalità di Miller-Rabin è un test di primalità, ossia un algoritmo per determinare se un numero intero è primo. La sua versione originale, dovuta a , è deterministica, ma dipende dall'ipotesi di Riemann generalizzata, un'importante congettura matematica tuttora aperta. L'algoritmo è stato successivamente modificato da Michael Rabin che ne ha ottenuto una versione simile al test di Fermat e al . (it)
- Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел. (ru)
- Test Millera-Rabina – test pierwszości, czyli algorytm określający czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas . Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci. (pl)
- 米勒-拉賓質數判定法（英語：Miller–Rabin primality test）是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。1976年，卡内基梅隆大学的计算机系教授首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，於1980年，由以色列耶路撒冷希伯來大學的迈克尔·拉宾教授作出修改，提出了不依赖于该假设的随机化算法。 (zh)
- Тест простоти Міллера — Рабіна або тест Міллера – Рабіна — це тест простоти: алгоритм, який визначає чи є надане число простим. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену узагальнену гіпотезу Рімана; Міхаель Рабін змінив її, щоб отримати безумовний імовірнісний алгоритм. (uk)
- اختبار ميلر ورابين لأولية عدد ما (بالإنجليزية: Miller–Rabin primality test) هو اختبار احتمالي لمعرفة إذا ما كان العدد أوليّاً: وهو خوارزمية تحدد فيما إذا كان العدد المعطى من المحتمل أن يكون أوليًا ، على غرار اختبار فيرمات لأولية عدد ما . (ar)
- Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test (kurz MRT) ist ein probabilistischer Primzahltest und damit ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie. Oft wird zufällig gewählt, der MRT zählt in dieser Form zur Klasse der Monte-Carlo-Algorithmen. Durch wiederholtes Testen mit verschiedenen kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt des MRT, bei denen durch geeignete Wahl der ein Irrtum ausgeschlossen wird. (de)
- The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. (en)
- En mathématiques, le test de primalité de Miller-Rabin est un test de primalité probabiliste, de type Monte Carlo : étant donné un nombre entier, il donne une réponse oui/non pour conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablement premier. La probabilité qu'un nombre déclaré premier par l'algorithme soit en réalité composé peut être rendue aussi faible que souhaité, en fonction des paramètres d'entrées de l'algorithme. En cela il est analogue au test de primalité de Solovay-Strassen, mais toujours plus efficace que ce dernier. (fr)
- O teste Miller-Rabin (por Gary Miller e Michael Rabin) é um teste probabilístico da primitividade de um dado número n. Se um número n não passar pelo teste, n com certeza é um número composto (ou seja, não-primo). Se o número passar no teste, ele é primo, com uma probabilidade, sendo que denomina o conjunto de todos números primos. A margem de erro pode ser diminuída arbitrariamente, aplicando-se o teste várias vezes ao mesmo número n. O teste é parecido com o teste , portanto sua margem de erro é bem menor. (pt)
|
