Prímtesztek

Fermat teszt

2013. szeptember 30.

A teszt a kis-Fermat tételen alapszik. Azaz adott \(p\) prímszám és \(a\in\{2,\ldots,p-1\}\) esetén \[a^{p-1}\equiv 1\pmod{p}.\] Amennyiben találunk olyan \(a\) értéket, amelyre a kongruencia nem teljesül tudjuk, hogy \(p\) nem lehet prím. További információ itt.

Lucas-Lehmer teszt

2013. október 9.

Az \(M_p=2^p-1\) alakú Mersenne számok esetében igen hatékony prímteszt áll a rendelkezésünkre. Legyen \(s_i\) a következő sorozat: \(s_0=4\) és \(s_i=s_{i-1}^2-2\) ha \(i>0.\) Ekkor \(M_p\) prím pontosan akkor, ha \[s_{p-2}\equiv 0\pmod{M_p}.\] További információ itt. Az alábbi Sage kódot Matolcsy Kristóf készítette.

Proth teszt

2013. október 12.

Adott \(k\) és \(n\) pozitív egészek esetében, ahol \(k\) páratlan és kisebb, mint \(2^n\), a \(p=k2^n+1\) szám prím, ha valamilyen \(a\) egészre \[a^{(p-1)/2}\equiv -1\pmod{p}.\] További információ itt. Az alábbi Sage kódot Matolcsy Kristóf készítette.

Faktorizáció

Fermat faktorizáció

2013. október 10.

Amennyiben egy adott \(n\) egészről sikerül valamilyen prímteszt segítségével megmutatni, hogy összetett, akkor a következő természetes kérdés a prímfaktorizáció meghatározása. Erre ad választ Fermat módszere. Ez egy jól ismert azonosságra épít: \[a^2-b^2=(a-b)(a+b).\] Az \(n\) számot megpróbáljuk felírni, mint két négyzetszám különbsége és ha a fenti összefüggés nem a triviális \(1\times n\) felbontást adja, akkor két valódi osztót már ismerünk. További információ itt. Az alábbi Sage kódot Matolcsy Kristóf készítette.

Pollard-\(\rho\) faktorizáció

2013. október 13.

Ez a módszer véletlen függvényent felhasználva próbál nem triviális osztót meghatározni. A véletlen függvény alakja gyakran \(f(x)=x^2+c\) alakú. A lenti Sage kódban \(c=1\) a választás. További információ itt. Az alábbi Sage kódot Matolcsy Kristóf készítette.

Berlekamp faktorizáció

2014. március 22.

Berlekamp algoritmusa véges test feletti polinomok faktorizálását teszi lehetővé. Az algoritmus kihasználja, hogy adott \(p\) prímszám esetében \(a^p\equiv a\bmod{p}\) a kis Fermat-tétel miatt. Azaz az \(X^p-X\) polinom felbontását egyszerűen meg lehet adni: \[X^p-X=\prod_{a\in\mathbb{F}_p}(X-a).\] Így, amennyiben sikerül találni olyan \(g\) polinomot, amelyre \(g^p\equiv g\bmod{f},\) ahol az \(f\) polinom felbontását szeretnénk meghatározni, akkor az \[f\mid g^p-g\] reláció miatt \[f=\gcd(f,g^p-g)=\gcd(f,\prod_{a\in\mathbb{F}_q}(g(X)-a)).\] Felhasználva, hogy \(g(X)-a_1\) és \(g(X)-a_2\) relatív prímek, ha \(a_1\neq a_2\) adódik, hogy \[f=\prod_{a\in\mathbb{F}_q}\gcd(f,g(X)-a).\] Már csak az a kérdés hogyan találunk megfelelő \(g\) polinomot. Itt kihasználjuk, hogy \(g(X)^p\) egyszerűen számolható, ha \[g(X)=\sum_{i=1}^ng_iX^i,\] akkor \[g(X)^p=\sum_{i=1}^ng_iX^{p\cdot i}.\] Redukálva az \(X^{p\cdot i}\) polinomokat moduló \(f\) az együtthatók összehasonlításából kapunk egy homogén lineáris egyenletrendszert. Az egyenletrendszerhez tartozó mátrix magja alapján fel tudunk írni megfelelő \(g\) polinomot.

