Пребрајање делилаца

Пребрајање делилаца је лако разумљив алгоритам растављања на факторе. Суштинска идеја тестова поделе је да видимо да ли цео број н, може поделити сваки број у реду који је мањи од н. На пример, за цео број н = 12, само бројеви којим га делимо су 1,2,3,4,6,12. Избор само највећих простих бројева у примарној листи даје да је 12 = 3 × 4.

Метод

С обзиром на природан број н (у овом чланку н  се односи на "цео број који се рачуна"), процес подела се састоји од систематског тестирања да ли је н дељив са било којим мањим бројем. Јасно, то је само корисно за тестирање кандидата мањих од н, и како од два више јер је произвољно н чешће дељиво са два него са три, и тако даље. Овим наручивање, нема смисла у тестирању за дељивости од четири ако је број већ одређен и недељив са два, па три и било којим вишеструко већим бројем, итд. Дакле, напори се могу смањити избором само простих бројева као кандидата. Осим тога, пребрајање делилаца не треба ићи даље од корен из н  јер, ако је н дељив са неким бројем п, затим н = п × к и ако је к било који мањи број од п, н би раније био откривен са ку или са примарним делиоцем ку.

Дефинитивно здруживање простих делилаца је могуће. Претпоставимо да је П₁ и-ти главни делилац, тако да је П₁ = 2, П₂ = 3, _П3 = 5, итд. Затим се последњи прост број тестира као могући фактор н  П_i где је П²_{и + 1} > н; еквивалентноhere што би овде значило да је П_{и + 1} is a делилац. Дакле, тестирање са 2, 3, и 5 је довољно до н = 48 не само 25 зато што је квадрат следећег главног 49, а испод н = 25 само су 2 и 3 довољни. Када би квадратни корен из н био цео број, онда би и делилац н био савршен квадрат.

Пример поделе алгоритма, коришћењем случајног простог броја за просте бројеве генератора, као у (Пајтону):

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

Пребрајање делилаца ће гарант пронаћи фактор н ако постоји, јер проверава све могуће просте делиоце н. Према томе, ако алгоритам нађе једног делиоца, н, то је доказ да је н прост. Ако се пронађе више од једног делиоца, тада је н сложен број. Много рачунских предности је начин да се каже да прост број број чији квадрат не прелази н и дели га без остатка, онда н није прост.

Брзина

У најгорем случају, пребрајање делилаца је тежак алгоритам. За базу 2н цифре броја, а ако се полази од два и ради до квадратног корена из а, алгоритам захтева

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

пребрајање делилаца, где $\scriptstyle \pi (x)$ означава функцију расподеле простих бројева, за просте бројеве мање од x. Ово не узима у обзир примарно тестирање за добијање простих бројева као делилаца. Користна таблица не мора бити велика: П (3512) = 32749, последњу цифру која одговара у целом шеснаест-битном број и П (6542) = 65521 за непотписане целе шеснаест-битне бројеве. То би довољно да се тестира на просте бројеве до 65537² = 4,295,098,369. Припрема такве табеле (обично путем ератостеновог сита) ће бити само корисна ако много бројева треба да се тестира. Ако се уместо тога користи варијанта без простог тестирања, већ једноставно дељење сваког непарног броја мањег од квадратног корена базе-2н цифре број А, главни или не, то може да потраје и до око:

$2^{n/2}$

У оба случаја тражено време расте експоненцијално са цифрама броја.

Ипак, ово је сасвим задовољавајући начин, имајући у виду да чак и најпознатији алгоритми имају експоненцијални раст времена. За изабрана насумице из целих бројева датњ дужине, постоји 50% шансе да 2 представља делилац а, а 33% шансе да 3 представља делилац, и тако даље. Може се показати да 88% свих позитивних целих бројева имају делилац испод 100, а да је 92% садржи делилац у 1000. Према томе, када се суочи са произвољно великим а, вреди да се провери дељивост од малих простих бројева, јер за а = 1000, у основи 2н = 10.

Међутим, вишецифрени бројеви који немају делиоце у малим простим бројевима могу захтевати дане или месеце да  преброји делиоце. У таквим случајевима се користе друге методе, као што су квадратни сито и  укупан број поља сита(ГНФС). Пошто ове методе имају експоненцијални раст времена, практична граница од н цифара се постиже веома брзо. Из тог разлога, у криптографију јавног кључа, изабране вредности имају велике просте делиоце сличне величинама, тако да се не могу рачунати било  позната метода у корисном временском периоду на било ком слободно рачунарском систему или рачунару кластера као што су суперрачунар и рачунарске мреже. Највећи криптографија броја који је израчунат је RSA-768, користећи ГНФС и мрежу стотина рачунара. Време рада је око 2 године.

Литература

• Чилдс, Линдсеј Н. (2009). Конкретан увод у вишу алгебру Основни текстови у математици(3.део) Њујорк:Childs, Lindsay N. (2009). A concrete introduction to higher algebra. Undergraduate Texts in Mathematics (3rd изд.). 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 изд.). New York, NY: Springer-Verlag. ISBN 978-0-387-25282-7. Zbl 1088.11001. 
• Крандал, Ричард; Помернс, Карл (2005).

Спољашње везе

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