96 Â

WIAT

N

AUKI

Sierpieƒ 1997

P

oszukiwanie dzielników wielkiej
liczby

1

jest jednym z najtrudniej-

szych problemów teorii liczb.

W poprzednim odcinku opisa∏em wy-
dajne metody sprawdzania, czy dana
liczba majàca oko∏o dwustu cyfr jest licz-
bà pierwszà. Chocia˝ mo˝na za ich po-
mocà dowieÊç, ˝e liczba nie jest liczbà
pierwszà, to jednak nie podajà dzielni-
ków. Czy uda si´ wype∏niç t´ luk´?

Przypomnijmy, ˝e dzielnikiem licz-

by nazywamy dowolnà liczb´, która
dzieli jà bez reszty, a liczb´ nazywamy
liczbà pierwszà, gdy jedynymi jej dziel-
nikami sà ona sama i 1. Teraz troch´
„geografii”. Kraina liczb pierwszych,
Pierwszolandia, jest rzadko i przypad-
kowo rozrzucona na osi li-
czbowej. Ale Dzielnikolan-
dia, Êwiat liczb naturalnych,
jest bardzo odmienny. W
niej znajdujà si´ liczby
pierwsze o jedynym nie-
trywialnym dzielniku rów-
nym tej˝e liczbie. Wi´k-
szoÊç liczb to nie liczby
pierwsze; oczywiÊcie co
druga jest wielokrotnoÊcià
2, co trzecia wielokrotnoÊcià
3, dwie z trzech sà wielo-
krotnoÊcià 2 lub 3. (Zasta-
nów si´, Czytelniku, dlacze-
go nie pi´ç szóstych?) Ale
znaczàca cz´Êç liczb nie ma
˝adnych ma∏ych dzielni-
ków. JeÊli potrafimy znaleêç
jeden dzielnik liczby, to po-
zosta∏e sà dzielnikami ilo-
razu, który jest liczbà mniej-
szà; tak wi´c g∏ówna trud-
noÊç polega na znalezieniu
tego pierwszego.

To naprawd´ ci´˝kie za-

danie; amerykaƒski mate-
matyk F. N. Cole sp´dza∏
wszystkie niedziele w cià-
gu trzech lat nad kartkà pa-
pieru, by w roku 1903 od-
kryç, ˝e 2

67

– 1 = 193 707 721

x

761 838 257 287. W osta-

tnich dziesi´cioleciach po-
st´p by∏ du˝o szybszy. Carl
Pomerance z University of
Georgia przedstawi∏ naj-
nowsze osiàgni´cia w prze-
glàdowym artykule, który
ukaza∏ si´ w grudniowym

numerze czasopisma Notices of the Ame-
rican Mathematical Society; ten odcinek

REKREACJI MATEMATYCZNYCH

powsta∏

w∏aÊnie na podstawie jego artyku∏u.

Szkolny sposób znajdowania dzielni-

ków danej liczby jest sformalizowanà
metodà prób i b∏´dów: zaczynamy od
2, nast´pnie sprawdzamy 3 itd. – a˝ do
pierwiastka kwadratowego z badanej
liczby. Metoda jest jednak okropnie nie-
wydajna. W roku 1970 po udoskonale-
niu pozwala∏a znajdowaç dzielniki liczb
o 20 cyfrach. Do roku 1980 granica ta
zosta∏a podniesiona do 50 cyfr, w roku
1990 mo˝na ju˝ by∏o rozk∏adaç liczby
o 116 cyfrach, a w 1994 – o 129. W roku
1996 znaleziono nowy algorytm, który

pozwala roz∏o˝yç na czynniki liczby
o 130 cyfrach, i to szeÊciokrotnie szybciej
ni˝ poprzednie metody.

Post´p ten po cz´Êci zawdzi´czamy

zwi´kszeniu mocy komputerów, ale
komputer pracujàcy milion razy szyb-
ciej poprawi ten rekord tylko o kilka
cyfr. Najwa˝niejszà sprawà jest zatem
pomys∏.