Elliptikus görbés faktorizáció

2014. május 28.

Elliptikus görbék esetében be lehet vezetni egy összeadás műveletet, ezzel kapcsolatban készítettem egy Sage applikációt (2013. október). A görbe pontjainak összegét egy egyszerű geometriai eljárás adja meg. Két különböző pont esetében az őket összekötő egyenes az elliptikus görbét egy harmadik pontban is metszi, ebben a pontban állítunk egy merőleges egyenest az \(x\)-tengelyre és az adódó metszéspont a görbével a két pont összege. Amennyiben a két pont azonos, azaz egy adott pont kétszeresét szeretnénk kiszámítani, akkor a ponthoz tartozó érintő játsza a két ponton átmenő egyenes szerepét. Az egyenesek meredekségének kiszámításához osztásra is szükségünk van. Amennyiben a görbe test felett van értelmezve, akkor ez jól működik, minden nem nulla elemnek van inverze. Viszont például \(\mathbb{Z}_6\) felett 2-nek nincs inverze, így bizonyos pontok esetében az összeg kiszámítása nem lehetséges. Ezt fel tudjuk használni faktorizációhoz, ahogyan ezt Lenstra észrevette. Adott \(N\) összetett szám esetében veszünk \(\mathbb{Z}_N\) feletti elliptikus görbéket és azon pontokat. Megpróbáljuk kiszámítani a pontok többszöröseit és ha ez nem sikerül, akkor találunk nem triviális osztót \(N\)-hez. További információ itt. Az alábbi applikáció előfordulhat, hogy még hibát jelez, ez a Sage-ben egy ismert és javított hiba, a 6.2 verzióban már jól működik. Így amikor a Sage Cell Server frissítése lezajlik ezzel nem lesz probléma.

Euler faktorizáció

2014. szeptember 23.

Euler faktorizációs eljárása olyan \(N\) egészekre működik, amelyek előállnak két különböző módon két négyzetszám összegeként. Azaz \[N=a^2+b^2=c^2+d^2.\] Az előző felbontásban feltehetjük, hogy \(b\) és \(d\) paritása azonos. Legyen \[\gcd(a-c,d-b)=k.\] Kapjuk, hogy \[a-c=kl\mbox{ és }d-b=km.\] Innen pedig adódik, hogy \[l(a+c)=m(b+d),\] ahol \(l\) és \(m\) relatív prím egészek. Azaz \(m\) osztója \(a+c\)-nek. A fentiek alapján \[a+c=mn\mbox{ és }b+d=ln.\] Az \(N\) felbontása tehát \[\left(\left(\frac{k}{2}\right)^2+\left(\frac{n}{2}\right)^2\right)(l^2+m^2).\] További információ itt.

Diofantikus egyenletek

Pell-egyenlet

2013. november 26.

Legyen \(d\) egy egész, amely nem teljes négyzet. Ekkor az \[x^2-dy^2=\pm 1\] diofantikus egyenletet Pell-egyenletnek nevezzük. Az egyenlet megoldásai szoros összefüggésben állnak a \(\sqrt{d}\) valós szám lánctört alakjával, pontosabban az abból származó úgynevezett konvergensekkel. Például, ha \(d=2\), akkor \(\sqrt{d}\) első néhány konvergense a következő: \[1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}.\] Amennyiben \(x,y\) egy egész megoldás, akkor \(x\) egy ilyen konvergens számlálója, \(y\) pedig a nevezője. A fenti konvergensek esetében a következő értékeket kapjuk: \[-1,1,-1,1,-1,1,-1,1,\] tehát például \[3^2-2\cdot 2^2=1\] és \[7^2-2\cdot 5^2=-1.\] További információ itt.

Pell-egyenlet megoldó Sage interaktív kód

2013. december 21.

