Saiakuntzazko zatiketa

Saiakuntzazko zatiketa zenbaki osoak faktorizatzeko algoritmoen artean errazen ulertzen dena da. Saiakuntzazko zatiketaren oinarrian dagoen funtsezko ideia honakoa da: faktorizatu beharrekoa n zenbaki osoa n baino txikiagoak diren zenbakiez zatigarria den ikustea. Adibidez, n=12 zenbaki osoaren zatitzaile bakarrak 1,2,3,4,6 eta 12 dira. Zenbaki lehenen potentzia handienak soilik hartuz, 12=3 x 4 adierazpena lortuko genuke.

Metodoa

Faktorizatu beharreko n zenbaki osoa emanik, saiakuntzazko zatiketa n baino txikiagoa den beste edozein zenbakiz zatigarria den ikusteko azterketa edo saiakera sistematikoa egitea da. Argi dago, n baino handiagoak diren zenbakiekin saiatzeak ez duela zentzurik, eta beraz, 2 zenbakitik hasi eta gorako ordenean gainerako zenbakiekin saiatzea dela zentzuzkoena, probabilitate handiagoa baitago zenbaki bat 2-z zatigarria izateko 3-z zatigarria izateko baino, eta horrela gainerakoekin ere. Ordenazio horrekin saiatuz gero, ez du zentzurik izango n zenbakia 4-az zatigarria den aztertzeak, 2-z zatigarria den aztertua izango baita 4 zenbakira iristerako. Arrazonamendu bera aplikatuko genuke 3 zenbakiarentzat, etab. Zenbaki horiek guztiak aldez aurretik baztertuz gero, saiakuntzazko zatiketak eskatzen duen saiakera kopurua arintzea lortuko genuke, zenbaki lehenak besterik ez baikenituzke faktore posibletzat hartuko.

Gainera, faktore horiek ez dira $\scriptstyle {\sqrt {n}}$ baino handiagoak izango. Izan ere, faktorizatu beharreko n zenbakia p zenbakiaz zatigarria bada, n =p x q modukoa izango da, eta q zenbakia p baino handiagoa izango da, p bada saiakuntzazko zatiketaren bidez aurkitutako lehenengo faktorea. Bi kasu eman daitezke: p=q eta p<q. Lehenengo kasuan p=q=$\scriptstyle {\sqrt {n}}$ beteko da eta bigarren kasuan p<$\scriptstyle {\sqrt {n}}$ izan behar du. Hortaz, n-ren faktoreak aurkitzeko $\scriptstyle {\sqrt {n}}$ zenbakira artekoekin saiatzea nahikoa dela ikusten da.

Posiblea da, beraz, aztertu beharreko zenbaki lehenen muga zehaztea. Demagun $\scriptstyle P(i)$ dela i-garren zenbaki lehena. Horrela, $\scriptstyle P(1)=2$, $\scriptstyle P(2)=3$, $\scriptstyle P(3)=5$ etab. notazioaz adieraziko ditugu zenbaki lehenak. Faktorizatu beharreko n zenbaki osoa izanik, $\scriptstyle P(i)$ da aztertzea merezi duen azken zenbaki lehena, $\scriptstyle P(i+1)^{2}>n$ baita. Adibidez, n=48 zenbakirako, 2,3 eta 5 zenbaki lehenekin besterik ez dugu saiakera egingo, 5<$\scriptstyle {\sqrt {n}}$<7 baita; hurrengo zenbaki lehena den 7a azterketatik kanpo geratzen da, $\scriptstyle 7^{2}>48$. Bestalde, $\scriptstyle {\sqrt {n}}$ zenbaki osoa balitz, n-ren faktorea izango litzateke eta ondorioz n zenbaki karratu perfektua.

Hona hemen saiakuntzazko zatiketarako algoritmorako inplementazio bat, zenbaki lehenen sorkuntzarako algoritmo bat erabiltzen duena (Python programazio lengoaian idatzita dago):

