Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9.3. Négyzetszámok keresése

9.3. Négyzetszámok keresése

Ebben a pontban azt igazoljuk, hogy ha „elég sok” különböző pozitív egész egyikének sincs egy adott küszöbnél nagyobb prímosztója, akkor a számok közül kiválasztható néhány (esetleg csak egy, esetleg az összes), amelyek szorzata négyzetszám. (Ennek egy konkrét számokkal megfogalmazott változata a 3.3.12 feladatban szerepelt.) Ez a kérdés és annak lineáris algebrai megoldása meglepő módon a nagy számok prímtényezőkre bontásával kapcsolatban fontos szerepet játszik. A prímfelbontásra ugyanis nem ismeretes „gyors” algoritmus; egy (a gyakorlatban is használt) „viszonylag gyors” algoritmust éppen a szóban forgó feladat segítségével konstruálhatunk. (Mint tudjuk, a hatékony prímfelbontási algoritmus kérdése szorosan összefügg az ún. nyilvános jelkulcsú titkosírással, amelyet világszerte alkalmaznak a katonai, diplomáciai és üzleti életben egyaránt.) A feladat másik érdekessége, hogy a megoldásánál — az esetleg egyedül fontosnak hitt valós (vagy racionális vagy komplex) test helyett — természetes módon jelennek meg a modulo 2 maradékosztályok. További izgalmas és részben megoldatlan problémákhoz vezet, ha négyzetszámok helyett köbszámokat vagy tetszőleges magasabb hatványokat vizsgálunk.

9.3.1 Tétel

Legyenek 0<p1<…<pk tetszőleges prímszámok és 0<c1<…<ck+1 olyan egészek, amelyek egyikének sincs a pi-ktől különböző prímosztója. Ekkor a cj számok közül kiválasztható néhány különböző (esetleg csak egy, esetleg az összes) úgy, hogy a szorzatuk négyzetszám legyen.❶

Azonnal látszik, hogy a tétel k+1 helyett k darab cj-re már nem igaz, legyen pl. cj=pj.

Első bizonyítás: Képezzük a cj számainkból valahány különbözőnek a szorzatát minden lehetséges módon. Így 2k+1–1 szorzatot kapunk. Most vizsgáljuk meg, hogy egy (tetszőleges) szám hányféle lehet abból a szempontból, hogy prímtényezős felbontásában a pi prímek kitevője páros vagy páratlan; ez 2k lehetőség. A skatulyaelv alapján tehát a szorzataink között lesz két olyan, amelyekben az egyes prímek kitevői azonos paritásúak. Ha most ebből a két szorzatból elhagyjuk a közös tényezőket, és a megmaradtakat összeszorozzuk, akkor olyan szorzathoz jutunk, amely négyzetszám.❷

Második bizonyítás: Legyen T=F2 a modulo 2 test, és a c1,…, ck+1 számoknak feleltessünk meg c_jTk vektorokat a következőképpen:

Egy ilyen vektor tehát a számban szereplő prímek kitevőinek a paritását mutatja, és a c_j vektorok (modulo 2 vett) összeadása a cj számok szorzásának felel meg. Ez a k+1 darab Tk-beli vektor szükségképpen lineárisan összefüggő (a modulo 2 test felett), tehát van olyan nemtriviális lineáris kombinációjuk, amely 0_-t ad. Szorozzuk össze azokat a cj számokat, amelyeknek megfelelő c_j vektorok ebben a kombinációban nemnulla (azaz 1) együtthatóval szerepelnek. Mivel a megfelelő c_j vektorok összege nulla, ezért ez a szorzat négyzetszám.❷

A két bizonyítás közül a lineáris algebrát használó második felesleges nagyágyúnak tűnik. Mégis igen nagy a jelentősége, ugyanis ez egyben gyors algoritmust is ad egy jó szorzat megkeresésére (szemben a skatulyaelves első bizonyítással): a lineáris összefüggőségnél egy (homogén) lineáris egyenletrendszert kell megoldani, például Gauss-kiküszöböléssel. Ez a tény annál a fontos gyakorlati alkalmazásnál is lényeges szerepet játszik, amikor egy nagy összetett számot akarunk tényezőkre bontani. Erre a feladatra igazán gyors algoritmus nem ismeretes (szemben azzal, amikor csak a szám prím vagy összetett voltát szeretnénk eldönteni), de a jelenleg használt leggyorsabb módszerek általában a fentiekre (is) támaszkodnak.

