Prvočíselný rozklad

Jak už bylo řečeno v úvodu článku, prvočíselný rozklad čísla X není nic jiného, než určení prvočísel (přejít na článek Prvočíslo), které když spolu vynásobíme, dostaneme opět číslo X.

Nejlépe to pochopíte z příkladů:

4=22
10=21*51
12=22*31
14=21*71
15=31*51
16=24
...
52=22*13
68=22*17
153=32*17
1584=24*32*11
...

Nejlehčí je určování prvočíselného rozkladu čísel, které jsou prvočísla. V takovém případě je totiž prvočíselný rozklad samotné číslo X:

5=5
7=7
11=11
13=13
...

Prvočíselný rozklad se často používá při určování nejmenšího společného násobku (přejít na článek Nejmenší společný násobek) a největšího společného dělitele (přejít na článek Největší společný dělitel).

Možná vás napadá, jestli je možné některé číslo rozložit na více způsobům, nebo jestli lze určit prvočíselný rozklad každého čísla. Odpověď je ne a ano. Každé číslo (větší než jedna) lze rozložit pouze na jeden způsob. Ano, každé číslo lze rozložit. Tyto skutečnosti dokazuje základní věta aritmetiky.

Faktorizace dělením

Následující postup, jak rozložit nějaké číslo na součin prvočísel je ten nejhorší, jaký si můžete vybrat. Je velmi časově náročný, nicméně se na něm dá pochopit podstata faktorizace (rozkládání).

Máme-li nějaké číslo n, které chceme rozložit na součin prvočísel, nejprve musíme najít všechna prvočísla do hodnoty . Jakmile tato prvočísla máme, pokoušíme se jimi dělit původní číslo. Pokud dělení vyjde beze zbytku, víme, že daný dělitel je součástí rozkladu. Pokud nevyjde, posuneme se na další prvočíslo v našem seznamu. Jakmile dojdeme na konec seznamu, měli bychom mít rozklad hotový.

Předpokládám, že z předcházejícího vysvětlení asi moc moudří nejste, takže se pokusíme krok po kroku rozložit číslo 100.

n = 100

Musíme tedy najít prvočísla menší než 10 - 2, 3, 5, 7
Začneme od nejmenších:
1) 100 / 2 = 50, zbytek: 0 › přidáme do rozkladu číslo 2 
2) 50 / 2 = 25, zbytek: 0 › přidáme do rozkladu číslo 2
3) 25 / 2 = 12, zbytek: 1 › musíme otestovat další prvočíslo, tedy 3
4) 25 / 3 = 8, zbytek: 1 › musíme otestovat další prvočíslo, tedy 5
5) 25 / 5 = 5, zbytek 0 › přidáme do rozkladu číslo 5
6) 5 / 5 = 1, zbytek 0 › přidáme do rozkladu číslo 5
Jelikož je n rovno jedné, nemusíme další čísla testovat, rozklad je hotový.
100 = 2*2*5*5

Následuje ukázka, jak by mohl takový algoritmus vypadat v jazyce Python:

#-*- coding: utf-8 -*-
from math import*
import random
def faktorizace_delenim(i):
    prvocisla = [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]
    seznam=[]
    cislo = 0
    while len(prvocisla) != cislo:
        if i%prvocisla[cislo] == 0:
            seznam.append(prvocisla[cislo])
            i = i/prvocisla[cislo]
        else:
            cislo = cislo +1     
        if i == 1: break
    seznam.append(i)
    return seznam
print faktorizace_delenim(13)

Eulerova metoda

Pomocí této metody se dají rozložit pouze čísla, které jsou součtem dvou různých čtvercových čísel.

Tento vzorec upravíme na:

Nyní si zdafinujeme konstantu k=GCD((a-c), (d-b)) a konstantu n=GCD((a+c), (d+b)). GCD znamená největší společný dělitel (přejít na článek Největší společný dělitel). Musí tedy platit:

Výsledný vzorec bude tedy vypadat takto:

