MÁRTON Gyöngyvér

Algoritmusok

1. Euklidészi algoritmus: két egész szám (a, b) legnagyobb közös osztójának (d) a meghatározása, jelölése az angol szaknyelv alapján: gcd(a, b)

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:

gcd(64, 60) = 4
gcd(104, 221) = 13

2. Kiterjesztett Euklidészi 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 a kö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:
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

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: Az 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. Az inverz kiszámítására a kiterjesztett Eukleidészi algoritmust használjuk.

Megjegyzés: a fenti kongurenciának a megoldhatósági feltetele az, hogy gcd(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:
23·x = 1 mod 61, a megoldás: x = 8
17·x = 1 mod 27, a megoldás: x = 8

Ha n prím, akkor másik módszerrel is meghatározható az inverz, kis Fermát tétele alapján fennáll, hogy a^n-1 = 1 mod n, azaz a· a^n-2 = 1 mod n, ahonnan: x = a^n-2 mod n.

Példa:
Határozzuk meg 5, mod 17 szerint inverzét.

5^-1 = 5¹⁵ mod 17
5¹⁵ = 5⁸·5⁴·5²·5¹ = 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 gcd(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:

17·x = 25 mod 27, a megoldás: x = 11
17·11 = 187, 187 = 27·6 + 25

23·x = 15 mod 61, a megoldása: x = 59
23·59 = 1357, 1357 = 61·22 + 15

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 elosztjuk a gcd(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: alap^exp (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 algaritmus megvizsgálja az n páratlan számról hogy prím-e, vagy sem.

1. megkeressük azokat a q, k számokat, hogy fennáljon: q- párátlan és n = 2^k·q + 1
2. legyen x egy tetszőleges szám és y = x^q (mod n), 2 <= x < n
3. ha y = 1, akkor a szám prim, azaz True ad vissza az algoritmus
4. másképp j = 1, 2, ... , k-1 –re elvégezzük

Ha y = n-1 akkor a szám prim, azaz True ad vissza az algoritmus
Másképp, ha y = 1 akkor a szám nem prim, azaz False ad vissza az algoritmus
Meghatározzuk y = y·y ( mod n )

5. a szám nem prim, azaz False ad vissza az algoritmus

Példák:

legyen n = 63, ekkor n = 2³·7 + 1, tehát q = 7, k = 3
legyen x = 8, y = 8⁷ (mod 63) = 8
meghatározzuk y = 8·8 (mod 63) = 1 → False

legyen n = 61, ekkor n = 2²·15 + 1, tehát q = 15, k = 2
legyen x = 8, y = 8¹⁵ (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, meghatározzuk n = p - 1, ahol n prímfaktorizációja n = p₁^e₁·p₂^e₂·... ·p_k^e_k

1. legyen a egy tetszőleges elem a következő halmazból: {2, ..., p - 1}
2.i = 1, 2, ..., k-ra

meghatározzuk b = a^n/p_i mod p
ha b = 1, akkor új a értéket választunk, azaz az 1. lépéstől újra kezdjük a tesztelést

3. a primitív gyök

Példa:

1. p = 13, n = 12
2. n = 2²·3
3. legyen a = 8
4. i = 1,2-re meghatározzuk:

b = 8⁶ mod 13 = 12, ahol 6 = 12/2
b = 8⁴ 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 ⁶ mod 13 = 12, ahol 6 = 12/2
b = 7 ⁴ mod 13 = 9, ahol 4 = 12/3

5. tehát a = 7 primitív gyök

7¹mod 13 = 7
7²mod 13 = 10
7³ mod 13 = 5
7⁴mod 13 = 9
7⁵mod 13 = 11
7⁶mod 13 = 12

7⁷ mod 13 = 6
7⁸ mod 13 = 3
7⁹ mod 13 = 8
7¹⁰ mod 13 = 4
7¹¹ mod 13 = 2
7¹² mod 13 = 1

8¹mod 13 = 8
8²mod 13 = 12
8³ mod 13 = 5
8⁴mod 13 = 1
8⁵mod 13 = 8
8⁶mod 13 = 12

8⁷ mod 13 = 5
8⁸ mod 13 = 1
8⁹ mod 13 = 8
8¹⁰ mod 13 = 12
8¹¹ mod 13 = 5
8¹² mod 13 = 1

6. Álvéletlen számgenerálás (random number): lineáris kongruencián alapuló álvéletlen számok generálása, n számot generál véletlenszerűen, a kezd kiinduló érték alapján. Kriptográfiai számításokban nem alkalmazható.

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éktétel: az algoritmus meghatározza azt x egész számot mely eleget tesz a következő kongruencia rendszernek:

x ≡ a₁ mod m₁
x ≡ a₂ mod m₂
…
x ≡ a_n mod m_n

ahol m₁, m₂, ..., m_n> 0 és páronként relatív prímek, az a₁, a₂, ..., a_n pedig tetszőleges egész számok. A rendszernek egyetlen megoldás lesz mod(m₁· m₂· ...· m_n) szerint.

Az algoritmus:

chinese_remainder( n, m₁, m₂, ..., m_n, a₁, a₂,..., a_n )
{
    m = m₁* m₂* ... * m_n;
    res = 0;
    for i from 1 to n do
    {
        M = modulus div m_i;
        inv = inverz(M, m_i);
        res = (res + inv * M * a_i) mod m;
    }
    return res;
}

8. A Jacobi szimbólum meghatározása:
-1 értéket határoz meg az algoritmus, ha a nem négyzetes (kvadratikus) maradék mod n szerint, másképp, ha négyzetes maradék, akkor 1-et.

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

0² mod 7 = 0
1² mod 7 = 1
2² mod 7 = 4
3² mod 7 = 2
4² mod 7 = 2
5² mod 7 = 4
6² 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