Cím: A Carmichael-számokról
Szerző(k):  Járási István 
Füzet: 2000/március, 136 - 145. oldal  PDF file
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 ap-11(modp), ha (a,p)=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 an-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:
an-11(modn)minden  a-ra, amelyre  (a,n)=1.(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 pn-ből (p-1)(n-1) következik.
Az alábbiakban ezt be is fogjuk bizonyítani. A legkisebb Carmichael-szám 31117=561, továbbiak: 51317=1105, 73173=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:
Uk(m)=(6m+1)(12m+1)i=1k-2(92im+1),
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 1016-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 λ függvényt: ez n-hez azt a legkisebb λ(n) pozitív egészet rendeli, amelyre aλ(n)1(modn) minden, az n-hez relatív prím a egészre teljesül. A λ függvénynek fontos tulajdonsága, hogy n=i=1kpiαi esetén
λ(n)=[λ(p1α1),...,λ(pkαk)],
és az is belátható, hogy
λ(piαi)={φ(piαi)=piαi-1(pi-1), ha pi>2 vagy αi22αi-2, ha pi=2 és αi>2
(φ az Euler-függvényt és [...] 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 N1(modλ(N)).
Legyen N a keresett Carmichael-szám. Az algoritmus egy adott L számmal indul, amelyre L=λ(N) teljesül majd. Ezután meghatározzuk N összes lehetséges prímosztóját, tekintetbe véve a Carmichael-féle λ 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 1015-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 2p2>q és p3>r. Ezt később Duparc [12] általánosította: ha q, r prímek és mqr Carmichael-szám, akkor 2m2>q és m3>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 1015-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 pi prímtényezőt aiSM+1 alakban ír fel. Ekkor a Korselt-kritériumból kapjuk, hogy minden prímtényezőre SGai egész, ahol S az ai-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 ai, 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
73754112739103177812255466708144706313835814312130950858908976766878175943602213931188237121==5747734003220319000778899499188473399570423543440246391461042013626283371921438393026241.

 
 
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, (a,n)=1, x>y és
ax1(modn),(1)ay1(modn).(2)
Ekkor a(x,y)1(modn).

 
Bizonyítás. Felhasználjuk, hogy ha z=(x,y), 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|x1(modn) és a|d|y1(modn). Legyen r=|c|x és s=|d|y, ekkor az előzőek ar1(modn) és as1(modn) 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: ar-as=as(ar-s-1)0(modn), és így as(ar-s-1)=kn egy alkalmas egész k-ra. De (a,n)=1, így nar-s-1, vagyis az=ar-s1(modn).
 
2. Lemma. Legyenek p1, ..., pk páronként különböző prímek, és legyen n=p1...pk. Ekkor
i=1k(npi)pi-11(modn).

 
Bizonyítás. Mivel (npi,pi)=1, felírhatjuk minden i-re a kis Fermat tételt:
(npi)pi-11(modpi),
 

azaz
 
(npi)pi-1-1=cipi,
alkalmas ci pozitív egészekkel. Szorozzuk össze ezeket az egyenlőségeket:
i=1k((npi)pi-1-1)=ni=1kci.
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 (npi)pi-1alakú 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
(-1)k-1i=1k(npi)pi-1
tag, a harmadik pedig (-1)k. Ezek után az egyenletet így írhatjuk:
(-1)k-1i=1k(npi)pi-1+(-1)k=An,
 

vagyis
 
i=1k(npi)pi-1-10(modn).
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=p2m, ahol p prím, és m egész. Írjuk fel n prímtényezős felbontását:
n=pαi=1kpiαi,
ahol α2. Az n Carmichael-szám, így ha (a,n)=1, akkor an-11(modn). Az (a,n)=1 miatt (a,p)=1, és az előző kongruenciából an-11(modp). Felírhatjuk az Euler‐Fermat tételt a-ra és pα -ra, mivel (a,pα)=1:
apα-1(p-1)1(modpα).
Felhasználva az első lemmát: ha z=(n-1,pα-1(p-1)), akkor az1(modpα). Vizsgáljuk meg z-t! Látható, hogy z=(n-1,pα-1(p-1))=(n-1,p-1), mivel ha pα-1n, akkor p nem oszthatja (n-1)-et. Mivel α2, azért az1(modp2). Viszont z=(n-1,p-1), így létezik olyan tZ+, hogy p-1=zt. Így ha az utolsó kongruenciát a t-edik hatványra emeljük, akkor azt kapjuk, hogy ap-11(modp2). Legyen c=p-pφ(m)+1, ekkor az Euler‐Fermat tétel szerint cp-p=0(modm), és nyilván cp(modp2); speciálisan (c+1,n)=1. Legyen a=c+1; a binomiális tétel szerint (alkalmas b pozitív egésszel)
ap-1=(c+1)p-1=bc2+(p-1)c+1(p-1)p+1=p2-p+11-p1(modp2).
Ellentmondásra jutottunk, tehát nincs olyan p prím, amelyre p2n.
 
2. Tétel. Ha n Carmichael-szám, és p az n prímosztója, akkor (p-1)(n-1).
 
Bizonyítás. Mivel n Carmichael-szám, n négyzetmentes, és an-11(modn) minden a-ra, ha (a,n)=1. Felhasználva a Carmichael-féle λ függvényt és tulajdonságait, azt kapjuk, hogy aλ(n)1(modn). Mivel n=p1...pk, azért λ(n)=[p1-1,...,pk-1], és az 1. lemma miatt λ(n)(n-1). Így ha pn és n Carmichael-szám, akkor (p-1)(n-1).
 
3. Tétel. Ha n=p1...pk, ahol p1, ..., pk páronként különböző prímek, továbbá (pi-1)(n-1) (i=1, ..., k), akkor n Carmichael-szám.
 
Bizonyítás. Legyen (a,n)=1, és írjuk fel a kis Fermat tételt minden pi-re ((a,pi)=1, i=1, ..., k):
1ap1-1(modp1),1apk-1(modpk).
Emeljük az i-edik kongruenciát a ci=(n-1)(pi-1)-edik hatványra:
an-11(modp1),an-11(modpk).
Ezen a ponton két lehetőség közül választhatunk: Először nézzük meg az egyszerűbbet. A fenti kongruenciákból következik, hogy an-1-1 osztható p1, ..., pk-val, tehát an-11(modn). A másik lehetőség kissé hosszabb. Tekintsük a kongruenciákat úgy, mint egy szimultán kongruenciarendszert az an-1-re mint ismeretlenre nézve. Ezek után, felhasználva a kínai maradéktételt és a 2. lemmát, kapjuk, hogy an-11(modn).
 

A Korselt-kritérium bizonyítása után lássuk annak néhány következményét:
*1.pj nem oszthatja (pi-1)-et (1j<ik), mert ez ellentmondana annak, hogy (pi-1)(n-1) és pjn egyszerre teljesül. Ezért nincs páros Carmichael-szám.
*2.Ha n Carmichael-szám és van 4k+1 alakú prímosztója, akkor a 4k-1 alakú prímosztóinak száma páros. Hasonló igaz 4 helyett 6-ra is. Beláa hosszadalmas.
*3.Minden Carmichael-számnak legalább három különböző prímosztója van. Ha ugyanis csak két prímosztója lenne, azaz n=pq, ahol p, q prímek, akkor:
pq-1q-1=pq-p+p-1q-1=p+p-1q-1 egész,
így p-1q-1 egész, és ugyanígy q-1p-1 is egész; tehát p-1q-1=1, amiből p=q következik, de ez ellentmond a négyzetmentes tulajdonságnak.
 
3. Carmichael-számok konstruálása Carmichael-számokból
 
 

Az alábbiakban azt vizsgáljuk meg, miként lehet és érdemes Carmichael-számokat konstruálni már ismertekből. Elsőként a számtani sorozat lehetőségét vizsgáljuk. Megmutatjuk, hogy ilyen módon csak nagyon korlátozott mértékben juthatunk Carmichael-számokhoz, sőt az azoknál lényegesen gyakoribb négyzetmentes számokhoz.
 
4. Tétel. A négyzetmentes számok halmazában nincs végtelen számtani sorozat.
 
Bizonyítás. Tegyük fel, hogy létezik egy kívánt sorozat. Legyen p1p2...pn az első elem és d a differencia. Ekkor a sorozat minden eleme p1p2...pn+kd alakba írható, és ezek a számok négyzetmentesek. Tehát pi2 nem lehet osztója p1...pn+kd-nek semmilyen i-re és k-ra. Minden i-re két lehetőség van: (d,pi)=1 vagy (d,pi)=pi. Ha (d,pi)=1, akkor létezik olyan x, amelyre
xd-p1...pi-1pi+1...pn(modpi),
így pi-vel beszorozva:
p1...pn+pixd0(modpi2);
tehát ekkor k=pix választással egy olyan tagját találtuk meg a sorozatnak, amelynek van négyzetszám osztója. Ezért minden i-re (d,pi)=pi, tehát d=p1...pnd1.
A sorozat k-adik eleme:
p1...pn+kd=p1...pn+kp1...pnd1=p1...pn(1+kd1).
A fenti okoskodást folytathatjuk d1-re: ha (d1,pi)=1, akkor pi-hez létezik olyan xi, amelyre
xid1-1(modpi),
és akkor pixid1+1, tehát pi2p1...pn(xid1+1), ellentmondás.
Tehát azt kaptuk, hogy pi2d minden i=1, ..., n-re. Legyen a=p1...pn; ezzel a jelöléssel minden elem a+ka2d2 alakba írható. De a+ka2d2=a(1+kad2)-ben
k=ad2+2-t helyettesítve:
a(1+kad2)=a(1+(ad2+2)ad2)=a(1+2ad2+(ad2)2)=a(1+ad2)2.
Így ellentmondásra jutottunk, megmutattuk hogy minden végtelen számtani sorozatban van olyan elem, amelynek osztója egy négyzetszám.
 
Megjegyzés. Ugyanennek a tételnek egy elegánsabb és jól általánosítható bizonyítását adta Wladyslaw Narkiewicz egy levelében, a tétel bizonyítását egy két tagból álló szimultán kongruenciarendszer megoldására vezetve vissza.
 
A következőkben megvizsgáljuk, mikor lehet két Carmichael-szám szorzata is Carmichael-szám. Ezzel azonban a négyzetmentes tulajdonság miatt Carmichael-számok véges halmazából csak véges halmazt tudunk előállítani. A λ(N) függvény segítségével egyszerű választ adhatunk a fenti kérdésre. A kapott feltétel a Korselt-kritérium következménye.
 
5. Tétel. Legyenek N és Q Carmichael-számok. Az NQ szám pontosan akkor Carmichael-szám, ha (N,Q)=1, valamint N1(modλ(Q)) és Q1(modλ(N)).
 
Bizonyítás. (N,Q)=1 szükséges a szorzat négyzetmentességéhez. A Korselt-kritériumot fogjuk használni: NQ Carmichael-szám, ha pNQ-ból p-1NQ-1 következik. Legyen N=p1...pk, Q=q1...qs. Ezzel a jelöléssel a feltétel az, hogy az NQ-1pi-1 és az NQ-1qj-1 hányadosok értéke egész legyen.
Alakítsuk át ezeket a kifejezéseket:
NQ-1pi-1=NQ-Q+Q-1pi-1=Q(N-1)pi-1+Q-1pi-1.
Mivel N Carmichael-szám, azért N-1pi-1 egész, így Q-1pi-1-nek kell egésznek lennie, ha i=1, ..., k; ez viszont akkor és csak akkor teljesül, ha Q1(mod[p1-1,...,pk-1]). A Carmichael-függvényt használva ez éppen azt jelenti, hogy Q1(modλ(N)). A másik kongruencia ugyanígy látható be.
 
A következőkben azt az esetet vizsgáljuk meg, amikor nem egy Q Carmichael számot, hanem csupán egy négyzetmentes R számot választunk az N-hez szorzónak. Ekkor, ha N=p1...pk, R=q1...qs, annyit mondhatunk, hogy
NR-R+R-1pi-1=R(N-1)pi-1+R-1pi-1
szerint R1(modλ(N)) szükséges, de a másik esetben ez nem működik, mivel nem tudjuk, van-e egyáltalán olyan j, amelyre R-1qj-1 egész. Az előző bizonyítás gondolatmenetét használva mindössze annyit állíthatunk, hogy NRqj-1qj-1 egész kell legyen minden j=1, ..., s-re. Ezek alapján konstruálhatunk egy algoritmust ilyen R-ek keresésére, de az bonyolult és lassú lenne a négyzetmentesség vizsgálata miatt. Ezért N-et csak egyetlen prímmel szorozzuk; legyen ez a prím q. Ekkor a Korselt-kritérium alapján
Nq-1q-1=Nq-N+N-1q-1=N+N-1q-1 egész,
így N-1q-1 egész, és ha N=p1...pk és i=1,...,k, akkor
Nq-1pi-1=Nq-q+q-1pi-1=q(N-1)pi-1+q-1pi-1 egész.
Mivel N Carmichael-szám, azért q-1pi-1 egész kell legyen minden i=1,...,k-ra. Ez azt jelenti, hogy [p1-1,...,pk-1]q-1, vagyis λ(N)(q-1).
Ezek és az előző megállapítások alapján, ha létezik olyan k, amelyre q=kλ(N)+1 prím, és N-1kλ(N) egész, akkor Nq Carmichael-szám. Dirichlet tétele szerint az nλ(N)+1 (nZ+) számtani sorozatban végtelen sok prímszám található, így van rá esélyünk, hogy kívánt alakú prímet találjunk. Vajon találhatunk-e egy újabb p prímet Nq-hoz? Talán igen. Az előzőek alapján p-t így kereshetjük: kiszámítjuk λ(Nq)-t és Nq-1λ(Nq)-t, meghatározzuk Nq-1λ(Nq) összes osztóját, ezeket megszorozzuk λ(Nq)-val, és hozzáadunk 1-et, végül megnézzük, hogy ezek közül melyik prím. Ebben az algoritmusban λ(Nq) nagyon fontos, és úgy tűnik, nehéz kiszámítani. Szerencsére ez nincs így. Ha ismerjük λ(N)-et az előző ciklusból, akkor könnyen kiszámítható λ(Nq):
λ(N)=[p1-1,...,pk-1],λ(Nq)=[p1-1,...,pk-1,q-1],de  q=k1λ(N)+1, ígyλ(Nq)=[p1-1,...,pk-1,k1[p1-1,...,pk-1]]=k1[p1-1,...,pk-1]=k1λ(N).

Ezek alapján a következő algoritmust alkothatjuk meg:
*1.[inicializálás] m0:=λ(N), i:=1, k0:=1;
*2.[a Carmichael függvény értéke] mi:=ki-1(j)mi-1;
*3.ri:=Ni-1(j)-1mi;
*4.meghatározzuk az összes olyan j-t, amelyre ki(j)ri; legyen a megfelelő j indexek halmaza J;
*5.[prímtesztek] a ki(j)mi+1 számok prímségi tesztelése; legyen A azon j indexek halmaza, amelyekre ki(j)mi+1 prím; ha A üres, akkor a ciklus véget ér;
*6.[az újabb Carmichael-szám] Ni(j):=Ni-1(l)(ki(j)mi+1);
*7.[ciklusléptetés] vissza a 2. lépésre: i:=i+1;
Az első lépés előtt m0=λ(N)-et és k0=1-et kell megadni az induláshoz, ahol N a kiindulásul vett Carmichael-szám. Mivel egy ciklusban több ki(j)mi+1 alakú prímet is találhatunk, azért ezt az algoritmust kombinálni kell egy backtrack (visszaléptető) algoritmussal, hogy megtaláljuk az összes lehetséges Carmichael-számot. Ez az algoritmus egyszerűnek tűnik, azonban tartalmaz néhány bonyolult számítást, amelyek hosszú időt vehetnek igénybe.
A kritikus lépések a következők:
*1.Ni-1(l)-1mi kiszámítása;
*2.ki(j)-k keresése;
*3.a ki(j)mi+1 számok prímségi tesztelése.
Az utolsó problémára nagyon jó és gyors tesztek vannak. Véleményem szerint, ha a három esetet párhuzamosan kezeljük, akkor ezzel eléggé meggyorsíthatjuk az algoritmust. Az összekötő kapocs a számok ábrázolása. Ha a számokat prímhatványok szorzataként ábrázolnánk, akkor nagyon gyorsan lehetne osztani, osztókat meghatározni és n-1 prímfelbontása ismeretében viszonylag gyorsan meg lehet határozni n prím voltát. Tehát ha találnánk egy viszonylag gyors algoritmust n prímfelbontására n-1 prímfelbontásának ismeretében, akkor az egész algoritmus sokat gyorsulna. A prímtesztben a ki(j)mi+1 kifejezésben ki(j) is nagyon fontos. Szerencsére ri nagyságát jól tudjuk becsülni Ni-2 nagyságával:
ri=Ni-1-1mi=Ni-2(ki-1(j)mi-1+1)-1ki-1(j)mi-1=Ni-2+Ni-2-1mi-11ki-1(j)=Ni-2+ri-1ki-1(j),
ezért riNi-2 minden lehetséges i-re, Ni-2 értéke pedig minden ciklusban egy prímszorzóval növekszik, ri is legalább így növekszik, és minden reményünk megvan arra, hogy egy nagy számnak sok ki(j) osztója legyen.
 
 
Irodalomjegyzék
 
 


*[1]G. Löh és W. Niebuhr: A new algorithm for constructing large Carmichael numbers, Math. of Comput. 65 (1996) 823‐836.
*[2]R. G. E. Pinch: The Carmichael numbers up to 1015, Math. of Comput. 61 (1993), 381‐391.
*[3]W. R. Alford, A. Granville és C. Pomerance: There are infinitely many Carmichael numbers, Annals of Math., 140 (1994), 703‐722.
*[4]H. Dubner: Carmichael numbers and egyptian fractions, Math. Japonica 43 (1996), 411‐419.
*[5]D. E. Knuth: The art of computer programming, Vol 2., 2. edition, section 4.5.4.
*[6]J. Chernick: On Fermat's simple theorem, Bull. Amer. Math. Soc. 45 (1939), 269‐274.
*[7]M. Yorinaga: Numerical computations of Carmichael numbers, Math. J. Okayama Univ. 20 (1978), 151‐163.
*[8]M. Zhang: Searching for large Carmichael numbers, Sichuan Daxue Xuebao 29, 472‐474 (1992).
*[9]D. Guillame és F. Morain: Building Carmichael numbers with a large number of prime factors and generalization to other numbers, preprint, June (1992).
*[10]C. Pomerance: Carmichael numbers, 28th Nederlands Matematisch Congres, Delft, April 22, 1992.
*[11]N. G. W. H. Beeger: On composite numbers n for which an-11(modn) for every a prime to n, Scripta Math. 16, (1950) 133‐135.
*[12]H. J. A. Duparc: On Carmichael numbers, Simon Stevin 29, (1952) 21‐24.

 
 Járási István
matematikus egyetemi hallgató,
Debreceni Egyetem