[python] Faktorizace

[Jakub Vojáček]

Dobrý den,

Vyvýjím jednu aplikaci a potřebuji, aby daná aplikace uměla rozložit číslo na součin prvočísel (prvočíselný rozklad). Naprogramovat nějaký základní algoritmus není problém, ale problém nastane, pokud do algoritmu zadám nějaké větší číslo (např. 4848484848484841178813). 
Mému algoritmu toto číslo trvá dost dlouho, ale například na této stránce dostanu výsledek takřtka okamžitě: http://www.numberempire.com/primenumbers.php

Jaký algoritmus byste mi doporučili používat? Na menší čísla se dá použít faktorizace dělením:

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

ale tenhle algoritmus má tu nevýhodu, že bych ten seznam prvočísel (o velikost od 0 do sqrt(i)) musel vygenerovat, což trvá dost dlouho.

Další algoritmus co znám je Eulerova metoda, ale ta je použitelná pouze v některých speciálních případech:

#-*- 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)

Poslední algoritmus, který znám je Pollardův rho algoritmus. 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ě nějaký jiný faktorizační algoritmus). Nicméně zvládně celkem úspěšně najít dělitele i ohromných čísel:

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
print pollard(618131841351864132181230010152)


Znáte někdo nějaké efektivní řešení?

Děkuji

S pozdravem

Jakub Vojáček