Mik azok az elliptikus görbék, és mit állít róluk az egymillió dollárt érő Birch és Swinnerton-Dyer sejtés? Hogyan lehet az elliptikus görbékre újfajta titkosítási eljárásokat építeni? Mik azok a kvantumszámítógépek, és ha tényleg megvalósíthatók, akkor mire lesznek képesek a jövőben? Kell-e miattuk aggódnia Alice-nak és Bob-nak? Vajon a kriptográfusok, vagy a kiberbűnözők kerülnek ki győztesen ebből az emberiség egész történelmét végigkísérő kíméletlen háborúból?
Mit nevezünk primitív gyöknek, és mi köze ennek a Diffie-Hellman kulcscsere protokollhoz? Milyen esetekben ciklikus egy maradékosztálygyűrű multiplikatív csoportja? Mit állít az úgynevezett Korselt-kritérium a Carmichael-számokról? Hogyan lehet igazolni, hogy a redukált maradékosztályoknak legalább a háromnegyede Miller-Rabin-tanú? Mi a következménye, ha az RSA kulcsok generálásához véletlenül prímek helyett Carmichael-számokat használunk?
A bizonyításban megkonstruált függvény által megvalósított leképezés természetesen függeni fog attól, hogy pontosan milyen reprezentánsrendszert választunk -hez. Maga a tény azonban, hogy ez egy kölcsönösen egyértelmű megfeleltetés lesz és között, természetesen a reprezentánsrendszer megválasztásától függetlenül …
A ban bevezettük a csoport rendjének fogalmát, amely az adott csoport elemeinek a számát adja meg. Ez a multiplikatív csoport esetén a alapján épp az Euler-féle -függvény értékével egyezik meg, azaz: Ezután a ban definiáltuk …
Tekintsük például az alábbi egész számokból álló végtelen sorozatot, amely tehát a definíció alapján egy feletti harmadfokú polinom, hiszen a -es indexű tagjától kezdve csupa számokból áll (ne feledjük, a számozás a nulladik indextől indul): …
A bizonyításban szereplő és függvények képlete első ránézésre kissé mesterkéltnek tűnhet. Ennek technikai oka van, ugyanis a szám fogalmát eddig csak a természetes és az egész számok körére korlátoztuk, az úgynevezett tört- vagy racionális számokat …
Először a Carmichael-számok paritására vonatkozó állítást igazoljuk. Legyen tetszőleges Carmichael-szám. Az és az egész számok egymáshoz relatív prímek. Ugyanis bármilyen közös osztó a 6. pontja alapján osztója e két szám különbségének, azaz -nek, és így …
A megoldáshalmaz minden eleme kielégíti az első kongruenciát, azaz -rel azonos modulo maradékosztályban van. Következésképp a alapján minden esetén létezik olyan egész szám, hogy teljesül az alábbi egyenlet: Tehát tulajdonképpen azokat az egész számokat keressük, …
A utáni megjegyzés alapján nem Fermat-tanú csak redukált maradékosztály lehet, ezért fennáll az tartalmazási reláció. Így az részcsoport reláció igazolásához a alapján csak azt kell megmutatni, hogy nemüres és zárt a -beli csoportműveletre nézve. Az …
A tételt a kitevőre vonatkozó teljes indukcióval fogjuk igazolni. Nézzük először a esetet! A 3. pontja alapján ekkor épp megegyezik a multiplikatív csoporttal. Ennek rendje a modulo redukált maradékosztályok számával, azaz -vel egyezik meg, ami …
Ha négyzetmentes, akkor a alapján nem osztható semmilyen egész szám négyzetével, így nyilván pozitív prímszámok négyzetével sem. Megfordítva: Tegyük fel, hogy nem négyzetmentes, azaz létezik olyan egész szám, hogy . Legyen egy olyan prímszám, amely …
Előszöris megmutatjuk, hogy a ban bevezetett műveletek nem vezetnek ki az halmazból, azaz algebrai értelemben is műveletek (lásd a t). A 1. és 2. pontjai alapján ugyanis nemnulla polinomok összegének foka legfeljebb a polinomok fokainak …
A továbbiakban reprezentáljuk az és polinomokat az alábbi végtelen sorozatokkal, ahol jelöli az gyűrű nullelemét: A szerint e két polinom összegének -adik tagját az alábbi képletből kapjuk: Szintén a alapján a két polinom szorzatának -adik …
Tegyük fel, hogy az polinomfüggvény olyan, hogy tetszőleges gyűrűelemhez az alábbi kifejezés eredményét rendeli hozzá: Ennek értékét esetén tehát az alábbi kifejezés kiértékelésével számíthatjuk ki: Emeljük ki -et minden olyan tagból, amelyikből lehet: Ismételgessük ezt …
Legyen az gyűrű nulleleme, továbbá vezessük be az alábbi jelöléseket: Ennek megfelelően és az alábbi sorozatokkal reprezentálhatók: Az 1. állítás: Mivel , vagyis az index nagyobb fokánál, emiatt , tehát az összegpolinom -edik tagja . …
Tekintsük elsőként az gyöktényezőt. A alapján felírható az alábbi alakban valamilyen alkalmas polinommal: Mivel egységelemes, továbbá az gyöktényező főegyütthatója az egységelem – hiszen az ugye a alapján megegyezik a hozzátartozó polinomfüggvény elsőfokú tagjának, azaz -nek …
A 4. pontja alapján tehát azt a legkisebb pozitív kitevőt keressük, amellyel a elemet hatványozva a csoport -vel jelölt egységelemét kapjuk. Ez a hatvány a 2. pontja alapján a elem -adik hatványa lesz, azaz felírható …
Minden egyes, a tételben szereplő osztóból állítsuk elő az összes olyan számpárt, amelynek első tagja , második tagja pedig egy olyan -nél kisebb nemnegatív egész szám, amely relatív prím -hez. A alapján pontosan darab olyan …
A csoport a maradékosztálygyűrű redukált maradékosztályaiból áll, ezért a alapján ennek a csoportnak a rendje , azaz a miatt . Mivel a miatt bármely elem rendje osztója a csoport rendjének, ezért ha , akkor -ben …
Elsőként azt mutatjuk meg, hogy ha Carmichael-szám, akkor teljesíti a fenti két kritériumot. Először igazoljuk, hogy négyzetmentes, ami a alapján azt jelenti, hogy nem létezik olyan pozitív prímosztója, amelynek a négyzetével is osztható. Tegyük fel …