Az alábbiakban ezt a faktorizációs eljárást vázoljuk. Legyen N egy nagy páratlan összetett szám, a feladat N-et (nemtriviálisan) szorzattá bontani. A teljes hatványok felismerésére és felbontására egyszerűen adhatunk egy jó algoritmust (lásd a 9.3.7 feladatot), így elég azt az esetet néznünk, amikor N-nek legalább két különböző prímosztója van.

Tegyük fel, hogy

azaz N|(u+v)(u-v), de Nu±v Ekkor N és u+v legnagyobb közös osztója nyilván N-nek egy nemtriviális osztója. Ezt a legnagyobb közös osztót az euklideszi algoritmus segítségével „gyorsan” meg tudjuk határozni.

Keressünk most a (*) és (**) feltételeket kielégítő u-t és v-t. Foglalkozzunk egyelőre csak (*)-gal. Először olyan b számokat próbálunk gyártani, amelyekre b2-nek az N-nel vett (legkisebb pozitív) osztási maradéka, c, csak „kicsi” prímekkel osztható. Ilyen c-t remélhetünk, ha pl. N-nél, 2N-nél stb. egy picit nagyobb számot választunk b-nek. Rögzítsünk le egy (N-től függő) R korlátot, és a b számot akkor tartsuk meg, ha c minden prímosztója R-nél kisebb, egyébként dobjuk el, majd próbáljunk ki egy újabb b értéket stb. Ily módon gyűjtsünk össze k+1 darab bj, cj párt, ahol k=π(R) az R-ig terjedő prímek száma. Ekkor bj2cj mod N, j=1,2,k+1 Közben mindig érdemes euklideszi algoritmussal kiszámítani b és N legnagyobb közös osztóját is, és ha ez 1-nél nagyobb (de N-nél kisebb), akkor máris megkaptuk N egy nemtriviális osztóját. Azonban nem valószínű, hogy ekkora szerencsénk lenne. Így feltehetjük, hogy a kapott bj-k (és így a cj-k is) az N-hez relatív prímek.

A 9.3.1 Tételre adott második bizonyítás szerint a cj-k közül gyors algoritmussal kiválasztható néhány olyan, amelyek szorzata egy v2 négyzetszám. Az ezeknek megfelelő bj-k szorzatát jelöljük u-val, ekkor a kongruenciák összeszorzásából a kívánt u2v2(mod N) adódik.

Meg kell még vizsgálnunk, hogy (**), azaz u±v mod N is teljesül-e. Azt állítjuk, hogy legalább 1/2 valószínűséggel igen. Legyen N (általunk nem ismert, de azért létező) prímtényezős felbontása N= q1t1 qsts(s2) Ekkor az u2v2 (mod N) kongruencia ekvivalens az u2v2  mod qjtj,  j=1,2,,s kongruenciarendszerrel. Egy qt páratlan prímhatvány modulusra nézve az u2v2 (mod qt) kongruencia pontosan akkor teljesül, ha u≡±v (mod qt). Ezalól csak az jelenthetne kivételt, ha q|u+v és q|uv egyszerre állna fenn, de ekkor q|(u+v)+(uv)=2u, ahonnan q>2 miatt q|u, ami (u,N)=1 alapján lehetetlen. Így az u2v2  mod qjtj, j=1,2,,s kongruenciarendszer 2s-féleképpen valósulhat meg: minden egyes kongruenciában uv vagy u-v mod qjtj Ebből a 2s számú esetből összesen kettő olyan, amikor u≡±v (mod N), nevezetesen amikor mindegyik kongruenciában „+”, illetve mindegyik kongruenciában „–” áll. Az u és a v kiválasztását (az u2v2 (mod N) feltétel megoldásai körében) tekinthetjük lényegében véletlenszerűnek, és emiatt az egyes eseteket egyforma valószínűnek képzelve azt nyerjük, hogy 1–2/2s≥1/2 valószínűséggel u±v  mod N is teljesül. Ennek megfelelően, előbb-utóbb (de inkább előbb) szinte biztosan találunk olyan u,v párt, amelyekre (**) is érvényes, és ezzel eljutottunk N egy valódi osztójához.