Na poczàtku stulecia matematycy

Allan J. C. Cunningham i Herbert J.
Woodall zapoczàtkowali tzw. Projekt
Cunninghama majàcy na celu rozk∏ad
liczb postaci r

k

±

1 dla r pomi´dzy 2

i 12 oraz du˝ych k. WÊród tych liczb
jest wiele obiektów ulubionych przez
matematyk´ rekreacyjnà: liczby Mer-
senne’a M

k

= 2

k

– 1, liczby Fermata F

k

=

2

2

k

+ 1, oraz tzw. repunitsy (czyli po-

wtarzajàce si´ jedynki) R

k

= 1111...1 =

(10

k

– 1)/9. Zazwyczaj ten problem ata-

kuje si´ za pomocà „kwadra-
towego sita”, które zawdzi´-
czamy Pomerance’owi.

Metoda nazwana zosta∏a

sitem, poniewa˝ traktuje
Dzielnikolandi´ jako piasz-
czystà pustyni´, przesiewa-
jàc niechciane liczby jak
ziarnka piasku. Prekursorem
sit jest sito Eratostenesa zna-
ne ju˝ staro˝ytnym Grekom.
Przemierzamy Dzielnikolan-
di´, odsiewajàc wszystkie
wielokrotnoÊci 2 – pierwszej
z liczb pierwszych. Nast´p-
nie odnajdujemy najmniej-
szà liczb´, która nam zosta-
∏a – 3: jest to kolejna liczba
pierwsza. Znów przemierza-
my Dzielnikolandi´, odsie-
wajàc wszystkie wielokrot-
noÊci 3. Konsekwentnie od-
rzucamy wszystkie wielo-
krotnoÊci 5 itd. W koƒcu po
nieskoƒczonej liczbie prze-
siewaƒ na naszej nieskoƒ-
czonej pustyni pozostanie je-
dynie Pierwszolandia.

Pomerance zaczà∏ od pro-

blemu, który zosta∏ mu po-
stawiony w szkole Êredniej:
roz∏ó˝ na czynniki 8051
w czasie pi´ciu minut.
Stwierdzi∏, ˝e do rozwiàza-
nia tego problemu potrzeb-
ny jest jakiÊ pomys∏, ale za
póêno wpad∏ na to, ˝e trzeba
zapisaç 8051 jako ró˝nic´
dwóch kwadratów: 8051 =
8100 – 49 = 90

2

– 7

2

. Algebra-

REKREACJE MATEMATYCZNE

Ian Stewart

Ruchome piaski Dzielnikolandii

SITO ERATOSTENESA jest metodà wyszukiwania

liczb pierwszych.

JUAN VELASCO

Computer Graphics

Â

WIAT

N

AUKI

Sierpieƒ 1997 97

iczna to˝samoÊç a

2

– b

2

= (a+b)(a–b) za-

pewnia, ˝e liczba ta mo˝e zostaç za-
pisana jako iloczyn (90 – 7)

x

(90 + 7) =

83

x

97. Pomys∏ ten przypisuje si´

XVII-wiecznemu francuskiemu mate-
matykowi Pierre’owi de Fermat.

W latach dwudziestych naszego stu-

lecia Maurice Kraitchik – autor Mathe-
matical Recreations – udoskonali∏ metod´
Fermata. Zauwa˝y∏ mianowicie, ˝e za-
miast przedstawiaç liczb´ n w postaci
ró˝nicy kwadratów niekiedy wystarczy
przedstawiç w ten sposób pewnà wielo-
krotnoÊç tej liczby. Dla przyk∏adu za-
∏ó˝my, ˝e mo˝emy zapisaç

kn = a

2

– b

2

= (a + b)(a – b)

Istnieje pewna klasa ma∏o interesujà-

