Talteoretiska_algoritmer.sagews

Kryptering 1

Talteoretiska algoritmer

load('../kryptering.sage')

*** Pythonbibliotek för kryptering, version 2017 ***

Eratosthenes såll

Nedan ser vi en enkelt implementation av Eratosthenes såll.

n = 1000
a = [True for k in [0..n]]  # inledningsvis betraktar vi alla tal 0, 1, ..., n som möjliga primtal
a[0] = False  # talet 0 är inte ett primtal
a[1] = False  # talet 1 är inte ett primtal
b = 2  #  första ostrukna tal, d.v.s. ett primtal
while b <= sqrt(n) :
    for c in [2..n/b] :
        a[b * c] = False  # talet b * c är inte ett primtal
    b = a.index(True, b + 1)  # finn nästa primtal, d.v.s. nästa ostrukna tal

De positioner i listan a vars element är lika med True är primtal.

# enumerate ger en lista var element har formen (index, element)
primtal1000 = [p for (p, s) in enumerate(a) if s]
primtal1000

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Låt oss kontrollera om alla kvarvarande tal är primtal.

all([ZZ(p).is_prime() for p in primtal1000])

True

Fermats primtalstest och Carmichaeltal

För vilka $a$ låter vi oss luras att $15$ är ett primtal? Med andra ord, för vilka $a$ är $a^{n-1} \equiv 1 \pmod{n}$?

n = 15
[a for a in [2..n-1] if power_mod(a, n - 1, n) == 1]

[4, 11, 14]

För vilka heltal $a$ kommer Fermats primtalstest finna att $15$ är sammansatt?

[a for a in [2..n-1] if power_mod(a, n - 1, n) != 1]

[2, 3, 5, 6, 7, 8, 9, 10, 12, 13]

Det minsta Carmichaeltalet är $561$, d.v.s. ett sammansatt tal som Fermats primtalstest inte kan visa är sammansatt.

n = 561
[a for a in [2..n-1] if power_mod(a, n, n) != a]

[]

Miller-Rabins primtalstest

Med funktionen valuation(a, p) kan man bestämma det stösta heltal $k$ sådant att $p^k \mid a$.

n = 132241  # det heltal vi vill avgöra om det är ett primtal
k = valuation(n - 1, 2)
m = n // 2^k
print 'k =', k, 'och m =', m

k = 4 och m = 8265

b = Mod(randint(2, n - 2), n)  # välj bas
b = b^m
if b in [-1, 1] :
    print 'Talet', n, 'har passerat Millers test i basen', b
else :
    for i in [1..k-1] :
        b = b^2
        if b == -1 :
            print 'Talet', n, 'har passerat Millers test i basen', b
            break
        elif b == 1 :
            print u'Talet', n, u'är sammansatt'
            break

Talet 132241 har passerat Millers test i basen 132240

Fermatfaktorisering

n = 20255029  # det heltal vi vill faktorisera
a = floor(sqrt(n)) + 1
while not (a^2 - n).is_square() :
    a += 1
b = sqrt(a^2 - n)
print n, '=', a - b, '*', a + b

20255029 = 4073 * 4973

Pollars $(p - 1)$-metod

n = 20255029
a = randint(2, n - 1)
r = Mod(a, n)
k_max = 1000  # för att undvika en oändlig loop
for k in [2..k_max] :
    r = r^k
    d = gcd(r - 1, n)
    if 1 < ZZ(d) < n :
        print d, u'är en faktor till', n
        print 'a =', a, 'och k =', k
        break

4973 är en faktor till 20255029 a = 8289690 och k = 113

Pseudoslumptal

Blum-Blum-Shubs pseudoslumpbitsgenerator

Funktion BlumBlumShub returnerar en bitström om $n$ stycken bitar, som generats enligt Blum-Blum-Shubs pseudoslumpbitsgenerator. Argumenten $x_0$ och $m$ är slumpfrö respektive modulus. Heltalet $m$ ska vara produkten av två primtal $p$ och $q$, som båda är kongruenta med~3 modulo~4. Välj t.ex. primtalen $p = 10039$ och $q = 20507$. Båda ger resten $3$ vid division med~$4$.

p, q = 10039, 20507
p % 4, q % 4

(3, 3)

m = p * q
m

205869773

Startvärdet $x_0$ skapar vi genom att välja ett heltal $x$ som är relativt prima med $m$, t.ex. $x = 5212861$.

x = 5212861
gcd(x, m)

1

Sätt $x_0 \equiv x^2 \pmod{m}$.

x0 = x^2 % m
x0

139118186

Vi använder dessa värden för att generera en bitström av femton pseudoslumpbitar.

BlumBlumShub(x0, m, 15)

[0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0]

Linear Feedback Shift Register

LFSR (Linera Feedback Shift Register) är en annan metod att generera en ström av pseudoslumpbitar. Funktionen LFSR returnerar en bitström om $n$ bitar enligt rekursionsformeln $$x_{i+j} \equiv k_0 x_{i} + k_1 x_{i+1} + \dots + k_{j-1} x_{i+j-1} \pmod{2}, \quad i = 0, 1, 2, \ldots,$$ där $\boldsymbol{x} = (x_0, x_1, \ldots, x_{j-1})$ och $\boldsymbol{k} = (k_0, k_1, \ldots, k_{j-1})$. Om t.ex. $$x_{i+4} \equiv x_i + x_{i+2} \pmod{2}, \quad i = 0, 1, 2, \ldots,$$ där $x_0 = 0$, $x_1 = 1$, $x_2 = 0$ och $x_3 = 0$, så är $\boldsymbol{x} = (0,1,0,1)$ och $\boldsymbol{k} = (1,0,1,0)$. Låf $f(x_0, x_1, x_2, x3) = x_0 + x_2$. Då är $x_{i+4} \equiv f(x_i, x_{i+1}, x_{i+2}, x_{i+3}) \pmod{2}$. De tjugo första pseudoslumpbitarna ges av följande.

def f(x) :
    return (x[0] + x[2]) % 2

LFSR([0, 1, 0, 0], f, 20)

[0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]

Lehmers slumptalsgenerator

Välj ett positivt heltal $m$ samt tre heltal $x_0$, $a$ och~$c$ i $\mathbb{Z}_m$. Den rekursiva formeln $$x_n \equiv a x_{n-1} + c \pmod{m}, \quad n = 1, 2, 3, \ldots,$$ genererar en följd av heltal $(x_0, x_1, x_2, x_3, \ldots)$. Då $m = 1237$, $a = 673$, $c = 118$ och $x_0 = 45$ så ges de tjugo första pseudoslumptalen av följande

Lehmer(45, 673, 118, 1237, 20)

[45, 715, 120, 473, 538, 988, 773, 807, 186, 359, 510, 699, 485, 1192, 758, 608, 1092, 256, 463, 1230]