Az alábbi Sage kód adott pozitív, nem teljes négyzet \(d\) érték esetén megkeresi a legkisebb \(x,y\) megoldását az \(x^2-dy^2=1\) Pell-egyenletnek. A táblázatban láthatóak adott \(n\) értékhez tartozó konvergensek számlálói: \(r_n\) és nevezői: \(s_n\). Például \(d=2013\) esetében azt látjuk, hogy a legkisebb megoldás: \[(x,y)=(152409599,3396960).\]

Frobenius-probléma: Wilf-módszer

2014. január 27.

A Frobenius-probléma lineáris diofantikus egyenletekhez kapcsolódik. Adott \[a_1,a_2,\ldots,a_k\] 1-nél nagyobb különböző egészek úgy, hogy \(a_{i+1}\) nagyobb, mint \(a_{i}\) és a legnagyobb közös osztójuk 1. Meg lehet mutatni (pl. teljes indukció segítségével), hogy ha \(n\) elég nagy, akkor léteznek nem negatív egészek \(x_1,x_2,\ldots,x_k\) úgy, hogy \[a_1x_1+a_2x_2+\ldots+a_kx_k=n.\] Keressük azt a legnagyobb pozitív egész számot, amely nem állítható elő ilyen módon. Wild rekurzív módszere azon alapul, hogy egy adott \(n\) előállítható, ha \(n-a_1\) vagy \(n-a_2\) vagy \(\ldots n-a_k\) előáll megfelelő lineáris kombinációként. Amennyiben találunk \(a_1\) egymást követő egész számot, amelyek előállnak, akkor attól kezdve minden egész előáll. A következő Sage kód ezt az eljárást szemlélteti. A számokat moduló \(a_k\) tekintjük, az osztályokat pedig egy lámpaként, ha egy adott osztály előáll, akkor feloltjuk. Alaphelyzetben minden lámpa le van oltva, kivéve a \(0\), mert a nulla triviálisan előállítható lineáris kombinációként. Ezután a fenti gondolatmenet szerint haladunk körbe az irányított gráfon. Egy adott lámpát a fentiek szerint feloltunk és akkor állunk meg ha található legalább \(a_1\) db összefüggő világító lámpa, a legutolsó fel nem oltott lámpa maradékosztályából kerül ki a legnagyobb nem előállítható szám, ezt könnyen meg tudjuk határozni, ha figyelembe vesszük hányszor értünk körbe a gráfon.

Diofantikus halmazok

2014. február 28.

Pozitív egészek egy \(a_1,a_2,\ldots,a_m\) halmaza diofantikus halmaz, ha bármely két különböző \(a_i,a_j\) esetén \(a_ia_j+1\) négyzetszám. Diophantus racionális számokból halmazt adott meg, ez pedig a következő: \[\left\{\frac{1}{16}, \frac{33}{16}, \frac{17}{4}, \frac{105}{16}\right\}.\] Egészekből álló halmazra Fermat adott egy négy elemből álló példát: \(\{1,3,8,120\}\). Euler pedig egy végtelen családot adott meg: \[\{a, b, a + b + 2r, 4r(r + a)(r + b)\},\] ahol \(ab+1=r^2.\) Baker és Davenport megmutatta 1969-ben, hogy ha \(1,3,8,d\) egy diofantikus halmaz, akkor \(d=120\), eredményükben felhasználták a diofantikus egyenletek több osztályára azóta sikeresen alkalmazott Baker-módszert. Dujella igazolta, hogy nem létezik 6 elemű diofantikus halmaz, később belátta, hogy csak véges sok 5 elemű diofantikus halmaz létezik. Dujella honlapján további hasznos információk találhatóak diofantikus halmazokról. Bérczessel, Dujellával és Hajduval közösen most egy olyan általánosítást vizsgálunk, amelynél az eredeti \(F(a_i,a_j)=a_ia_j+1\) polinom helyett más típusú polinomok szerepelnek. Például \[F(x,y)=(u_1x^2+u_2xy+u_3y^2+u_4x+u_5y+u_6)^2+u_7x+u_8y+u_9.\] Ebben az esetben az \(F(x,y)=z^2\) egyenlet egész megoldásainak a struktúráját kell vizsgálni. Szalay egy eredménye alapján a megoldások vagy az \(u_7x+u_8y+u_9=0\) egyenesre esnek vagy két ellipszis belső pontjai. Ezt felhasználva felső korlát adható az erre a polinomra vonatkozó diofantikus halmazok méretére. Egy Sage kódot is írtunk, amely adott \(u_i\) paraméterek esetén meghatározza a diofantikus halmazokat.

