Vissza

Algoritmusok


1. Euklideszi algoritmus: két egész szám (a, b) legnagyobb közös osztójának (d) a meghatározása:
euclid( a, b )
{
    a = abs(a);
    b = abs(b);
    while ( b != 0 ) {
        r = a mod b;
        a = b;
        b = r;
    }
    d = a;
    return d;
}
Példák:
1. lnko(64, 60) = 4
2. lnko(104, 221) = 13


2. Kiterjesztett Euklideszi algoritmus: két pozitív egész szám (a, b) legnagyobb közös osztójának a d-nek a meghatározása és azon másik két egész szám (x, y) meghatározása melyekre fenn áll akövetkezõ összefüggés : a·x + b·y = d

exteuclid( a, b )
{
    // a > b
    x0 = 1; x1 = 0;
    y0 = 0; y1 = 1;
    while ( b != 0 ) {
        r = a mod b;
        q = a div b;
        a = b;
        b = r;
        xx = x1;
        yy = y1;
        x1 = x0 - q * x1;
        y1 = y0 - q * y1;
        x0 = xx;
        y0 = yy;
    }
    d = a; x = x0; y = y0;
    return (d, x, y);
}

Példák:
1. 64 · x + 60 · y = 4, a megoldás { x = 1, y = -1}
q
a
b
x1
x[0]
y1
y[0]
0
64
60
0
1
1
0
1
60
4
1
0
-1
1
15
4
0
-15
1
16
-1

2. 60 · x + 35 · y = 5, a megoldás { x = 3, y = -5}
q
a
b
x1
x[0] y1
y[0]

60
35
0
1
1
0
1
35
25
1
0
-1
1
1
25
10
-1
1
2
-1
2
10
5
3
-1
-5
2
2
5
0
-5
3
12
-5


3. Inverz meghatározása: Adott egész a szám mod n szerinti inverzének a meghatározása, azaz azon x egész szám meghatározása melyre fenn áll a következõ lineáris kongruencia: a · x = 1 mod n.

Megjegyzés: a fenti kongurenciának a megoldhatósági feltetele az, hogy lnko(a, n) = 1

m_invers( a, n )
{
    (d, x, y) = ext_euclid( a, n);
    if ( d == 1 )
        if ( x < 0 ) return x + n;
        else return x;
    else return 0;
}

Példák:
1. 23·x = 1 mod 61, a megoldás { x = 8 }
2 17·x = 1 mod 27, a megoldás 1. { x = 8 }

Ha n prím, akkor másik módszerrel is meghatározható az inverz: kiindulva, hogy: phi(n) = n-1, akkor aphi(n) = 1 mod n kongruenciát végig osztva a-val kapjuk
aphi(n)-1 = a-1 mod n
a-1 = an-2 mod n

Példa:
1. Határozzuk meg 5, mod 17 szerint inverzét.
5-1 = 515 mod 17
515 = 58·54·52·51 = 5·8·13·16 = 7 mod 17
Ellen?rzés: 5·7 = 1 mod 17

4. Lineáris konruencia megoldása: Azon x egész szám meghatározása, melyre fenn áll a következõ lineáris kongruencia: a · x = b mod n.

Megjegyzés: a fenti kongurenciának a megoldhatósági feltetele az, hogy lnko(a, n) osztója legyen b-nek
congruence( a, b, n )
{
    (d, x, y) = ext_euclid( a, n );
    if( b mod d != 0) return 0;
    else{
        a = a div d;
        b = b div d;
        n = n div d;
        a1 = m_invers( a, n );
        if( a1 != 0 ) {
            k = ( b * a1 ) mod n;
            return k;
    }
    else return 0;
    }
}

Példák:
1.
17x = 25 mod 27, a megoldás: { x = 11 }
17 · 11 = 187, 187 = 27 · 6 + 25

2.
23·x = 15 mod 61,  a megoldása: { x = 59 }
23 · 59 = 1357, 1357 = 61 · 22 + 15
3.
60·x = 16 mod 64, a megoldás: { x = 12, 28, 44, 60 }
60 · 28 =1680, 1680 = 64 · 26 + 16

Megjegyzés: a feni konguenciát elöbb osztom az lnko( 60, 64 ) = 4 -el: 15·x = 4 mod 16. Az algoritmus csak az x = 12 megoldást határozza meg.

5. Gyorshatványozás algoritmusa: alapexp (mod m) értékének a meghatározása
fast_exp( alap, exp, m )
{
    res = 1;
    while(exp > 0)
    {
        if (exp mod 2 == 1 )
            res = ( res * alap ) mod m;
        alap = ( alap * alap ) mod m;
        exp = exp / 2;
    }
    if ( res < 0 ) res = m + res;
    return res;
}


6. Miller-Rabin prímteszt: az algpritmus az n páratlan számról vizsgálja meg, hogy prím-e
1. keressük q, k számokat úgy, hogy q- párátlan és n = 2k·q+1
2. legyen x tetsz?leges szám és y = xq ( mod n ), 2<=x< n
3. ha y = 1 → True
4. másképp j = 1, 2, ... , k –ra elvégezzük
Ha y = n-1 → True
Másképp, ha y = 1 → False
Másképp, legyen y = y·y ( mod n )
5. False