cych rozwiàzaƒ, gdy a + b oraz a – b sà
wielokrotnoÊciami n, natomiast klasa
interesujàcych rozwiàzaƒ obejmuje licz-
by nie b´dàce wielokrotnoÊciami n. W
przypadku interesujàcego rozwiàzania
najwi´kszy wspólny dzielnik n i (a – b)
– oznaczany NWD(n; a – b) – musi byç
nietrywialnym dzielnikiem n, to zna-
czy ró˝nym od n i od 1. (Mo˝na tak˝e
u˝yç NWD(n; a + b), ale liczba wi´ksza
jest oczywiÊcie wi´kszym wyzwaniem.)
JeÊli spróbujemy znaleêç NWD me-
todami szkolnymi, a wi´c rozk∏adaç n
i a – b na czynniki pierwsze, po czym
sprawdzaç, które liczby pierwsze majà
te rozk∏ady wspólne, to daleko nie za-
jdziemy, poniewa˝ musimy roz∏o˝yç na

czynniki pierwsze liczb´ n. Istnieje jed-
nak skuteczniejsza metoda obliczania
NWD, znana ju˝ Euklidesowi ponad
2000 lat temu.

PrzypuÊçmy, ˝e chcemy roz∏o˝yç na

czynniki liczb´ 415 813. Zauwa˝amy, ˝e
15 x 415 813 = 2498

2

– 53

2

, tak wi´c dziel-

nikiem jest NWD(415 813; 2498 – 53) =
NWD(415 813; 2445). Dalej wykonujemy
nast´pujàce czynnoÊci:

1. Dzielimy 415 813 przez 2445,

otrzymujàc iloraz i reszt´: 415 813 =
170

x

2445 + 163.

2. Zauwa˝amy w powy˝szym rów-

naniu, ˝e jeÊli liczba dzieli bez reszty
415 813 i 2445, to musi tak˝e dzieliç bez
reszty 163. A zatem NWD(415 813; 2445)
= NWD(2445; 163).

3. Powtarzamy ten proces, dzielàc

2445 przez 163, by otrzymaç iloraz i
reszt´: 2445 = 15

x

163 + 0.

Poniewa˝ reszta wynosi 0, to 163

dzieli bez reszty 2445, a zatem
NWD(2445; 163) = 163. To z kolei ozna-
cza, ˝e 163 jest dzielnikiem 415 813;
wykonujàc dzielenie, otrzymujemy
drugi dzielnik 2551.

Wszystko to bardzo dobrze wyglàda,

ale powodzenie metody zale˝y od wy-
boru dobrego mno˝nika, w tym przy-
padku 15. Kraitchik mia∏ pomys∏, jak
uniknàç zgadywanki. Zaczynamy od
najmniejszej liczby x, której kwadrat jest
wi´kszy ni˝ n = 415 813, a mianowicie

x = 645. Wypisujemy wszystkie liczby
postaci Q(x) = x

2

– n dla x rosnàcego

i sprawdzamy, czy któraÊ z nich ma ∏a-
twy rozk∏ad. Oto co otrzymujemy:

x

Q(x)

dzielniki

645

212

2

2

x

53

646

1503

3

2

x

167

647

2796

2

2

x

3

x

233

648

4091

4091

649

5388

2

2

x

3

x

449

i tak dalej a˝ do

690

60 287 19

2

x

167

W tym momencie widzimy, ˝e ilo-

czyn Q(646)Q(690) = (3

2

x

167)

x

(19

2

x

167) = 3

2

x

19

2

x

167

2

jest doskona∏ym

kwadratem. Kraitchik dostrzeg∏, ˝e to
pozwala nam zapisaç pewne wielokrot-
noÊci n w postaci (646

x

690)

2

– (3

x

19

x

167)

2

, co z kolei umo˝liwia znalezienie

dzielnika jak poprzednio. Ta metoda da-
je dzielnik 2551.

Proponuj´ roz∏o˝enie w ten sam

