| dbo:abstract
|
- En teoria de nombres, el test de Lucas és un test de primalitat per a un nombre natural n i requereix que els factors cosins de n - 1 siguin coneguts. Si hi ha un nombre natural a menor que n i més gran que 1 que verifica les condicions així com per a tots els factors primers q de n - 1, llavors n és primer. Si no pot trobar tal a , llavors n és un nombre compost. Per exemple, prengui n = 71. Llavors, n - 1 = 70 = (2) (5) (7).Preneu-vos ara a = 11. En primer lloc: Això no demostra que l'ordre multiplicatiu d'11 mod 71 és 70, perquè algun factor de 70 encara podria funcionar amunt. Verifiquem llavors 70 dividit pels seus factors primers: Llavors, l'ordre multiplicatiu d'11 mod 71 és 70 i d'aquesta manera, 71 és primer. Per realitzar aquestes hauria d'usar el mètode accelerat de exponenciació binària. Aquest algorisme és correcte, ja que si a passa el primer pas, podem deduir que a i n són coprimers. Si a també passa el segon pas, llavors l'ordre de a al grup (Z/nZ)* és igual a n- 1, el que significa que l'ordre d'aquest grup és n- 1, implicant que n és primer. Recíprocament, si n és primer, llavors hi ha una arrel primitiva mòdul n i qualsevol arrel primitiva passarà dos passos de l'algorisme. (ca)
- من أجل اختبار أعداد ميرسين، المرجو النظر إلى اختبار لوكاس-ليهمر لأولية عدد ما. (ar)
- Der Lucas-Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 1950er Jahren von Derrick Henry Lehmer und später nochmals von John Brillhart und John L. Selfridge verbessert. Er sollte nicht mit dem Lucas-Lehmer-Test für Mersenne-Zahlen verwechselt werden. (de)
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n − 1, lo que significa que el orden de ese grupo es n − 1, implicando que n es primo. Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo. (es)
- In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime. (en)
- Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier n, connaissant les facteurs premiers de n – 1. (fr)
- De algemene Lucas-Lehmertest is een algoritme om te bepalen of een natuurlijk getal een priemgetal is. Hiervoor moeten de priemfactoren van het getal bekend zijn. De test is ontwikkeld door Edouard Lucas en Derrick Henry Lehmer en wordt met name gebruikt in de numerieke getaltheorie. (nl)
- В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым. (ru)
- I talteori är Lucas-Lehmertestet ett primtalstest för naturliga talet n; det krävs att primtalsfaktorerna i n − 1 redan är kända Om det för varje primtalsfaktor q i n-1 finns något a mindre än n och större än 1 så att både och gäller för alla primtalsfaktorer q av n -1, då är n ett primtal. Om inget sådant tal a kan hittas, är n ett sammansatt tal. Exempelvis, om n = 71, n − 1 = 70 = (2)(5)(7).Testa a = 11 först: Detta visar inte att multiplikatordningen av 11 mod 71 är 70 då någon faktor av 70 och kan fungera ovan. Så testa 70 delat med dess primtalsfaktorer: Multiplikatsordnignen av 11 mod 71 är 70, således är 71 ett primtal. För att göra denna bör man alltid börja med att använda binär exponentiering. Algoritmens korrekthet förklaras som följer: om a klarar första steget av algoritmen kan vi sluta oss till att a och n är relativt prima. Om a också klarar andra steget, då är a i gruppen (Z/nZ)* lika med n − 1, vilket betyder att den gruppens ordning är n - 1, vilket antyder att n är ett primtal. Omvänt, om n är ett primtal finns det primitiv rot modulo n, och alla sådana primitiva rötter kommer att klara båda algoritmens steg. (sv)
- В теорії чисел тест простоти Люка — це тест простоти натурального числа n; для його роботи необхідно знати розкладання на прості множники. Вони утворюють базис для , який дозволяє підтвердити за поліноміальний час, що число є простим. (uk)
|
| rdfs:comment
|
- من أجل اختبار أعداد ميرسين، المرجو النظر إلى اختبار لوكاس-ليهمر لأولية عدد ما. (ar)
- Der Lucas-Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 1950er Jahren von Derrick Henry Lehmer und später nochmals von John Brillhart und John L. Selfridge verbessert. Er sollte nicht mit dem Lucas-Lehmer-Test für Mersenne-Zahlen verwechselt werden. (de)
- In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime. (en)
- Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier n, connaissant les facteurs premiers de n – 1. (fr)
- De algemene Lucas-Lehmertest is een algoritme om te bepalen of een natuurlijk getal een priemgetal is. Hiervoor moeten de priemfactoren van het getal bekend zijn. De test is ontwikkeld door Edouard Lucas en Derrick Henry Lehmer en wordt met name gebruikt in de numerieke getaltheorie. (nl)
- В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым. (ru)
- В теорії чисел тест простоти Люка — це тест простоти натурального числа n; для його роботи необхідно знати розкладання на прості множники. Вони утворюють базис для , який дозволяє підтвердити за поліноміальний час, що число є простим. (uk)
- En teoria de nombres, el test de Lucas és un test de primalitat per a un nombre natural n i requereix que els factors cosins de n - 1 siguin coneguts. Si hi ha un nombre natural a menor que n i més gran que 1 que verifica les condicions així com per a tots els factors primers q de n - 1, llavors n és primer. Si no pot trobar tal a , llavors n és un nombre compost. Per exemple, prengui n = 71. Llavors, n - 1 = 70 = (2) (5) (7).Preneu-vos ara a = 11. En primer lloc: Llavors, l'ordre multiplicatiu d'11 mod 71 és 70 i d'aquesta manera, 71 és primer. (ca)
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. (es)
- I talteori är Lucas-Lehmertestet ett primtalstest för naturliga talet n; det krävs att primtalsfaktorerna i n − 1 redan är kända Om det för varje primtalsfaktor q i n-1 finns något a mindre än n och större än 1 så att både och gäller för alla primtalsfaktorer q av n -1, då är n ett primtal. Om inget sådant tal a kan hittas, är n ett sammansatt tal. Exempelvis, om n = 71, n − 1 = 70 = (2)(5)(7).Testa a = 11 först: Detta visar inte att multiplikatordningen av 11 mod 71 är 70 då någon faktor av 70 och kan fungera ovan. Så testa 70 delat med dess primtalsfaktorer: (sv)
|
