Számrendszerek Feladat. Számrendszerek. Németh Bence május 13

Számrendszerek Feladat

Számrendszerek Németh Bence

2014. május 13.

Németh Bence

Számrendszerek


Á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



Á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



Á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




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




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




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



Á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



Á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




Definíció (periodikus pont) A p pont periodikus, ha ∃k > 0 : φk (p) = p

Németh Bence

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




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



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



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

       



Á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


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



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



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



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



Köszönöm a figyelmet!

Németh Bence

Számrendszerek



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

Számrendszerek Feladat. Számrendszerek. Németh Bence május 13

Recommend Documents