Cím:	A Carmichael-számokról
Szerző(k):	Járási István
Füzet:	2000/március, 136 - 145. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   1. Bevezetés     A számítógépes hálózatokon keresztül történő kommunikáció térhódítása nyomán előtérbe került az ún. nyilvános jelkulcsú titkosítási eljárások iránti igény. A nyilvánosság ebben az esetben azt jelenti, hogy a titkosítás módja (az üzenetek kódolásának és dekódolásának elve) minden, a kommunikációban résztvevő szereplő számára ismert, így a rendszerhez bárki csatlakozhat, ha készít magának egy csakis általa ismert titkos ,,kulcsot'' (bizonyos, a rendszer által előírt szabványok szerint) és nyilvánosságra hoz (mintegy a saját ,,telefonszámaként'') egy másik kulcsot; az előbbi és a címzett nyilvános kulcsa segítségével titkosítja az általa elküldött üzenetet, amelyet a címzett a saját titkos és a feladó nyilvános kulcsa segítségével tud megfejteni. E ,,kétkulcsos'' rendszernek a részletes leírása helyett itt csupán arra a tényre utalunk, hogy az egyik ilyen, széles körben elterjedt rendszer (az RSA-séma) esetében a kulcsok előállításához két nagy (több száz jegyből álló) prímszámra van szükség, és a rendszer eleget tesz annak a kívánalomnak, hogy az $A$ által $B$-nek írt üzenetet csak $B$ képes megfejteni, viszont bárki képes meggyőződni arról, hogy az üzenet csakis $A$-tól származhatott, tehát hamisíthatatlan. Ezek az egymásnak ellentmondani látszó követelmények egy roppant ,,negatív'' ténynek köszönhetően elégíthetők ki: jelenleg nem ismert olyan algoritmus, amellyel egy sokszáz jegyű számot prímszámok szorzatára lehetne bontani ─ természetesen számítógéppel ─ kevesebb, mint néhány milliárd év leforgása alatt! Hogyan készíthet viszont magának egy résztvevő ilyen nagy prímszámot? Tegyük fel, hogy találomra választ sok nagy számot, és megnézi, van-e közöttük prím. Megmutatható, hogy ha ,,elég sokat'' választ, akkor a számok között nagy valószínűséggel talál prímet. A kérdés azonban az, hogyan döntse el egy kiválasztott $n$ számról, hogy az prímszám-e. A szám prímtényezőkre bontása, mint arra már utaltunk, reménytelennek látszó próbálkozás. Fermat tétele szerint $a^{p-1}\equiv 1\left(\text{mod}p\right)$, ha $\left(a\mathrm{,}p\right)=1$ és $p$ prím. Ennek nyomán kézenfekvőnek tűnik a következő: választ egy, az $n$-hez relatív prím $a$ egészet (ez valóban megtehető) majd kiszámítja $a^{n-1}$-nek az $n$-nel való osztási maradékát (géppel ez könnyűszerrel elvégezhető). Ha a kapott maradék nem az $1$, akkor $n$ bizonyosan nem prím. A másik esetben, ha a maradék 1, nagyon egyszerű lenne feltételezni, hogy $n$ prím; csakhogy néhány összetett $n$ szám is rendelkezik a következő tulajdonsággal: $\begin{array}{c}{\displaystyle a^{n-1}\equiv 1\left(\text{mod}n\right)\text{minden <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math>-ra, amelyre <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>a</mi><mn>,</mn><mspace width="0.5mm"></mspace><mi>n</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow><mo stretchy="false">=</mo><mn>1</mn></math>.}}\end{array}$ (1) Ezeket a számokat Carmichael-számoknak nevezzük. Ha (1) teljesül $n$-re, akkor csak abban lehetünk biztosak, hogy a kérdéses szám prím vagy Carmichael-szám. Azt hogy Carmichael-szám létezik, 1910 óta tudjuk, amikor is R. D. Carmichael megadott néhány ilyen tulajdonságú számot. Bár az első példák 1910-ből valók, az ún. Korselt-kritérium 1899-re datálódik: Egy összetett $n$ szám pontosan akkor Carmichael-szám, ha $n$ négyzetmentes, és minden $p$ prímre $p\mid n$-ből $\left(p-1\right)\mid \left(n-1\right)$ következik. Az alábbiakban ezt be is fogjuk bizonyítani. A legkisebb Carmichael-szám $3\cdot 11\cdot 17=561$, továbbiak: $5\cdot 13\cdot 17=1105$, $7\cdot 31\cdot 73=15841$. Ezt követően 1939-ben Chernick [6] talált egy univerzális formulát, amelynek segítségével Carmichael-számokat kaphatunk: $\begin{array}{c}{\displaystyle U_k\left(m\right)=\left(6m+1\right)\left(12m+1\right)\prod _{i=1}^{k-2}\left(9\cdot 2^{i}m+1\right)\mathrm{,}}\end{array}$ ha az összes tényező prím. Mások sok prímtényezős Carmichael-számokat állítottak elő: 1978-ban Yorinaga [7] legfeljebb 15 tényezősöket, Zhang [8] 1305 tényezős, Guillame és Morain [9] 5104 tényezős számokat konstruáltak. Szisztematikus kereséssel Pinch [2] megtalálta az összes Carmichael-számot ${10}^{16}$-ig. Manapság az egyik legnagyobb ismert Carmichael-számnak $1101518$ tényezője van, Günter Löh és Wolfgang Niebuhr [1] találta 1996-ban. Persze a legfontosabb kérdés az, hogy van-e végtelen sok Carmichael-szám. A válasz: igen. Ezt W. R. Alford, A. Granville és C. Pomerance [3] bizonyította be 1994-ben, nem elemi úton. A bizonyítás alapjául szolgáló heurisztikus algoritmus Erdős Páltól származik, erre később még vissza fogunk térni. Az alábbiakban megemlítünk néhány, Carmichael-számot konstruáló algoritmust: 1. Definiáljuk először a $\lambda$ függvényt: ez $n$-hez azt a legkisebb $\lambda \left(n\right)$ pozitív egészet rendeli, amelyre $a^{\lambda \left(n\right)}\equiv 1\left(\text{mod}n\right)$ minden, az $n$-hez relatív prím $a$ egészre teljesül. A $\lambda$ függvénynek fontos tulajdonsága, hogy $n=\prod _{i=1}^k{p}_i^{{\alpha }_i}$ esetén $\begin{array}{c}{\displaystyle \lambda \left(n\right)=\left[\lambda \left(p_1^{{\alpha }_1}\right)\mathrm{,}\text{...}\mathrm{,}\lambda \left(p_k^{{\alpha }_k}\right)\right]\mathrm{,}}\end{array}$ és az is belátható, hogy $\begin{array}{c}{\displaystyle \lambda \left(p_i^{{\alpha }_i}\right)=\{{\displaystyle \begin{array}{c}\hfill {\displaystyle \phi \left(p_i^{{\alpha }_i}\right)=p_i^{{\alpha }_i-1}\left(p_i-1\right)\mathrm{,}\text{<span style="font-weight: normal;font-style: normal;"> ha </span>}{p}_i>2\text{<span style="font-weight: normal;font-style: normal;"> vagy </span>}{\alpha }_i\le 2}\\ \hfill {\displaystyle 2^{{\alpha }_i-2}\mathrm{,}\text{<span style="font-weight: normal;font-style: normal;"> ha </span>}{p}_i=2\text{<span style="font-weight: normal;font-style: normal;"> és </span>}{\alpha }_i>2}\end{array}}}\end{array}$ ($\phi$ az Euler-függvényt és $\left[\text{...}\right]$ a legkisebb közös többszöröst jelöli). Löh és Niebhur algoritmusának alapja R. D. Carmichael tétele, mely szerint egy összetett $N$ szám pontosan akkor Carmichael-szám, ha $N\equiv 1\left(\text{mod}\lambda \left(N\right)\right)$. Legyen $N$ a keresett Carmichael-szám. Az algoritmus egy adott $L$ számmal indul, amelyre $L=\lambda \left(N\right)$ teljesül majd. Ezután meghatározzuk $N$ összes lehetséges prímosztóját, tekintetbe véve a Carmichael-féle $\lambda$ függvény tulajdonságait és a Korselt-kritérium alábbi következményét: Legyen $S$ az $N$ prímosztóinak a halmaza, az $S$-beli prímek szorzatának a maradéka $L$-lel osztva legyen $k$. Ha $k=1$, akkor $S$ elemeinek szorzata Carmichael-szám. Ha $k>1$, akkor megkeressük az $S$-nek egy olyan valódi $T$ részhalmazát, amelyben az elemek szorzata szintén $k$ maradékot ad $L$-lel osztva. Az $S$-nek a $T$-be nem tartozó elemeit összeszorozva kapunk Carmichael-számot. 2. A következő eljárás segítségével határozta meg R. G. E. Pinch [2] a Carmichael-számokat ${10}^{15}$-ig. Két eredményt használt: az egyik N. G. W. H. Beeger [11]-től származik 1950-ből: ha $r>q>p$ prímek és $pqr$ Carmichael-szám, akkor $2p^2>q$ és $p^3>r$. Ezt később Duparc [12] általánosította: ha $q$, $r$ prímek és $mqr$ Carmichael-szám, akkor $2m^2>q$ és $m^3>r$. Ezeket speciális esetekre egyébként R. G. E. Pinch is belátja az említett cikkben, az általános eset szép és rövid bizonyítása például [10]-ben található meg. Az eljárás tulajdonképpen megkeresi minden rögzített $d$-re a $d$ prímtényezős Carmichael-számokat ${10}^{15}$-ig úgy, hogy rögzít $d-2$ darab prímet a Korselt-kritérium már említett következményét figyelembe véve, és ezekhez keres a fenti tulajdonságok és még néhány egyéb tulajdonság segítségével két új prímtényezőt. 3. H. Dubner [4] is foglalkozott Carmichael-szám konstrukciós algoritmusokkal, cikkében egyiptomi törtek segítségével állít elő Carmichael-számokat. Konstrukciójának az a lényege, hogy minden $p_i$ prímtényezőt $a_{i}SM+1$ alakban ír fel. Ekkor a Korselt-kritériumból kapjuk, hogy minden prímtényezőre $\frac{SG}{a_i}$ egész, ahol $S$ az $a_i$-k összege, $G$ pedig egy igen bonyolult kifejezés. Ekkor, mivel $G$ tulajdonságai nehezen meghatározhatóak, $S$-re teszünk feltételt. Ha $S$-nek osztója minden $a_i$, akkor a kritérium teljesül, és a prímek szorzata Carmichael-szám lesz. Ez a feltétel elvezet a tökéletes és a majdnem tökéletes számok elméletéhez, ami kapcsolódik az egyiptomi törtek kérdésköréhez. 4. A legfontosabb algoritmus Erdős Pál nevéhez fűződik. Mint már említettük, végül ennek alapján sikerült bizonyítani azt, hogy végtelen sok Carmichael-szám létezik. A heurisztikus eljárásban olyan $L$-et keresünk, amelyhez sok olyan $p$ prímszám van, amelyre $p-1$ osztója $L$-nek. Ha ezek közül néhánynak a szorzata $L$-lel osztva 1 maradékot ad, akkor ez a szorzat Carmichael-szám. Valóban, a $p-1$ számok osztják $L$-et, amire nézve a szorzat 1-gyel kongruens, így a Korselt-kritérium alapján a szorzat Carmichael-szám. A Carmichael-számok elméletében nagyon fontos a Korselt-kritérium. Ennek nem elemi bizonyítása ismert, ld. [10] (a kritériumot csoportelméleti eszközökkel bizonyítja a szerző). Ebben a cikkben olyan bizonyítást mutatunk be a kritériumra, amely nem használja a csoport fogalmát, és rámutatunk néhány fontosabb következményre, mint például arra, hogy miért nincs páros Carmichael-szám. A cikk második részében egy olyan algoritmust írunk le, amely viszonylag gyorsan tud már ismert Carmichael-számokból továbbiakat előállítani . A legnagyobb így konstruált Carmichael-szám a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle 7\cdot 37\cdot 541\cdot 12739\cdot 10317781\cdot 22554667081\cdot 447063138358143121\cdot }\\ \hfill {\displaystyle \cdot 30950858908976766878175943602213931188237121=}\\ \hfill {\displaystyle =5747734003220319000778899499188473399570423543440246391461042013626283371921438393026241\mathrm{.}}\end{array}}}\end{array}$     2. A Korselt-kritérium elemi bizonyítása     Az alábbiakban bebizonyítjuk a Korselt-kritériumot. Ehhez két segédtételen keresztül jutunk el. Közülük igazán csak az elsőre lesz szükségünk, a másodikat csupán arra fogjuk használni, hogy az egyik tételre kétféle bizonyítást is adhassunk.   1. Lemma. Legyenek $a$, $n$, $x$, $y$ pozitív egészek, $\left(a\mathrm{,}n\right)=1$, $x>y$ és $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccc}\hfill {\displaystyle a^x}& {\displaystyle \equiv 1\left(\text{mod}n\right)\mathrm{,}}\hfill & \hfill {\displaystyle \left(1\right)}\\ \hfill {\displaystyle a^y}& {\displaystyle \equiv 1\left(\text{mod}n\right)\mathrm{.}}\hfill & \hfill {\displaystyle \left(2\right)}\end{array}}}\end{array}$ Ekkor $a^{\left(x\mathrm{,}y\right)}\equiv 1\left(\text{mod}n\right)$.   Bizonyítás. Felhasználjuk, hogy ha $z=\left(x\mathrm{,}y\right)$, akkor léteznek olyan $c$, $d$ egészek, amelyekre $z=cx+dy$. Ha (1)-et és (2)-t ezekre a hatványokra emeljük, akkor azt kapjuk, hogy $a^{|c|x}\equiv 1\left(\text{mod}n\right)$ és $a^{|d|y}\equiv 1\left(\text{mod}n\right)$. Legyen $r=|c|x$ és $s=|d|y$, ekkor az előzőek $a^r\equiv 1\left(\text{mod}n\right)$ és $a^s\equiv 1\left(\text{mod}n\right)$ alakba írhatóak; tegyük fel, hogy például $r>s$, akkor $r-s=cx+dy=z$. Kivonva az utolsó kongruenciát az előzőből: $a^r-a^s=a^s\left(a^{r-s}-1\right)\equiv 0\left(\text{mod}n\right)$, és így $a^s\left(a^{r-s}-1\right)=kn$ egy alkalmas egész $k$-ra. De $\left(a\mathrm{,}n\right)=1$, így $n\mid a^{r-s}-1$, vagyis $a^z=a^{r-s}\equiv 1\left(\text{mod}n\right)$.   2. Lemma. Legyenek $p_1$, $\text{...}$, $p_k$ páronként különböző prímek, és legyen $n=p_1\cdot \text{...}\cdot p_k$. Ekkor $\begin{array}{c}{\displaystyle \sum _{i=1}^k{\left(\frac{n}{p_i}\right)}^{p_i-1}\equiv 1\left(\text{mod}n\right)\mathrm{.}}\end{array}$   Bizonyítás. Mivel $\left(\frac{n}{p_i}\mathrm{,}{p}_i\right)=1$, felírhatjuk minden $i$-re a kis Fermat tételt: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle {\left(\frac{n}{p_i}\right)}^{p_i-1}\equiv 1\left(\text{mod}{p}_i\right)\mathrm{,}}\\ \multicolumn{2}{c}{\text{<div style="line-height: -5pt"> </div>}}\\ \multicolumn{2}{c}{\text{<br>azaz}}\\ \multicolumn{2}{c}{\text{<div style="line-height: -5pt"> </div>}}\\ \hfill {\displaystyle {\left(\frac{n}{p_i}\right)}^{p_i-1}-1=c_i\cdot p_i\mathrm{,}}\end{array}}}\end{array}$ alkalmas $c_i$ pozitív egészekkel. Szorozzuk össze ezeket az egyenlőségeket: $\begin{array}{c}{\displaystyle \prod _{i=1}^k\left({\left(\frac{n}{p_i}\right)}^{p_i-1}-1\right)=n\cdot \prod _{i=1}^k{c}_i\mathrm{.}}\end{array}$ A bal oldalon a szorzások elvégzése után egy szorzatokból álló összeget kapunk; ezt az összeget három részre oszthatjuk: az első részben szerepeljenek azok a tagok, amelyek két vagy több ${\left(\frac{n}{p_i}\right)}^{p_i-1}$alakú tényezőt tartalmaznak. Ezek a tagok oszthatóak $n$-nel, így átvihetjük őket a jobb oldalra, ami így osztható marad $n$-nel. A második rész a $\begin{array}{c}{\displaystyle {\left(-1\right)}^{k-1}\cdot \sum _{i=1}^k{\left(\frac{n}{p_i}\right)}^{p_i-1}}\end{array}$ tag, a harmadik pedig ${\left(-1\right)}^k$. Ezek után az egyenletet így írhatjuk: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle {\left(-1\right)}^{k-1}\cdot \sum _{i=1}^k{\left(\frac{n}{p_i}\right)}^{p_i-1}+{\left(-1\right)}^k=A\cdot n\mathrm{,}}\\ \multicolumn{2}{c}{\text{<div style="line-height: -5pt"> </div>}}\\ \multicolumn{2}{c}{\text{<br>vagyis}}\\ \multicolumn{2}{c}{\text{<div style="line-height: -5pt"> </div>}}\\ \hfill {\displaystyle \sum _{i=1}^k{\left(\frac{n}{p_i}\right)}^{p_i-1}-1\equiv 0\left(\text{mod}n\right)\mathrm{.}}\end{array}}}\end{array}$ Most pedig következik a Korselt-kritérium bizonyítása. Ezt három lépésben tesszük meg.   1. Tétel. Ha $n$ Carmichael-szám, akkor négyzetmentes.   Bizonyítás. Tegyük fel, hogy $n=p^{2}m$, ahol $p$ prím, és $m$ egész. Írjuk fel $n$ prímtényezős felbontását: $\begin{array}{c}{\displaystyle n=p^{\alpha }\cdot \prod _{i=1}^k{p}_i^{{\alpha }_i}\mathrm{,}}\end{array}$ ahol $\alpha \ge 2$. Az $n$ Carmichael-szám, így ha $\left(a\mathrm{,}n\right)=1$, akkor $a^{n-1}\equiv 1\left(\text{mod}n\right)$. Az $\left(a\mathrm{,}n\right)=1$ miatt $\left(a\mathrm{,}p\right)=1$, és az előző kongruenciából $a^{n-1}\equiv 1\left(\text{mod}p\right)$. Felírhatjuk az Euler‐Fermat tételt $a$-ra és $p^{\alpha }$ -ra, mivel $\left(a\mathrm{,}{p}^{\alpha }\right)=1$: $\begin{array}{c}{\displaystyle a^{p^{\alpha -1}\left(p-1\right)}\equiv 1\left(\text{mod}{p}^{\alpha }\right)\mathrm{.}}\end{array}$ Felhasználva az első lemmát: ha $z=\left(n-\mathrm{1,}{p}^{\alpha -1}\left(p-1\right)\right)$, akkor $a^z\equiv 1\left(\text{mod}{p}^{\alpha }\right)$. Vizsgáljuk meg $z$-t! Látható, hogy $z=\left(n-\mathrm{1,}{p}^{\alpha -1}\left(p-1\right)\right)=\left(n-\mathrm{1,}p-1\right)$, mivel ha $p^{\alpha -1}\mid n$, akkor $p$ nem oszthatja $\left(n-1\right)$-et. Mivel $\alpha \ge 2$, azért $a^z\equiv 1\left(\text{mod}{p}^2\right)$. Viszont $z=\left(n-\mathrm{1,}p-1\right)$, így létezik olyan $t\in {\text{Z}}^{+}$, hogy $p-1=zt$. Így ha az utolsó kongruenciát a $t$-edik hatványra emeljük, akkor azt kapjuk, hogy $a^{p-1}\equiv 1\left(\text{mod}{p}^2\right)$. Legyen $c=p-p^{\phi \left(m\right)+1}$, ekkor az Euler‐Fermat tétel szerint $c\equiv p-p=0\left(\text{mod}m\right)$, és nyilván