| dbo:abstract
|
- Jako pseudoprvočísla se v teorii čísel označují taková celá čísla, která jsou sice složená, ale přitom splňují některé z testů, které dokáží většinu složených čísel odlišit od prvočísel. (Takové testy platí pro všechna prvočísla, ale většina složených čísel jim nevyhoví.) Jednotlivé druhy pseudoprvočísel jsou definovány podle konkrétních testů, kterými je nelze rozlišit od prvočísla. Základní skupinou pseudoprvočísel jsou ta definovaná na základě Malé Fermatovy věty; pokud se hovoří o „pseudoprvočíslech“ bez upřesnění, míní se jimi zpravidla právě tato. (cs)
- Els nombres pseudoprimers són els que no essent primers, verifiquen el test de primalitat de base b: Siguin un nombre enter i un altre nombre enter no primer. El nombre és pseudoprimer respecte a la base si . Els nombres pseudoprimers respecte qualsevol base són els nombres de Carmichael. (ca)
- عدد شبه أولي (بالإنجليزية: Pseudoprime) هو عدد أولي محتمل. (ar)
- Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele Möglichkeiten für solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll. Ein historisch bedeutendes Beispiel einer Pseudoprimzahl ist die Zahl . Sie ist eine Fermatsche Pseudoprimzahl zur Basis (und auch einigen anderen Basen). (de)
- En nombroteorio, pseŭdoprimo estas (entjero, kiu havas propraĵojn komunajn al ĉiuj primoj), kiu estas ne reale primo. Pseŭdoprimoj povas esti klasifikitaj laŭ propraĵoj, kiujn ili kontentigas. La plej grava klaso de pseŭdoprimoj venas de malgranda teoremo de Fermat kaj de ĉi tie estas nomataj kiel pseŭdoprimoj de Fermat. Ĉi tiu teoremo diras: se p estas primo kaj a estas interprimo al p, 1≤a, tiam ap-1-1 estas per p. Se nombro x estas , a estas interprimo al x, 1≤a kaj x dividas na ax-1-1, tiam x estas pseŭdoprimo al bazo a. Nombro x, kiu estas pseŭdoprimo por ĉiu valoro de a (a estu interprimo al x), estas nombro de Carmichael. La plej malgranda pseŭdoprimo de Fermat por la bazo 2 estas 341. Ĝi estas ne primo pro tio, ke egalas al 11·31, sed ĝi verigas malgrandan teoremon de Fermat: 2340≡1 (mod 341). La malofteco de ĉi tia pseŭdoprimoj havas gravajn praktikajn implikaciojn. Ekzemple algoritmoj tiaj kiel RSA postulas eblecon rapide trovi grandajn primojn. La kutima algoritmo por generi primojn estas generi hazardajn neparajn nombrojn kaj provi ilin por primeco. Tamen, primecaj testoj estas malrapidaj. Se la uzanto konsentas toleri arbitre malgrandan ŝancon, ke la nombro trovita estas ne primo, sed pseŭdoprimo, do eblas uzi la multe pli rapidan kaj pli simplan primeca provo de Fermat. Alia maniero estas uzi pli rafinitajn nociojn de pseŭdoprimeco, ekzemple forta pseŭdoprimoj aŭ , por kiu ne estas analogaj de nombroj de Carmichael. Ĉi tiu kondukas al probablecaj algoritmoj, ekzemple primeca provo de Solovay-Strassen kaj , kiuj produktas tion, kio estas sciata kiel . Industrio-grada primo estas entjero, por kiu primeco ne estas rigore pruvita, sed estas nur arbitre malgranda probablo de komponigiteco. Estas malfinie multaj pseŭdoprimoj al donita bazo (fakte, malfinie multaj nombroj de Carmichael), sed ili estas iom malofta. Estas nur 3 pseŭdoprimoj al bazo 2 pli sube de 1000, kaj estas nur 245 pli sube de miliono. Pseŭdoprimoj al bazo 2 estas nomataj ankaŭ kiel nombroj de Poulet aŭ iam nombroj de Sarrus. La nombroj de Poulet kaj nombroj de Carmichael (en grasa tiparo) supren ĝis 41041 estas: Nombro de Poulet, ĉiuj el kies divizoroj d dividas na 2d-2, estas . Estas malfinie multaj nombroj de Poulet, kiuj ne estas supernombroj de Poulet. La unua plej malgrandaj pseŭdoprimoj por bazoj a≤200 estas donitaj en jena tabelo. La koloroj markigas la kvanton de primaj faktoroj. (eo)
- Los pseudoprimos son aquellos números que, sin ser primos, verifican el test de base b, o lo que es lo mismo: Siendo n perteneciente a los números enteros, se dice que n es pseudoprimo respecto la base b si es compuesto y además verifica la congruencia: es decir, n divide a bn-1-1. Esta propiedad es un caso particular del Pequeño Teorema de Fermat y por tanto siempre se verifica para números primos. (es)
- A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes. Pseudoprimes are of primary importance in public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Carl Pomerance estimated in 1988 that it would cost $10 million to factor a number with 144 digits, and $100 billion to factor a 200-digit number (the cost today is dramatically lower but still prohibitively high). But finding two large prime numbers as needed for this use is also expensive, so various probabilistic primality tests are used, some of which in rare cases inappropriately deliver composite numbers instead of primes. On the other hand, deterministic primality tests, such as the AKS primality test, do not give false positives; there are no pseudoprimes with respect to them. (en)
- Un nombre pseudo-premier est un nombre premier probable (un entier naturel qui partage une propriété commune à tous les nombres premiers) qui n'est en fait pas premier. Les nombres pseudo-premiers peuvent être classés selon la propriété qu'ils satisfont. (fr)
- In matematica, un numero pseudoprimo è un numero che, pur non essendo primo, soddisfa alcune proprietà forti che devono essere necessariamente soddisfatte dai primi, ovvero rispetto a una serie di test si comporta analogamente ad un numero primo. La definizione di numero pseudoprimo dipende quindi dal contesto, e da cosa si intende per "comportarsi come un numero primo". I numeri pseudoprimi appaiono spesso come output di algoritmi che ricercano numeri primi, usando alcune proprietà forti che questi devono soddisfare. (it)
- 유사 소수(pseudo primes)는 불완전하나마 소수를 생성해내는 생성함수를 지칭한다. 또는 그러한 생성함수를 통해서 만들어지는 소수를 말한다. 의사소수로도 불린다. 그러나 생성함수 그 자체로는 불완전한 것이 아니다. (ko)
- 擬素数（ぎそすう、英：pseudoprime）は、実際には素数ではない確率的素数（全ての素数に共通の性質を持つ整数）。擬素数は、それが満たす素数の特性により分類される。 擬素数という用語を全ての概素数（合成数と本当に素数である数の両方）とするものもある。 擬素数は、大きな数を素因数分解することの難しさを利用する公開鍵暗号において最も重要である。カール・ポメランスは1988年に144桁の数字を因数分解するのに1000万ドル、200桁の数を因数分解するのに1000億ドルかかると見積もっていた（今日ではこれよりずっと安くなっているが、それでも法外に高額である）。しかし、これを用いるのに必要な2つの大きな素数を見つけるのにも費用がかかるため、様々な確率的素数判定が用いられ、まれに素数ではなく合成数が不適切に素数と判定される場合もある。一方でAKS素数判定法などの決定的素数判定法では偽陽性が生じることはなく、擬素数はない。 (ja)
- Liczby pseudopierwsze – liczby naturalne, które spełniają niektóre własności charakteryzujące liczby pierwsze, ale same nie są liczbami pierwszymi. Najbardziej istotną kategorią są liczby pseudopierwsze Fermata, które spełniają warunki małego twierdzenia Fermata: ap−1 − 1 jest podzielne przez p dla pewnego a. Jeśli p nie jest pierwsza, to jest nazywana wtedy pseudopierwszą przy podstawie a. Liczba x, która jest pseudopierwsza przy każdej podstawie względnie pierwszej z x jest nazywana liczbą Carmichaela. Najmniejszą liczbą pseudopierwszą przy podstawie 2 jest 341. Nie jest to liczba pierwsza, bo 341 = 11 • 31, ale spełnia warunki twierdzenia: 2340 ≡ 1 (mod 341). Rzadkość występowania takich liczb ma znaczenie praktyczne. Przykładowo algorytmy kryptografii asymetrycznej takie jak RSA wymagają szybkiego znajdywania kilkusetcyfrowych liczb pierwszych. Standardowo generuje się w nich losową liczbę nieparzystą i testuje czy jest pierwsza. Ponieważ deterministyczne sprawdzanie tego trwałoby długo, korzysta się zwykle z probabilistycznych testów takich jak test pierwszości Fermata. Innymi kategoriami liczb pseudopierwszych są i , dla których nie ma analogów liczb Carmichaela. Odpowiadają im algorytmy testowania Solovaya-Strassena i Millera-Rabina. Istnieje nieskończenie wiele liczb pseudopierwszych przy danej podstawie (istnieje nawet nieskończenie wiele liczb Carmichaela), ale są one dosyć rzadkie. Przykładowo istnieją tylko 3 pseudopierwsze liczby przy podstawie 2 mniejsze od 1000, i tylko 245 takich liczb mniejszych od miliona. Liczby pseudopierwsze przy podstawie 2 nazywane są czasem liczbami Pouleta. Poniższa tabela zawiera pierwszych 50 takich liczb, z wytłuszczeniem tych, które są dodatkowo liczbami Carmichaela: Poniższa tabela przedstawia najmniejsze liczby pseudopierwsze przy podstawach a ≤ 200. Kolorami zaznaczono ilość czynników pierwszych. (pl)
- Pseudoprimtal är ett heltal som delar en egenskap som är gemensam för alla primtal, men som egentligen inte är primtal. Pseudoprimtal klassificeras efter vilken egenskap av primtal som de uppfyller. Enligt Fermats lilla sats gäller att om ett primal p inte delar ett tal a så gäller att p delar , men till exempel gäller att talet är delbart med fastän inte är ett primtal och 2 inte delar 341. 341 är ett . Att p inte delar a är ett nödvändigt villkor för att p ska dela , och detta oberoende av om p är primtal eller ej, ty om p delar a så delar p också och alltå inte . Vissa källor använder termen pseudoprimtal om alla troliga primtal, både sammansatta tal och faktiska primtal. Pseudoprimtal används för det mesta i asymmetrisk kryptering, som använder sig av svårigheten att faktorisera stora tal i sina primtalsfaktorer. beräknade år 1998 att det skulle kosta $10 miljoner att faktorisera ett tal med 144 siffror, och $10 miljarder att faktorisera ett 200-siffrigt tal. Men att hitta och faktorisera rätt primtal för denna användning är motsvarande dyrt, så olika sannolikhetsbaserade primtalstester används för att hitta primtal bland många, av vilka i sällsynta fall felaktigt identifiera sammansatta tal som primtal. (sv)
- Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел. Существование псевдопростых является препятствием для тестов простоты, пытающихся использовать те или иные свойства простых чисел для определения простоты данного числа. (ru)
- Um pseudoprimo é um número primo provável (um inteiro que partilha propriedades com os números primos) que não é verdadeiramente primo. Pseudoprimos são classificados de acordo com a propriedade dos primos que satisfazem. Pseudoprimos têm importância primária na criptografia de chave pública, em algoritmos que utilizam números primos grandes em seu funcionamento, e em geral se baseiam no grande custo computacional de fatorar inteiros. Muitas vezes encontrar números primos grandes deterministicamente também é um problema de custo computacional elevado, e portanto podem ser usados testes de primalidade probabilísticos, que em raros casos dão falsos positivos, identificando números compostos como primos. Tais números são classificados como pseudoprimos em relação a este teste. (pt)
- 伪素数是指满足素数的某种性质，但并不一定是素数的数。根据所满足的性质的不同可以划分不同种类的伪素数。其中最有名的伪素数是满足费马小定理的合数，即费马伪素数。 (zh)
- Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел. Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа. (uk)
|
| rdfs:comment
|
- Jako pseudoprvočísla se v teorii čísel označují taková celá čísla, která jsou sice složená, ale přitom splňují některé z testů, které dokáží většinu složených čísel odlišit od prvočísel. (Takové testy platí pro všechna prvočísla, ale většina složených čísel jim nevyhoví.) Jednotlivé druhy pseudoprvočísel jsou definovány podle konkrétních testů, kterými je nelze rozlišit od prvočísla. Základní skupinou pseudoprvočísel jsou ta definovaná na základě Malé Fermatovy věty; pokud se hovoří o „pseudoprvočíslech“ bez upřesnění, míní se jimi zpravidla právě tato. (cs)
- Els nombres pseudoprimers són els que no essent primers, verifiquen el test de primalitat de base b: Siguin un nombre enter i un altre nombre enter no primer. El nombre és pseudoprimer respecte a la base si . Els nombres pseudoprimers respecte qualsevol base són els nombres de Carmichael. (ca)
- عدد شبه أولي (بالإنجليزية: Pseudoprime) هو عدد أولي محتمل. (ar)
- Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele Möglichkeiten für solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll. Ein historisch bedeutendes Beispiel einer Pseudoprimzahl ist die Zahl . Sie ist eine Fermatsche Pseudoprimzahl zur Basis (und auch einigen anderen Basen). (de)
- Los pseudoprimos son aquellos números que, sin ser primos, verifican el test de base b, o lo que es lo mismo: Siendo n perteneciente a los números enteros, se dice que n es pseudoprimo respecto la base b si es compuesto y además verifica la congruencia: es decir, n divide a bn-1-1. Esta propiedad es un caso particular del Pequeño Teorema de Fermat y por tanto siempre se verifica para números primos. (es)
- Un nombre pseudo-premier est un nombre premier probable (un entier naturel qui partage une propriété commune à tous les nombres premiers) qui n'est en fait pas premier. Les nombres pseudo-premiers peuvent être classés selon la propriété qu'ils satisfont. (fr)
- In matematica, un numero pseudoprimo è un numero che, pur non essendo primo, soddisfa alcune proprietà forti che devono essere necessariamente soddisfatte dai primi, ovvero rispetto a una serie di test si comporta analogamente ad un numero primo. La definizione di numero pseudoprimo dipende quindi dal contesto, e da cosa si intende per "comportarsi come un numero primo". I numeri pseudoprimi appaiono spesso come output di algoritmi che ricercano numeri primi, usando alcune proprietà forti che questi devono soddisfare. (it)
- 유사 소수(pseudo primes)는 불완전하나마 소수를 생성해내는 생성함수를 지칭한다. 또는 그러한 생성함수를 통해서 만들어지는 소수를 말한다. 의사소수로도 불린다. 그러나 생성함수 그 자체로는 불완전한 것이 아니다. (ko)
- 擬素数（ぎそすう、英：pseudoprime）は、実際には素数ではない確率的素数（全ての素数に共通の性質を持つ整数）。擬素数は、それが満たす素数の特性により分類される。 擬素数という用語を全ての概素数（合成数と本当に素数である数の両方）とするものもある。 擬素数は、大きな数を素因数分解することの難しさを利用する公開鍵暗号において最も重要である。カール・ポメランスは1988年に144桁の数字を因数分解するのに1000万ドル、200桁の数を因数分解するのに1000億ドルかかると見積もっていた（今日ではこれよりずっと安くなっているが、それでも法外に高額である）。しかし、これを用いるのに必要な2つの大きな素数を見つけるのにも費用がかかるため、様々な確率的素数判定が用いられ、まれに素数ではなく合成数が不適切に素数と判定される場合もある。一方でAKS素数判定法などの決定的素数判定法では偽陽性が生じることはなく、擬素数はない。 (ja)
- Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел. Существование псевдопростых является препятствием для тестов простоты, пытающихся использовать те или иные свойства простых чисел для определения простоты данного числа. (ru)
- 伪素数是指满足素数的某种性质，但并不一定是素数的数。根据所满足的性质的不同可以划分不同种类的伪素数。其中最有名的伪素数是满足费马小定理的合数，即费马伪素数。 (zh)
- Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел. Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа. (uk)
- En nombroteorio, pseŭdoprimo estas (entjero, kiu havas propraĵojn komunajn al ĉiuj primoj), kiu estas ne reale primo. Pseŭdoprimoj povas esti klasifikitaj laŭ propraĵoj, kiujn ili kontentigas. La plej grava klaso de pseŭdoprimoj venas de malgranda teoremo de Fermat kaj de ĉi tie estas nomataj kiel pseŭdoprimoj de Fermat. Ĉi tiu teoremo diras: se p estas primo kaj a estas interprimo al p, 1≤a, tiam ap-1-1 estas per p. Se nombro x estas , a estas interprimo al x, 1≤a kaj x dividas na ax-1-1, tiam x estas pseŭdoprimo al bazo a. Nombro x, kiu estas pseŭdoprimo por ĉiu valoro de a (a estu interprimo al x), estas nombro de Carmichael. (eo)
- A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes. (en)
- Liczby pseudopierwsze – liczby naturalne, które spełniają niektóre własności charakteryzujące liczby pierwsze, ale same nie są liczbami pierwszymi. Najbardziej istotną kategorią są liczby pseudopierwsze Fermata, które spełniają warunki małego twierdzenia Fermata: ap−1 − 1 jest podzielne przez p dla pewnego a. Jeśli p nie jest pierwsza, to jest nazywana wtedy pseudopierwszą przy podstawie a. Liczba x, która jest pseudopierwsza przy każdej podstawie względnie pierwszej z x jest nazywana liczbą Carmichaela. (pl)
- Pseudoprimtal är ett heltal som delar en egenskap som är gemensam för alla primtal, men som egentligen inte är primtal. Pseudoprimtal klassificeras efter vilken egenskap av primtal som de uppfyller. Enligt Fermats lilla sats gäller att om ett primal p inte delar ett tal a så gäller att p delar , men till exempel gäller att talet är delbart med fastän inte är ett primtal och 2 inte delar 341. 341 är ett . Att p inte delar a är ett nödvändigt villkor för att p ska dela , och detta oberoende av om p är primtal eller ej, ty om p delar a så delar p också och alltå inte . (sv)
- Um pseudoprimo é um número primo provável (um inteiro que partilha propriedades com os números primos) que não é verdadeiramente primo. Pseudoprimos são classificados de acordo com a propriedade dos primos que satisfazem. (pt)
|