Miért nem igazán hatékony ez az algoritmus sem? Az ördög a mellőzött részletekben lakozik: hogyan keressük a b-ket és hogyan válasszuk meg az R korlátot. Az első kérdésnél mély számelméleti megfontolások segítenek némileg növelni annak az esélyét, hogy alkalmas b-t találjunk. Az R kijelölésénél pedig azzal a dilemmával kell szembenézni, hogy kis R esetén kevés bj-t kell összegyűjteni, azonban ritkán akad jó b horogra, nagy R mellett pedig viszonylag gyakran találunk jó b-t, viszont igen sok kell belőlük. Itt is mély számelméleti tételek alapján lehet az optimális R-et megkapni.

A 9.3.1 Tételnek a négyzetszámok helyett köbszámokra, illetve magasabb hatványokra vonatkozó általánosításával a 9.3.1–9.3.4 feladatokban foglalkozunk.

Feladatok

9.3.1 Köbszámok. Legyenek 0<p1<…<pk tetszőleges prímszámok és 0<c1<…<ct olyan egészek, amelyek egyikének sincs a pi-ktől különböző prímosztója.

a) Mutassuk meg, hogy t≤2k esetén nem feltétlenül tudunk kiválasztani néhány különböző cj-t úgy, hogy ezek szorzata köbszám legyen.

b) Bizonyítsuk be, hogy t≥2·3k+1 esetén biztosan kiválasztható néhány különböző cj úgy, hogy ezek szorzata köbszám legyen.

c) Bizonyítsuk be, hogy tk+1 esetén biztosan kiválasztható néhány cj úgy, hogy ezek szorzata köbszám legyen, és a tényezők között mindegyik cj legfeljebb kétszer fordul elő.

M*9.3.2 Chevalley tétele. Legyen p egy pozitív prímszám és legyenek fi(x1, x2,…, xt), i=1,2,…,k olyan egész együtthatós, t-változós polinomok, amelyek konstans tagja 0 és i=1kdegfi<t Lássuk be, hogy az fi(x1, x2,…, xt)≡0 (mod p), i=1,2,…,k kongruenciarendszernek létezik nemtriviális megoldása. (Melyik ismert tételt kapjuk abban a speciális esetben, ha mindegyik polinom elsőfokú?)

*9.3.3 Köbszámok újra. Legyenek 0<p1<…<pk tetszőleges prímszámok és 0<c1<…<ct olyan egészek, amelyek egyikének sincs a pi-ktől különböző prímosztója. Bizonyítsuk be, hogy t≥2k+1 esetén biztosan kiválasztható néhány különböző cj úgy, hogy ezek szorzata köbszám legyen.

*9.3.4 Magasabb hatványok. Általánosítsuk az előző feladatot köbszámok helyett q-adik hatványokra, ahol q tetszőleges prímszám.

Megjegyzés: A megfelelő állítás (más eszközökkel) igazolható arra az esetre is, amikor q prímhatvány, azonban tetszőleges q egészre a probléma megoldatlan.

9.3.5 Összegek oszthatósága.

a) Mutassuk meg, hogy n egész számból mindig kiválasztható néhány, amelyek összege osztható n-nel.

*b) Mutassuk meg, hogy 2n–1 egész számból mindig kiválasztható n olyan, amelyek összege osztható n-nel.

9.3.6

a) Mutassuk meg, hogy bármely n>1-hez található három olyan egész szám, amelyek s négyzetösszegére n|s, de n2  s 

b) Lássuk be, hogy (n,s/n)=1 is elérhető.

9.3.7 Adjunk gyors algoritmust a teljes hatványok felismerésére és felbontására.

9.3.8 Faktorizáció. Egy másik faktorizációs eljárás vázlata a következő. Próbáljuk meg az N nagy páratlan összetett számot N=x2y2 alakban előállítani. Ennek érdekében vizsgáljuk meg rendre az xN számokra, hogy x2N négyzetszám-e. Ha felhasználjuk, hogy egy négyzetszám 3-mal, 5-tel, 7-tel, 8-cal stb. osztva csak speciális maradékot adhat, akkor ez jelentősen megkönnyíti az x keresését.

a) Ha s darab különböző prím szerint nézzük x2N lehetséges maradékait, akkor körülbelül az x számok hányadrészéről derül ki, hogy x2N biztosan nem lehet négyzetszám?

b) Ez a faktorizációs módszer mikor talál (viszonylag) gyorsan N=de felbontást: ha d kicsi és e nagy vagy ha d és e közel egyforma?

c) Bontsuk tényezőkre ezzel a módszerrel a 86519 és 584189 számokat. (Csak kalkulátort használjunk, és elegendő a 3 és 8 modulusokkal „szitálni”.)