sposób nast´pujàcych liczb: 777 923,
603 181 oraz 21 720 551. Wyniki zosta-
nà podane w jednym z kolejnych

SPRZ¢-

˚E¡ ZWROTNYCH

.

Co jest istotà metody Kraitchika?

Chodzi o znalezienie takich wartoÊci
Q(x), które majà proste dzielniki, a na-
st´pnie po∏àczenie tych wartoÊci w celu
otrzymania pe∏nego kwadratu. W roku
1975 John Brillhart i Michael A. Morri-

W

grudniu 1996 roku pyta∏em w tej rubryce, czy istniejà jeszcze inni mate-
matycznie uzdolnieni rzeêbiarze i projektanci. OczywiÊcie tak. Paul Tu-

cker z Dillsburg (Pensylwania) opowiedzia∏ mi o fascynujàcej matematycznej
stolarce. Tucker, który sam jest stolarzem, b´dàc w Bibliotece Publicznej im.
Amelii Givins w Mount Holly Springs, niewielkim miasteczku niedaleko miejsca

jego zamieszkania, zobaczy∏ na drzwiach
i parawanach podobne do sieci struktury ufor-
mowane z przeplatajàcych si´ spiralnych

form. SpecjaliÊci od architektury stwierdzili,
˝e te spirale zosta∏y zrobione przez odpo-
wiednie zaginanie pr´tów, ale Tucker zorien-
towa∏ si´ od razu po s∏ojach, ˝e musia∏y one
byç frezowane. Zaopatrzony w jedyny war-
toÊciowy dowód rzeczowy, p∏ytk´ mosi´˝nà
z datà „September 15, 1885” Tucker odwie-
dzi∏ Urzàd Patentowy. Z pomocà jego i lo-
kalnego towarzystwa historycznego skoja-
rzy∏ te drzwi z Mosesem Y. Ransomem, który
˝y∏ i pracowa∏ w Cleveland (Ohio) pod ko-
niec XIX wieku. Okazuje si´, ˝e Ransom wy-
myÊli∏ sprytne sposoby frezowania i przepla-
tania spirali. Gdyby ktoÊ chcia∏ zapoznaç si´
z nimi, to jego patent z 28 paêdziernika 1884
roku ma numer 307 332, a z 15 sierpnia
1885 roku 326 329.

SPRZ¢˚ENIE ZWROTNE

PRZEPLATAJÑCE SI¢ SPIRALE

zdobià drzwi biblioteki

(zbli˝enie obok).

son sformalizowali procedur´. Zaczy-
namy od wybrania „podstawy dzielni-
ków”, tzn. listy stosunkowo ma∏ych
liczb pierwszych. W powy˝szym przy-
k∏adzie dowolna lista, która zawiera 3,
19 oraz 167, b´dzie dobra. Nast´pnie
liczymy kolejne liczby Q(x) jak po-
przednio, ale zachowujemy tylko te, któ-
re sà iloczynami liczb pierwszych z ba-
zy. W ˝argonie matematycznym mó-
wimy, ˝e x jest g∏adkie. Ka˝demu g∏ad-
kiemu x przyporzàdkowujemy wektor
o wspó∏rz´dnych sk∏adajàcych si´ z zer
i jedynek; 0 oznacza, ˝e odpowiadajàca
liczba pierwsza dzieli Q(x) w pot´dze
parzystej, a 1 oznacza pot´g´ nieparzy-
stà. A oto lista wektorów:

x

Q(x)

wektor

645

212

nieg∏adkie

646

1503

(0,0,1)

647

2796

nieg∏adkie

....
....

690

60 287 (0,0,1)

Teraz szukamy zbioru wektorów,

których wspó∏rz´dne dodane do siebie
dajà liczby parzyste: na przyk∏ad (0,0,1)
+ (0,0,1) = (0,0,2). Wtedy odpowiadajà-
cy iloczyn Q(x) jest doskona∏ym kwa-
dratem, poniewa˝ wszystkie liczby
pierwsze pojawiajà si´ w parzystych
pot´gach.