Zkusíme si rozložit číslo 5353:

5353=132+722=272+682
k=2
n=20
m=2
l=7

Tento algoritmus lze pochopitelně aplikovat pouze na čísla, které se rovnají součinu dvou prvočísel. Je zde ale jedna potíž, ani když je číslo tvořeno součinem dvou prvočísel nemusí být tento algoritmus vždy úspěšný. Tento algoritmus nebude fungovat tehdy, pokud je číslo tvořeno 4k+3 nebo 4k+1:

3053 = 43 * 71
3053 = 4*763+1

3051 = 3*3*3*113
3051 = 4*762+3

Následuje zdrojový kód tohoto algoritmu v jazyce Python:

#-*- coding: utf-8 -*-
from math import*
import random
def nejvetsi_spolecny_delitel(cislo1,cislo2):
    while cislo2 != 0:
        r=cislo1%cislo2
        cislo1=cislo2
        cislo2=r
    return cislo1
def ctverec(x, cislo = 2):
    while 1:
        r=x-cislo**2
        if r < 0:
            return -1, -1
        if int(sqrt(r)) == sqrt(r):
            return cislo, sqrt(r)
        cislo = cislo+1

def euler(x):
    a, b = ctverec(x)
    if a == -1:
        return u"Toto číslo nelze pomocí tohoto algoritmu rozložit. "
    c, d = ctverec(x, min([a, b])+1)
    if (a == c or a == d):
        return u"Toto číslo nelze pomocí tohoto algoritmu rozložit. "
    k=abs(nejvetsi_spolecny_delitel(a-c, d-b))
    n=abs(nejvetsi_spolecny_delitel(a+c, d+b))
    m=(a+c)/n
    l=(d+b)/n
    return str((k/2)**2+(n/2)**2)+" * "+str(m**2+l**2)+" = "+str(x)
print euler(1000009)

Pollardův rho algoritmus

Tento algoritmus byl vymyšlen v roce 1975 Johnem Pollardem. Tento algoritmus se velmi hodí na rozkládání čísel s nízkým faktorem (s nízkými čísly v prvočíselném rozkladu). Pracuje na podobném principu jako faktorizace dělením, ale s tím rozdílem, že se nesnaží najít všechny členy prvočíselného rozkladu, ale pouze jeden (a ani ten nemusí být prvočíslo, proto musíme na výstup z toho algoritmu aplikovat ještě faktorizaci dělením).

a = náhodné číslo z intervalu (2, n-3)
b = náhodné číslo z intervalu (1, n-1)
g = 1
Dokud g == 1:
    a = f(a, n)
    b = f(b, n)
    b = f(b, n)
    g = GCD(a-b, n)
Když g == n:
    return -1
return g

V předchozím popisu se třikrát vyskytuje funkce f. Ta přijímá parametry x, n a vrací x^2+y mod n, kde y je náhodné číslo z intervalu (1, n-1).

Jak už bylo řečeno, tento algoritmus vrací nějakého dělitele daného čísla. Ale tento dělitel nemusí být vždy nutně prvočíslo. Proto se výstup z programu musí testovat nějakým dalším algoritmem.

Pokud tento algoritmus aplikujeme 10 krát například na číslo 618131841351864132181230010152, dostaneme násleudjící výstup:

4
3
3
6
3
18
2
88
12
9

Opět následuje zdrojový kód v jazyce Python:

from math import*
import random
def nejvetsi_spolecny_delitel(cislo1,cislo2):
    while cislo2 != 0:
        r=cislo1%cislo2
        cislo1=cislo2
        cislo2=r
    return cislo1
def f(x, n):      
    return (x**2+random.randint(1, n-1))%n
def pollard(n):
    a = random.randint(2, n-3)
    b = random.randint(1, n-1)
    g = 1
    while g == 1:
        a = f(a, n)
        b = f(b, n)
        b = f(b, n)
        g = nejvetsi_spolecny_delitel(abs(a-b), n)
    if g == n:
        return -1
    return g