Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
161.Podstawowepojęcia
TWIERDZENIE1.3.Każdaliczbanaturalnan>1dasięprzedstawićwpostaci
nlpip2···pk,
przyczymk≥1,liczbyzaśpi,...,pksąpierwsze.
(1.1)
Dowód:Zastosujemyindukcję.Przynl2przyjmiemyoczywiściekl1,pil2.
Załóżmyterazprawdziwośćtezydlawszystkichn<N.JeśliNjestliczbąpierwszą,to
kładziemykl1,pilN.WprzeciwnymraziemożemynapisaćNlab,1<a,b<N,
bykorzystajączzałożeniaindukcyjnego,otrzymać
alpi···pr,
blpr+i···p5
coprowadzidoNlpi···p5.
(pi∈P),
WNIOSEK1.Każdaliczbanaturalnan>1maprzynajmniejjedendzielnikpierwszy,
anajmniejszyznichnieprzekraczadn.
Dowód:Pierwszaczęśćjestnatychmiastowymwnioskiemztwierdzenia,drugazaś
wynikazuwagi,żejeślipjestnajmniejsząliczbąpierwsządzielącąnorazdln/p,to
djestdzielnikiemn,azatemd≥piotrzymujemynlpd≥p2,awięcp≤dn.
WNIOSEK2.Każdaliczbanaturalnan>1dasięprzedstawićwpostacinlp
ip
α1
2···
α2
···p
k,przyczymk≥1,wykładnikiIisąliczbaminaturalnymi,liczbyzaśpi,...,pk
αk
sąróżnymiliczbamipierwszymi.
Dowód:Wystarczywewzorze(1.1)połączyćrówneczynnikipierwsze.
3.Sprawdzenie,czydanaliczbaNjestpierwsza,niejestnaogółsprawąprostą.
Wnarzucającejsięmetodzie,polegającejnasprawdzeniupodzielnościNprzezliczby
pierwszemniejszeodN,można,dziękiwnioskowi1ztwierdzenia1.3,ograniczyćsię
doliczbpierwszych,nieprzekraczającychdN,aleilośćtychliczbdladużychNjest
rzędu2dN/logN(cowynikaztzw.twierdzeniaoliczbachpierwszych,któreudowod-
nimywrozdziale5),azatemnależywykonaćprzynajmniejtyleżoperacjidzielenia,co
dlawielkichNniejestwykonalne.Pewienprostytestprobabilistycznypodamyjako
zastosowaniewniosku2ztwierdzenia2.10.
DladużychNteoretycznienajszybsząznanąmetodępodaliniedawnoM.Agrawal,
N.KayaliN.Saxena[1].WymagaonaconajwyżejBlogi2Noperacji,przyczymB
jestpewnąstałą.Poprzednioznanabyłajedyniemetodawymagającaconajwyżej
Bexp(CloglogNlogloglogN)
operacji,przyczymBiCsąpewnymistałymi(Adleman,Pomerance,Rumely[1]).
AlgorytmyprzydatnewpraktycemożeCzytelnikznaleźćwksiążceD.E.Knutha[1]
orazwpodręcznikuN.Koblitza[1]iwmonografiach:Crandall,Pomerance[1]iRiesel
[1].Istniejetakżeszeregmetodprobabilistycznych,którewwieluwypadkachokazują
sięskuteczne.PatrznaprzykładAdleman,Huang[1],Adleman,Pomerance,Rumely[1].
W1876rokuE.Lucasudowodnił,żeliczba2i27l1,mająca39cyfr,jestpierwsza,
ajegorekordzostałpobitydopierowroku1951,gdyJ.C.P.Miller[1],używająckom-
puteraEDSAC,znalazł79-cyfrowąliczbępierwszą1+180(2i27l1)2.Wrokpotem
