Prebrajanje delilaca

Prebrajanje delilaca je lako razumljiv algoritam rastavljanja na faktore. Suštinska ideja testova podele je da vidimo da li ceo broj n, može podeliti svaki broj u redu koji je manji od n. Na primer, za ceo broj n = 12, samo brojevi kojim ga delimo su 1,2,3,4,6,12. Izbor samo najvećih prostih brojeva u primarnoj listi daje da je 12 = 3 × 4.

Metod[uredi | uredi izvor]

S obzirom na prirodan broj n (u ovom članku n se odnosi na "ceo broj koji se računa"), proces podela se sastoji od sistematskog testiranja da li je n deljiv sa bilo kojim manjim brojem. Jasno, to je samo korisno za testiranje kandidata manjih od n, i kako od dva više jer je proizvoljno n češće deljivo sa dva nego sa tri, i tako dalje. Ovim naručivanje, nema smisla u testiranju za deljivosti od četiri ako je broj već određen i nedeljiv sa dva, pa tri i bilo kojim višestruko većim brojem, itd. Dakle, napori se mogu smanjiti izborom samo prostih brojeva kao kandidata. Osim toga, prebrajanje delilaca ne treba ići dalje od koren iz n jer, ako je n deljiv sa nekim brojem p, zatim n = p × k i ako je k bilo koji manji broj od p, n bi ranije bio otkriven sa ku ili sa primarnim deliocem ku.

Definitivno združivanje prostih delilaca je moguće. Pretpostavimo da je P₁ i-ti glavni delilac, tako da je P₁ = 2, P₂ = 3, _P₃ = 5, itd. Zatim se poslednji prost broj testira kao mogući faktor n P_i gde je P²_{i + 1} > n; ekvivalentnohere što bi ovde značilo da je P_{i + 1} is a delilac. Dakle, testiranje sa 2, 3, i 5 je dovoljno do n = 48 ne samo 25 zato što je kvadrat sledećeg glavnog 49, a ispod n = 25 samo su 2 i 3 dovoljni. Kada bi kvadratni koren iz n bio ceo broj, onda bi i delilac n bio savršen kvadrat.

Primer podele algoritma, korišćenjem slučajnog prostog broja za proste brojeve generatora, kao u (Pajtonu):

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n < 2:
        return []
    prime_factors = []
    for p in prime_sieve(int(n**0.5) + 1):
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1:
        prime_factors.append(n)
    return prime_factors

Prebrajanje delilaca će garant pronaći faktor n ako postoji, jer proverava sve moguće proste delioce n. Prema tome, ako algoritam nađe jednog delioca, n, to je dokaz da je n prost. Ako se pronađe više od jednog delioca, tada je n složen broj. Mnogo računskih prednosti je način da se kaže da prost broj broj čiji kvadrat ne prelazi n i deli ga bez ostatka, onda n nije prost.

Brzina[uredi | uredi izvor]

U najgorem slučaju, prebrajanje delilaca je težak algoritam. Za bazu 2n cifre broja, a ako se polazi od dva i radi do kvadratnog korena iz a, algoritam zahteva

\pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}

prebrajanje delilaca, gde $\scriptstyle \pi (x)$ označava funkciju raspodele prostih brojeva, za proste brojeve manje od x. Ovo ne uzima u obzir primarno testiranje za dobijanje prostih brojeva kao delilaca. Koristna tablica ne mora biti velika: P (3512) = 32749, poslednju cifru koja odgovara u celom šesnaest-bitnom broj i P (6542) = 65521 za nepotpisane cele šesnaest-bitne brojeve. To bi dovoljno da se testira na proste brojeve do 65537² = 4,295,098,369. Priprema takve tabele (obično putem eratostenovog sita) će biti samo korisna ako mnogo brojeva treba da se testira. Ako se umesto toga koristi varijanta bez prostog testiranja, već jednostavno deljenje svakog neparnog broja manjeg od kvadratnog korena baze-2n cifre broj A, glavni ili ne, to može da potraje i do oko:

2^{n/2}

U oba slučaja traženo vreme raste eksponencijalno sa ciframa broja.

Ipak, ovo je sasvim zadovoljavajući način, imajući u vidu da čak i najpoznatiji algoritmi imaju eksponencijalni rast vremena. Za izabrana nasumice iz celih brojeva datnj dužine, postoji 50% šanse da 2 predstavlja delilac a, a 33% šanse da 3 predstavlja delilac, i tako dalje. Može se pokazati da 88% svih pozitivnih celih brojeva imaju delilac ispod 100, a da je 92% sadrži delilac u 1000. Prema tome, kada se suoči sa proizvoljno velikim a, vredi da se proveri deljivost od malih prostih brojeva, jer za a = 1000, u osnovi 2n = 10.

Međutim, višecifreni brojevi koji nemaju delioce u malim prostim brojevima mogu zahtevati dane ili mesece da prebroji delioce. U takvim slučajevima se koriste druge metode, kao što su kvadratni sito i ukupan broj polja sita(GNFS). Pošto ove metode imaju eksponencijalni rast vremena, praktična granica od n cifara se postiže veoma brzo. Iz tog razloga, u kriptografiju javnog ključa, izabrane vrednosti imaju velike proste delioce slične veličinama, tako da se ne mogu računati bilo poznata metoda u korisnom vremenskom periodu na bilo kom slobodno računarskom sistemu ili računaru klastera kao što su superračunar i računarske mreže. Najveći kriptografija broja koji je izračunat je RSA-768, koristeći GNFS i mrežu stotina računara. Vreme rada je oko 2 godine.

Literatura[uredi | uredi izvor]

Čilds, Lindsej N. (2009). Konkretan uvod u višu algebru Osnovni tekstovi u matematici(3.deo) Njujork:Childs, Lindsay N. (2009). A concrete introduction to higher algebra. Undergraduate Texts in Mathematics (3rd izd.). New York, NY: Springer-Verlag. ISBN 978-0-387-74527-5. Zbl 1165.00002.
Crandall, Richard; Pomerance, Carl (2005). Prime numbers. A computational perspective (2nd izd.). New York, NY: Springer-Verlag. ISBN 978-0-387-25282-7. Zbl 1088.11001.
Krandal, Ričard; Pomerns, Karl (2005).

Spoljašnje veze[uredi | uredi izvor]

Javascript Prime Factor Calculator using trial division. Can handle numbers up to about 9×10¹⁵