Számrendszerek Feladat
Számrendszerek Németh Bence
2014. május 13.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek Legyen Λ ⊆ Rn rács, M : Λ → Λ alapmátrix, melyre det(M) 6= 0, 0 ∈ D ⊆ Λ véges jegyhalmaz.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek Legyen Λ ⊆ Rn rács, M : Λ → Λ alapmátrix, melyre det(M) 6= 0, 0 ∈ D ⊆ Λ véges jegyhalmaz. Definíció (Generalized number system) A (Λ, M, D) hármast számrendszernek nevezzük, ha ∀x ∈ Λ felírható x=
n X
M i di
i=0
alakban, ahol di ∈ D és n ∈ N. A (dn . . . d1 d0 ) sorozatot az x kifejtésének nevezzük. Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Tétel Ha (Λ, M, D) számrendszer, akkor 1
D teljes maradékrendszer modulo M,
2
M expanzív,
3
det(I − M) 6= ±1
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Tétel Ha (Λ, M, D) számrendszer, akkor 1
D teljes maradékrendszer modulo M,
2
M expanzív,
3
det(I − M) 6= ±1
Definíció (Radix rendszer) Ha (Λ, M, D) eleget tesz az (1). és a (2). feltételnek, akkor radix rendszernek nevezzük.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Definíció Λ két eleme akkor és csak akkor kongruens modulo M, ha a Λ/MΛ faktorcsoport ugyanazon mellékosztályába esnek.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Definíció Λ két eleme akkor és csak akkor kongruens modulo M, ha a Λ/MΛ faktorcsoport ugyanazon mellékosztályába esnek. Tétel A Λ/MΛ faktorcsoport rendje |det(M)|.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek Definíció (Pálya) Legyen φ : Λ → Λ, φ(x ) = M −1 (x − d) , ahol d ∈ D és x ≡ d(modM). Az x , φ(x ), φ2 (x ), φ3 (x ), . . . sorozatot x pályájának nevezzük.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek Definíció (Pálya) Legyen φ : Λ → Λ, φ(x ) = M −1 (x − d) , ahol d ∈ D és x ≡ d(modM). Az x , φ(x ), φ2 (x ), φ3 (x ), . . . sorozatot x pályájának nevezzük. Tétel Mivel M −1 kontrakció és D véges, ezért letezik egy k.k norma Λ-n és egy C konstans, hogy ∀x ∈ Λ pályája előbb-utóbb belép az S = {x ∈ Λ|kx k < C } véges halmazba. Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Definíció (periodikus pont) A p pont periodikus, ha ∃k > 0 : φk (p) = p
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Definíció (periodikus pont) A p pont periodikus, ha ∃k > 0 : φk (p) = p Tétel ∀x ∈ Λ pályája végül periodikus.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított számrendszerek
Definíció (periodikus pont) A p pont periodikus, ha ∃k > 0 : φk (p) = p Tétel ∀x ∈ Λ pályája végül periodikus. Tétel (Λ, M, D) számrendszert alkot, ha ∀x ∈ Λ pályája végül 0.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Egyszerűsített számrendszerek Definíció (Canonical number system) Legyen Λ = Zn , M a c(x ) = c0 + c1 x + · · · + cn−1 x n−1 + x n egész együtthatós polinom Frobenius társmátrixa, D = {(i, 0, . . . , 0) ∈ Zn |0 ≤ i < |c0 |} véges jegyhalmaz. Ha (Λ, M, D) számrendszer, akkor egyszerűsített számrendszer, a c(x ) polinom pedig CNS polinom.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Egyszerűsített számrendszerek
M=
0 0 ... 1 0 ... 0 1 ... .. .. . . . . . 0 0 ...
Németh Bence
0 0 0 .. .
−c0 −c1 −c2 .. .
1 −cn−1
Számrendszerek
Számrendszerek Feladat
Általánosított számrendszerek Egyszerűsített számrendszerek Általánosított bináris számrendszerek
Általánosított bináris számrendszerek
Definíció (Generalized binary number system Ha (Λ, M, D) a c(x ) CNS polinom által meghatározott számrendszer és c0 = 2, akkor (Λ, M, D) általánosított bináris számrendszer.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Feladat Legyen (Λ, M, D) a c(x ) CNS polinom által meghatározott számrendszer általánosított bináris számrendszer x ∈ Λ kifejtése (dn . . . d1 d0 ) Feladat Keressünk olyan x ∈ Z számokat, melyekre (x , 0, 0, . . . , 0), (x , x , 0, . . . , 0) ∈ Λ kifejtését bináris számként értelmezve prímszámokat kapunk.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Feladat Legyen (Λ, M, D) a c(x ) CNS polinom által meghatározott számrendszer általánosított bináris számrendszer x ∈ Λ kifejtése (dn . . . d1 d0 ) Feladat Keressünk olyan x ∈ Z számokat, melyekre (x , 0, 0, . . . , 0), (x , x , 0, . . . , 0) ∈ Λ kifejtését bináris számként értelmezve prímszámokat kapunk. Cél Olyan (x , p1 , p2 ) hármasok keresése, ahol p1 , p2 kb. 320 bit méretű prímek. Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Eszközök Meglévő, szimbolikus keretrendszerben vizsgált probléma hatékonyabb vizsgálata. GeneralNumberSystems C++ template library (Éles Dávid, 2013) Számrendszerek kezelése, kifejtés előállítása. GMPLib The GNU Multiple Precision Arithmetic Library Kifejtésként kapot számok kezelése, valószínűségi prímtesztelés.
Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Folyamat Elem vizsgálata Legyen adott c(x ) CNS polinom, és x ∈ Z. 1
(x,0,0,. . . ,0) kifejtése
2
a kifejtésből p1 előállítása
3
ha p1 biztos nem prím vége
4
(x,x,0,. . . ,0) kifejtése
5
a kifejtésből p2 előállítása
6
ha p2 biztos nem prím vége
7
(x , p1 , p2 ) jelölt
8
p1 , p2 egzakt prímtesztelése...
Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Köszönöm a figyelmet!
Németh Bence
Számrendszerek
Számrendszerek Feladat
Feladat Eszközök Folyamat Eredmények
Kovács,A.: Radix Representation of Numbers http://compalg.inf.elte.hu/~attila/materials/ RepresentingNumbers.pdf Burcsi,P., Kovács,A.: Exhaustive search methods for CNS polynomials, http://compalg.inf.elte.hu/~attila/pub/ SearchingForCnsPolynomials.pdf Kovács,A.: Generalized binary number systems, http: //compalg.inf.elte.hu/~attila/pub/GenBinNumsys.pdf Éles,D.: GeneralNumberSystems, https://github.com/elesd/GeneralNumberSystems The GNU Multiple Precision Arithmetic Library, https://gmplib.org/ Németh Bence
Számrendszerek