Kriptográfia

Shamir-féle titokmegosztás

2014. április 28.

A titokmegosztás feladata a következő: olyan eljárás megadása, amelynél \(k\) vagy több szereplő rekonstruálni tudja a titkot, de \(k\)-nál kevesebb nem. Az alábbiakban bemutatjuk a Shamir-féle titokmegosztást, ami véges testek feletti polinomokat használ fel. Egyik nagy előnye a rugalmas bővíthetőség, azaz, ha a későbbiekben új szereplőnek szükséges titokrészletet biztosítani, akkor nem kell az egész rendszert megváltoztatni. A korábbi titokrészletek változatlanul használhatóak maradnak.

Rekurzív sorozatok

Rekurzív sorozatok és szummák

2014. június 27.

Stancliff 1953-ban egy igen érdekes észrevételt tett az \(F_{11}=89\) számmal kapcsolatban: \[ \frac{1}{F_{11}}=\frac{1}{89}=0.0112358\ldots=\sum_{k=0}^{\infty}\frac{F_k}{10^{k+1}}. \] A fenti összefüggésben \(F_n\) jelöli a jól ismert Fibonacci sorozatot. Ahogyan látható \(F_{11}\) reciproka esetében a tizedesjegyeknél a sorozat első néhány egymást követő eleme tűnik fel: \(0, 1, 1, 2, 3, 5, 8.\) Az alábbiakban megadunk egy Sage applikációt, amely adott sorozat esetében kiszámítja a szumma összegét.

Rekurzív sorozatokok zárt alakja

2014. augusztus 26.

Rekurzív sorozatok, rekurzív függvények a matematika sok területén felbukkannak természetes módon. A rekurzió miatt adott érték meghatározása számolásigényes. Most megmutatjuk, hogy lineáris algebrai módszerekkel ez sokszor orvosolható. Tekintünk egy lineáris rekurzív sorozatot: \[u_n=au_{n-1}+bu_{n-2}+cu_{n-3}\] adott \(u_0,u_1,u_2\) kezdőértékekkel. Bevezetünk egy mátrixot, amely segítségével áttérhetünk lineáris algebrára. Legyen \[A=\begin{pmatrix}a & b & c\\ 1 & 0 & 0\\ 0 & 1 & 0\end{pmatrix}.\] Ekkor \[A\begin{pmatrix}u_2\\u_1\\u_0\end{pmatrix}=\begin{pmatrix}u_3\\u_2\\u_1\end{pmatrix}\] és általában \[A^n\begin{pmatrix}u_2\\u_1\\u_0\end{pmatrix}=\begin{pmatrix}u_{n+2}\\u_{n+1}\\u_n\end{pmatrix}.\] Azaz elegendő az \(A\) mátrix \(n\)-edik hatványának zárt alakját meghatározni, ezt a problémát a lineáris algebra résznél már tárgyaltuk.

Lineáris algebra

Mátrixok \(n\)-edik hatványának zárt alakja

2014. július 19.

Adott mátrix esetében az \(n\)-edik hatvány kiszámítására meg lehet határozni zárt alakot. Itt azt használjuk fel, hogy diagonális mátrixok esetében a hatványozás egyszerű, csak a főátlóban szereplő elemeket kell hatványozni. Így egy adott mátrix esetében sajátértékek-sajátvektorok segítségével diagonalizálunk és azután hatványozunk. Ezután már csak két mátrix szorzás szükséges a zárt alak meghatározására. Ezt a módszert \(3\times 3\)-as mátrixok esetében Sage-ben implementáltuk. Megjegyezzük, hogy az alap példánkban olyan mátrixot választottunk, amelynek minden sajátértéke egész, így a számolás egyszerűbb, a végeredmény áttekinthetőbb.