def saiakuntzazko zatiketa(n):
    """Zenbaki oso baten faktore diren zenbaki lehenen zerrenda itzultzen du."""
    if n < 2:
        return []
    prime_factors = []
    for p in prime_sieve(int(n**0.5)):
        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

Saiakuntzazko zatiketak n-ren faktoreren bat aurkitzea bermatzen du, existituz gero, n-ren faktore lehen guztiak begiratzen dituelako. Ondorioz, algoritmoak n faktore bakar bat aurkitzen badu frogatua geratuko da n zenbaki lehena dela. Faktore bat baino gehiago aurkitzen baditu, n zenbaki konposatua izango da.

Konplexutasun konputazionala

Kasurik okerrenean, saiakuntzazko zatiketaren algoritmoa konputazionalki oso garestia da. Algoritmoak 2-tik hasi eta $\scriptstyle {\sqrt {n}}$ zenbakira artekoekin egingo ditu zatigarritasun probak. Hori horrela izanik,

$\pi ({\sqrt {n}})\approx {2{\sqrt {n}} \over \ln n}$

saiakera egin beharko ditu, non $\pi (x)$ funtzioa zenbaki lehenen kontaketa funtzioa den; x baino txikiagoak diren zenbaki lehenen kopurua, alegia. Faktore izateko hautagaiak zenbaki lehenak izanik, zenbaki lehenen testa egiteak gainkarga sortuko du; kalkulu horretan gainkarga hori ez da kontuan izan. Zenbaki lehenen testa erabili gabe, $\scriptstyle {\sqrt {n}}$ baino txikiagoak diren zenbaki bakoiti guztiez zatitzea erabakiz gero, lehena izan edo ez,

${{\sqrt {n}} \over 2}$

saiakera inguru beharko dira; faktorizatu beharreko n zenbakia handia denean, saiakuntza kopurua dexente hazten da.

Saiakuntzazko zatiketaren algoritmoa konputazionalki ezinezkoa gertatzen da tamainaz antzekoak eta handiak diren faktoreak dituen n zenbakietarako. Gutxienez faktore txikiren bat baduen n zenbakia izanik, saiakuntzazko zatiketa faktore txiki hori aurkitzeko metodo azkarra izan daiteke. Kontuan izan behar da, ausazko n baterako, %50eko probabilitatea dagoela 2a zenbaki horren faktore izateko, %33koa 3a bere faktorea izateko eta horrela jarraiki. Egiazta daiteke zenbaki oso positiboen %88ak 100 baino txikiagoa den faktore bat baduela eta %91k 1000 baino txikiagoa den faktore bat.

Faktore lehen txikirik ez duten digitu kopuru handiko zenbakiak saiakuntzazko zatiketaren bitartez faktorizatzeak egunak edo hilabeteak eman ditzake. Halakoetan beste metodo batzuk erabili ohi dira: Metodo kuadratikoa, GNFS Metodoa, adibidez.

Zenbaki handien faktorizazioarekin sortzen diren zailtasun konputazional horiek kontuan izanik, gako publikoko kriptografian tamainaz handiak eta haien artean oso antzekoak diren faktore lehenak aukeratzea gomendatzen da. Horrela, ez da posible izango zenbakia erraz faktorizatzea. RSA-768 da faktorizatua izan den RSA zenbakirik handiena. 232 digituko zenbakia da (768 bit), GNFS eta ehunka konputagailuz osaturiko sarea erabili ziren eta deskodetze-prozesuak 2 urte inguru iraun zituen (2009).

Ikus, gainera

• Zenbaki osoen faktorizazioa
• Zenbaki lehenen testa

Kanpo estekak

• (Ingelesez) Weisstein, Eric W.: "Trial Division" MathWorld-en.
• Trial Division PlanetMath-en
• Faktore Lehenak saiakuntzazko zatiketaren bitartez Jvascript Kalkulagailua. 9×10¹⁵ baino txikiago diren zenbakiekin lan egin dezake.

• Datuak: Q1333681