G∏ównà przeszkodà w szybkim wy-

konywaniu tej procedury jest problem
rozpoznawania g∏adkich wartoÊci x. Na
przyk∏ad chcielibyÊmy szybko i bez pro-
blemów wskazaç x = 646 i 690 bez wy-
liczania wszystkich pozosta∏ych Q(x).
W roku 1981 Pomerance zorientowa∏ si´,
˝e wariant sita Eratostenesa mo˝e byç
u˝yty do odsiewania g∏adkich wartoÊci
x „w sposób niewiarygodnie szybki”.
Ten ulepszony algorytm jest znany ja-
ko kwadratowe sito. Podwoi∏ on d∏u-
goÊç liczb, które mo˝na rozk∏adaç na
czynniki.

Jak to bywa, Pomerance mia∏ k∏opoty

ze znalezieniem kogoÊ, kto chcia∏by wy-
próbowaç jego nowy algorytm. Uwa˝a-
no, ˝e „algorytm u∏amków ∏aƒcucho-
wych”

2

jest szybszy. Pierwszà osobà,

która zastosowa∏a kwadratowe sito, by∏
Joseph L. Gerver z Rutgers University;
roz∏o˝y∏ on liczb´ o 47 cyfrach (dzielnik
3

22

– 1) z projektu Cunninghama. W ro-

ku 1984 James A. Davis i Diane B. Hol-
dridge z Sandia National Laboratories
wypróbowali nowy algorytm na bar-
dziej wymagajàcej liczbie 111...111 sk∏a-
dajàcej si´ z 71 jedynek. Davis znalaz∏
sposób na ulepszenie nowej metody, co
umo˝liwi∏o roz∏o˝enie tej liczby.

Jak na ironi´ inny zespó∏ w Sandia

w∏aÊnie zakoƒczy∏ prac´ nad kompute-

rowym chipem dla celów kryptografii
opartym na stucyfrowej liczbie, sàdzo-
no bowiem, ˝e roz∏o˝enie na czynniki
takiej liczby by∏o praktycznie niemo˝li-
we. D∏ugoÊç jej jednak zbytnio zbli˝a∏a
si´ do 71, dalsze wi´c prace nad tym chi-
pem zarzucono.

W roku 1994 metoda ta zainspirowa-

∏a Arjena K. Lenstr´ i jego kolegów z
Bellcore do przygotowania opartego na
Internecie programu rozk∏adu liczby
o 129 cyfrach. Ka˝dy, kto chcia∏, móg∏
puÊciç cz´Êç kodu na swoim kompute-
rze, w tle generujàc cz´Êç listy wekto-
rów. Nast´pnie przesy∏ano wyniki do
centrali. Gdy tylko pojawi∏ si´ zbiór
wektorów z parzystymi sumami, wszy-
scy przerwali obliczenia. Bazy dzielni-
ków z milionem liczb pierwszych nale-
˝à dziÊ do typowych.

Znane sà tak˝e inne nowe metody.

W roku 1988 brytyjski matematyk John
Pollard zastanawia∏ si´, czy w rozk∏a-
dzie na czynniki mo˝na zastosowaç al-
gebraicznà teori´ liczb. W tej teorii zwy-
czajne liczby sà poszerzane o pierwiastki
równaƒ wielomianowych, tworzàc „cia-
∏o”. Cia∏em nazywamy zbiór liczb, któ-
re mo˝na dodawaç, odejmowaç, mno-
˝yç i dzieliç, stosujàc zwyk∏e prawa
algebraiczne bez generowania liczb spo-
za zbioru. Je˝eli cia∏o na przyk∏ad za-
wiera pierwiastki kwadratowe, to 13
mo˝na zapisaç jako iloczyn dwóch nie-
wymiernych czynników:

13 = (√

––

14 + 1)(√

––

14 – 1).