Példák:
1.
legyen n = 63, ekkor n = 23 · 7 + 1, tehát q = 7, k = 3
legyen x = 8, y = 87 ( mod 63 ) = 8
meghatározzuk y = 8 · 8 ( mod 63) = 1 → False

2.
legyen n = 61ekkor n = 22 · 15 + 1, tehát q = 15, k = 2
legyen x = 8, y = 815 ( mod 61 ) = 50
meghatározzuk y = 50 · 50 ( mod 61) = 60 → True


7. Primitív gyök meghatározása, adott p prím szám esetében, legyen n = p - 1, p rendje
legyen n prímfaktorizációja n = p1e1·p2e2·... ·pkek
1. legyen a egy tetsz?leges elem a következ? halmazból: {2, ..., p - 1}
2.i = 1, 2, ..., k-ra meghatározzuk b = an/pi
3. ha b =1, akkor az 1. lépést?l újra kezdünk,
4. a primitív gyök

Példa:
1. p = 13, n = 12, p rendje
2. n = 22·3, n prímfaktorizációja
3. legyen a = 8
4. i = 1,2-re meghatározzuk:
b = 8 6 mod 13 = 12, ahol 6 = 12/2
b = 8 4 mod 13 = 1, ahol 4 = 12/3
b = 1 tehát visszalépünk a 3-as pontra, mert a = 8 nem primitív gyök
3. legyen a = 7
4. i = 1,2-re meghatározzuk:
b = 7 6 mod 13 = 12, ahol 6 = 12/2
b = 7 4 mod 13 = 9, ahol 4 = 12/3
5. tehát a = 7 primitív gyök

71mod 13 = 7
72 mod 13 = 10
73 mod 13 = 5
74 mod 13 = 9
75 mod 13 = 11
76 mod 13 = 12
77 mod 13 = 6
78 mod 13 = 3
79 mod 13 = 8
710 mod 13 = 4
711 mod 13 = 2
712 mod 13 = 1

81mod 13 = 8
82 mod 13 = 12
83 mod 13 = 5
84 mod 13 = 1
85 mod 13 = 8 
86 mod 13 = 12
87 mod 13 = 5
88 mod 13 = 1
89 mod 13 = 8
810 mod 13 = 12
811 mod 13 = 5
812 mod 13 = 1


6. Véletlen szám generálás ( random number ): lineáris kongruencián alapuló véletlenszám generálás, n számot generál véletlenszer?en, a kezd kiinduló érték alapján

1.szorzo = 7^5
2. modulus = 2^31 - 1
3. novel = 66
4. veletlen_lista = []
5. x = kezd
6. i = 1, 2, ... , n-re elvégezzük
veletlen_lista = veletlen_lista + [x]
x = kov_elem(x, szorzo, novel, modulus)
ahol: kov_elem(x, a, c, m) = (a·x+c)mod m

7. Kínai maradék tétel: az algoritmus meghatározza azon x egész számot mely eleget tesz a következ? kongruencia rendszernek:
x ≡ a1 mod m1
x ≡ a2 mod m2

x ≡ an mod mn
ahol m1, m2, ..., mn> 0 páronként relatív prímek, a1, a2, ..., an pedig tetsz?leges egész számok. A rendszernek egyetlen megoldás lesz mod(m1· m2· ...· mn) szerint.

Az algoritmus:
chinese_remainder( n, m1, m2, ..., mn , a1, a2,..., an )
{
    m = m1* m2* ... * mn;
    res = 0;
    for i from 1 to n do
    {
        M = modulus div mi;
        inv = inverz(M, mi);
        res = (res + inv * M * ai) mod m;
    }
    return res;
}  

8. A Jacobi szimbólum meghatározása
Jacobi_symbol( a, n )
{
    if (a == 0)
       if (n == 1) return 1;
       else return 0;
    if (a == 2) {
       if (n mod 8) == 1) return 1;
       if (n mod 8) == 7) return 1;
       if (n mod 8) == 3) return -1;
       if (n mod 8) == 5) return -1;
    }
    if ( a >= n )
       return Jacobi_symbol(a mod n, n);
    if ( a mod 2 == 0)
       return Jacobi_symbol(2, n) * Jacobi_symbol(a/2, n);
    if ( (a mod 4) == 3 and (n mod 4) == 3)
       return (-1) * Jacobi
_symbol(n, a);
    else return Jacobi
_symbol(n, a);
}

Példa:
legyen n = 7, a = 0,1,2,3,4,5,6 akkor
02 mod 7 = 0
12 mod 7 = 1
22 mod 7 = 4
32 mod 7 = 2
42 mod 7 = 2
52 mod 7 = 4
62 mod 7 = 1
azaz
Jacobi(3, 7) = -1, 3, nem négyztes maradék
Jacobi(5, 7) = -1, 5, nem négyzetes maradék
Jacobi(6, 7) = -1, 6, nem négyzetes maradék

Jacobi(0, 7) = 1, 0, négyztes maradék
Jacobi(1, 7) = 1, 1, négyztes maradék
Jacobi(2, 7) = 1, 2 négyztes maradék
Jacobi(4, 7) = 1, 4 négyztes maradék