| dbo:abstract
|
- في نظرية الأعداد، مبرهنة بروث هي اختبار أولية أعداد بروث. (ar)
- El teorema de Proth és un test de primalitat per als nombres de Proth inventat per François Proth al voltant de 1878. Aquest teorema sosté que si p és un nombre de Proth, és a dir de la forma k 2 n +1 amb k senar i k <2 n , llavors si per a algun nombre enter a : (1) llavors p és un nombre primer anomenat cosí de Proth . Aquest test funciona a la pràctica perquè si p és primer, el 50% dels valors de a compleixen amb la condició indicada dalt. Si a és un nombre primer i p no és un residu quadràtic mòdul a llavors a tampoc és residu quadràtic mòdul p i es compleix la condició del teorema. A la pràctica s'utilitzen diferents nombres primers petits per a la variable a i es calcula el símbol de Jacobi fins que: la qual cosa és molt més ràpid que la exponenciació modular per trobar el valor de a , ja que en aquest cas, després de calcular p mod a , s'han de realitzar uns pocs càlculs usant nombres menors que a , mentre que amb la fórmula (1) s'han de realitzar més de (ln p /ln 2) multiplicacions modulars mòdul p , el que és molt costós en temps de càlcul. (ca)
- El teorema de Proth es un test de primalidad para los números de Proth inventado por François Proth alrededor de 1878. Este teorema sostiene que si p es un número de Proth, es decir de la forma k2n + 1 con k impar y k < 2n, entonces si para algún número entero a: (1) entonces p es un número primo llamado primo de Proth. Este test funciona en la práctica porque si p es primo, el 50% de los valores de a cumplen con la condición indicada arriba. Si a es un número primo y p no es un residuo cuadrático módulo a entonces a tampoco es residuo cuadrático módulo p y se cumple la condición del teorema. En la práctica se usan diferentes números primos pequeños para la variable a y se calcula el símbolo de Jacobi hasta que: lo cual es mucho más rápido que la exponenciación modular para hallar el valor de a, ya que en este caso, luego de calcular p mod a, se deben realizar unos pocos cálculos usando números menores que a, mientras que con la fórmula (1) se deben realizar más de (ln p/ln 2) multiplicaciones modulares módulo p, lo que es muy costoso en tiempo de cálculo. (es)
- En théorie des nombres, le théorème de Proth est le test de primalité suivant, spécifique aux nombres de Proth, c'est-à-dire aux entiers naturels de la forme p = k2n + 1 avec 0 < k < 2n : Pour qu'un nombre de Proth p soit premier, (il faut et) il suffit qu'il existe un entier a tel que a (p–1)/2 ≡ –1 (mod p) ou, de façon équivalente mais un peu plus fidèle : Soient p un nombre de Proth et a un entier dont le symbole de Jacobi (a/p) est égal à –1. Alors, p est premier si (et seulement si) a (p–1)/2 ≡ –1 (mod p). (fr)
- In number theory, Proth's theorem is a primality test for Proth numbers. It states that if p is a Proth number, of the form k2n + 1 with k odd and k < 2n, and if there exists an integer a for which then p is prime. In this case p is called a Proth prime. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration. In practice, however, a quadratic nonresidue of p is found via a modified Euclid's algorithm and taken as the value of a, since if a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. For such an a the Legendre symbol is Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive), the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a running time that varies randomly. Note that if a is chosen to be a quadratic nonresidue as described above, the runtime is constant, safe for the time spent on finding such a quadratic nonresidue. Finding such a value is very fast compared to the actual test. (en)
- 프로트의 정리는 수론에서 프로트 수에 대한 이다. 만일 가 이고, 홀수 를 갖는 형태의 프로트 수일 때, 어떤 정수 에 대해서 다음과 같이 표현될 수 있다면, 는 소수 (이때 이 소수는 프로트 소수라고 한다)이다. 이 소수 판별법은 프로트 수에 대해서는 매우 단순하고 유용하다. (ko)
- In teoria dei numeri, il teorema di Proth è un test di primalità per i numeri di Proth. Il teorema afferma che, se p è un numero di Proth, nella forma k2n + 1 con k dispari e k < 2n, allora se per qualche numero intero a, allora p è primo (ed è chiamato primo di Proth). Questo test è pratico perché se p è primo, qualunque a arbitrariamente scelto ha circa il 50% di probabilità di funzionare. (it)
- In de getaltheorie, een onderdeel van de wiskunde, geeft de stelling van Proth voorwaarden waaronder een prothgetal een priemgetal is. Prothgetallen zijn kandidaten voor priemgetallen, maar niet elk prothgetal is priem. De stelling zegt dat het prothgetal , met oneven en een priemgetal is, als er een geheel getal is, waarvoor In dat geval wordt een prothpriemgetal genoemd. Dit is een praktische toets, want als priem is, voldoet bijna de helft van alle te kiezen getallen . De stelling is vernoemd naar François Proth (1852-1879). (nl)
- 普罗斯定理是數論的一個定理，可以判斷普罗斯数是否是質數。 如果p是普罗斯数，也就是滿足k2n + 1形式的數，其中k為奇數，且k < 2n，那么如果对于某个整数a，有 则p是素数。此時p稱為普罗斯質數。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的機會滿足這個關係式。 若a是是模p的二次非剩余，則上述定理的逆定理也成立，因此有一種可以找a的方式，就是在最小的質數中依序找a，計算雅可比符号，直到下式成立為止 的素性测试是亂數演算法，可能會產生偽陽性的結果（不是素數的數卻通過素性测试），根據普罗斯定理的演算法是拉斯維加斯算法，其答案都是對的，但要找到答案的時間則是隨機變化。 (zh)
- В теории чисел теорема Прота является тестом простоты для чисел Прота. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 5199 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- في نظرية الأعداد، مبرهنة بروث هي اختبار أولية أعداد بروث. (ar)
- En théorie des nombres, le théorème de Proth est le test de primalité suivant, spécifique aux nombres de Proth, c'est-à-dire aux entiers naturels de la forme p = k2n + 1 avec 0 < k < 2n : Pour qu'un nombre de Proth p soit premier, (il faut et) il suffit qu'il existe un entier a tel que a (p–1)/2 ≡ –1 (mod p) ou, de façon équivalente mais un peu plus fidèle : Soient p un nombre de Proth et a un entier dont le symbole de Jacobi (a/p) est égal à –1. Alors, p est premier si (et seulement si) a (p–1)/2 ≡ –1 (mod p). (fr)
- 프로트의 정리는 수론에서 프로트 수에 대한 이다. 만일 가 이고, 홀수 를 갖는 형태의 프로트 수일 때, 어떤 정수 에 대해서 다음과 같이 표현될 수 있다면, 는 소수 (이때 이 소수는 프로트 소수라고 한다)이다. 이 소수 판별법은 프로트 수에 대해서는 매우 단순하고 유용하다. (ko)
- In teoria dei numeri, il teorema di Proth è un test di primalità per i numeri di Proth. Il teorema afferma che, se p è un numero di Proth, nella forma k2n + 1 con k dispari e k < 2n, allora se per qualche numero intero a, allora p è primo (ed è chiamato primo di Proth). Questo test è pratico perché se p è primo, qualunque a arbitrariamente scelto ha circa il 50% di probabilità di funzionare. (it)
- In de getaltheorie, een onderdeel van de wiskunde, geeft de stelling van Proth voorwaarden waaronder een prothgetal een priemgetal is. Prothgetallen zijn kandidaten voor priemgetallen, maar niet elk prothgetal is priem. De stelling zegt dat het prothgetal , met oneven en een priemgetal is, als er een geheel getal is, waarvoor In dat geval wordt een prothpriemgetal genoemd. Dit is een praktische toets, want als priem is, voldoet bijna de helft van alle te kiezen getallen . De stelling is vernoemd naar François Proth (1852-1879). (nl)
- 普罗斯定理是數論的一個定理，可以判斷普罗斯数是否是質數。 如果p是普罗斯数，也就是滿足k2n + 1形式的數，其中k為奇數，且k < 2n，那么如果对于某个整数a，有 则p是素数。此時p稱為普罗斯質數。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的機會滿足這個關係式。 若a是是模p的二次非剩余，則上述定理的逆定理也成立，因此有一種可以找a的方式，就是在最小的質數中依序找a，計算雅可比符号，直到下式成立為止 的素性测试是亂數演算法，可能會產生偽陽性的結果（不是素數的數卻通過素性测试），根據普罗斯定理的演算法是拉斯維加斯算法，其答案都是對的，但要找到答案的時間則是隨機變化。 (zh)
- В теории чисел теорема Прота является тестом простоты для чисел Прота. (ru)
- El teorema de Proth és un test de primalitat per als nombres de Proth inventat per François Proth al voltant de 1878. Aquest teorema sosté que si p és un nombre de Proth, és a dir de la forma k 2 n +1 amb k senar i k <2 n , llavors si per a algun nombre enter a : (1) llavors p és un nombre primer anomenat cosí de Proth . Aquest test funciona a la pràctica perquè si p és primer, el 50% dels valors de a compleixen amb la condició indicada dalt. (ca)
- El teorema de Proth es un test de primalidad para los números de Proth inventado por François Proth alrededor de 1878. Este teorema sostiene que si p es un número de Proth, es decir de la forma k2n + 1 con k impar y k < 2n, entonces si para algún número entero a: (1) entonces p es un número primo llamado primo de Proth. Este test funciona en la práctica porque si p es primo, el 50% de los valores de a cumplen con la condición indicada arriba. (es)
- In number theory, Proth's theorem is a primality test for Proth numbers. It states that if p is a Proth number, of the form k2n + 1 with k odd and k < 2n, and if there exists an integer a for which then p is prime. In this case p is called a Proth prime. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration. (en)
|
| rdfs:label
|
- مبرهنة بروث (ar)
- Teorema de Proth (ca)
- Teorema de Proth (es)
- Théorème de Proth (fr)
- Teorema di Proth (it)
- 프로트의 정리 (ko)
- Stelling van Proth (nl)
- Proth's theorem (en)
- Теорема Прота (ru)
- 普罗斯定理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