Pomys∏ Pollarda, zwany obecnie

sitem cia∏a liczb, polega na u˝yciu ta-
kich „rozk∏adów” do rozbijania wiel-
kich liczb, by w koƒcu otrzymaç praw-
dziwe dzielniki. Metoda ta okaza∏a si´
skuteczna, gdy Arjen Lenstra wraz
z Hendrikiem W. Lenstrà, Jr., z Uni-
versity of California w Berkeley oraz
Markiem S. Manasse z Digital u˝yli jej
skutecznie do roz∏o˝enia dziewiàtej licz-
by Fermata. Ze swoimi ponad 150 cy-
frami by∏a daleko poza zasi´giem sita
kwadratowego.

Dziedzina praktycznego rozk∏adania

liczb dzi´ki nowym pomys∏om stale si´
poszerza. Zastanawiam si´, czy mate-
matycy w przysz∏oÊci odkryjà zdecydo-
wanie lepsze sposoby przesiewania pia-
sków Dzielnikolandii w poszukiwaniu
tych nieuchwytnych dzielników. Tylko
czas mo˝e przynieÊç odpowiedê.

T∏umaczyli

Zdzis∏aw Pogoda i Robert Wolak

Przypisy t∏umaczy:

1

Podobnie jak w artykule z ubieg∏ego miesiàca, tak

i tu rozwa˝ane sà liczby naturalne, i autor konse-
kwentnie pomija przymiotnik „naturalna”.

2

Chodzi tu oczywiÊcie o algorytm Euklidesa, któ-

ry prowadzi do u∏amków ∏aƒcuchowych nazywa-
nych te˝ ciàg∏ymi.

98 Â

WIAT

N

AUKI

Sierpieƒ 1997

Ksià˝ka R. Zubrina w przyst´pny sposób
porusza nast´pujàce zagadnienia:

●

ró˝ne koncepcje za∏ogowych wypraw

na Marsa;

●

plan Mars Direct, proponujàcy nisko-

bud˝etowe loty za∏ogowe na Marsa za
10 lat;

●

technologie rakietowe, umo˝liwiajàce

dotarcie na Marsa;

●

trajektorie podró˝y mi´dzyplanetar-

nej i mo˝liwoÊci transportu pomi´dzy
Ziemià a Marsem;

●

sposoby pokonywania przeciwnoÊci:

promieniowania kosmicznego, braku
grawitacji, burz py∏owych i surowego
marsjaƒskiego klimatu;

●

plan zbadania planety przez kolejne

misje za∏ogowe, z wykorzystaniem po-
jazdów terenowych i telerobotów;

●

budowa sta∏ej marsjaƒskiej bazy dla

kilkuset osób, z terenami zielonymi
i uprawami;

●

technologie potrzebne ludziom na

Marsie: produkcja paliwa rakietowego
i paliwa do pojazdów marsjaƒskich, wy-
twarzanie tlenu, wody itd.;

●

wyjàtkowy charakter Czerwonej Pla-

nety, umo˝liwiajàcy ludzkie osadnictwo
i rozwój cywilizacji przemys∏owej;

●

perspektywy kolonizacji Marsa;

●

co b´dzie si´ op∏acaç produkowaç na

Marsie i przywoziç na Ziemi´, czyli pod-
stawy marsjaƒskiej gospodarki;

●

t

terraformowanie – proces przeobra-

˝ania Marsa na podobieƒstwo Ziemi:
przekszta∏cenie powierzchni i atmosfe-
ry planety do postaci umo˝liwiajàcej
rozwój ziemskiej biosfery, czyli zmiana
planety zimnej, suchej i wymar∏ej w ˝y-
wà, ciep∏à i wilgotnà.

Robert Zubrin, Richard Wagner

CZAS MARSA

Dlaczego i w jaki sposób musimy
skolonizowaç Czerwonà Planet´

Seria „Na Êcie˝kach nauki”

Prószyƒski i S-ka