\input style
\chapter{zamechaniya ob uprazhneniyah}
uPRAZHNENIYA, POMESHCHENNYE V KNIGAH NASTOYASHCHEJ SERII, PREDNAZNACHENY KAK DLYA
SAMOSTOYATELXNOJ PRORABOTKI, TAK I DLYA SEMINARSKIH ZANYATIJ. tRUDNO, ESLI
NE NEVOZMOZHNO IZUCHITX PREDMET, TOLXKO CHITAYA TEORIYU I NE PRIMENYAYA
POLUCHENNUYU INFORMACIYU DLYA RESHENIYA SPECIALXNYH ZADACH I TEM SAMYM NE
ZASTAVLYAYA SEBYA OBDUMYVATX TO, CHTO BYLO PROCHITANO. kROME TOGO, MY LUCHSHE
VSEGO ZAUCHIVAEM TO, CHTO SAMI OTKRYVAEM DLYA SEBYA. pO|TOMU
UPRAZHNENIYA OBRAZUYUT VAZHNUYU CHASTX DANNOJ RABOTY; BYLI PREDPRINYATY
OPREDELENNYE POPYTKI, CHTOBY OTOBRATX UPRAZHNENIYA, V KOTORYH
BY SODERZHALOSX KAK MOZHNO BOLXSHE INFORMACII I KOTORYE BYLO BY INTERESNO RESHATX.

vO MNOGIH KNIGAH LEGKIE UPRAZHNENIYA DAYUTSYA VPEREMESHKU S ISKLYUCHITELXNO
TRUDNYMI. zACHASTUYU |TO OCHENX NEUDOBNO, TAK KAK PERED TEM, KAK PRISTUPATX K
RESHENIYU ZADACHI, CHITATELX OBYAZATELXNO DOLZHEN PREDSTAVLYATX SEBE, SKOLXKO
VREMENI UJDET U NEGO NA |TO RESHENIE (INACHE ON MOZHET RAZVE TOLXKO
PROSMOTRETX VSE ZADACHI). kLASSICHESKIM PRIMEROM ZDESX YAVLYAETSYA KNIGA
rICHARDA bELLMANA "dINAMICHESKOE PROGRAMMIROVANIE"; |TO VAZHNAYA PIONERSKAYA
RABOTA, V KOTOROJ V KONCE KAZHDOJ GLAVY POD RUBRIKOJ "uPRAZHNENIYA I
ISSLEDOVATELXSKIE PROBLEMY" DAETSYA CELYJ RYAD ZADACH, GDE NARYADU S GLUBOKIMI
ESHCHE NERESHENNYMI PROBLEMAMI VSTRECHAYUTSYA ISKLYUCHITELXNO TRIVIALXNYE VOPROSY.
gOVORYAT, CHTO ODNAZHDY KTO-TO SPROSIL D-RA bELLMANA, KAK OTLICHITX
UPRAZHNENIYA OT ISSLEDOVATELXSKIH PROBLEM, I TOT OTVETIL: "eSLI VY
MOZHETE RESHITX ZADACHU, |TO---UPRAZHNENIE; V PROTIVNOM SLUCHAE |TO---PROBLEMA".

mOZHNO PRIVESTI MNOGO DOVODOV V POLXZU TOGO, CHTO V KNIGE TIPA |TOJ DOLZHNY
BYTX KAK ISSLEDOVATELXSKIE PROBLEMY, TAK I OCHENX PROSTYE UPRAZHNENIYA, I DLYA
TOGO CHTOBY CHITATELYU NE PRIHODILOSX LOMATX GOLOVU NAD TEM, KAKAYA ZADACHA
LEGKAYA, A KAKAYA TRUDNAYA, MY VVELI "OCENKI", KOTORYE UKAZYVAYUT STEPENX
TRUDNOSTI KAZHDOGO UPRAZHNENIYA. eTI OCENKI IMEYUT SLEDUYUSHCHEE ZNACHENIE:
\descrtable{
\bf oCENKA  & \bf oB�YASNENIE \cr
00 & chREZVYCHAJNO LEGKOE UPRAZHNENIE, NA KOTOROE MOZHNO OTVETITX SRAZU ZHE,
     ESLI PONYAT MATERIAL TEKSTA, I KOTOROE POCHTI VSEGDA MOZHNO RESHITX "V UME".\cr
%% 11
10 & pROSTAYA ZADACHA, KOTORAYA ZASTAVLYAET ZADUMATXSYA NAD PROCHITANNYM
     MATERIALOM, NO NE PREDSTAVLYAET NIKAKIH OSOBYH TRUDNOSTEJ. nA RESHENIE TAKOJ
     ZADACHI TREBUETSYA NE BOLXSHE ODNOJ MINUTY; V PROCESSE RESHENIYA MOGUT
     PONADOBITXSYA KARANDASH I BUMAGA. \cr
20 & zADACHA SREDNEJ TRUDNOSTI, POZVOLYAYUSHCHAYA PROVERITX, NASKOLXKO HOROSHO
     PONYAT TEKST. nA TO CHTOBY DATX ISCHERPYVAYUSHCHIJ OTVET, TREBUETSYA PRIMERNO
     15--20~MINUT. \cr
30 & zADACHA UMERENNOJ TRUDNOSTI I/ILI SLOZHNOSTI, DLYA UDOVLETVORITELXNOGO
     RESHENIYA KOTOROJ TREBUETSYA BOLXSHE DVUH CHASOV. \cr
40 & oCHENX TRUDNAYA ILI TRUDOEMKAYA ZADACHA, KOTORUYU, VEROYATNO, SLEDUET
     VKLYUCHITX V PLAN PRAKTICHESKIH ZANYATIJ. pREDPOLAGAETSYA, CHTO STUDENT MOZHET
     RESHITX TAKUYU ZADACHU, NO DLYA |TOGO EMU POTREBUETSYA ZNACHITELXNYJ OTREZOK
     VREMENI; ZADACHA RESHAETSYA NETRIVIALXNYM OBRAZOM. \cr
50 & iSSLEDOVATELXSKAYA PROBLEMA, KOTORAYA (NASKOLXKO |TO BYLO IZVESTNO AVTORU
     V MOMENT NAPISANIYA) ESHCHE NE POLUCHILA UDOVLETVORITELXNOGO RESHENIYA. eSLI
     CHITATELX NAJDET RESHENIE |TOJ ZADACHI, EGO NASTOYATELXNO PROSYAT OPUBLIKOVATX
     EGO; KROME TOGO, AVTOR DANNOJ KNIGI BUDET OCHENX PRIZNATELEN, ESLI EMU
     SOOBSHCHAT RESHENIE, KAK MOZHNO BYSTREE (PRI USLOVII, CHTO ONO PRAVILXNO). \cr
}

iNTERPOLIRUYA PO |TOJ "LOGARIFMICHESKOJ" SHKALE, MOZHNO PRIKINUTX, CHTO
OZNACHAET LYUBAYA PROMEZHUTOCHNAYA OCENKA. nAPRIMER, OCENKA~17 GOVORIT O TOM,
CHTO DANNOE UPRAZHNENIE CHUTX LEGCHE, CHEM UPRAZHNENIE SREDNEJ TRUDNOSTI. zADACHA
S OCENKOJ~50, ESLI ONA BUDET RESHENA KAKIM-LIBO CHITATELEM, V SLEDUYUSHCHIH
IZDANIYAH DANNOJ KNIGI MOZHET IMETX UZHE OCENKU~45.

aVTOR CHESTNO STARALSYA DAVATX OB�EKTIVNYE OCENKI, NO TOMU, KTO SOSTAVLYAET
ZADACHI, TRUDNO PREDVIDETX, NASKOLXKO TRUDNYMI |TI ZADACHI OKAZHUTSYA DLYA
KOGO-TO DRUGOGO; K TOMU ZHE U KAZHDOGO CHELOVEKA SUSHCHESTVUET OPREDELENNYJ TIP
ZADACH, KOTORYE ON RESHAET BYSTREE. nADEYUSX, CHTO VYSTAVLENNYE MNOJ OCENKI
DAYUT PRAVILXNOE PREDSTAVLENIE O STEPENI TRUDNOSTI ZADACH, NO V OBSHCHEM
IH NUZHNO VOSPRINIMATX KAK ORIENTIROVOCHNYE, A NE ABSOLYUTNYE.

eTA KNIGA NAPISANA DLYA CHITATELEJ SAMYH RAZNYH STEPENEJ MATEMATICHESKOJ
PODGOTOVKI I ISKUSHENNOSTI, PO|TOMU NEKOTORYE UPRAZHNENIYA PREDNAZNACHENY
TOLXKO DLYA CHITATELEJ S MATEMATICHESKIM UKLONOM. eSLI V KAKOM-LIBO
UPRAZHNENII MATEMATICHESKIE PONYATIYA ILI REZULXTATY ISPOLXZUYUTSYA BOLEE SHIROKO,
CHEM |TO NEOBHODIMO DLYA TEH, KOGO V PERVUYU OCHEREDX INTERESUET
PROGRAMMIROVANIE ALGORITMOV, TO PERED OCENKOJ TAKOGO UPRAZHNENIYA
STAVITSYA BUKVA "\emph{m}". eSLI DLYA RESHENIYA UPRAZHNENIYA TREBUETSYA
ZNANIE VYSSHEJ MATEMATIKI V BOLXSHEM OB�EME, CHEM |TO DANO V NASTOYASHCHEJ
%% 12
KNIGE, TO STAVYATSYA BUKVY~"\emph{vm}". pOMETKA~"\emph{vm}" OTNYUDX NE
YAVLYAETSYA SVIDETELXSTVOM TOGO, CHTO DANNOE UPRAZHNENIE TRUDNOE.

pERED NEKOTORYMI UPRAZHNENIYAMI STOIT STRELKA~"$\btr$"; |TO OZNACHAET, CHTO
DANNOE UPRAZHNENIE OSOBENNO POUCHITELXNO I EGO REKOMENDUETSYA OBYAZATELXNO
VYPOLNITX. sAMO SOBOJ RAZUMEETSYA, NIKTO NE OZHIDAET, CHTO CHITATELX (ILI
STUDENT) BUDET RESHATX VSE ZADACHI, POTOMU-TO NAIBOLEE POLEZNYE IZ NIH I
VYDELENY. eTO SOVSEM NE ZNACHIT, CHTO DRUGIE ZADACHI NE STOIT RESHATX! kAZHDYJ
CHITATELX DOLZHEN PO KRAJNEJ MERE POPYTATXSYA RESHITX VSE ZADACHI S
OCENKOJ~10 I NIZHE; STRELKI ZHE POMOGUT VYBRATX, KAKIE ZADACHI S BOLEE
VYSOKIMI OCENKAMI SLEDUET RESHITX V PERVUYU OCHEREDX.

k BOLXSHINSTVU UPRAZHNENIJ PRIVEDENY OTVETY; ONI POMESHCHENY V SPECIALXNOM
RAZDELE V KONCE KNIGI. pOLXZUJTESX IMI MUDRO;
V OTVET SMOTRITE TOLXKO POSLE TOGO, KAK VY PRILOZHILI DOSTATOCHNO USILIJ,
CHTOBY RESHITX ZADACHU SAMOSTOYATELXNO, ILI ZHE ESLI DLYA RESHENIYA DANNOJ
ZADACHI U VAS NET VREMENI. eSLI POLUCHEN SOBSTVENNYJ OTVET, LIBO ESLI VY
DEJSTVITELXNO PYTALISX RESHITX ZADACHU, TOLXKO V |TOM SLUCHAE OTVET,
POMESHCHENNYJ V KNIGE, BUDET POUCHITELXNYM I POLEZNYM. kAK PRAVILO, OTVETY K
ZADACHAM IZLAGAYUTSYA OCHENX KRATKO, SHEMATICHNO, TAK KAK PREDPOLAGAETSYA, CHTO
CHITATELX UZHE CHESTNO PYTALSYA RESHITX ZADACHU SOBSTVENNYMI SILAMI. iNOGDA V
PRIVEDENNOM RESHENII DAETSYA MENXSHE INFORMACII, CHEM SPRASHIVALOSX,
CHASHCHE---NAOBOROT. vPOLNE VOZMOZHNO, CHTO POLUCHENNYJ VAMI OTVET OKAZHETSYA LUCHSHE
OTVETA, POMESHCHENNOGO V KNIGE, ILI VY NAJDETE OSHIBKU V |TOM OTVETE; V TAKOM
SLUCHAE AVTOR BYL BY OCHENX OBYAZAN, ESLI BY VY KAK MOZHNO SKOREE PODROBNO
SOOBSHCHILI EMU OB |TOM. v POSLEDUYUSHCHIH IZDANIYAH NASTOYASHCHEJ KNIGI
BUDET POMESHCHENO UZHE ISPRAVLENNOE RESHENIE VMESTE S IMENEM EGO AVTORA.

\bigskip
\centerline{\bf sVODKA USLOVNYH OBOZNACHENIJ}
\ctable{
\emph{#}\bskip\hfil&\bskip#\hfil\cr
$\btr$ &  rEKOMENDUETSYA \cr
m & s MATEMATICHESKIM UKLONOM \cr
vm & tREBUET ZNANIYA "VYSSHEJ MATEMATIKI" \cr
00 & tREBUET NEMEDLENNOGO OTVETA \cr
10 & pROSTOE (NA ODNU MINUTU) \cr
20 & sREDNEJ TRUDNOSTI (NA CHETVERTX CHASA) \cr
30 & pOVYSHENNOJ TRUDNOSTI \cr
40 & dLYA "MATPRAKTIKUMA" \cr
50 & iSSLEDOVATELXSKAYA PROBLEMA \cr
}

\excercises
\ex[00] chTO OZNACHAET POMETKA~"\emph{m20}"?

\ex[10] kAKOE ZNACHENIE DLYA CHITATELYA IMEYUT UPRAZHNENIYA, POMESHCHAEMYE V UCHEBNIKAH?

\ex[m50] dOKAZHITE, CHTO ESLI~$n$---CELOE CHISLO, $n>2$, TO
URAVNENIE~$x^n+y^n=z^n$ NERAZRESHIMO V CELYH POLOZHITELXNYH CHISLAH~$x$, $y$, $z$.

%% 13
\chapno=2\chapnotrue\chapter{sLUCHAJNYE CHISLA} % 3
\epigraph
vSYAKIJ, KTO PITAET SLABOSTX K ARIFMETICHESKIM METODAM POLUCHENIYA SLUCHAJNYH
CHISEL, GRESHEN VNE VSYAKIH SOMNENIJ.
\signed dZHON FON nEJMAN (1951)

\epigraph
kRUGLYE CHISLA VSEGDA FALXSHIVY.
\signed s|MYU|LX dZHONSON (OKOLO 1750)

\epigraph Lest men suspect your tale untrue, \goodbreak
Keep probability in view%
\note{1}%
{chTOBY LYUDI POVERILI VASHIM ROSSKAZNYAM, POMNITE O
 VEROYATNOSTI.---{\sl pRIM. PEREV.\/}
}.
\signed dZHON g|J (1727)

\subchap{vvedenie} % 3.1
"sLUCHAJNO VYBRANNYE" CHISLA OKAZYVAYUTSYA POLEZNYMI DLYA SAMYH RAZLICHNYH CELEJ.
 vOT NEKOTORYE PRIMERY:
\medskip
a)~\emph{mODELIROVANIE.} kOGDA S POMOSHCHXYU VYCHISLITELXNOJ
MASHINY MODELIRUYUTSYA PRIRODNYE YAVLENIYA, SLUCHAJNYE CHISLA
POZVOLYAYUT PRIBLIZITX MODELX K REALXNOSTI. mODELIROVANIE PRIMENYAETSYA VO
MNOGIH OBLASTYAH: OT YADERNOJ FIZIKI (CHASTICY ISPYTYVAYUT SLUCHAJNYE
SOUDARENIYA) DO SISTEMNOGO ANALIZA (SKAZHEM, LYUDI VHODYAT V BANK CHEREZ
SLUCHAJNYE INTERVALY VREMENI).

b)~\emph{vYBORKA.} chASTO BYVAET, CHTO PROVERKA VSEH VOZMOZHNYH VARIANTOV
PRAKTICHESKI NEOSUSHCHESTVIMA. tOGDA NA NEKOTORYE VOPROSY POZVOLYAET POLUCHITX
OTVETY SLUCHAJNAYA VYBORKA.

c)~\emph{chISLENNYJ ANALIZ.} dLYA RESHENIYA SLOZHNYH ZADACH VYCHISLITELXNOJ
MATEMATIKI BYLA RAZRABOTANA OSTROUMNAYA TEHNIKA, ISPOLXZUYUSHCHAYA SLUCHAJNYE
CHISLA. oB |TOM NAPISAN RYAD KNIG.

d)~\emph{pROGRAMMIROVANIE DLYA VYCHISLITELXNYH MASHIN.} sLUCHAJNYE ZNACHENIYA
SLUZHAT HOROSHIM ISTOCHNIKOM DANNYH PRI ISPYTANII |FFEKTIVNOSTI RAZLICHNYH
ALGORITMOV DLYA VYCHISLITELXNYH MASHIN. v |TOJ KNIGE NAS BUDET V OSNOVNOM
INTERESOVATX IMENNO TAKOE ISPOLXZOVANIE SLUCHAJNYH CHISEL. pO|TOMU PREZHDE
CHEM POJDET RECHX O DRUGIH ALGORITMAH, ZDESX, V TRETXEJ GLAVE, BUDUT
RASSMOTRENY SLUCHAJNYE CHISLA.

e)~\emph{pRINYATIE RESHENIJ.} gOVORYAT, CHTO MNOGIE RUKOVODITELI PRINIMAYUT
RESHENIYA, BROSAYA MONETKU ILI KOSTI. hODYAT DAZHE
%% 14
SLUHI, CHTO NEKOTORYE PROFESSORA V KOLLEDZHAH DOBIVAYUTSYA USPEHA IMENNO
TAKIM OBRAZOM. iNOGDA BYVAET VAZHNO PRINIMATX SOVERSHENNO NEPREDVZYATYE
RESHENIYA. pOLEZNO PREDUSMOTRETX TAKUYU VOZMOZHNOSTX DLYA ALGORITMOV,
PRIMENYAEMYH V VYCHISLITELXNYH MASHINAH, NAPRIMER V SLUCHAYAH, KOGDA PRINYATIE
DETERMINIROVANNOGO RESHENIYA MOZHET PRIVESTI K ZAMEDLENIYU SCHETA.
sLUCHAJNOSTX, KROME TOGO,---SUSHCHESTVENNAYA CHASTX OPTIMALXNYH STRATEGIJ V
TEORII IGR.

f)~\emph{rAZVLECHENIYA.} mNOGIE PROVODYAT VREMYA, TASUYA KARTY, BROSAYA KOSTI
ILI NABLYUDAYA ZA KOLESOM RULETKI, I NAHODYAT V |TOM NEIZ�YASNIMOE
UDOVOLXSTVIE. tAKIM TRADICIONNYM ISPOLXZOVANIEM SLUCHAJNYH CHISEL
OB�YASNYAETSYA, POCHEMU TERMIN "mONTE-kARLO" SLUZHIT OBSHCHIM NAIMENOVANIEM DLYA
VSEH ALGORITMOV, V KOTORYH PRIMENYAYUT SLUCHAJNYE CHISLA.
\medskip
sTALO OBYCHNYM V |TOM MESTE POSVYASHCHATX NESKOLXKO ABZACEV FILOSOFSKOMU
OBSUZHDENIYU TOGO, CHTO ZHE TAKOE "SLUCHAJNOSTX". v NEKOTOROM SMYSLE TAKOGO
OB�EKTA, KAK SLUCHAJNOE CHISLO, PROSTO NET. sKAZHEM, DVOJKA---|TO SLUCHAJNOE
CHISLO? sKOREE MY GOVORIM O \emph{POSLEDOVATELXNOSTI NEZAVISIMYH} SLUCHAJNYH
CHISEL S OPREDELENNYM \emph{ZAKONOM RASPREDELENIYA,} I |TO OZNACHAET, GRUBO
GOVORYA, CHTO KAZHDOE CHISLO BYLO POLUCHENO SAMYM PROIZVOLXNYM OBRAZOM,
BEZ VSYAKOJ SVYAZI S DRUGIMI CHLENAMI POSLEDOVATELXNOSTI, I CHTO U NEGO ESTX
OPREDELENNAYA VEROYATNOSTX OKAZATXSYA V LYUBOM ZADANNOM INTERVALE.

\dfn{rAVNOMERNYM} NAZYVAETSYA TAKOE RASPREDELENIE, PRI KOTOROM KAZHDOE
VOZMOZHNOE CHISLO RAVNOVEROYATNO. oBYCHNO, ESLI SPECIALXNO NE OGOVORENO
CHTO-LIBO INOE, IMEYUT V VIDU RAVNOMERNYE RASPREDELENIYA.

kAZHDAYA IZ DESYATI CIFR OT~$0$ DO~$9$ SOSTAVLYAET PRIMERNO ODNU DESYATUYU CHASTX
VSEH CIFR VO VSYAKOJ SLUCHAJNOJ (RAVNOMERNOJ) POSLEDOVATELXNOSTI CIFR. lYUBAYA
ZADANNAYA PARA DVUH SOSEDNIH CIFR DOLZHNA SOSTAVLYATX PRIMERNO
$\frac1/{100}$~CHASTX VSEH PAR, VSTRECHAYUSHCHIHSYA V POSLEDOVATELXNOSTI,
I~T.~D. tEM NE MENEE, ESLI MY RASSMOTRIM KAKUYU-NIBUDX KONKRETNUYU SLUCHAJNUYU
POSLEDOVATELXNOSTX IZ MILLIONA CIFR, V NEJ SOVSEM NE OBYAZATELXNO
OKAZHETSYA ROVNO $100\,000$~NULEJ, $100\,000$~EDINIC I~T.~D. v
DEJSTVITELXNOSTI VEROYATNOSTX TAKOGO SOBYTIYA OCHENX MALA. zAKONOMERNOSTX ZHE
VYPOLNYAETSYA V SREDNEM DLYA \emph{POSLEDOVATELXNOSTI} TAKIH POSLEDOVATELXNOSTEJ.

lYUBAYA ZADANNAYA POSLEDOVATELXNOSTX STOLX ZHE VEROYATNA, KAK I
POSLEDOVATELXNOSTX, SOSTOYASHCHAYA IZ ODNIH \emph{NULEJ.} bOLEE TOGO, DOPUSTIM,
CHTO MY VYBIRAEM SLUCHAJNYM OBRAZOM POSLEDOVATELXNOSTX IZ MILLIONA CIFR.
pUSTX OKAZALOSX, CHTO PERVYE $999\,999$
%% 15
IZ NIH RAVNY NULYU. i V |TOM SLUCHAE VEROYATNOSTX TOGO, CHTO POSLEDNYAYA CIFRA
BUDET NULEM, VSE ESHCHE V TOCHNOSTI RAVNA~$\frac 1/{10}$, ESLI VYBORKA
DEJSTVITELXNO SLUCHAJNAYA. dLYA MNOGIH |TI UTVERZHDENIYA ZVUCHAT KAK PARADOKS,
NO NA SAMOM DELE V NIH NET PROTIVORECHIYA.

sUSHCHESTVUET NESKOLXKO SPOSOBOV SFORMULIROVATX HOROSHEE ABSTRAKTNOE
OPREDELENIE SLUCHAJNOJ POSLEDOVATELXNOSTI. mY ESHCHE VERNEMSYA K |TOMU
INTERESNOMU VOPROSU V~\S~3.5. pOKA ZHE DOSTATOCHNO INTUITIVNO PONYATX IDEYU.

rANXSHE UCHENYE, NUZHDAVSHIESYA DLYA SVOEJ RABOTY V SLUCHAJNYH CHISLAH,
RASKLADYVALI KARTY, BROSALI KOSTI ILI VYTASKIVALI SHARY IZ URNY, KOTORUYU
PREDVARITELXNO "KAK SLEDUET TRYASLI". v 1927~G.\ l.~tIPPETT OPUBLIKOVAL
TABLICY, SODERZHASHCHIE SVYSHE $40\,000$~SLUCHAJNYH CIFR, "PROIZVOLXNO VZYATYH IZ
OTCHETOV O PEREPISI". pOZZHE BYLI SKONSTRUIROVANY SPECIALXNYE MASHINY,
MEHANICHESKI VYRABATYVAYUSHCHIE SLUCHAJNYE CHISLA. pERVUYU TAKUYU MASHINU V
1939~G.\ ISPOLXZOVALI m.~dZH.~kENDALL I~b.~b|BINGTON-sMIT PRI SOZDANII
TABLIC, VKLYUCHAYUSHCHIH 100~TYSYACH SLUCHAJNYH CIFR. v 1955~G.\ KOMPANIYA RAND
Corporation OPUBLIKOVALA HOROSHO IZVESTNYE TABLICY S MILLIONOM SLUCHAJNYH
CIFR, POLUCHENNYH DRUGOJ TAKOJ MASHINOJ. iZVESTNAYA MASHINA ERNIE,
VYRABATYVAYUSHCHAYA SLUCHAJNYE CHISLA, OPREDELYAET VYIGRAVSHIE NOMERA V
bRITANSKOJ LOTEREE. [sM.\ STATXI kENDALLA I b|BINGTON-sMITA V
{\sl Journal of the Royal Statistical Society,\/}
Series~A, {\bf 101} (1938), 147--166, I Series~v, {\bf 6} (1939), 51--61,
A TAKZHE OBZOR V~{\sl Math.\ Comp.,\/} {\bf 10} (1956), 39--43.]

vSKORE POSLE SOZDANIYA VYCHISLITELXNYH MASHIN NACHALISX POISKI |FFEKTIVNYH
METODOV POLUCHENIYA SLUCHAJNYH CHISEL, PRIGODNYH DLYA ISPOLXZOVANIYA V
PROGRAMMAH. v PRINCIPE MOZHNO RABOTATX I S TABLICAMI, ODNAKO, |TOT METOD
IMEET OGRANICHENIYA, SVYAZANNYE S KONECHNYM OB�EMOM PAMYATI MASHIN I ZATRATAMI
VREMENI DLYA VVODA CHISEL V MASHINU V TOM SLUCHAE, KOGDA TABLICA OKAZYVAETSYA
SLISHKOM KOROTKOJ. kROME TOGO, DOVOLXNO NEPRIYATNO GOTOVITX TABLICY
ZARANEE, DA I VOOBSHCHE IMETX S NIMI DELO. mOZHNO PRISOEDINITX K evm MASHINU
TIPA ERNIE, NO I |TOT PUTX OKAZYVAETSYA NEUDOVLETVORITELXNYM, POTOMU CHTO
PRI OTLADKE PROGRAMMY NEVOZMOZHNO VOSPROIZVESTI VTORICHNO VYCHISLENIYA,
SDELANNYE RANEE.

nESOVERSHENSTVO VSEH |TIH METODOV PROBUDILO INTERES K POLUCHENIYU SLUCHAJNYH
CHISEL S POMOSHCHXYU ARIFMETICHESKIH OPERACIJ VYCHISLITELXNOJ MASHINY. pERVYM
TAKOJ PODHOD V 1946~G.\ PREDLOZHIL dZHON FON nEJMAN, ISPOLXZOVAVSHIJ METOD
"SEREDINY KVADRATA". iDEYA ZAKLYUCHAETSYA V TOM, CHTO PREDYDUSHCHEE SLUCHAJNOE
CHISLO VOZVODITSYA V KVADRAT, A ZATEM IZ REZULXTATA IZVLEKAYUTSYA SREDNIE
CIFRY. pUSTX, NAPRIMER, MY VYRABATYVAEM DESYATIZNACHNYE CHISLA I DOPUSTIM,
CHTO PREDYDUSHCHEE CHISLO BYLO RAVNO~$5772156649$;
%% 16
VOZVEDYA EGO V KVADRAT, POLUCHIM
$$
33317792380594909201,
$$
I PO|TOMU SLEDUYUSHCHEE CHISLO RAVNO~$7923805949$.

mETOD VYZYVAET DOVOLXNO OCHEVIDNOE VOZRAZHENIE. kAK MOZHET BYTX SLUCHAJNOJ
VYRABOTANNAYA TAKIM SPOSOBOM POSLEDOVATELXNOSTX, ESLI KAZHDYJ EE CHLEN
POLNOSTXYU OPREDELEN SVOIM PREDSHESTVENNIKOM?

oTVET ZAKLYUCHAETSYA V TOM, CHTO |TA POSLEDOVATELXNOSTX \emph{NE} SLUCHAJNA
NO \emph{VYGLYADIT} KAK SLUCHAJNAYA. v TIPICHNYH PRILOZHENIYAH OBYCHNO NE IMEET
ZNACHENIYA, KAK SVYAZANY DRUG S DRUGOM DVA POSLEDUYUSHCHIH CHISLA
POSLEDOVATELXNOSTI; TAKIM OBRAZOM, NESLUCHAJNYJ HARAKTER
POSLEDOVATELXNOSTI NE YAVLYAETSYA NEZHELATELXNYM. iNTUITIVNO METOD SEREDINY
KVADRATA DOLZHEN DOVOLXNO HOROSHO "PEREMESHIVATX" PREDYDUSHCHEE CHISLO.

v NAUCHNO-TEHNICHESKOJ LITERATURE POSLEDOVATELXNOSTI, VYRABATYVAEMYE
DETERMINISTSKIMI SPOSOBAMI, NAZYVAYUTSYA \emph{PSEVDOSLUCHAJNYMI} ILI
\emph{KVAZISLUCHAJNYMI.} zDESX ZHE MY BUDEM NAZYVATX IH PROSTO SLUCHAJNYMI
POSLEDOVATELXNOSTYAMI, PONIMAYA, CHTO ONI TOLXKO \emph{PROIZVODYAT
VPECHATLENIE} SLUCHAJNYH. nAVERNOE, VSE, CHTO MOZHNO SKAZATX O SLUCHAJNOJ
POSLEDOVATELXNOSTI, |TO TO, CHTO ONA "PO VNESHNEMU VIDU SLUCHAJNAYA". tOCHNYE
MATEMATICHESKIE OPREDELENIYA SLUCHAJNOSTI DAYUTSYA V~\S~3.5. vYRABOTANNYE
DETERMINISTSKIMI METODAMI SLUCHAJNYE CHISLA OKAZALISX PRIGODNYMI POCHTI DLYA
VSEH PRILOZHENIJ (HOTYA, KONECHNO, ONI NE MOGUT ZAMENITX ERNIE V LOTEREYAH).

oDNAKO PERVONACHALXNYJ "METOD SEREDINY KVADRATA" FON nEJMANA OKAZALSYA
SRAVNITELXNO SKUDNYM ISTOCHNIKOM SLUCHAJNYH CHISEL. nEDOSTATOK EGO
ZAKLYUCHAETSYA V TOM, CHTO POSLEDOVATELXNOSTI IMEYUT TENDENCIYU PREVRASHCHATXSYA V
KOROTKIE CIKLY POVTORYAYUSHCHIHSYA |LEMENTOV. nAPRIMER, ESLI KAKOJ-NIBUDX CHLEN
POSLEDOVATELXNOSTI OKAZHETSYA RAVNYM NULYU, VSE POSLEDUYUSHCHIE CHLENY TAKZHE
BUDUT NULYAMI. v NACHALE PYATIDESYATYH GODOV NEKOTORYE UCHENYE
PROVODILI |KSPERIMENTY S METODOM SEREDINY KVADRATA. dZH.~e.~fORSAJT,
RABOTAVSHIJ S CHETYREHZNACHNYMI (A NE S DESYATIZNACHNYMI) CHISLAMI, PROVERIL
16~CHISEL V KACHESTVE NACHALXNYH ZNACHENIJ POSLEDOVATELXNOSTEJ oKAZALOSX,
CHTO~12 IZ NIH POROZHDALI POSLEDOVATELXNOSTI, OKANCHIVAYUSHCHIESYA CIKLOM~$6100$,
$2100$, $4100$, $8100$, $6100$,~\dots, A DVE POSLEDOVATELXNOSTI VYRODILISX
V NULX. oBSHIRNYE |KSPERIMENTY PO ISSLEDOVANIYU METODA SEREDINY KVADRATA
PROVEL n.~mETROPOLIS, OPERIROVAVSHIJ GLAVNYM OBRAZOM DVOICHNYMI CHISLAMI.
rABOTAYA S 20-RAZRYADNYMI CHISLAMI, ON POKAZAL, CHTO SUSHCHESTVUET
TRINADCATX RAZLICHNYH CIKLOV, V KOTORYE MOGUT VYRODITXSYA
POSLEDOVATELXNOSTI; DLINA PERIODA SAMOGO BOLXSHOGO IZ NIH RAVNA~$142$.
kAK TOLXKO POSLEDOVATELXNOSTX VYROZHDAETSYA V NULX, DOVOLXNO LEGKO NACHATX
VYRABOTKU SLUCHAJNYH CHISEL ZANOVO. gORAZDO TRUDNEJ BOROTXSYA
%% 17
S DLINNYMI CIKLAMI. vSE ZHE r.~fLOJD (SM.~UPR.~7) PREDLOZHIL
OSTROUMNYJ METOD, POZVOLYAYUSHCHIJ ZAREGISTRIROVATX VOZNIKNOVENIE CIKLA V
POSLEDOVATELXNOSTI. mETOD fLOJDA TREBUET NEBOLXSHOJ PAMYATI MASHINY,
UVELICHIVAET VREMYA VYRABOTKI SLUCHAJNOGO CHISLA VSEGO V TRI RAZA I SRAZU ZHE
SIGNALIZIRUET, KAK TOLXKO V POSLEDOVATELXNOSTI POYAVLYAETSYA VSTRECHAVSHEESYA
RANEE CHISLO.

tEORETICHESKIE NEDOSTATKI METODA SEREDINY KVADRATA OBSUZHDAYUTSYA V UPR.~9
I~10. s DRUGOJ STORONY, OTMETIM, CHTO, RABOTAYA S 38-RAZRYADNYMI DVOICHNYMI
CHISLAMI, n.~mETROPOLIS OBNARUZHIL POSLEDOVATELXNOSTX, SOSTOYASHCHUYU
IZ $750\,000$~CHLENOV, OTLICHAYUSHCHIHSYA DRUG OT DRUGA. sTATISTICHESKIE TESTY
PODTVERDILI SLUCHAJNYJ HARAKTER POLUCHENNOJ POSLEDOVATELXNOSTI IZ
$750000 \times 38$~BITOV. eTO PODTVERZHDAET, CHTO, PRIMENYAYA METOD SEREDINY
KVADRATA, \emph{MOZHNO} POLUCHITX POLEZNYE REZULXTATY. tEM NE MENEE BEZ
PREDVARITELXNYH TRUDOEMKIH VYCHISLENIJ EMU NE STOIT IZLISHNE DOVERYATX.

mNOGIE DATCHIKI SLUCHAJNYH CHISEL, POPULYARNYE SEJCHAS, NEDOSTATOCHNO HOROSHI.
sREDI POLXZOVATELEJ NAMETILASX TENDENCIYA IZBEGATX IH IZUCHENIYA. dOVOLXNO
CHASTO KAKOJ-NIBUDX STARYJ SRAVNITELXNO NEUDOVLETVORITELXNYJ METOD
PEREDAETSYA OT ODNOGO PROGRAMMISTA K DRUGOMU VSLEPUYU, I SEGODNYASHNIJ
POLXZOVATELX UZHE NICHEGO NE ZNAET OB EGO NEDOSTATKAH. v |TOJ GLAVE MY
UBEDIMSYA, CHTO NETRUDNO IZUCHITX SAMYE VAZHNYE SVOJSTVA DATCHIKOV
SLUCHAJNYH CHISEL I NAUCHITXSYA PRIMENYATX |TI ZNANIYA.

iZOBRESTI PROSTOJ DATCHIK SLUCHAJNYH CHISEL NE TAK LEGKO. nESKOLXKO LET NAZAD
|TOT FAKT PROIZVEL NA AVTORA BOLXSHOE VPECHATLENIE. oN TOGDA PYTALSYA
SOZDATX FANTASTICHESKI HOROSHIJ DATCHIK SLUCHAJNYH CHISEL NA OSNOVE
SLEDUYUSHCHEGO SVOEOBRAZNOGO METODA.

\alg K.(dATCHIK "SVERHSLUCHAJNYH" CHISEL.) s POMOSHCHXYU |TOGO ALGORITMA DANNOE
DESYATIZNACHNOE DESYATICHNOE CHISLO~$X$ MOZHNO PREOBRAZOVATX V DRUGOE CHISLO,
KOTOROE, KAK PREDPOLAGAETSYA, YAVLYAETSYA SLEDUYUSHCHIM CHLENOM SLUCHAJNOJ
POSLEDOVATELXNOSTI. kAZALOSX BY, ALGORITM POZVOLYAET VYRABOTATX DOSTATOCHNO
SLUCHAJNUYU POSLEDOVATELXNOSTX, NO VYYASNILOSX, CHTO |TO SOVSEM NE TAK.
pRICHINY NEUDACHI RAZBIRAYUTSYA NIZHE. (chITATELYU NET NUZHDY SLISHKOM VNIKATX V
DETALI. dOSTATOCHNO UBEDITXSYA V BOLXSHOJ SLOZHNOSTI ALGORITMA.)

\st[vYBRATX CHISLO ITERACIJ.] uSTANOVITX~$Y\asg\floor{X/10^9}$, ZADAV EGO
RAVNYM STARSHEJ CIFRE CHISLA~$X$. (mY POVTORIM $Y+1$~RAZ SHAGI S~\stp{2}
PO~\stp{13} VKLYUCHITELXNO. dRUGIMI SLOVAMI, SLUCHAJNOE CHISLO BUDET
VYCHISLYATXSYA \emph{SLUCHAJNOE} CHISLO RAZ.)

\st[vYBRATX SLUCHAJNYJ SHAG.] uSTANOVITX~$Z\asg\floor{X/10^8}\bmod 10$,
T.~E.~PRISVOITX~$Z$ ZNACHENIE, RAVNOE VTOROJ PO STARSHINSTVU CIFRE CHISLA~$X$.
pEREJTI K VYPOLNENIYU SHAGA~\stp{$(3+Z)$}.
%% 18
(dRUGIMI SLOVAMI, DALEE MY VYPOLNYAEM \emph{SLUCHAJNO} VYBRANNYJ SHAG PROGRAMMY!)

\st[oBESPECHITX~$X\ge 5\cdot 10^9$.] eSLI~$X<5\cdot 10^9$, TO
USTANOVITX~$X\asg X+5\cdot 10^9$.

\st[sEREDINA KVADRATA.] zAMENITX~$X$ CHISLOM~$\floor{X^2/10^5}\bmod 10^{10}$,
T.~E.\ SEREDINOJ KVADRATA CHISLA~$X$.

\st[uMNOZHITX.] zAMENITX~$X$ NA~$(1001001001 X) \bmod 10^{10}$.

\st[pSEVDODOPOLNENIE.] eSLI~$X<10^8$, TO USTANOVITX~$X\asg X+9814055677$,
V PROTIVNOM SLUCHAE~$X\asg 10^{10}-X$.

\st[pERESTAVITX POLOVINKI.] pOMENYATX MESTAMI $5$~STARSHIH I $5$~MLADSHIH
CIFR, T.~E.\
USTANOVITX~$X\asg 10^5 \floor{X \bmod 10^5}+\floor{X/10^5}$, ILI,
PO-DRUGOMU, VZYATX SREDNIE $10$~CIFR CHISLA~$(10^{10}+1)X$.

\st[uMNOZHITX.] (sM.~SHAG~\stp{5}.)

\st[uMENXSHITX CIFRY.] uMENXSHITX NA EDINICU KAZHDUYU OTLICHNUYU OT NULYA CIFRU
CHISLA~$X$ (V DESYATICHNOM PREDSTAVLENII).

\st[mODIFICIROVATX NA~$99999$.] eSLI~$X<10^5$, TO
USTANOVITX~$X\asg X^2+99999$, V PROTIVNOM SLUCHAE~$X\asg X-99999$.

\st[nORMALIZOVATX.] (zDESX~$X$ NE MOZHET BYTX RAVNYM NULYU.) eSLI~$X<10^9$,
TO USTANOVITX~$X\asg 10X$ I POVTORITX |TOT SHAG.

\st[mODIFICIROVANNAYA SEREDINA KVADRATA.] zAMENITX~$X$
NA~$\floor{X(X-1)/10^5}\bmod 10^{10}$, T.~E.\ VZYATX SREDNIE 10~CIFR CHISLA~$X(X-1)$.

\st[pOVTORITX?] eSLI~$Y>0$, TO UMENXSHITX~$Y$ NA~$1$ I VERNUTXSYA NA
SHAG~\stp{2}. eSLI~$Y=0$, ALGORITM ZAVERSHEN, PRICHEM TEKUSHCHEE ZNACHENIE~$X$
SCHITAETSYA ISKOMYM SLUCHAJNYM CHISLOM.
\algend
(hOTELOSX NAPISATX NASTOLXKO SLOZHNUYU PROGRAMMU, REALIZUYUSHCHUYU OPISANNYJ VYSHE
ALGORITM, CHTOBY CHELOVEK, CHITAYUSHCHIJ EE TEKST, NE MOG BY BEZ OB�YASNENIJ
DOGADATXSYA, CHTO ZHE V NEJ DELAETSYA.)

uCHITYVAYA VSE MERY PREDOSTOROZHNOSTI, PRINYATYE V ALGORITME~K, NE KAZHETSYA
LI VPOLNE PRAVDOPODOBNYM, CHTO S EGO POMOSHCHXYU MOZHNO POLUCHITX BESKONECHNOE
MNOZHESTVO ABSOLYUTNO SLUCHAJNYH CHISEL? nET! v DEJSTVITELXNOSTI, KAK TOLXKO
|TOT ALGORITM BYL REALIZOVAN NA evm, POCHTI SRAZU ZHE ITERACII SOSHLISX K
CHISLU~$6065038420$, KOTOROE, V REZULXTATE NEVEROYATNOGO SOVPADENIYA,
PREOBRAZUETSYA SAMO V SEBYA (SM.~TABL.~1). pRI DRUGOM NACHALXNOM ZNACHENII
POSLEDOVATELXNOSTX, NACHINAYA S CHLENA S NOMEROM~$7401$, POVTORYAETSYA S DLINOJ
PERIODA~$3178$.

mORALX |TOJ ISTORII ZAKLYUCHAETSYA V TOM, CHTO \emph{SLUCHAJNYE CHISLA NELXZYA
VYRABATYVATX S POMOSHCHXYU SLUCHAJNO VYBRANNOGO ALGORITMA.} nUZHNA KAKAYA-NIBUDX
TEORIYA.

v |TOJ GLAVE MY RASSMOTRIM METODY VYRABOTKI SLUCHAJNYH CHISEL, PREVOSHODYASHCHIE
METOD SEREDINY KVADRATA I ALGORITM~K V TOM OTNOSHENII, CHTO DLYA NIH MOZHNO
TEORETICHESKI GARANTIROVATX
%% 19
\htable{tABLICA~1}%
{kOLOSSALXNOE SOVPADENIE: CHISLO 6065038420 PREOBRAZUETSYA V SEBYA S POMOSHCHXYU ALGORITMA~K}%
{\strut #\bskip\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip&\vrule\bskip#\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip\cr
shAG & \hbox{$X$ (V KONCE SHAGA)} \span & shAG & \hbox{$X$ (V KONCE SHAGA)}\span \cr
K1  & 6065038420 &     & K9  & 1107855700 \cr
K3  & 6065038420 &     & K10 & 1107755701 \cr
K4  & 6910360760 &     & K11 & 1107755701 \cr
K5  & 8031120760 &     & K12 & 1226919902 & Y=3\cr
K6  & 1968879240 &     & K5  & 0048821902 \cr
K7  & 7924019688 &     & K6  & 9862877579 \cr
K8  & 9631707688 &     & K7  & 7757998628 \cr
K9  & 8520606577 &     & K8  & 2384626628 \cr
K10 & 8520506578 &     & K9  & 1273515517 \cr
K11 & 8520506578 &     & K10 & 1273415518 \cr
K12 & 0323372207 & Y=6 & K11 & 1273415518 \cr
K6  & 9676627793 &     & K12 & 5870802097 & Y=2\cr
K7  & 2779396766 &     & K11 & 5870802097 \cr
K8  & 4942162766 &     & K12 & 3172562687 & Y=1\cr
K9  & 3831051655 &     & K4  & 1540029446 \cr
K10 & 3830951656 &     & K5  & 7015475446 \cr
K11 & 3830951656 &     & K6  & 2984524554 \cr
K12 & 1905867781 & Y=5 & K7  & 2455429845 \cr
K12 & 3319967479 & Y=4 & K8  & 2730274845 \cr
KB  & 6680032521 &     & K9  & 1620163734 \cr
K7  & 3252166800 &     & K10 & 1620063735 \cr
K8  & 2218966800 &     & K11 & 1620063735 \cr
    &            &     & K12 & 6065038420 & Y=0 \cr
}
VYPOLNENIE OPREDELENNYH SVOJSTV SLUCHAJNOJ POSLEDOVATELXNOSTI I OTSUTSTVIE
VYROZHDENIYA. bUDUT IZLOZHENY NEKOTORYE DETALI, OBESPECHIVAYUSHCHIE TAKOE
SLUCHAJNOE POVEDENIE, I UDELENO VNIMANIE TEHNIKE PRIMENENIYA SLUCHAJNYH CHISEL.
v CHASTNOSTI, NAPRIMER, BUDET POKAZANO, KAK TASOVATX KARTY S POMOSHCHXYU
PROGRAMMY DLYA~evm.

\excercises
\rex[20] pREDPOLOZHIM, VY HOTITE, NE ISPOLXZUYA evm, POLUCHITX
SLUCHAJNUYU DESYATICHNUYU CIFRU. kAKOJ IZ PERECHISLENNYH NIZHE METODOV VY PREDPOCHTETE?

a)~oTKROJTE TELEFONNYJ SPRAVOCHNIK V PROIZVOLXNOM MESTE (T.~E.\ TKNITE PALXCEM
KUDA UGODNO) I VOZXMITE MLADSHUYU CIFRU PERVOGO POPAVSHEGOSYA
NOMERA NA VYBRANNOJ VAMI STRANICE.

b)~sDELAJTE TO ZHE SAMOE, NO VOSPOLXZUJTESX MLADSHEJ CIFROJ NOMERA
\emph{STRANICY.}

%% 20
c)~bROSXTE KOSTX V FORME PRAVILXNOGO IKOSA|DRA, KAZHDAYA IZ DVADCATI GRANEJ
KOTOROGO POMECHENA CIFRAMI~$0$, $0$, $1$, $1$,~\dots, $9$, $9$. zAPISHITE
CIFRU, KOTOROJ BUDET POMECHENA VERHNYAYA GRANX OSTANOVIVSHEJSYA KOSTI. (dLYA
|KSPERIMENTA REKOMENDUETSYA POLXZOVATXSYA STOLOM S TVERDOJ OBITOJ SUKNOM POVERHNOSTXYU.)

d)~pOSTAVXTE NA MINUTU RYADOM S ISTOCHNIKOM RADIOAKTIVNOGO IZLUCHENIYA SCHETCHIK
gEJGERA (PRIMITE MERY PREDOSTOROZHNOSTI). vOSPOLXZUJTESX MLADSHEJ CIFROJ
CHISLA OTSCHETOV, POKAZANNOGO SCHETCHIKOM. (pREDPOLAGAETSYA, CHTO GEJGEROVSKIJ
SCHETCHIK POKAZYVAET CHISLO OTSCHETOV V DESYATICHNOM VIDE I PERED NACHALOM
|KSPERIMENTA ON BYL USTANOVLEN NA NULX.)

e)~vZGLYANITE NA SVOI CHASY I, ESLI SEKUNDNAYA STRELKA NAHODITSYA
MEZHDU CHISLAMI~$6n$ I~$6(n+1)$, VYBERITE CIFRU~$n$.

f)~pOPROSITE PRIYATELYA ZADUMATX SLUCHAJNUYU CIFRU I PUSTX ON VAM EE NAZOVET.

g)~pUSTX TO ZHE SAMOE SDELAET VASH NEDRUG.

h)~pREDPOLOZHIM, CHTO V ZABEGE UCHASTVUET $10$~ABSOLYUTNO NEIZVESTNYH
VAM LOSHADEJ. sOVERSHENNO PROIZVOLXNO PRONUMERUJTE IH CIFRAMI OT~$0$
DO~$9$. vOSPOLXZUJTESX NOMEROM POBEDITELYA ZABEGA.

\ex[m22] kAKOVA VEROYATNOSTX OBNARUZHITX ROVNO $100\,000$~|KZEMPLYAROV LYUBOJ
ZADANNOJ ZARANEE CIFRY V SLUCHAJNOJ POSLEDOVATELXNOSTI, SOSTOYASHCHEJ IZ
$1\,000\,000$~DESYATICHNYH CIFR?

\ex[10] kAKOE CHISLO POLUCHITSYA POSLE PRIMENENIYA METODA SEREDINY KVADRATA
K CHISLU~$1010101010$?

\ex[10] pOCHEMU PRI VYPOLNENII SHAGA~K11 ALGORITMA~K ZNACHENIE~$X$ NE MOZHET
BYTX RAVNYM NULYU? chTO PROIZOSHLO BY S ALGORITMOM, ESLI BY~$h$ MOGLO BYTX NULEM?

\ex[15] oB�YASNITE, POCHEMU V LYUBOM SLUCHAE NELXZYA OZHIDATX
POLUCHENIYA "BESKONECHNOGO MNOZHESTVA" SLUCHAJNYH CHISEL S POMOSHCHXYU ALGORITMA~K
(DAZHE ESLI BY NE PROIZOSHLO SOVPADENIYA, PRIVEDENNOGO V TABL.~1), SCHITAYA
ZARANEE IZVESTNYM TOT FAKT, CHTO LYUBAYA POSLEDOVATELXNOSTX, VYRABOTANNAYA S
ISPOLXZOVANIEM |TOGO ALGORITMA, V KONCE KONCOV STANET PERIODICHESKOJ?

\rex[m20] pREDPOLOZHIM, CHTO MY HOTIM VYRABOTATX POSLEDOVATELXNOSTX CELYH
CHISEL~$X_0$, $X_1$, $X_2$,~\dots{} V INTERVALE~$0\le X_n < m$.
pUSTX~$f(x)$---LYUBAYA FUNKCIYA, TAKAYA, CHTO ESLI~$0 \le x < m$, TO~$0\le f(x)<m$.
rASSMOTRIM POSLEDOVATELXNOSTX, POLUCHENNUYU S POMOSHCHXYU
SOOTNOSHENIYA~$X_{n+1}=f(X_n)$. (pRIMERAMI YAVLYAYUTSYA METOD SEREDINY KVADRATA
I ALGORITM~k.)

a)~pOKAZHITE, CHTO POSLEDOVATELXNOSTX V KONCE KONCOV STANOVITSYA
PERIODICHESKOJ, T.~E.\ SUSHCHESTVUYUT TAKIE CHISLA~$\lambda$ I~$\mu$, CHTO
ZNACHENIYA~$X_0$, $X_1$,~\dots, $X_\mu$,~\dots, $X_{\mu+\lambda-1}$ RAZLICHNY,
NO~$X_{n+\lambda}=X_n$,  KOGDA~$n\ge \mu$. nAJDITE MAKSIMALXNOE I
MINIMALXNOE VOZMOZHNYE ZNACHENIYA~$\mu$ I~$\lambda$.

b)~pOKAZHITE, CHTO SUSHCHESTVUET~$n>0$, TAKOE, CHTO~$X_n=X_{2n}$;
NAIMENXSHEE ZNACHENIE |TOGO~$n$ LEZHIT V INTERVALE~$\mu \le n \le \mu+\lambda$.
zNACHENIE~$X_n$ YAVLYAETSYA EDINSTVENNYM V TOM SMYSLE, CHTO
ESLI~$X_n=X_{2n}$ I~$X_r=X_{2r}$, TO~$X_r=X_n$ (SLEDOVATELXNO, $r-n$
KRATNO~$\lambda$).

\rex[20] pRIMENITE REZULXTATY PREDYDUSHCHEGO UPRAZHNENIYA, CHTOBY
POSTROITX PRAKTICHNYJ ALGORITM VYRABOTKI SLUCHAJNYH CHISEL, DOPOLNYAYUSHCHIJ
DATCHIK TIPA~$X_{n+1}=f(X_n)$. vASH ALGORITM DOLZHEN: a)~OBLADATX SVOJSTVOM
PRIOSTANAVLIVATX VYRABOTKU SLUCHAJNYH CHISEL POSLEDOVATELXNOSTI, KAK
TOLXKO POVTORYAETSYA RANEE VSTRECHAVSHEESYA CHISLO, b)~VYRABOTATX PO MENXSHEJ
MERE~$\lambda$ |LEMENTOV PERED OSTANOVKOJ, HOTYA ZNACHENIE~$\lambda$ ZARANEE
NEIZVESTNO, I~c)~ISPOLXZOVATX NEBOLXSHUYU PAMYAGX (T.~E.\ NE RAZRESHAETSYA.
PROSTO ZAPOMINATX VSE VYCHISLENNYE POSLEDOVATELXNYE ZNACHENIYA).

\ex[28] pOLNOSTXYU PROVERXTE METOD SEREDINY KVADRATA DLYA SLUCHAYA
DVUZNACHNYH CHISEL. a)~mY MOZHEM NACHATX S LYUBOGO IZ 100~VOZMOZHNYH
ZNACHENIJ~$00$, $01$,~\dots, $99$. v SKOLXKIH SLUCHAYAH MY V KONCE KONCOV
PRIDEM K POVTORENIYU CIKLA~$00$, $00$,~\dots? [\emph{pRIMER.} nACHAV S~$43$,
MY POLUCHIM POSLEDOVATELXNOSTX~$43$, $84$, $05$, $02$, $00$, $00$,
$00$,~$\ldots\,$.] b)~sKOLXKO MOZHET POLUCHITXSYA RAZLICHNYH CIKLOV? kAKOVA DLINA
PERIODA SAMOGO DLINNOGO CIKLA? c)~kAKOE NACHALXNOE ZNACHENIE
%% 21
POZVOLYAET POLUCHITX SAMUYU DLINNUYU POSLEDOVATELXNOSTX NEPOVTORYAYUSHCHIHSYA |LEMENTOV?

\ex[m14] dOKAZHITE, CHTO METOD SEREDINY KVADRATA, ISPOLXZUYUSHCHIJ
$2n\hbox{-ZNACHNYE}$ CHISLA S OSNOVANIEM~$b$, IMEET SLEDUYUSHCHIJ NEDOSTATOK:
NACHINAYA S CHISLA~$X$, U KOTOROGO STARSHIE $n$~CIFR RAVNY NULYU, VSE
POSLEDUYUSHCHIE |LEMENTY POSLEDOVATELXNOSTI STANOVYATSYA VSE MENXSHE I MENXSHE,
POKA NE OBRATYATSYA V NULX.

\ex[m16] sOHRANIV PREDPOLOZHENIYA PREDYDUSHCHEGO UPRAZHNENIYA, CHTO MOZHNO SKAZATX
O POSLEDOVATELXNOSTI |LEMENTOV, SLEDUYUSHCHIH ZA CHISLOM~$X$, U
KOTOROGO \emph{SAMYE MLADSHIE} $n$~CIFR RAVNY NULYU? chTO, ESLI MLADSHIE
$(n+1)$~CIFR RAVNY NULYU?

\rex[m26] rASSMOTRIM SLUCHAJNYE POSLEDOVATELXNOSTI,
VYRABATYVAEMYE DATCHIKAMI TIPA OPISANNOGO V UPR.~6. eSLI MY VYBIRAEM~$f(x)$
I~$X_0$ SLUCHAJNO I PREDPOLAGAEM, CHTO LYUBYE IZ $m^m$~VOZMOZHNYH
FUNKCIJ~$f(x)$ I $m$~NACHALXNYH ZNACHENIJ~$X_0$ RAVNOVEROYATNY, TO KAKOVA
VEROYATNOSTX TOGO, CHTO V KONCE KONCOV POSLEDOVATELXNOSTX VYRODITSYA, OBRAZUYA
CIKL S DLINOJ PERIODA~$\lambda=1$?

[\emph{zAMECHANIE.} pREDPOLOZHENIYA, PRINYATYE V |TOJ ZADACHE, DAYUT
VOZMOZHNOSTX VPOLNE ESTESTVENNYM OBRAZOM ZADUMATXSYA O "SLUCHAJNOM" DATCHIKE
SLUCHAJNYH CHISEL PODOBNOGO TIPA. mOZHNO OZHIDATX, CHTO METOD, PODOBNYJ
ALGORITMU~K, DOLZHEN BYTX POHOZHIM NA SREDNIJ DATCHIK, RASSMOTRENNYJ ZDESX.
rESHENIE ZADACHI DAET MERU TOGO, NASKOLXKO "KOLOSSALXNO" NA SAMOM DELE
SOVPADENIE, PRIVEDENNOE V TABL.~1.]

\rex[m31] iSPOLXZUYA PREDPOLOZHENIYA PREDYDUSHCHEGO UPRAZHNENIYA, NAJDITE SREDNYUYU
DLINU CIKLA, KOTORYJ OBRAZUETSYA V POSLEDOVATELXNOSTYAH. kAKOJ SREDNEJ DLINY
DOSTIGAET POSLEDOVATELXNOSTX, PREZHDE CHEM NACHATX CIKLITXSYA? (v OBOZNACHENIYAH
UPR.~6 MY HOTIM OPREDELITX SREDNIE ZNACHENIYA~$\lambda$ I~$\mu+\lambda$.)

\ex[m42] eSLI~$f(x)$ VYBIRAETSYA SLUCHAJNO V SMYSLE UPR.~11, KAKOVA
SREDNYAYA DLINA \emph{SAMOGO DLINNOGO} CIKLA, POLUCHENNOGO V REZULXTATE
IZMENENIYA NACHALXNOGO ZNACHENIYA~$X_0$? [\emph{zAMECHANIE.} oTVET IZVESTEN
DLYA SPECIALXNOGO SLUCHAYA, KOGDA V KACHESTVE FUNKCII~$f(x)$ RASSMATRIVAETSYA
PERESTANOVKA; SM. UPR.~1.3.3-23.]

\ex[m38] eSLI~$f(x)$ VYBIRAETSYA SLUCHAJNO V SMYSLE UPR.~11, KAKOVO SREDNEE
CHISLO RAZLICHNYH CIKLOV, POLUCHAEMYH V REZULXTATE IZMENENIYA NACHALXNOGO
ZNACHENIYA? (sR.~S~UPR.~8(b).)

\ex[m15] eSLI~$f(x)$ VYBIRAETSYA SLUCHAJNO V SMYSLE UPR.~11, KAKOVA
VEROYATNOSTX TOGO, CHTO NI ODIN IZ CIKLOV NE IMEET DLINY~$1$,
BEZOTNOSITELXNO K VYBORU~$X_0$?

\ex[15] pOSLEDOVATELXNOSTX, VYRABATYVAEMAYA S POMOSHCHXYU METODA, OPISANNOGO
V UPR.~6, DOLZHNA NACHATX POVTORYATXSYA SAMOE POZDNEE POSLE VYRABOTKI
$m$~ZNACHENIJ. pREDPOLOZHIM, CHTO MY OBOBSHCHILI METOD TAK, CHTO $X_{n+1}$~TEPERX
ZAVISIT NE TOLXKO OT~$X_n$, NO I OT~$X_{n-1}$. fORMALXNO PUSTX~$f(x, y)$
BUDET TAKAYA FUNKCIYA, CHTO ESLI~$0\le x$, $y<m$, TO~$0\le f(x, y)< m$.
nACHINAEM STROITX POSLEDOVATELXNOSTX S PROIZVOLXNOGO VYBORA~$X_0$ I~$X_1$.
zATEM POLAGAEM
$$
X_{n+1}=f(X_n, X_{n-1}) \rem{DLYA $n>0$.}
$$
kAKUYU MAKSIMALXNUYU DLINU PERIODA MOZHNO POLUCHITX V |TOM SLUCHAE?

\ex[10] oBOBSHCHITE IDEYU PREDYDUSHCHEGO UPRAZHNENIYA TAK, CHTOBY $X_{n+1}$~ZAVISELO
OT $k$~PREDYDUSHCHIH ZNACHENIJ |LEMENTOV POSLEDOVATELXNOSTI.

\ex[m22] pRIDUMAJTE METOD, ANALOGICHNYJ PREDLOZHENNOMU V UPR.~7,
DLYA OBNARUZHENIYA CIKLA DATCHIKA SLUCHAJNYH CHISEL OBSHCHEGO VIDA,
RASSMOTRENNOGO V PREDYDUSHCHEM UPRAZHNENII.

\ex[m50] rESHITE ZADACHI, POSTAVLENNYE V UPR.~11--15, DLYA BOLEE
OBSHCHEGO SLUCHAYA, KOGDA $X_{n+1}$~ZAVISIT OT PREDYDUSHCHIH $k$~|LEMENTOV
POSLEDOVATELXNOSTI. kAZHDAYA IZ~$m^{m^k}$ FUNKCIJ~$f(x_1, x_2,~\ldots, x_k)$
DOLZHNA RASSMATRIVATXSYA KAK RAVNOVEROYATNAYA. [\emph{zAMECHANIE.} kOLICHESTVO
FUNKCIJ, DAYUSHCHIH \emph{MAKSIMALXNYJ} PERIOD, PRIVODITSYA V UPR.~2.3.4.2-23.]

%% 22
\subchap{vyrabotka ravnomerno raspredelennyh sluchajnyh chisel} % 3.2
v |TOM PARAGRAFE MY RASSMOTRIM METODY POLUCHENIYA POSLEDOVATELXNOSTI
SLUCHAJNYH DROBEJ, T.~E.\ SLUCHAJNYH \emph{DEJSTVITELXNYH CHISEL~$U_n$,
RAVNOMERNO RASPREDELENNYH MEZHDU NULEM I EDINICEJ.} tAK KAK V
VYCHISLITELXNOJ MASHINE DEJSTVITELXNOE CHISLO VSEGDA PREDSTAVLYAETSYA S
OGRANICHENNOJ TOCHNOSTXYU, FAKTICHESKI MY BUDEM GENERIROVATX CELYE CHISLA~$X_n$
V INTERVALE OT~$0$ DO NEKOTOROGO~$m$. tOGDA DROBX
$$
U_n=X_n/m
\eqno(1)
$$
POPADET V INTERVAL OT NULYA DO EDINICY. oBYCHNO~$m$ NA EDINICU BOLXSHE
MAKSIMALXNOGO CHISLA, KOTOROE MOZHNO ZAPISATX V MASHINNOM SLOVE [($m$ RAVNO
\emph{RAZMERU SLOVA} (word size)]. pO|TOMU~$X_n$ MOZHNO INTERPRETIROVATX
(KONSERVATIVNO) KAK CELOE SODERZHIMOE MASHINNOGO SLOVA S DESYATICHNOJ
ZAPYATOJ, RASPOLOZHENNOJ SPRAVA, A~$U_n$ MOZHNO SCHITATX (LIBERALXNO) DROBXYU,
SODERZHASHCHEJSYA V TOM ZHE SLOVE, S ZAPYATOJ V KRAJNEJ LEVOJ POZICII.

\subsubchap{lINEJNYJ KONGRU|NTNYJ METOD} % 3.2.1
nAILUCHSHIE IZ IZVESTNYH SEGODNYA DATCHIKOV SLUCHAJNYH CHISEL PREDSTAVLYAYUT SOBOJ
CHASTNYE SLUCHAI SLEDUYUSHCHEJ SHEMY, PREDLOZHENNOJ d.~X.~lEMEROM V~1948~G.\
[sM. Proc. 2nd Symposium on Large-Scale Digital Computing Machinery
(Cambridge: Harvard University Press, 1951), 141--146.] vYBIRAEM CHETYRE
"MAGICHESKIH CHISLA":
$$
\vcenter{\halign{
$#$\hfil\bskip&#\bskip\hfil&\bskip\hfil$#$&${}#$\hfil\cr
X_0, & NACHALXNOE ZNACHENIE; & X_0&\ge 0; \cr
  a, & MNOZHITELX;          &   a&\ge 0; \cr
  c, & PRIRASHCHENIE;         &   c&\ge 0; \cr
  m, & MODULX;             &   m&> X_0, m>a, m>c.\cr
}}
\eqno(1)
$$
tOGDA ISKOMAYA POSLEDOVATELXNOSTX SLUCHAJNYH CHISEL~$\<X_n>$ POLUCHAETSYA IZ SOOTNOSHENIYA
$$
X_{n+1}=(aX_n+c) \bmod m, \rem{$n\ge 0$.}
\eqno (2)
$$

oNA NAZYVAETSYA \dfn{LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTXYU.}
%% 23

nAPRIMER, PRI~$X_0=a=c=7$, $m=10$ POSLEDOVATELXNOSTX VYGLYADIT TAK:
$$
7,\; 6,\; 9,\; 0,\; 7,\; 6,\; 9,\; 0,\;~\ldots
\eqno (3)
$$
kAK VIDNO IZ PRIVEDENNOGO PRIMERA, POSLEDOVATELXNOSTX NE VSEGDA
OKAZYVAETSYA "SLUCHAJNOJ", ESLI VYBIRATX~$X_0$, $a$, $c$, $m$ PROIZVOLXNO. v
POSLEDUYUSHCHIH RAZDELAH |TOJ GLAVY BUDUT PODROBNO ISSLEDOVANY PRINCIPY
VYBORA |TIH ZNACHENIJ.

pRIMER~(3) ILLYUSTRIRUET TOT FAKT, CHTO KONGRU|NTNYE POSLEDOVATELXNOSTI
VSEGDA "ZACIKLIVAYUTSYA", T.~E.\ V KONCE KONCOV CHISLA OBRAZUYUT CIKL, KOTORYJ
POVTORYAETSYA BESKONECHNOE CHISLO RAZ. eTO SVOJSTVO PRISUSHCHE VSEM
POSLEDOVATELXNOSTYAM, IMEYUSHCHIM OBSHCHIJ VID~$X_{n+1}=f(X_n)$; SM.~UPR.~3.1-6.
pOVTORYAYUSHCHIJSYA CIKL NAZYVAETSYA \dfn{PERIODOM.} dLINA PERIODA U
POSLEDOVATELXNOSTI~(3) RAVNA~$4$. rEALXNYE POSLEDOVATELXNOSTI, KOTORYMI
POLXZUYUTSYA, IMEYUT, KONECHNO, SRAVNITELXNO BOLXSHOJ PERIOD.

sPECIALXNOGO UPOMINANIYA ZASLUZHIVAET CHASTNYJ SLUCHAJ~$c=0$, KOGDA PROCESS
VYRABOTKI SLUCHAJNYH CHISEL PROISHODIT NESKOLXKO BYSTREE. pOZZHE MY UVIDIM,
CHTO OGRANICHENIE~$c=0$ UMENXSHAET DLINU PERIODA POSLEDOVATELXNOSTI, NO PRI
|TOM VSE ESHCHE MOZHNO POLUCHITX OTNOSITELXNO BOLXSHOJ PERIOD. v PERVONACHALXNOM
METODE lEMERA BYLO PRINYATO~$c=0$, HOTYA AVTOR I UPOMYANUL VOZMOZHNOSTX
ISPOLXZOVANIYA~$c\ne 0$. iDEYA POLUCHENIYA BOLEE DLINNYH POSLEDOVATELXNOSTEJ
ZA SCHET OBOBSHCHENIYA~$c\ne 0$ PRINADLEZHIT tOMSONU
[{\sl Comp. J.,\/} {\bf 1} (1958), 83, 86] I NEZAVISIMO rOTENBERGU
[{\sl JACM,\/} {\bf 7} (1960), 75--77].

mNOGIMI AVTORAMI TERMINY \dfn{MULXTIPLIKATIVNYJ KONGRU|NTNYJ METOD} I
\dfn{SMESHANNYJ KONGRU|NTNYJ METOD} PRIMENYAYUTSYA DLYA OBOZNACHENIYA LINEJNYH
KONGRU|NTNYH METODOV S~$c=0$ I~$c\ne0$ SOOTVETSTVENNO.

vO VSEJ |TOJ GLAVE BUKVY~$a$, $c$, $m$, $X_0$ BUDUT ISPOLXZOVATXSYA V TOM
SMYSLE, KAK |TO PRINYATO VYSHE. bOLEE TOGO, CHTOBY UPROSTITX MNOGIE NASHI
FORMULY, OKAZYVAETSYA POLEZNYM OPREDELITX
$$
b=a-1.
\eqno(4)
$$
mOZHNO SRAZU ZHE OTBROSITX SLUCHAJ~$a=1$, TAK KAK PRI |TOM $X_n=(X_0+nc) \bmod m$,
I OCHEVIDNO, CHTO POSLEDOVATELXNOSTX NE SLUCHAJNAYA. vARIANT~$a=0$
ESHCHE HUZHE. sLEDOVATELXNO, DLYA PRAKTICHESKIH CELEJ MY MOZHEM PREDPOLOZHITX, CHTO
$$
a\ge 2, \qquad b \ge 1.
\eqno (5)
$$

tEPERX MOZHNO OBOBSHCHITX SOOTNOSHENIE~(2),
$$
X_{n+k}=(a^k X_n+(a^k-1)c/b) \bmod m,
\rem{$k\ge 0$, $n\ge 0$},
\eqno (6)
$$
VYRAZIV $(n+k)\hbox{-J}$~CHLEN PRYAMO CHEREZ~$n\hbox{-J}$. (sLEDUET OBRATITX
VNIMANIE NA CHASTNYJ SLUCHAJ~$n=0$.) pOSLEDOVATELXNOSTX, SOSTAVLENNAYA
%% 24
IZ KAZHDOGO $k\hbox{-GO}$~CHLENA NASHEJ POSLEDOVATELXNOSTI
OBRAZUET DRUGUYU LINEJNUYU KONGRU|NTNUYU POSLEDOVATELXNOSTX S
MNOZHITELEM~$a^k$ I PRIRASHCHENIEM~$((a^k-1)c/b)$.

\excercises
\ex[10] v PRIMERE~(3) ILLYUSTRIRUETSYA SITUACIYA, KOGDA~$X_4=X_0$, TAK
CHTO POSLEDOVATELXNOSTX OPYATX NACHINAETSYA SNACHALA. nAJDITE PRIMER TAKOJ
LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S~$m=10$, V KOTOROJ
$X_0$~VSTRECHAETSYA TOLXKO ODIN RAZ.

\rex[m20] pOKAZHITE, CHTO, ESLI~$a$ I~$m$ VZAIMNO PROSTYE, CHISLO~$X_0$
BUDET PERIODICHESKI POVTORYATXSYA.

\ex[m10] oB�YASNITE, POCHEMU, ESLI~$a$ I~$m$ NE YAVLYAYUTSYA VZAIMNO PROSTYMI,
POSLEDOVATELXNOSTX V KAKOM-TO SMYSLE NEUDACHNAYA I, VEROYATNO, NE
SLISHKOM SLUCHAJNAYA. pO|TOMU, VOOBSHCHE GOVORYA, MY BUDEM STARATXSYA VYBIRATX~$a$
I~$m$  VZAIMNO PROSTYMI.

\ex[11] dOKAZHITE SOOTNOSHENIE~(6).

\ex[m20] sOOTNOSHENIE~(6) VYPOLNYAETSYA DLYA~$k\ge 0$. eSLI |TO VOZMOZHNO,
POLUCHITE FORMULU, VYRAZHAYUSHCHUYU~$X_{n+k}$ CHEREZ~$X_n$ I DLYA
\emph{OTRICATELXNYH} ZNACHENIJ~$k$.

\subsubsubchap{vYBOR MODULYA}%3.2.1.1
sNACHALA OBSUDIM, KAK PRAVILXNO VYBIRATX CHISLO~$m$. mY HOTIM, CHTOBY
ZNACHENIE~$m$ BYLO DOSTATOCHNO BOLXSHIM, TAK KAK DLINA PERIODA NE MOZHET BYTX
BOLXSHE~$m$. (dAZHE ESLI TREBUYUTSYA TOLXKO SLUCHAJNYE NULI I EDINICY,
NE SLEDUET BRATX~$m=2$, TAK KAK PRI |TOM V LUCHSHEM SLUCHAE POLUCHITSYA NABOR
$$
\ldots, 0, 1, 0, 1, 0, 1,\ldots\,!
$$

mETODY ISPOLXZOVANIYA RAVNOMERNO RASPREDELENNYH SLUCHAJNYH CHISEL DLYA
POLUCHENIYA POSLEDOVATELXNOSTI NULEJ I EDINIC OBSUZHDAYUTSYA V~\S~3.4.)

dRUGOJ FAKTOR, VLIYAYUSHCHIJ NA VYBOR~$m$---|TO SKOROSTX VYRABOTKI CHISEL: MY
HOTIM PODOBRATX TAKOE ZNACHENIE, CHTOBY BYSTREE VYCHISLYATX~$(aX_n+c)\bmod m$.

rASSMOTRIM V KACHESTVE PRIMERA MASHINU~\MIX. mY MOZHEM VYCHISLYATX~$y \bmod
m$, POMESHCHAYA~$y$ V REGISTRY~|A| I~|X|, POSLEDUYUSHCHIM DELENIEM NA~$m$.
pREDPOLOZHIV, CHTO~$y$ I~$m$---POLOZHITELXNYE CHISLA, MOZHNO UBEDITXSYA, CHTO V
REZULXTATE V REGISTRE~|X| OKAZHETSYA~$y\bmod m$. nO TAK KAK
DELENIE---SRAVNITELXNO MEDLENNAYA OPERACIYA, EE MOZHNO IZBEZHATX ZA SCHET OSOBO
UDOBNOGO VYBORA~$m$, PRINYAV EGO RAVNYM \emph{RAZMERU SLOVA} (T.~E.~NA
EDINICU BOLXSHE MAKSIMALXNOGO CELOGO CHISLA, RAZMESHCHAYUSHCHEGOSYA V SLOVE
VYCHISLITELXNOJ MASHINY).

pUSTX~$w$---TAKOE MAKSIMALXNOE CELOE CHISLO. tOGDA OPERACIYA SLOZHENIYA
PROIZVODITSYA PO MODULYU~$w$, A UMNOZHENIE PO MODULYU~$w$ TAKZHE SRAVNITELXNO
PROSTO, TAK KAK NUZHNYJ REZULXTAT POLUCHAETSYA V MLADSHIH RAZRYADAH
PROIZVEDENIYA. tAKIM OBRAZOM, SLEDUYUSHCHAYA
%% 25
PROGRAMMA |FFEKTIVNO VYCHISLYAET~$(aX+c)\bmod w$:
$$
\vcenter{
\mixcode
LDA  & A
MUL  & X
SLAX & 5
ADD  & C
\endmixcode
}
\eqno(1)
$$

rEZULXTAT POLUCHAETSYA V REGISTRE~|A|. v KONCE VYPOLNENIYA |TOJ
POSLEDOVATELXNOSTI KOMAND MOZHET PROIZOJTI PEREPOLNENIE, SIGNAL KOTOROGO
MOZHNO VYKLYUCHITX, NAPISAV VSLED ZA POSLEDNEJ KOMANDOJ~"|JOV *+1|".

mENEE SHIROKO IZVESTNUYU TONKUYU TEHNIKU MOZHNO ISPOLXZOVATX DLYA VYCHISLENIJ PO
MODULYU~$(w+1)$. pO PRICHINAM, O KOTORYH BUDET SKAZANO NIZHE, PRI~$m=w+1$ MY
OBYCHNO POLAGAEM~$c=0$. pO|TOMU NAM NUZHNO VYCHISLYATX PROSTO~$(aX)\bmod(w+1)$.
eTO DELAET SLEDUYUSHCHAYA PROGRAMMA:
$$
\vcenter{
\mixcode
LDAN & X
MUL  & A
STX  & TEMP
SUB  & TEMP
JANN & *+3
INCA & 2
ADD  & =W-1=
\endmixcode
}
\eqno(2)
$$

v REGISTRE~|A| TEPERX SODERZHITSYA ZNACHENIE~$(aX)\bmod (w+1)$. kONECHNO, ONO
MOZHET BYTX LYUBYM V INTERVALE MEZHDU~$0$ I~$w$. pO|TOMU CHITATELX VPOLNE
ZAKONNO MOZHET SPROSITX, KAK MOZHNO ZAPISATX TAK MNOGO ZNACHENIJ S POMOSHCHXYU
|A|-REGISTRA! (oCHEVIDNO, CHTO V REGISTRE NE MOGUT POMESHCHATXSYA CHISLA,
BOLXSHIE, CHEM~$w-1$.) oTVET SOSTOIT V TOM, CHTO PEREPOLNENIE PROIZOJDET
TOGDA I TOLXKO TOGDA, KOGDA REZULXTAT RAVEN~$w$ (V PREDPOLOZHENII, CHTO
SIGNAL PEREPOLNENIYA BYL RANEE VYKLYUCHEN).

dLYA DOKAZATELXSTVA TOGO, CHTO PROGRAMMA~(2), V SAMOM DELE,
VYCHISLYAET~$(aX)\bmod (w+1)$, ZAMETIM, CHTO V STROKE~04 MY VYCHITAEM
MLADSHUYU POLOVINU PROIZVEDENIYA IZ STARSHEJ. pEREPOLNENIYA PRI |TOM
PROIZOJTI NE MOZHET, I, ESLI~$aX=qw+r$, GDE~$0\le r < w$, V REGISTRE~|A|
POSLE VYPOLNENIYA STROKI~04 OKAZHETSYA ZNACHENIE~$r-q$. zAMETIM, CHTO
$$
aX=q(w+1)+(r-q),
$$
A TAK KAK~$q<w$,  IMEEM~$-w < r-q < w$. sLEDOVATELXNO,
$(aX)\bmod(w+1)$~RAVNYAETSYA LIBO~$r-q$, LIBO~$r-q+(w+1)$ V ZAVISIMOSTI OT
TOGO, KAKOE IZ NERAVENSTV~$r-q\ge 0$ ILI~$r-q<0$ VYPOLNYAETSYA.
eSLI MY POLXZUEMSYA KONGRU|NTNYM METODOM S~$m=w+1$, OTBRASYVATX
ZNACHENIYA~$w$, ESLI ONI POLUCHAYUTSYA, BYVAET OBYCHNO
%% 26
LEGKO, DOBAVLYAYA K PROGRAMME~(2) KOMANDY
$$
\vbox{
\mixcode
JOV & * +1 \global\pcntr=-1
\dots \global\pcntr=8
JNOV & *+3
LDAN & A
JMP  & *-4
\endmixcode
}
\eqno(3)
$$

s POMOSHCHXYU POHOZHEJ TEHNIKI MOZHNO VYCHISLYATX PROIZVEDENIE DVUH CHISEL PO
MODULYU~$(w-1)$; SM.~UPR.~8.

v POSLEDUYUSHCHIH RAZDELAH NAM POTREBUETSYA UMETX PREDSTAVLYATX~$m$ V VIDE
PROIZVEDENIYA PROSTYH CHISEL. eTO POMOZHET PRAVILXNO VYBRATX MNOZHITELX~$a$.
v TABL.~1 PRIVODITSYA FAKTORIZACIYA CHISEL VIDA~$w\pm 1$ POCHTI DLYA VSEH
IZVESTNYH RAZMEROV SLOV. bOLEE POLNYE DANNYE MOZHNO NAJTI V KNIGE
e.~kANNINGH|MA I~X.~vUDALLA (Factorization of~$y^n\pm 1$, Francis Hodgson,
London, 1925) ILI POLUCHITX S POMOSHCHXYU METODOV P.~4.5.4.

chITATELX MOZHET ZADATX SPRAVEDLIVYJ VOPROS, POCHEMU NAS TAK BESPOKOYAT
ZNACHENIYA~$m=w\pm1$, ESLI UDOBSTVA VYBORA~$m=w$ NASTOLXKO OCHEVIDNY?
pRICHINA ZAKLYUCHAETSYA V TOM, CHTO PRI~$m=w$ \emph{MLADSHIE CIFRY CHISLA~$X_n$
NAMNOGO MENEE SLUCHAJNY, CHEM STARSHIE.} eSLI~$d$ YAVLYAETSYA DELITELEM~$m$ I ESLI
% !!! STILX SNOSOK DOLZHEN BYTX TAKIM, CHTOBY NE PUTATX |TU SNOSKU
% S VERHNIM INDEKSOM.
$$
Y_n=X_n \bmod d %
\hbox{\note{1}%
{fORMULA~(4) OPREDELYAET NOVUYU POSLEDOVATELXNOSTX OSTATKOV~$\gamma_0$,
 $\gamma_1$,~\dots, $\gamma_n$, \dots, DLYA KOTOROJ
 VYPOLNENO~(5).---{\sl pRIM. RED.\/}},
}
\eqno(4)
$$
TO, KAK MOZHNO LEGKO POKAZATX,
$$
Y_{n+1}=(aY_n+c)\bmod d
\eqno(5)
$$
(IBO NAJDETSYA NEKOTOROE CELOE~$q$, DLYA KOTOROGO~$X_{n+1}=aX_n+c-qm$, I
PO|TOMU ESLI~$d$ YAVLYAETSYA DELITELEM~$m$, TO, PEREHODYA K SRAVNENIYU PO
MODULYU~$d$, POLUCHIM~(5)).

chTOBY PROILLYUSTRIROVATX VAZHNOSTX SOOTNOSHENIYA~(5), PREDPOLOZHIM, NAPRIMER,
CHTO IMEETSYA DVOICHNAYA VYCHISLITELXNAYA MASHINA. eSLI~$m=w=2^e$, TO MLADSHIE
CHETYRE BITA~$X_n$ PREDSTAVLYAYUT CHISLO~$Y_n=X_n\bmod 2^4$. sUSHCHNOSTX
FORMULY~(5) ZAKLYUCHAETSYA V TOM, CHTO MLADSHIE CHETYRE BITA~$X_n$ OBRAZUYUT
KONGRU|NTNUYU POSLEDOVATELXNOSTX S PERIODOM, NE PREVYSHAYUSHCHIM~16. tOCHNO TAK
ZHE MLADSHIE PYATX BITOV PERIODICHNY S PERIODOM, RAVNYM SAMOE
BOLXSHEE~32. sAMYJ ZHE MLADSHIJ BIT~$X_n$ LIBO SOHRANYAET POSTOYANNOE ZNACHENIE,
LIBO STROGO PERIODICHESKI IZMENYAETSYA OT NULYA DO EDINICY.

pODOBNOJ SITUACII NE VOZNIKAET, KOGDA~$m=w\pm 1$. v |TOM SLUCHAE MLADSHIE
BITY~$X_n$ VEDUT SEBYA TAK ZHE SLUCHAJNO, KAK I STARSHIE. nAPRIMER, CHLENY
POSLEDOVATELXNOSTI PRI~$w=2^{35}$ I~$m=2^{35}-1$
%% 27
{\catcode`.=\active\def.{\cdot}\offinterlineskip
\htable{tABLICA 1}%
{rAZLOZHENIE~$w\pm 1$ NA PROSTYE MNOZHITELI}%
{\strut\hfil$#$\bskip&\vrule\hfil\bskip$#$\bskip\hfil\vrule&\bskip$#$\hfil\cr
2^e-1 & e & 2^e+1 \cr
\noalign{\hrule}
                             7.31.151 & 15 & 3^2.11.331 \cr
                           3.5.17.257 & 16 & 65537 \cr
                               131071 & 17 & 3.43601 \cr
                          3^2.7.19.73 & 18 & 5.13.37.109 \cr
                               524287 & 19 & 3.174763 \cr
                       3.5^2.11.31.41 & 20 & 17.61681 \cr
                          7^2.127.337 & 21 & 3^2.43.5419 \cr
                          3.23.89.683 & 22 & 5.397.2113 \cr
                            47.178481 & 23 & 3.2796203 \cr
                    3^2.5.7.13.17.241 & 24 & 97.257.673 \cr
                          31.601.180l & 25 & 3.11.251.4051 \cr
                          3.2731.8191 & 26 & 5.53.157.1613 \cr
                          7.73.262657 & 27 & 3^4.19.87211 \cr
                    3.5.29.43.113.127 & 28 & 17.15790321 \cr
                        233.1103.2089 & 29 & 3.59.3033169 \cr
              3^2.7 .11 .31 .151 .331 & 30 & 5^2.13.41.61.1321 \cr
                           2147483647 & 31 & 3.715827883 \cr
                     3.5.17.257.65537 & 32 & 641.6700417 \cr
                       7.23.89.599479 & 33 & 3^2 .67.683.20857 \cr
                       3.43691.131071 & 34 & 5.137.953.26317 \cr
                     31.71.127.122921 & 35 & 3.11.43.281.86171 \cr
              3^2.5.7.13.19.37.73.109 & 36 & 17.241.433.38737 \cr
                        223.616318177 & 37 & 3.1777.25781083 \cr
                      3.174763.524287 & 38 & 5.229.457.525313 \cr
                     7.79.8191.121369 & 39 & 3^2 .2731.22366891 \cr
              3.5^2.11.17.31.41.61681 & 40 & 257.4278255361 \cr
                      13367.164511353 & 41 & 3.83.8831418697 \cr
              3^2.7^2.43.127.337.5419 & 42 & 5.13.29.113.1429.14449 \cr
                     431.9719.2099863 & 43 & 3.2932031007403 \cr
               3.5.23.89.397.683.2113 & 44 & 17.353.2931542417 \cr
                7.31.73.151.631.23311 & 45 & 3^3.11.19.331.18837001 \cr
                  3.47.178481.2796203 & 46 & 5.277.1013.1657.30269 \cr
                   2351.4513.13264529 & 47 & 3.283.165768537521 \cr
         3^2.5.7.13.17.97.241.257.673 & 48 & 193.65537.22253377 \cr
                 179951.3203431780337 & 59 & 3.2833.37171.1824726041 \cr
3^2.5^2.7.11.13.31.41.61.151.331.1321 & 60 & 17.241.61681.4562284561 \cr
          7^2.73.127.337.92737.649657 & 63 & 3^3.19.43.5419.77158673929 \cr
         3.5.17.257.641.65537.6700417 & 64 &274177.67280421310721 \cr
\noalign{\hrule\smallskip\hrule}
                               10^e-1 &  e & 10^e+1\cr
\noalign{\hrule}
                       3^3.7.11.13.37 &  6 & 101.9901\cr
                         3^2.239.4649 &  7 & 11.909091\cr
                    3^2.11.73.101.137 &  8 & 17.5882353\cr
                        3^4.37.333667 &  9 & 7.11.13.19.52579\cr
                   3^2.11.41.271.9091 & 10 & 101.3541.27961\cr
                     3^2.21649.513239 & 11 & 11^2.23.4093.8779\cr
              3^3.7.11.13.37.101.9901 & 12 & 73.137.99990001\cr
         3^2.11.17.73.101.137.5882353 & 16 & 353.449.641.1409.69857\cr
\noalign{\hrule\smallskip\hrule}
}
}
%% 28
BUDUT NE SLISHKOM SLUCHAJNY, ESLI VYCHISLYATX VYCHETY PO MODULYU~$31$, $71$,
$127$ ILI~$122921$ (SR.~S~TABL.~1). v TO ZHE VREMYA MLADSHIE BITY BUDUT
VPOLNE SLUCHAJNY (IH MOZHNO RASSMATRIVATX KAK VYCHETY CHLENOV
POSLEDOVATELXNOSTI, POLUCHENNYE PRI SRAVNENII PO MODULYU~$2$).

dRUGAYA VOZMOZHNOSTX---|TO VYBOR V KACHESTVE~$m$ NAIBOLXSHEGO PROSTOGO CHISLA,
MENXSHEGO, CHEM~$w$. eGO MOZHNO NAJTI, PRIMENYAYA TEHNIKU P.~4.5.4, V KOTOROM
ESTX I TABLICA SOOTVETSTVUYUSHCHIH BOLXSHIH PROSTYH CHISEL.

dLYA BOLXSHINSTVA PRILOZHENIJ MLADSHIE BITY NE SUSHCHESTVENNY, I VYBOR~$m=w$
YAVLYAETSYA VPOLNE UDOVLETVORITELXNYM PRI USLOVII, CHTO PROGRAMMIST,
POLXZUYUSHCHIJSYA SLUCHAJNYMI CHISLAMI, DELAET |TO RAZUMNO.

\excercises

\ex[12] iZ UPR.~3.2.1-3 MY ZAKLYUCHILI, CHTO U SAMYH LUCHSHIH
KONGRU|NTNYH DATCHIKOV CHISLA~$a$ I~$m$ VZAIMNO PROSTYE. pOKAZHITE, CHTO V
|TOM SLUCHAE MOZHNO POLUCHITX~$(aX+c)\bmod w$ V REGISTRE~$X$ S POMOSHCHXYU VSEGO
\emph{TREH} KOMAND~\MIX, A NE CHETYREH, KAK V PRIMERE~(1).

\ex[16] nAPISHITE PODPROGRAMMU~\MIX, UDOVLETVORYAYUSHCHUYU TREM USLOVIYAM:
\descrtable{
     oBRASHCHENIE: & |JMP RANDM| \cr
 uSLOVIYA VHODA: & v YACHEJKE~|XRAND| SODERZHITSYA CELOE CHISLO~$X$. \cr
uSLOVIYA VYHODA: & $X\asg |rA|\asg(aX+c)\bmod w$, $|rX|\asg 0$,
                  PEREPOLNENIE "VYKLYUCHENO".\cr
}
(tAKIM OBRAZOM, V REZULXTATE OBRASHCHENIYA K |TOJ PODPROGRAMME BUDET
POLUCHENO SLEDUYUSHCHEE SLUCHAJNOE CHISLO LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI.)

\ex[20] kAK OPISATX NA YAZYKE AVTOKODA~\MIX{} KONSTANTU~$w-1$ NEZAVISIMO OT
RAZMERA BAJTA?

\ex[10] oB�YASNITE SMYSL POSLEDOVATELXNOSTI KOMAND~(3).

\ex[20] dANO, CHTO $m$~MENXSHE MAKSIMALXNOGO CELOGO, POMESHCHAYUSHCHEGOSYA V SLOVE,
A~$x$ I~$y$---NEOTRICATELXNYE CELYE CHISLA, MENXSHIE, CHEM~$m$. pOKAZHITE, CHTO
DLYA VYCHISLENIYA RAZNOSTI~$(x-y)\bmod m$ DOSTATOCHNO CHETYREH KOMAND~\MIX{} I NE
NUZHNA OPERACIYA DELENIYA. kAKOVA NAILUCHSHAYA PROGRAMMA DLYA
VYCHISLENIYA SUMMY~$(x+y)\bmod m$?

\rex[20] v PREDYDUSHCHEM UPRAZHNENII PREDPOLAGAETSYA, CHTO VYCHITANIE PO~$\bmod m$
PROSHCHE, CHEM SLOZHENIE PO~$\bmod m$. rASSMOTRITE POSLEDOVATELXNOSTI,
OBRAZUYUSHCHIESYA PO PRAVILU
$$
X_{n+1}=(aX_n-c) \bmod m.
$$

sUSHCHESTVENNO LI ONI OTLICHAYUTSYA OT LINEJNYH KONGRU|NTNYH
POSLEDOVATELXNOSTEJ, OPREDELENNYH V TEKSTE? uDOBNEE LI ONI DLYA
|FFEKTIVNOGO VYCHISLENIYA NA MASHINAH?

\ex[m24] kAKIE HARAKTERNYE OSOBENNOSTI TABL.~1 VY MOZHETE OTMETITX?

\rex[20] nAPISHITE \MIX-PROGRAMMU DLYA VYCHISLENIYA~$(aX)\bmod (w-1)$,
ANALOGICHNUYU~(2). zNACHENIYA~$0$ I~$w-1$ NA VHODE I VYHODE VASHEJ PROGRAMMY
SLEDUET SCHITATX |KVIVALENTNYMI.

\ex[23] nAPISHITE \MIX-PROGRAMMU DLYA VYCHISLENIYA~$(aX)\bmod (w-2)$,
ANALOGICHNUYU TREBUYUSHCHEJSYA V UPR.~8.

\subsubsubchap{vYBOR MNOZHITELYA}%3.2.1.2
 v |TOM PODPUNKTE MY POKAZHEM, KAK VYBIRATX MNOZHITELX~$a$, CHTOBY POLUCHATX
\emph{PERIOD MAKSIMALXNOJ
%% 29
DLINY.} dLYA LYUBOJ POSLEDOVATELXNOSTI, PREDNAZNACHENNOJ DLYA ISPOLXZOVANIYA V
KACHESTVE ISTOCHNIKA SLUCHAJNYH CHISEL, VAZHEN BOLXSHOJ PERIOD. dEJSTVITELXNO,
NAM BY HOTELOSX, CHTOBY PERIOD SODERZHAL ZNACHITELXNO BOLXSHE CHISEL, CHEM |TO
NEOBHODIMO DLYA RESHENIYA KAKOJ-LIBO ODNOJ ZADACHI. pO|TOMU ZAJMEMSYA ZDESX
DLINOJ PERIODA. chITATELYU SLEDUET, ODNAKO, POMNITX, CHTO
BOLXSHOJ PERIOD---|TO TOLXKO ODIN IZ NEOBHODIMYH PRIZNAKOV SLUCHAJNOSTI NASHEJ
POSLEDOVATELXNOSTI. vPOLNE VOZMOZHNY ABSOLYUTNO NESLUCHAJNYE
POSLEDOVATELXNOSTI S OCHENX BOLXSHIM PERIODOM. nAPRIMER, PRI~$a=c=1$
POSLEDOVATELXNOSTX SVODITSYA PROSTO K~$X_{n+1}=(X_n+1)\bmod m$. oCHEVIDNO,
EE PERIOD RAVEN~$m$, TEM NE MENEE EE NIKAK NELXZYA NAZVATX SLUCHAJNOJ.
dRUGIE SOOBRAZHENIYA, VLIYAYUSHCHIE NA VYBOR MNOZHITELYA, BUDUT PRIVEDENY V |TOJ
GLAVE POZZHE.

tAK KAK VOZMOZHNY TOLXKO $m$~RAZLICHNYH ZNACHENIJ, DLINA PERIODA NE MOZHET
PREVYSHATX~$m$. dOSTIZHIMA LI MAKSIMALXNAYA DLINA~$m$? pRIVEDENNYJ VYSHE
PRIMER POKAZYVAET, CHTO DA, HOTYA VYBOR~$a=c=1$ I NE PRIVODIT K ZHELAEMOJ
POSLEDOVATELXNOSTI. iSSLEDUEM \emph{VSE} VOZMOZHNYE SPOSOBY VYBORA~$a$
I~$c$, KOTORYE DAYUT PERIOD DLINY~$m$. [\emph{zAMECHANIE.} kOGDA PERIOD
IMEET DLINU~$m$, KAZHDOE CHISLO OT~$0$ DO~$(m-1)$ VSTRECHAETSYA ZA PERIOD
ROVNO ODIN RAZ. pO|TOMU V |TOM SLUCHAE VYBOR~$X_0$ NE VLIYAET NA DLINU PERIODA.]

\proclaim tEOREMA A. dLINA PERIODA LINEJNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI RAVNA~$m$ TOGDA I TOLXKO TOGDA, KOGDA
\item{i)}~$c$ I~$m$---VZAIMNO PROSTYE CHISLA;
\item{ii)}~$b=a-1$ KRATNO~$p$ DLYA LYUBOGO PROSTOGO~$p$, YAVLYAYUSHCHEGOSYA DELITELEM~$m$;
\item{iii)}~$b$ KRATNO~$4$, ESLI~$m$ KRATNO~$4$.

iDEI DOKAZATELXSTVA IZVESTNY NE MENEE STA LET. pERVOE DOKAZATELXSTVO
TEOREMY V DANNOJ FORMULIROVKE BYLO DANO m.~gRINBERGEROM DLYA CHASTNOGO
SLUCHAYA~$m=2^e$ ({\sl JACM,\/} {\bf 8} (1961), 383--389). dOSTATOCHNOSTX
USLOVIJ~(i), (ii), (iii) V OBSHCHEM SLUCHAE BYLA POKAZANA hALLOM I dOBELLOM
({\sl SIAM Review,\/} {\bf 4} (1962), 230--254). dLYA DOKAZATELXSTVA
TEOREMY RASSMOTRIM SNACHALA NEKOTORYE VSPOMOGATELXNYE REZULXTATY TEORII
CHISEL, KOTORYE INTERESNY I SAMI PO SEBE.

\proclaim lEMMA~P. pUSTX~$p$---PROSTOE CHISLO, A~$e$---POLOZHITELXNOE CELOE,
TAKOE, CHTO~$p^e>2$. eSLI
$$
x\equiv 1 \pmod{p^e}, \quad x \not\equiv 1 \pmod{p^{e+1}},
\eqno(1)
$$
TO
$$
x^p \equiv 1 \pmod{p^{e+1}}, \quad x^p \not\equiv 1 \pmod{p^{e+2}}.
\eqno(2)
$$

\proof mY IMEEM~$x=1+qp^e$,  GDE~$q$---NEKOTOROE CELOE, NE KRATNOE~$p$.
%% 30
pO FORMULE BINOMA ZAPISHEM
$$
\eqalign{
x^p&=1+\perm{p}{1}qp^e+\cdots+\perm{p}{p-1}q^{p-1}p^{(p-1)e}+q^pp^{pe}=\cr
&=1+qp^{e+1}\left(1+{1\over p}\perm{p}{2}qp^e+{1\over p}\perm{p}{3}q^2p^{2e}+
 \cdots+{1\over p}\perm{p}{p}q^{p-1}p^{(p-1)e}\right).\cr
}
$$

vYRAZHENIE V SKOBKAH---CELOE CHISLO, PRICHEM KAZHDOE SLAGAEMOE KRATNO~$p$, ZA
ISKLYUCHENIEM PERVOGO CHLENA. v SAMOM DELE,
ESLI~$1<k<p$, TO~$\perm{p}{k}$ DELITSYA NA~$p$ (SR.~S~UPR.~1.2.6-10).
sLEDOVATELXNO,
$$
{1\over p}\perm{p}{k}q^{k-1}p^{(k-1)e}
$$
DELITSYA NA~$p^{(k-1)e}$. pOSLEDNIJ CHLEN~$q^{p-1}p^{(p-1)e-1}$ DELITSYA
NA~$p$, TAK KAK~$(p-1)e>1$ PRI~$p^e>2$. tAKIM OBRAZOM, $x^p=1+q'p^{e+1}$,
GDE~$q'$---CELOE CHISLO, KOTOROE NE DELITSYA NA~$p$. tEM SAMYM
DOKAZATELXSTVO ZAVERSHENO. (\emph{zAMECHANIE:} OBOBSHCHENIE |TOGO
REZULXTATA SODERZHITSYA V UPR.~3.2.2-11~(a).)
\proofend

\proclaim lEMMA~Q. {pUSTX RAZLOZHENIE~$m$ NA PROSTYE MNOZHITELI IMEET VID
$$
m=p_1^{e_1}\ldots p_t^{e_t}.
\eqno(3)
$$
\hiddenpar
dLINA~$\lambda$ PERIODA LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI,
OPREDELYAEMOJ~$(X_0, a, c, m)$, RAVNA NAIMENXSHEMU OBSHCHEMU KRATNOMU
DLIN~$\lambda_j$ PERIODOV LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ
$$
(X_0 \bmod p_j^{e_j}, a p_j^{e_j}, c p_j^{e_j}, p_j^{e_j}),
\rem{$1\le j \le t$.}
$$
}

\proof iNDUKCIEJ PO~$t$ DOSTATOCHNO DOKAZATX, CHTO, ESLI~$r$ I~$s$---VZAIMNO
PROSTYE CHISLA, DLINA~$\lambda$ PERIODA LINEJNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI, OPREDELYAEMOJ~$(X_0, a, c, rs)$, RAVNA NAIMENXSHEMU
OBSHCHEMU KRATNOMU DLIN~$\lambda_1$ I~$\lambda_2$ PERIODOV
POSLEDOVATELXNOSTEJ~$(X_0 \bmod r, a \bmod r, c \bmod r, r)$
I~$(X_0 \bmod s, a \bmod s, c \bmod s, s)$.

v PREDYDUSHCHEM RAZDELE (SM.~FORMULU~(5)) MY VIDELI, CHTO ESLI OBOZNACHITX
|LEMENTY |TIH TREH POSLEDOVATELXNOSTEJ SOOTVETSTVENNO~$X_n$, $Y_n$, $Z_n$,
TO VYPOLNYAYUTSYA SLEDUYUSHCHIE SOOTNOSHENIYA:
$$
Y_n=X_n \bmod r \hbox{ I } Z_n=X_n \bmod s
\rem{DLYA VSEH~$n\ge 0$.}
$$
%% 31
pO|TOMU IZ SVOJSTVA~D P.~1.2.4 NAHODIM, CHTO
$$
X_n=X_k  \rem{TOGDA I TOLXKO TOGDA, KOGDA~$Y_n=Y_k$ I~$Z_n=Z_k$.}
\eqno (4)
$$
pUSTX~$\lambda'$---NAIMENXSHEE OBSHCHEE KRATNOE DLIN~$\lambda_1$ I~$\lambda_2$;
DOKAZHEM, CHTO~$\lambda'=\lambda$. tAK KAK~$X_n=X_{n+\lambda}$ DLYA VSEH
DOSTATOCHNO BOLXSHIH~$n$, IMEEM~$Y_n=Y_{n+\lambda}$ (SLEDOVATELXNO,
$\lambda$ KRATNO~$\lambda_1$) I~$Z_n=Z_{n+\lambda}$ (SLEDOVATELXNO,
$\lambda$ KRATNO~$\lambda_2$), I PO|TOMU~$\lambda\ge\lambda'$. s DRUGOJ
STORONY, MY ZNAEM, CHTO~$Y_n=Y_{n+\lambda'}$ I~$Z_n=Z_{n+\lambda'}$ DLYA
VSEH DOSTATOCHNO BOLXSHIH~$n$. pO|TOMU NA OSNOVANII~(4)
IMEEM~$X_n=X_{n+\lambda'}$, IZ CHEGO POLUCHAEM~$\lambda\le\lambda'$, TAK
CHTO~$\lambda=\lambda'$.
\proofend

tEPERX MY GOTOVY DOKAZATX TEOREMU~A. iMEYA V VIDU LEMMU~Q, DOSTATOCHNO
DOKAZATX TEOREMU DLYA SLUCHAYA, KOGDA $m$~ESTX STEPENX PROSTOGO CHISLA. v
SAMOM DELE, NERAVENSTVO
$$
p_1^{e_1} \ldots p_t^{e_t}=\lambda=\NOK(\lambda_1,~\ldots, \lambda_t)
\le \lambda_1 \ldots \lambda_t \le p_1^{e_1}\ldots p_t^{e_t}
$$
MOZHET BYTX SPRAVEDLIVO V TOM I TOLXKO TOM SLUCHAE,
ESLI~$\lambda_j=p_j^{e_j}$ DLYA~$1\le j \le t$.

pO|TOMU PREDPOLOZHIM, CHTO~$m=p^e$, GDE~$p$---PROSTOE, A~$e$---POLOZHITELXNOE
CELOE CHISLO. oCHEVIDNO, CHTO PRI~$a=1$ TEOREMA SPRAVEDLIVA, PO|TOMU MOZHNO
SCHITATX~$a>1$. dLINA PERIODA RAVNA~$m$ TOGDA I TOLXKO TOGDA, KOGDA KAZHDOE
CELOE CHISLO~$x$, TAKOE, CHTO~$0 \le x < m$, VSTRECHAETSYA V
POSLEDOVATELXNOSTI NA PROTYAZHENII PERIODA (POSKOLXKU NI ODNO IZ ZNACHENIJ
NE MOZHET VSTRETITXSYA ZA PERIOD BOLEE ODNOGO RAZA). tAKIM OBRAZOM, PERIOD
IMEET DLINU~$m$ V TOM I TOLXKO TOM SLUCHAE, ESLI DLINA PERIODA
POSLEDOVATELXNOSTI S~$X_0=0$ RAVNA~$m$, CHTO
OPRAVDYVAET PREDPOLOZHENIE~$X_0=0$. iZ. FORMULY~3.2.1-(6) IMEEM
$$
X_n=\left({a^n-1 \over a-1}\right) c \bmod m.
\eqno (5)
$$
eSLI CHISLA~$c$ I~$m$ NE YAVLYAYUTSYA VZAIMNO PROSTYMI, $X_n$ NIKOGDA NE MOZHET
BYTX RAVNO~$1$. pO|TOMU USLOVIE~(i) OKAZYVAETSYA NEOBHODIMYM. pERIOD
IMEET DLINU~$m$ TOGDA I TOLXKO TOGDA, KOGDA NAIMENXSHEE POLOZHITELXNOE
ZNACHENIE~$n$, DLYA KOTOROGO~$X_n=X_0=0$, TAKOVO, CHTO~$n=m$. tEPERX V
SILU~(5) I USLOVIYA~(i) NASHA TEOREMA SVODITSYA K DOKAZATELXSTVU SLEDUYUSHCHEGO
UTVERZHDENIYA.

\proclaim lEMMA~R. pREDPOLOZHIM, CHTO~$1<a<p^e$, GDE~$p$---PROSTOE CHISLO.
eSLI~$\lambda$---NAIMENXSHEE  POLOZHITELXNOE  CELOE, DLYA
KOTOROGO~$(a^\lambda-1)/(a-1)\equiv 0 \pmod{p^e}$, TO
$$
\lambda=p^e\hbox{TOGDA I TOLXKO TOGDA, KOGDA }
\cases{
a\equiv 1 \pmod{p} & PRI $p>2$,\cr
a\equiv 1 \pmod{4} & PRI $p=2$.
}
$$
%% 32
\proof pREDPOLOZHIM, CHTO~$\lambda=p^e$. eSLI~$a\not\equiv 1 \pmod{p}$,
TO~$(a^n-1)/(a-1)\equiv 0 \pmod{p^e}$ V TOM I TOLXKO TOM SLUCHAE,
KOGDA~$a^n-1\equiv 0 \pmod{p^e}$. uSLOVIE~$a^{p^e}-1\equiv 0 \pmod{p^e}$
TOGDA TREBUET, CHTOBY VYPOLNYALOSX SOOTNOSHENIE~$a^{p^e}\equiv 1 \pmod{p}$.
nO IZ TEOREMY~1.2.4F SLEDUET, CHTO~$a^{p^e}\equiv a \pmod{p}$; TAKIM
OBRAZOM POLUCHAEM~$a\not\equiv 1 \pmod{p}$, CHTO PRIVODIT K
PROTIVORECHIYU. eSLI ZHE~$p=2$ I~$a\equiv 3 \pmod{4}$, TO IZ UPR.~8
IMEEM~$(a^{2^{e-1}}-1)/(a-1)\equiv 0 \pmod{2^e}$. eTI SOOBRAZHENIYA
OBOSNOVYVAYUT NEOBHODIMOSTX RAVENSTVA~$a=1+qp^f$, GDE~$p^f>2$, A~$q$ NE
KRATNO~$p$ DLYA LYUBYH~$\lambda=p^e$.

oSTAETSYA POKAZATX, CHTO |TO USLOVIE \emph{DOSTATOCHNO} DLYA VYPOLNENIYA
SOOTNOSHENIYA~$\lambda=p^e$. pOVTORNO ISPOLXZUYA LEMMU~P, NAHODIM, CHTO
$$
a^{p^g}\equiv 1 \pmod{p^{f+g}}, \quad
a^{p^g}\not\equiv 1 \pmod{p^{f+g+1}},
$$
I PO|TOMU
$$
\eqalign{
(a^{p^g}-1)/(a-1) &\equiv 0 \pmod{p^g}, \cr
(a^{p^g}-1)/(a-1) &\not\equiv 0 \pmod{p^{g+1}}.\cr
}
\eqno(6)
$$

v CHASTNOSTI, $(a^{p^e}-1)/(a-1)\equiv 0 \pmod{p^e}$. tAKIM OBRAZOM, V
KONGRU|NTNOJ POSLEDOVATELXNOSTI~$(0, a, 1, p^e)$
IMEEM~$X_n=(a^n-1)/(a-1) \bmod p^e$; PO|TOMU DLINA EE PERIODA RAVNA~$\lambda$,
T.~E.~$X_n=0$ TOGDA I TOLXKO TOGDA, KOGDA~$n$ KRATNO~$\lambda$. sLEDOVATELXNO,
$p^e$ KRATNO~$\lambda$. eTO VOZMOZHNO TOLXKO, ESLI~$\lambda=p^g$ DLYA
NEKOTOROGO~$g$. iZ SOOTNOSHENIYA~(6) POLUCHAEM~$\lambda=p^e$, CHTO ZAVERSHAET
DOKAZATELXSTVO.
\proofend

tEPERX ZAKONCHENO I DOKAZATELXSTVO TEOREMY~A.
\proofend

v ZAKLYUCHENIE |TOGO RAZDELA RASSMOTRIM SPECIALXNYJ SLUCHAJ CHISTO
MULXTIPLIKATIVNYH DATCHIKOV, DLYA KOTORYH~$c=0$. hOTYA PRI |TOM VYRABOTKA
SLUCHAJNYH CHISEL PROISHODIT NESKOLXKO BYSTREE, TEOREMA~A POKAZYVAET, CHTO
DOBITXSYA MAKSIMALXNOJ DLINY PERIODA NELXZYA. dEJSTVITELXNO, |TO VPOLNE
OCHEVIDNO, TAK KAK CHLENY POSLEDOVATELXNOSTI UDOVLETVORYAYUT SOOTNOSHENIYU
$$
X_{n+1}=aX_n\bmod m,
\eqno(7)
$$
I ZNACHENIE~$X_n=0$ MOZHET V NEJ VSTRETITXSYA, TOLXKO ESLI
POSLEDOVATELXNOSTX VYROZHDAETSYA V NULX. vOOBSHCHE, ESLI~$d$---LYUBOJ
DELITELX~$m$ I ESLI~$X_n$ KRATNO~$d$, VSE POSLEDUYUSHCHIE ZNACHENIYA~$X_{n+1}$,
$X_{n+2}$,~\dots{} TOZHE KRATNY~$d$. pO|TOMU PRI~$c=0$ ZHELATELXNO, CHTOBY
$X_n$~BYLI VZAIMNO PROSTY S~$m$ DLYA VSEH~$n$, A |TO OGRANICHIVAET DLINU PERIODA.

mOZHNO DOBITXSYA PRIEMLEMO BOLXSHOGO PERIODA, DAZHE ESLI MY NASTAIVAEM,
CHTOBY~$c=0$. pOPYTAEMSYA TEPERX NAJTI TAKIE USLOVIYA,
%% 33
OPREDELYAYUSHCHIE MNOZHITELX, CHTOBY I V |TOM CHASTNOM SLUCHAE
DLINA PERIODA BYLA MAKSIMALXNA.

vSLEDSTVIE LEMMY~Q PERIOD POSLEDOVATELXNOSTI POLNOSTXYU OPREDELYAETSYA
PERIODAMI POSLEDOVATELXNOSTEJ S~$m=p^e$, TAK CHTO RASSMOTRIM IMENNO TAKUYU
SITUACIYU. mY IMEEM~$X_n=a^n X_0 \bmod p^e$, I YASNO, CHTO DLINA PERIODA
RAVNA~$1$, ESLI~$a$ KRATNO~$p$\note{1}%
{eSLI~$a$ KRATNO~$p$, TO, VOOBSHCHE GOVORYA, PERIOD NE
 PREVOSHODIT~$e$.---{\sl pRIM. RED.\/}
}. pO|TOMU VYBEREM~$a$ VZAIMNO PROSTYM
S~$p^e$. tOGDA PERIOD
RAVEN NAIMENXSHEMU CELOMU~$\lambda$, TAKOMU, CHTO~$X_0=a^\lambda X_0 \bmod p^e$.
eSLI NAIBOLXSHIJ OBSHCHIJ DELITELX~$X_0$ I~$p^e$ ESTX~$p^f$, |TO USLOVIE
|KVIVALENTNO SLEDUYUSHCHEMU:
$$
a^\lambda \equiv 1 \pmod{p^{e-f}}.
\eqno(8)
$$
pO TEOREME eJLERA (UPR.~1.2.4-28)
$$
a^{\varphi(p^{e-f})} \equiv 1 \pmod{p^{e-f}};
$$
SLEDOVATELXNO, $\lambda$~ESTX DELITELX:
$$
\varphi(p^{e-f})=p^{e-f-1}(p-1).
$$

dLYA VZAIMNO PROSTYH~$a$ I~$m$ NAIMENXSHEE CELOE~$\lambda$, DLYA
KOTOROGO~$a^\lambda \equiv 1 \pmod{m}$, OBYCHNO NAZYVAYUT \dfn{PORYADKOM PO
MODULYU~$m$}. vELICHINA~$a$, KOTOROJ SOOTVETSTVUET \emph{MAKSIMALXNO}
VOZMOZHNYJ PORYADOK PO MODULYU~$m$, NAZYVAETSYA \dfn{PERVOOBRAZNYM |LEMENTOM}
PO MODULYU~$m$\note{2}%
{nE SLEDUET PUTATX PERVOOBRAZNYJ |LEMENT S PERVOOBRAZNYM KORNEM.
 pERVOOBRAZNYE KORNI SUSHCHESTVUYUT NE DLYA VSEH~$m$.---{\sl pRIM. RED.\/}
}.

oBOZNACHIM CHEREZ~$\lambda(m)$ PORYADOK PERVOOBRAZNOGO |LEMENTA, T.~E.\
MAKSIMALXNO VOZMOZHNYJ PORYADOK PO MODULYU~$m$. pREDYDUSHCHIE ZAMECHANIYA
POKAZYVAYUT, CHTO~$\lambda(p^e)$ ESTX DELITELX~$p^{e-1}(p-1)$;
NE SOSTAVLYAET TRUDA (SM.~NIZHE UPR.~11--16) PRIVESTI
TOCHNYE ZNACHENIYA~$\lambda(m)$ V SLEDUYUSHCHIH SLUCHAYAH:
$$
\eqalignrem{
& \lambda(2)=1, \quad \lambda(4)=2, \quad \lambda(2^e)=2^{e-2}, & ESLI $e\ge3$,\cr
& \lambda(p^e)=p^{e-1}(p-1), & ESLI $p>2$, \cr
& \lambda(p_1^{e_1}\ldots p_t^{e_t})=\NOK(\lambda(p_1^{e_1},\ldots, \lambda(p_t^{e_t}))).\cr
}
\eqno(9)
$$

nASHI ZAMECHANIYA MOZHNO SUMMIROVATX V SLEDUYUSHCHEJ TEOREME:

\proclaim tEOREMA~B. (r. kARMAJKL)
[R. D. Carmichael, {\sl Bull.\ Amer.\ Math.\ Soc.,\/} {\bf 16} (1910), 232--238].
mAKSIMALXNO VOZMOZHNYJ PRI~$c=0$ PERIOD RAVEN~$\lambda(m)$,
GDE~$\lambda(m)$ OPREDELYAETSYA VYRAZHENIYAMI~(9). tAKOJ PERIOD REALIZUETSYA, ESLI
\medskip
\item{i)}~$X_0$ I~$m$---VZAIMNO PROSTYE CHISLA;
\item{ii)}~$a$---PERVOOBRAZNYJ |LEMENT PO MODULYU~$m$. \endmark

%% 34

zAMETXTE, CHTO ESLI~$m$---PROSTOE CHISLO, MOZHNO POLUCHITX DLINU PERIODA~$m-1$,
CHTO VSEGO LISHX NA EDINICU MENXSHE MAKSIMALXNOGO ZNACHENIYA.

vOPROS TEPERX ZAKLYUCHAETSYA V TOM, KAK NAHODITX PERVOOBRAZNYE |LEMENTY PO
MODULYU~$m$. iZ UPRAZHNENIJ V KONCE PARAGRAFA VYTEKAET

\proclaim tEOREMA~C. chISLO~$a$ ESTX PERVOOBRAZNYJ |LEMENT PO MODULYU~$p^e$
TOGDA I TOLXKO TOGDA, KOGDA
\medskip
\item{i)}~$p^e=2$, $a$---NECHETNOE; ILI~$p^e=4$, $a \bmod 4=3$; ILI~$p^e=8$,
 $a \bmod 8=3, 5, 7$; ILI~$p=2$, $e \ge 4$, $a \bmod 8=3$ ILI~$5$;
 %
\hiddenpar\noindent ILI
\item{ii)}~$p$---NECHETNOE, $e=1$, $a \not\equiv 0 \pmod{p}$
I~$a^{(p-1)q} \not\equiv 1 \pmod{p}$ DLYA LYUBOGO PROSTOGO DELITELYA~$q$ CHISLA~$p-1$;
 %
\hiddenpar\noindent ILI
\item{iii)}~$p$---NECHETNOE, $e>1$, $a$~UDOVLETVORYAET~(ii)
I~$a^{p-1} \not\equiv 1 \pmod{p^2}$\note{1}%
{pODRAZUMEVAETSYA, CHTO~$p$--- PROSTOE; ESLI MODULX IMEET VID~$2$, $2^2$,
$p^e$, GDE~$p$---NECHETNOE, PERVOOBRAZNYE |LEMENTY BUDUT I PERVOOBRAZNYMI
KORNYAMI.---{\sl  pRIM. RED.\/}
}. \endmark

uSLOVIYA~(ii) I~(iii) |TOJ TEOREMY LEGKO PROVERYAYUTSYA NA VYCHISLITELXNOJ
MASHINE DLYA BOLXSHIH ZNACHENIJ~$p$, ESLI DLYA VYCHISLENIYA STEPENEJ ISPOLXZOVATX
|FFEKTIVNYE METODY, OBSUZHDAEMYE V P.~4.6.3. nAKONEC, ESLI NAM DANY
VELICHINY~$a_j$, YAVLYAYUSHCHIESYA PERVOOBRAZNYMI |LEMENTAMI PO MODULYU~$p_j^{e_j}$,
MOZHNO NAJTI EDINSTVENNOE ZNACHENIE~$a$, TAKOE,
CHTO~$a \equiv a_j \pmod{p_j^{e_j}}$, $1\le j \le t$, PRIMENYAYA "KITAJSKUYU TEOREMU
OB OSTATKAH", KOTORAYA OBSUZHDAETSYA V~P.4.3.2. sLEDOVATELXNO, $a$~BUDET
PERVOOBRAZNYM |LEMENTOM PO MODULYU~$p_1^{e_1}\ldots p_t^{e_t}$. eTO DAET
NAM DOVOLXNO |FFEKTIVNYJ SPOSOB
VYCHISLENIYA MNOZHITELEJ, UDOVLETVORYAYUSHCHIH USLOVIYU TEOREMY~v,
DLYA LYUBOGO ZNACHENIYA~$m$. oDNAKO V OBSHCHEM SLUCHAE VYCHISLENIYA OKAZYVAYUTSYA
NESKOLXKO DLINNYMI.

dLYA VAZHNOGO SLUCHAYA~$m=2^e$ PRI~$e\ge 4$ PRIVEDENNYE VYSHE USLOVIYA SVODYATSYA
K EDINSTVENNOMU PROSTOMU TREBOVANIYU,
CHTOBY~$a \equiv 3\hbox{ ILI } 5 \pmod{8}$.
v |TOM SLUCHAE CHETVERTAYA CHASTX VSEH VOZMOZHNYH MNOZHITELEJ DAET
MAKSIMALXNYJ PERIOD.

vTOROJ NAIBOLEE RASPROSTRANENNYJ SLUCHAJ, |TO~$m=10^e$. pOLXZUYASX LEMMAMI~r
I~Q, NETRUDNO POLUCHITX NEOBHODIMYE I
DOSTATOCHNYE USLOVIYA DOSTIZHENIYA MAKSIMALXNOGO PERIODA DLYA DESYATICHNOJ
VYCHISLITELXNOJ MASHINY.

\proclaim tEOREMA~D. eSLI~$m=10^e$, $e\ge 5$, $c=0$ I~$X_0$ NE KRATNO~$2$
ILI~$5$, PERIOD LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI
RAVEN~$5\times10^{e-2}$ V TOM I TOLXKO TOM SLUCHAE, KOGDA~$a \bmod 200$
PRINIMAET ODNO
%% 35
IZ SLEDUYUSHCHIH $32$~ZNACHENIJ:
$$
\eqalign{
& 3,11,13,19,21,27, 29, 37, 53,59, 61, 67, 69,77, 83,91,109,117,\cr
& 123,131,133,139,141,147,163,171,173,179,181,187,189.197.~\endmark\cr
}
\eqno(10)
$$

\excercises
\ex[10] kAKOVA DLINA PERIODA LINEJNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI S~$X_0=5772156648$, $a=3141592621$, $c=2718281829$, $m=10000000000$?

\ex[10] gARANTIRUET LI VYPOLNENIE SLEDUYUSHCHIH DVUH USLOVIJ:
(i)~$c$~NECHETNOE, (ii)~$a\bmod 4=1$, MAKSIMALXNUYU DLINU PERIODA,
KOGDA~$m=2^e$, T.~E.\ STEPENX DVOJKI?

\ex[13] pREDPOLOZHIM, CHTO~$m=10^e$, GDE~$e\ge 3$, A~$c$  NE KRATNO NI~$2$,
NI~$5$. pOKAZHITE, CHTO LINEJNAYA KONGRU|NTNAYA POSLEDOVATELXNOSTX BUDET IMETX
MAKSIMALXNO BOLXSHOJ PERIOD TOGDA I TOLXKO TOGDA, KOGDA~$a\bmod 20=1$.

\ex[20] chEMU RAVNO ZNACHENIE~$X_{2^{e-1}}$, ESLI~$a$ I~$c$ UDOVLETVORYAYUT
USLOVIYAM TEOREMY~A, $m=2^e$, $X_0=0$?

\rex[20] nAJDITE VSE MNOZHITELI~$a$, UDOVLETVORYAYUSHCHIE USLOVIYAM TEOREMY~A,
KOGDA~$m=2^{35}+1$ (PROSTYE MNOZHITELI CHISLA~$m$ MOZHNO NAJTI IZ TABL.~3.2.1.1-1).

\ex[20] nAJDITE VSE MNOZHITELI~$a$, UDOVLETVORYAYUSHCHIE USLOVIYAM TEOREMY~A,
PRI~$m=10^6-1$ (SM.~TABL.~3.2.1.1-1).

\rex[m24] pERIOD KONGRU|NTNOJ POSLEDOVATELXNOSTI NE OBYAZATELXNO NACHINATX
S~$X_0$. oDNAKO MY VSEGDA MOZHEM NAJTI INDEKSY~$\mu\ge0$, $\lambda>0$,
TAKIE, CHTO~$X_{n+\lambda}=X_n$ DLYA LYUBYH~$n\ge\mu$, PRICHEM~$\mu$
I~$\lambda$---NAIMENXSHIE ZNACHENIYA, OBLADAYUSHCHIE |TIM SVOJSTVOM.
(sR.~S~UPR.~3.1-6 I~3.2.1-1.) pUSTX~$\mu_j$, $\lambda_j$ SOOTVETSTVUYUT
POSLEDOVATELXNOSTI~$(X_0 \bmod p_j^{e_j}, a \bmod p_j^{e_j},
c \bmod p_j^{e_j},  p_j^{e_j})$ I~$\mu$, $\lambda$
SOOTVETSTVUYUT POSLEDOVATELXNOSTI~$(X_0, a, c, p_1^{e_1}\ldots p_t^{e_t})$;
LEMMA~Q USTANAVLIVAET, CHTO $\lambda$~ESTX NAIMENXSHEE OBSHCHEE KRATNOE
DLYA~$\lambda_1$,~\dots, $\lambda_t$. chEMU RAVNO ZNACHENIE~$\mu$, VYRAZHENNOE
CHEREZ~$\mu_1$,~\dots, $\mu_t$? kAKOE MAKSIMALXNOE ZNACHENIE~$\mu$ MOZHNO
POLUCHITX, IZMENYAYA~$X_0$, $a$ I~$c$ PRI
FIKSIROVANNOM~$m=p_1^{e_1}\ldots p_t^{e_t}$?

\ex[m20] pOKAZHITE, CHTO ESLI~$a \bmod 4=3$, $e>1$,
TO~$(a^{2^{e-1}}-1)/(a-1) \equiv 0 \pmod{2^e}$. (iSPOLXZUJTE LEMMU~P.)

\rex[m22] (u.~tOMSON.) dLYA~$c=0$ I~$m=2^e\ge 8$ TEOREMY~B I~C UTVERZHDAYUT,
CHTO DLINA PERIODA RAVNA~$2^{e-2}$ V TOM I TOLXKO TOM SLUCHAE, KOGDA
MNOZHITELX~$a$ UDOVLETVORYAET SOOTNOSHENIYAM~$a\bmod 8=3$ ILI~$a \bmod 8=5$.
pOKAZHITE, CHTO KAZHDAYA TAKAYA POSLEDOVATELXNOSTX V SUSHCHNOSTI YAVLYAETSYA
LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTXYU S~$m=2^{e-2}$, IMEYUSHCHEJ
\emph{POLNYJ} PERIOD V SLEDUYUSHCHEM SMYSLE:
\medskip
\item{a)}~ESLI~$X_{n+1}=(4c+1) X_n \bmod 2^e$ I~$X_n=4Y_n+1$, TO
$$
Y_{n+1}=((4c+1) Y_n+c) \bmod 2^{e-2};
$$
\item{b)}~ESLI~$X_{n+1}=(4c-1)X_n \bmod 2^e$ I~$X_n=((-1)^n (4Y_n+1))
\bmod 2^e$,  TO
$$
Y_{n+1}=((1-4c)Y_n-c)\bmod 2^{e-2}.
$$
[\emph{zAMECHANIE.} v |TIH FORMULAH~$c$---NECHETNOE CELOE. v LITERATURE MOZHNO
VSTRETITX UTVERZHDENIYA O TOM, CHTO POSLEDOVATELXNOSTI S~$c=0$, UDOVLETVORYAYUSHCHIE
%%  36
USLOVIYAM TEOREMY~B, NESKOLXKO BOLEE SLUCHAJNY, CHEM TE, KOTORYE
UDOVLETVORYAYUT USLOVIYAM TEOREMY a, NESMOTRYA NA TO, CHTO V SLUCHAE TEOREMY~B
PERIOD V CHETYRE RAZA MENXSHE. eTO UPRAZHNENIE OPROVERGAET PODOBNYE UTVERZHDENIYA.]

\ex[m21] dLYA KAKIH ZNACHENIJ~$m$ SPRAVEDLIVO RAVENSTVO~$\lambda(m)=\varphi(m)$?

\ex[m28] pUSTX~$x$---NECHETNOE CELOE CHISLO, BOLXSHEE~$1$.
  %
\hiddenpar
(a)~pOKAZHITE, CHTO SUSHCHESTVUET EDINSTVENNOE CELOE~$f>1$, TAKOE, CHTO
$x\equiv 2^f \pm 1 \pmod{2^{f+1}}$.
  %
\hiddenpar
(b)~pRI USLOVII, CHTO~$1<x<2^e-1$, A~$f$---SOOTVETSTVUYUSHCHEE CELOE CHISLO
IZ~P.(a), POKAZHITE, CHTO PORYADOK~$x \pmod{2^e}$ RAVEN~$2^{e-f}$.
  %
\hiddenpar
(c)~v CHASTNOSTI, |TO DOKAZYVAET TEOREMU~C(i).

\ex[m26] pUSTX~$p$---NECHETNOE PROSTOE CHISLO dOKAZHITE CHTO ESLI~$e>1$,
TO~$a$---PERVOOBRAZNYJ |LEMENT PO MODULYU~$p^e$ V TOM I TOLXKO TOM SLUCHAE,
KOGDA~$a$---PERVOOBRAZNYJ  |LEMENT PO MODULYU~$p$ I~$a^{p-1}\equiv 1 \pmod{p^2}$.
(pREDPOLOZHITE, CHTO~$\lambda(p^e)=p^{e-1}(p-1)$. eTO DOKAZYVAETSYA NIZHE V
UPR.~14 I~16.

\ex[m22] pUSTX~$p$---PROSTOE CHISLO I~$a$ NE YAVLYAETSYA PERVOOBRAZNYM
|LEMENTOM PO MODULYU~$p$. pOKAZHITE, CHTO LIBO~$a$ KRATNO~$p$
LIBO~$a^{(p-1)/q}\equiv 1 \pmod{p}$ DLYA NEKOTOROGO PROSTOGO CHISLA~$q$,
DELYASHCHEGO~$p-1$.

\ex[m18] pUSTX~$e>1$, $p$---NECHETNOE PROSTOE I~$a$---PERVOOBRAZNYJ |LEMENT PO
MODULYU~$p$, DOKAZHITE, CHTO TOGDA LIBO~$a$, LIBO~$a+p$---PERVOOBRAZNYJ
|LEMENT PO MODULYU~$p^e$. [\emph{uKAZANIE:} SM.~UPR.~12.]

\ex[m29] (a)~pUSTX~$a_1$, $a_2$ VZAIMNO PROSTYE S~$m$. pUSTX DLYA |TIH
CHISEL  PORYADKI PO MODULYU~$m$ RAVNY~$\lambda_1$, $\lambda_2$ SOOTVETSTVENNO.
dOKAZHITE CHTO ESLI~$\lambda$---NAIMENXSHEE OBSHCHEE KRATNOE~$\lambda_1$
I~$\lambda_2$, TO~$a_1^{\kappa_1}a_2^{\kappa_2}$ IMEET PORYADOK~$\lambda$
PO MODULYU~$m$ DLYA VYBRANNYH NADLEZHASHCHIM OBRAZOM~$\kappa_1$, $\kappa_2$.
[\emph{uKAZANIE}. rASSMOTRITE SNACHALA SLUCHAJ, KOGDA~$\lambda_1$
I~$\lambda_2$---VZAIMNO PROSTYE CHISLA.]
(b)~pUSTX~$\lambda(m)$---MAKSIMALXNYJ PO VSEM |LEMENTAM PORYADOK PO
MODULYU~$m$. dOKAZHITE, CHTO~$\lambda(m)$ KRATNO PORYADKU PO MODULYU~$m$ DLYA
LYUBOGO |LEMENTA. dRUGIMI SLOVAMI, DOKAZHITE,
CHTO~$a^{\lambda(m)} \equiv 1 \pmod{m}$ DLYA LYUBOGO~$a$, VZAIMNO PROSTOGO S~$m$.

\rex[m24] pUSTX~$p$---PROSTOE CHISLO.
(a)~pUSTX~$f(x)=x^n+c_1 x^{n-1}+\cdots+c_n$, GDE VSE~$c$---CELYE CHISLA,
I ZADANO TAKOE CELOE~$a$, CHTO~$f(a) \equiv 0 \pmod{p}$.
pOKAZHITE, CHTO SUSHCHESTVUET POLINOM~$q(x)=x^n+q_1x^{n-2}+\cdots+q_{n-1}$ S CELYMI
KO|FFICIENTAMI, TAKOJ, CHTO~$f(x)\equiv (x-a)q(x) \pmod{p}$ DLYA VSEH CELYH~$x$.
(b)~pUSTX~$f(x)$---POLINOM, TaKOJ ZHe, KaK I V~(a). poKAZHITE, CHTO~$f(x)$
IMEET  SAMOE BOLXSHEE $n$~RAZLICHNYH "KORNEJ" PO MODULYU~$p$, T.E.\
SUSHCHESTVUET SAMOE BOLXSHEE $n$~CELYH CHISEL~$a$, TAKIH,
CHTO~$f(a)\equiv 0 \pmod{p}$, $0\le a < p$.
(c)~v UPR.~15(b) UTVERZHDAETSYA, CHTO POLINOM~$f(x)=x^{\lambda(p)}-1$ IMEET
$p-1$~RAZLICHNYH KORNEJ; SLEDOVATELXNO, SUSHCHESTVUET CELOE~$a$ S PORYADKOM~$p-1$.

\ex[m26] nE VSE ZNACHENIYA, PERECHISLENNYE V TEOREME~D MOZHNO POLUCHITX
METODOM, IZLOZHENNYM V TEKSTE. nAPRIMER, CHISLO~$11$ NE YAVLYAETSYA
PERVOOBRAZNYM |LEMENTOM PO MODULYU~$5^e$. kAK |TO MOZHET BYTX ESLI~$11$ (V
SOOTVETSTVII  S TEOREMOJ~D)---PERVOOBRAZNYJ |LEMENT PO MODULYU~$10^e$?
kAKIE IZ CHISEL, PERECHISLENNYH V TEOREME~D,---PERVOOBRAZNYE |LEMENTY KAK PO
MODULYU~$2^e$, TAK I~$5^e$?

\ex[m25] dOKAZHITE TEOREMU~D. (sR.\ S PREDYDUSHCHIM UPRAZHNENIEM.)

\ex[40] sOSTAVXTE TABLICU NEKOTORYH HOROSHIH MNOZHITELEJ~$a$ DLYA KAZHDOGO IZ
ZNACHENIJ~$m$, PERECHISLENNYH V TABL.~3.2.1.1-1, V PREDPOLOZHENII~$c=0$.

\ex[m24] kAKOVA DLINA PERIODA LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI,
DLYA KOTOROJ (i)~$X_0=0$; (ii)~$a$---PERVOOBRAZNYJ |LEMENT PO
MODULYU~$p_j^{e_j}$, $1\le i \le t$; DLYA VSEH STEPENEJ PROSTYH CHISEL V
RAZLOZHENII~$m=p_1^{e_1}\ldots p_t^{e_t}$ NA PROSTYE MNOZHITELI; (iii)~$c$
I~$m$ VZAIMNO PROSTY?

\subsubsubchap{mOSHCHNOSTX\note{1}%
{v ORIGINALE "potency",--- {\sl pRIM. PEREV.\/}}}%3.2.1.3
 v PREDYDUSHCHEM RAZDELE MY POKAZALI, CHTO MAKSIMALXNYJ PERIOD MOZHNO POLUCHITX
PRI~$b=a-1$, KRATNOM
%% 37
VSEM PROSTYM DELITELYAM CHISLA~$m$ ($b$ TAKZHE DOLZHNO BYTX KRATNO~$4$, ESLI
$m$~DELITSYA NA~$4$). eSLI~$z$---OSNOVANIE, KOTOROE ISPOLXZUETSYA V MASHINE
(TAK, $z=2$---DLYA DVOICHNOJ MASHINY I~$z=10$---DLYA DESYATICHNOJ), A~$m$---RAZMER
SLOVA~$z^e$ MASHINY, TO MNOZHITELX
$$
a=z^k+1, \rem{$2\le k < e$,}
\eqno(1)
$$
UDOVLETVORYAET |TIM USLOVIYAM. iZ TEOREMY~3.2.1.2.A TAKZHE SLEDUET, CHTO
MOZHNO PRINYATX~$c=1$. rEKURRENTNOE SOOTNOSHENIE TEPERX IMEET VID
$$
X_{n+1}=((z^k+1)X_n+1) \bmod z^e.
\eqno(2)
$$

pRI VYCHISLENIYAH MOZHNO IZBEZHATX UMNOZHENIYA; DOSTATOCHNO PROSTOGO SLOZHENIYA I SDVIGA.

nAPRIMER, PREDPOLOZHIM, CHTO~$a=B^2+1$, GDE~$B$---RAZMER BAJTA \MIX. vMESTO
KOMAND, PRIVEDENNYH V~P.3.2.1.1, MOZHNO NAPISATX TAKUYU PROGRAMMU:
$$
\vcenter{
\mixcode
LDA  & X
SLA  & 2
ADD  & X
INCA & 1
\endmixcode
}
\eqno(3)
$$
vREMYA EE VYPOLNENIYA UMENXSHAETSYA S~$16u$ DO~$7u$.

vVIDU SKAZANNOGO MNOZHITELI VIDA~(1) SHIROKO OBSUZHDALISX V LITERATURE I
REKOMENDOVALISX MNOGIMI AVTORAMI. oDNAKO POCHTI PYATILETNIE PROVEROCHNYE
|KSPERIMENTY POKAZYVAYUT, CHTO \emph{SLEDUET IZBEGATX MNOZHITELEJ, IMEYUSHCHIH
TAKOJ PROSTOJ VID, KAK~(1)}. pRICHIN ZDESX NESKOLXKO. pREZHDE VSEGO VREMYA
SCHETA NE UMENXSHAETSYA NA SAMOM DELE VDVOE, KAK |TO PROISHODIT V
PRIMERE~(3). eSLI DOBAVITX K PROGRAMME KOMANDY~|JMP|, |STJ|, |STA|, |JNOV|,
SRAVNITELXNYE VREMENA SCHETA BUDUT RAVNY~$22u$ DLYA MULXTIPLIKATIVNOGO
METODA I~$13u$ DLYA METODA, ISPOLXZUYUSHCHEGO SLOZHENIE I SDVIG. kROME |TOGO,
NEOBHODIMO UCHESTX VREMYA RABOTY OSNOVNOJ PROGRAMMY, ISPOLXZUYUSHCHEJ SLUCHAJNYE
CHISLA. chISTAYA |KONOMIYA MASHINNOGO VREMENI V PROCENTAH POCHTI NICHTOZHNA. a NA
MNOGIH SOVREMENNYH MASHINAH UMNOZHENIE VYPOLNYAETSYA \emph{BYSTREE,} CHEM SDVIG
I SLOZHENIE!

sAMYJ VESKIJ ARGUMENT, PREPYATSTVUYUSHCHIJ ISPOLXZOVANIYU MNOZHITELYA
VIDA~$z^k+1$, ZAKLYUCHAETSYA V TOM, CHTO ON PRIVODIT K NEDOSTATOCHNO
SLUCHAJNYM CHISLAM. oDNA IZ PRICHIN |TOGO SVYAZANA S KONCEPCIEJ "MOSHCHNOSTI",
KOTORUYU MY SEJCHAS OBSUDIM.

\dfn{mOSHCHNOSTX} LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM
PERIODOM OPREDELYAETSYA KAK NAIMENXSHEE CELOE CHISLO~$s$, TAKOE, CHTO
$$
b^s \equiv 0 \pmod{m}.
\eqno(4)
$$
%% 38
(tAKOE CELOE~$s$ VSEGDA SUSHCHESTVUET, ESLI MNOZHITELX UDOVLETVORYAET USLOVIYAM
TEOREMY~3.2.1.2A, V CHASTNOSTI, ESLI $b$~KRATNO LYUBOMU PROSTOMU DELITELYU~$m$.)

mY MOZHEM ANALIZIROVATX SLUCHAJNOSTX POSLEDOVATELXNOSTI, PRINIMAYA~$X_0=0$,
TAK KAK NULX OBYAZATELXNO VSTRECHAETSYA NA PROTYAZHENII EE PERIODA. v TAKOM
SLUCHAE IMEEM~$X_n=((a^n-1)c/b)\bmod m$ I, RAZLOZHIV~$a^n-1=(b+1)^n-1$ PO
FORMULE BINOMA, NAHODIM
$$
X_n=c\left(n+\perm{n}{2}b+\cdots+\perm{n}{s}b^{s-1}\right) \bmod m.
\eqno(5)
$$
vSE CHLENY S~$b^s$, $b^{s+1}$ I T.~D.\ MOZHNO OPUSTITX, TAK KAK ONI KRATNY~$m$.

iSHODYA IZ URAVNENIYA~(5), RASSMOTRIM NEKOTORYE CHASTNYE SLUCHAI. eSLI~$a=1$,
MOSHCHNOSTX RAVNA~$1$ I, KAK MY UZHE VIDELI,
$X_n \equiv cn \pmod{m}$, TAK CHTO POSLEDOVATELXNOSTX YAVNO NE SLUCHAJNAYA.
eSLI MOSHCHNOSTX RAVNA~$2$, IMEEM~$X_n \equiv cn+cb\perm{n}{2}$, I
SNOVA POSLEDOVATELXNOSTX NELXZYA SCHITATX SLUCHAJNOJ. dEJSTVITELXNO,
$$
X_{n+1}-X_n \equiv c+cbn,
$$
TAK CHTO RAZNOSTX MEZHDU SOSEDNIMI SLUCHAJNYMI CHISLAMI VYRAZHAETSYA OCHENX
PROSTOJ ZAVISIMOSTXYU OT~$n$. eSLI
$$
d=cb \bmod m,
$$
TOCHKA~$(X_n, X_{n+1}, X_{n+2})$ VSEGDA LEZHIT NA ODNOJ IZ CHETYREH
PLOSKOSTEJ V TREHMERNOM PROSTRANSTVE:
$$
\eqalign{
x-2y+z &= d+m,\cr
x-2y+z &= d,\cr
x-2y+z &= d-m,\cr
x-2y+z &=d-2m.\cr
}
$$

eSLI MOSHCHNOSTX RAVNA~$3$, POSLEDOVATELXNOSTX VYGLYADIT NESKOLXKO BOLEE
SLUCHAJNOJ. nO~$X_n$, $X_{n+1}$, I~$X_{n+2}$ VSE ESHCHE SVYAZANY SILXNOJ
ZAVISIMOSTXYU. rAZNOSTI~$X_{n+1}-X_n$ OBRAZUYUT POSLEDOVATELXNOSTX S
MOSHCHNOSTXYU~$2$, I TESTY POKAZYVAYUT, CHTO POSLEDOVATELXNOSTI S MOSHCHNOSTXYU~$3$
VSE ESHCHE NEDOSTATOCHNO HOROSHI. sOOBSHCHALOSX, CHTO PRIEMLEMYE REZULXTATY MOGUT
BYTX POLUCHENY DLYA ZNACHENIYA MOSHCHNOSTI, RAVNOGO~$4$ I VYSHE, NO |TO
OSPARIVALOSX MNOGIMI AVTORAMI. vIDIMO, DLYA DOSTATOCHNO SLUCHAJNYH ZNACHENIJ
TREBUETSYA MOSHCHNOSTX, RAVNAYA PO MENXSHEJ MERE~$5$.

pREDPOLOZHIM, NAPRIMER, CHTO~$m=2$ I~$a=2^k+1$. tOGDA~$b=2^k$, TAK CHTO
PRI~$k \ge 18$ ZNACHENIE~$b^2=2^{2k}$ KRATNO~$m$: MOSHCHNOSTX
RAVNA~$2$. eSLI~$k=17$, $16$,~\dots, $12$, MOSHCHNOSTX RAVNA~$3$, A
PRI~$k=11$, $10$, $9$ DOSTIGAETSYA ZNACHENIE~$4$. pO|TOMU S TOCHKI
ZRENIYA MOSHCHNOSTI EDINSTVENNO PRIEMLEMY TAKIE MNOZHITELI, DLYA KOTORYH~$k\le 8$.
%% 39
eTO ZNACHIT, CHTO~$a\le 257$, A MY UVIDIM POZZHE, CHTO
\emph{NEBOLXSHIH} MNOZHITELEJ TAKZHE SLEDUET IZBEGATX. iTAK, VSE
MNOZHITELI VIDA~$2^k+1$ PRI~$m=2^{35}$ OKAZYVAYUTSYA NEPRIEMLEMYMI.

pRI BOLXSHIH RAZMERAH SLOVA MNOZHITELI VIDA~$2^k+1$ PRINYATX MOZHNO. bYL
ISPYTAN I OPISAN V LITERATURE DATCHIK S~$m=2^{47}$, $a=2^9+1$ I MOSHCHNOSTXYU,
RAVNOJ~$6$ ({\sl CACM,\/} {\bf 4} (1961), 350--352).
nESMOTRYA NA |TO, NADO BYTX OCHENX OSTOROZHNYM S MNOZHITELYAMI TIPA~(1), POTOMU
CHTO POCHTI VSE IZVESTNYE NENADEZHNYE DATCHIKI BYLI IMENNO TAKOGO TIPA. v
DEJSTVITELXNOSTI DAZHE PRIVEDENNYJ PRIMER NE UDOVLETVORYAET STATISTICHESKIM
TESTAM P.3.3.4.

pRI~$m$, RAVNOM~$w\pm1$, GDE~$w$---RAZMER SLOVA, $m$, VOOBSHCHE GOVORYA, NE
RAZLAGAETSYA NA PROIZVEDENIYA VYSOKIH STEPENEJ PROSTYH CHISEL, TAK CHTO
BOLXSHAYA MOSHCHNOSTX NEVOZMOZHNA (SM.\ PRIMER~6). pO|TOMU V |TOM SLUCHAE
\emph{NE} STOIT POLXZOVATXSYA METODOM MAKSIMALXNOGO PERIODA, A SLEDUET
PRIMENYATX METOD CHISTOGO UMNOZHENIYA S~$c=0$.

vSE ESHCHE OSTAETSYA MNOGO SVOBODY V VYBORE MNOZHITELYA. vOOBSHCHE GOVORYA, MY HOTIM
SOHRANITX MOSHCHNOSTX VYSOKOJ, MNOZHITELX DOSTATOCHNO BOLXSHIM I, KROME TOGO,
IZBEZHATX SLISHKOM PROSTOGO PO VIDU NABORA CIFR V MNOZHITELE. pREDPOLOZHIM,
CHTO~$m=2^{35}$, A OPERACIYA UMNOZHENIYA USKORYAETSYA PRI UMENXSHENII
KOLICHESTVA "EDINICHNYH" BITOV V MNOZHITELE. mOZHNO REKOMENDOVATX
(|KSPERIMENTALXNO) TAKOJ MNOZHITELX, KAK~$2^{23}+2^{14}+2^2+1$.
chLEN~$2^{23}$ DELAET MNOZHITELX DOVOLXNO BOLXSHIM. chLEN~$2^2$ OBESPECHIVAET
VYSOKUYU MOSHCHNOSTX. eDINICA NEOBHODIMA DLYA POLUCHENIYA MAKSIMALXNOGO PERIODA,
A $2^{14}$~DOBAVLYAETSYA, CHTOBY MNOZHITELX NE OKAZALSYA SLISHKOM PROSTYM DLYA
VYRABOTKI DOSTATOCHNO SLUCHAJNOJ POSLEDOVATELXNOSTI (SR.~UPR.~8). chLEN,
PODOBNYJ~$2^{34}$, BYL BY ZDESX NE STOLX HOROSH, KAK~$2^{23}$, TAK KAK V
PROIZVEDENII~$2^{34}X_n$ ISPOLXZUETSYA TOLXKO SAMYJ MLADSHIJ BIT CHISLA~$X_n$
(KOTORYJ NE SLISHKOM SLUCHAEN). eSLI SKOROSTX UMNOZHENIYA NE YAVLYAETSYA
LIMITIRUYUSHCHEJ, BOLEE "SLUCHAJNYJ" MNOZHITELX (NAPRIMER, $a=3141592621$),
VEROYATNO, OKAZHETSYA ZNACHITELXNO BOLEE UDOVLETVORITELXNYM.

v DEJSTVITELXNOSTI KONCEPCIYA MOSHCHNOSTI DAET TOLXKO ODIN IZ KRITERIEV VYBORA
MNOZHITELYA; K NEMU MOZHNO DOBAVITX NEMALO DRUGIH. nIZHE, V P.3.3.4,
OBSUZHDAETSYA "SPEKTRALXNYJ TEST" DLYA MNOZHITELEJ LINEJNYH KONGRU|NTNYH
POSLEDOVATELXNOSTEJ. eTO---VAZHNYJ KRITERIJ, VKLYUCHAYUSHCHIJ, KAK CHASTNYE SLUCHAI,
MOSHCHNOSTX I VELICHINU MNOZHITELYA. v P.3.3.4 MY, NAPRIMER, UVIDIM,
CHTO VYBOR~$2^{23}+2^{13}+2^2+1$ NAMNOGO HUZHE, CHEM~$2^{23}+2^{14}+2^2+1$.
lYUBOJ MNOZHITELX, KOTORYJ BUDET SHIROKO ISPOLXZOVATXSYA, SLEDUET PROVERITX
SPEKTRALXNYM TESTOM.

\excercises
\ex[M10] pOKAZHITE, CHTO NEZAVISIMO OT TOGO, KAKIM OKAZHETSYA RAZMER BAJTA~$B$
MASHINY \MIX, PROGRAMMA~(3) SLUZHIT DATCHIKOM SLUCHAJNYH CHISEL S
MAKSIMALXNYM PERIODOM.

%% 40
\ex[10] kAKOVA MOSHCHNOSTX DATCHIKA, REALIZOVANNOGO \MIX-PROGRAMMOJ~(3)?

\ex[11] kAKOVA MOSHCHNOSTX LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI
PRI~$m=2^{35}$, $a=3141592621$? chEMU RAVNA MOSHCHNOSTX, ESLI
MNOZHITELX~$a=2^{23}+2^{13}+2^2+1$?

\ex[20] pOKAZHITE, CHTO, ESLI~$m=2^e\ge 8$, MAKSIMALXNAYA MOSHCHNOSTX
DOSTIGAETSYA PRI~$a \bmod 8 = 5$.

\ex[M20] dANO, CHTO~$m=p_1^{e_1}\ldots p_t^{e_t}$
I~$a=1+kp_1^{f_1}\ldots p_t^{f_t}$, GDE~$a$ UDOVLETVORYAET USLOVIYAM
TEOREMY~3.2.1.2A, A~$k$ I~$m$ VZAIMNO PROSTY. pOKAZHITE, CHTO MOSHCHNOSTX
RAVNA~$\max(\ceil{e_1/f_1},~\ldots, \ceil{e_t/f_t})$.

\rex[20] kAKIE IZ ZNACHENIJ~$m=w\pm1$ V TABL.~3.2.1.1-1 MOGUT DATX
MOSHCHNOSTX, RAVNUYU PO MENXSHEJ MERE~$4$? (iSPOLXZUJTE REZULXTAT UPR.~5.)

\ex[m20] eSLI CHISLO~$a$ UDOVLETVORYAET USLOVIYAM TEOREMY~3.2.1.2A,
ONO VZAIMNO PROSTO S~$m$; SLEDOVATELXNO, SUSHCHESTVUET CHISLO~$a'$, TAKOE,
CHTO~$aa'\equiv 1 \pmod{m}$. pOKAZHITE, CHTO~$a'$ MOZHNO PROSTO VYRAZITX S
POMOSHCHXYU~$b$.

\rex[m26] dATCHIK SLUCHAJNYH CHISEL S~$X_{n+1}=(2^{17}+3)X_n \bmod 2^{35}$
I~$X_0=1$ PODVERGLI SLEDUYUSHCHEMU TESTU. pUSTX~$Y_n=\floor{10X_n/2^{35}}$,
TOGDA~$Y_n$ DOLZHNA BYTX SLUCHAJNOJ CIFROJ MEZHDU~$6$ I~$9$, A
TRIADY~$(Y_{3n}, Y_{3n+1}, Y_{3n+2})$ DOLZHNY PRINIMATX LYUBOE IZ
$1000$~VOZMOZHNYH ZNACHENIJ OT~$(0, 0, 0)$ DO~$(9, 9, 9)$ S RAVNOJ
VEROYATNOSTXYU. nO V $30\,000$~PROVERENNYH CHISEL NEKOTORYE TRIADY
VSTRECHALISX OCHENX REDKO, A NEKOTORYE POYAVLYALISX GORAZDO CHASHCHE DRUGIH. mOZHETE
LI VY OB�YASNITX TAKOJ STRANNYJ REZULXTAT?

\subsubchap{dRUGIE METODY} %3.2.2
kONECHNO, LINEJNYE KONGRU|NTNYE POSLEDOVATELXNOSTI---NE EDINSTVENNYJ IZ
PREDLOZHENNYH DLYA VYCHISLITELXNYH MASHIN ISTOCHNIKOV SLUCHAJNYH CHISEL. v |TOM
PUNKTE MY PRIVEDEM OBZOR DRUGIH NAIBOLEE VAZHNYH METODOV. nEKOTORYE IZ NIH
DOSTATOCHNO VAZHNY TOGDA KAK DRUGIE PREDSTAVLYAYUT INTERES LISHX POSTOLXKU,
POSKOLXKU OKAZYVAYUTSYA SOVSEM NE TAKIMI HOROSHIMI, KAK KAZHUTSYA NA PERVYJ VZGLYAD.

oDNO IZ OBSHCHEPRINYATYH ZABLUZHDENIJ, S KOTORYMI PRIHODITSYA STALKIVATXSYA,
KOGDA RECHX IDET O POLUCHENII SLUCHAJNYH CHISEL ZAKLYUCHAETSYA V TOM, CHTO
DOSTATOCHNO VZYATX HOROSHIJ DATCHIK I SLEGKA EGO IZMENITX, CHTOBY VYRABOTATX
"ESHCHE BOLEE SLUCHAJNUYU" POSLEDOVATELXNOSTX. dOVOLXNO CHASTO |TO NEVERNO.
nAPRIMER, MY ZNAEM CHTO PO FORMULE
$$
X_{n+1}=(aX_n+c) \bmod m
\eqno(1)
$$
MOZHNO POLUCHITX DOVOLXNO HOROSHIE SLUCHAJNYE CHISLA nE BUDET LI POSLEDOVATELXNOSTX
$$
X_{n+1}=((aX_n) \bmod (m+1)+c) \bmod m
\eqno(2)
$$
ESHCHE BOLEE SLUCHAJNOJ? oTVET TAKOV, CHTO NOVAYA POSLEDOVATELXNOSTX S BOLXSHEJ
VEROYATNOSTXYU \emph{MENEE} SLUCHAJNA. zAMETIM, CHTO CELOSTNAYA TEORIYA DLYA NEE
RUSHITSYA, A V OTSUTSTVIE KAKOJ-LIBO TEORII O POVEDENIYA
POSLEDOVATELXNOSTI~(2) MY POPADAEM V OBLASTX
DATCHIKOV. TIPA~$X_{n+1}=f(X_n)$ SO SLUCHAJNO VYBRANNOJ FUNKCIEJ~$f$.
vMESTE S TEM UPR.~3.1-11--3.1-15 POKAZYVAYUT, CHTO |TI POSLEDOVATELXNOSTI
%% 41
VEDUT SEBYA SOVSEM NE TAK HOROSHO, KAK ESLI BY FUNKCIYA~(1) BYLA CHETKO
OPREDELENA.

rASSMOTRIM DRUGOJ PODHOD, PYTAYASX GENERIROVATX "BOLEE SLUCHAJNYE" CHISLA.
lINEJNYJ KONGRU|NTNYJ METOD MOZHNO OBOBSHCHITX, PREVRATIV EGO, SKAZHEM, V
KVADRATICHNYJ KONGRU|NTNYJ METOD:
$$
X_{n+1}=(dX_n^2+aX_n+c) \bmod m.
\eqno(3)
$$

v UPR.~8 OBOBSHCHAETSYA TEOREMA~3.2.1.2A S CELXYU POLUCHITX NEOBHODIMYE I
DOSTATOCHNYE USLOVIYA DLYA~$a$, $c$ I~$d$, TAKIE, CHTOBY POSLEDOVATELXNOSTX,
OPREDELENNAYA SOOTNOSHENIEM~(3), IMELA BY MAKSIMALXNYJ PERIOD~$m$.
oGRANICHENIYA OKAZYVAYUTSYA NE BOLEE ZHESTKIMI, CHEM V LINEJNOM METODE.

dLYA SLUCHAYA, KOGDA $m$~PREDSTAVLYAETSYA STEPENXYU DVOJKI, INTERESNYJ
KVADRATICHNYJ METOD PREDLOZHIL r.~kOV|YU. pUSTX
$$
X_0 \bmod 4 =2, \quad
X_{n+1}=X_n(X_n+1) \bmod 2^e, \rem{$n\ge 0$.}
\eqno(4)
$$
eTU POSLEDOVATELXNOSTX MOZHNO VYCHISLYATX POCHTI S TOJ ZHE |FFEKTIVNOSTXYU,
KAK I~(1), NE ZABOTYASX O PEREPOLNENII. oNA IMEET INTERESNUYU SVYAZX S
PERVONACHALXNYM METODOM SEREDINY KVADRATA FON nEJMANA. vOZXMEM~$Y_n$,
RAVNOE~$2^eX_n$, TAK CHTO~$Y_n$---CHISLO, PREDSTAVLENNOE S DVOJNOJ TOCHNOSTXYU
PUTEM PRIPISYVANIYA SPRAVA $e$~NULEJ DVOICHNOMU PREDSTAVLENIYU~$X_n$.
tOGDA~$Y_{n+1}$ SOSTOIT V TOCHNOSTI IZ $2e$~SREDNIH CIFR
CHISLA~$Y_n^2+2^eY_n$! tAKIM OBRAZOM, METOD kOV|YU POCHTI IDENTICHEN METODU
SEREDINY KVADRATA S DVOJNOJ TOCHNOSTXYU, S TOJ RAZNICEJ, CHTO ON GARANTIRUET
BOLXSHOJ PERIOD. mOZHNO PRIVESTI I DALXNEJSHIE DOKAZATELXSTVA SLUCHAJNOSTI
POLUCHAEMOJ POSLEDOVATELXNOSTI (SM. UPR. 3.3.4-25).

dRUGIE OBOBSHCHENIYA SOOTNOSHENIYA~(1) TAKZHE DOVOLXNO OCHEVIDNY. nAPRIMER, MY
MOGLI BY POPYTATXSYA UVELICHITX PERIOD POSLEDOVATELXNOSTI. pERIOD LINEJNOJ
KONGRU|NTNOJ POSLEDOVATELXNOSTI CHREZVYCHAJNO VELIK. oBYCHNO, ESLI
$m$~PRIBLIZHAETSYA K RAZMERU MASHINNOGO SLOVA, MY IMEEM DELO S PERIODAMI
PORYADKA~$10^9$ I BOLXSHE, TAK CHTO V TIPICHNYH ZADACHAH ISPOLXZUETSYA TOLXKO
OCHENX MALAYA CHASTX POSLEDOVATELXNOSTI. s DRUGOJ STORONY, VELICHINA
PERIODA VLIYAET NA STEPENX SLUCHAJNOSTI, KOTORAYA DOSTIGAETSYA V
POSLEDOVATELXNOSTI (SM.\ ZAMECHANIYA, PRIVEDENNYE POSLE
SOOTNOSHENIYA~3.3.4-13). pO|TOMU OBYCHNO MY STREMIMSYA POLUCHATX BOLXSHOJ PERIOD,
DLYA CHEGO I SUSHCHESTVUET RYAD METODOV. v ODNOM IZ NIH VVODITSYA
ZAVISIMOSTX~$X_{n+1}$ OT~$X_n$ I~$X_{n-1}$ VMESTO PROSTOJ ZAVISIMOSTI
TOLXKO OT~$X_n$. tOGDA DLINU PERIODA MOZHNO UVELICHITX DO~$m^2$, TAK
KAK POSLEDOVATELXNOSTX NACHNET POVTORYATXSYA NE RANXSHE, CHEM BUDET VYPOLNENO
RAVENSTVO~$(X_{n+\lambda}, X_{n+\lambda+1})=(X_n, X_{n+1})$.

pROSTEJSHIJ SLUCHAJ ZAVISIMOSTI~$X_{n+1}$ OT BOLEE CHEM ODNOGO IZ PREDYDUSHCHIH
ZNACHENIJ REALIZUETSYA V POSLEDOVATELXNOSTI fIBONACHCHI
$$
X_{n+1}=(X_n+X_{n-1}) \bmod m.
\eqno (5)
$$
%% 42
eTOT DATCHIK RASSMATRIVALSYA V NACHALE PYATIDESYATYH GODOV. oN DAET OBYCHNO
DLINU PERIODA, BOLXSHUYU, CHEM~$m$. oDNAKO TESTY S OPREDELENNOSTXYU POKAZALI,
CHTO CHISLA, POLUCHAEMYE IZ SOOTNOSHENIYA fIBONACHCHI~(5), YAVLYAYUTSYA
\emph{NEDOSTATOCHNO} SLUCHAJNYMI. pO|TOMU V NASTOYASHCHEE VREMYA FORMULA~(5)
INTERESNA GLAVNYM OBRAZOM KAK PREKRASNYJ "PLOHOJ PRIMER".

mOZHNO TAKZHE RASSMOTRETX DATCHIKI VIDA
$$
X_{n+1}=(X_n+X_{n-k}) \bmod m,
\eqno(6)
$$
GDE~$k$---DOSTATOCHNO BOLXSHOE CHISLO, PREDLOZHENNYE gRINOM, sMITOM I kLEMOM
(Green, Smith, Klem, {\sl JACM,\/} {\bf 6} (1959), 527--537).
pRI SOOTVETSTVUYUSHCHEM VYBORE~$X_0$, $X_1$,~\dots, $X_k$ |TA FORMULA
OBESHCHAET STATX ISTOCHNIKOM HOROSHIH SLUCHAJNYH CHISEL. nA PERVYJ
VZGLYAD SOOTNOSHENIE~(6) VYGLYADIT NE SLISHKOM UDOBNYM DLYA ISPOLXZOVANIYA V
MASHINE, TEM NE MENEE SUSHCHESTVUET OCHENX |FFEKTIVNAYA PROCEDURA DLYA EE REALIZACII.

\alg A.(aDDITIVNYJ DATCHIK CHISEL.) sNACHALA V YACHEJKI~$Z$, $Y[0]$, $Y[1]$,~\dots,
$Y[k]$ ZANOSYATSYA SOOTVETSTVENNO ZNACHENIYA~$X_k$, $X_k$, $X_{k-1}$,~\dots,
$X_0$, A $j$~PRINIMAETSYA RAVNYM~$k$. pOSLEDOVATELXNOE ISPOLXZOVANIE
ALGORITMA PRIVODIT K POLUCHENIYU POSLEDOVATELXNOSTI~$X_{k+1}$, $X_{k+2}$,
$\ldots\,$.
\st[$j<0$?] eSLI~$j<0$, USTANOVITX~$j\asg k$.

\st[pRIBAVITX,     ZAMENITX.]    uSTANOVITX~$Z\asg Y[j] \asg (Z+Y[j]) \bmod m$.

\st[uMENXSHITX~$j$.] uMENXSHITX~$j$ NA~$1$, VYDATX~$Z$.
\algend

eTOT ALGORITM NA YAZYKE~\MIX{} VYGLYADIT TAK (PRI USLOVII, CHTO INDEKSNYJ
REGISTR~6 NE ISPOLXZUETSYA V OSNOVNOJ PROGRAMME):
$$
\vcenter{
\mixcode
J6NN & *+2  & A1. $j<0$?
ENT6 & K    & uSTANOVITX~$j\asg k$.
LDA  & Z    & A2. pRIBAVITX, ZAMENITX.
ADD  & Y, 6 & $Z+Y[j]$ (VOZMOZHNO PEREPOLNENIE)
STA  & Y, 6 & $\rasg Y[j]$.
STA  & Z    & $\rasg Z$.
DEC6 & 1    & A3. uMENXSHITX~$j$.
\endmixcode
}
\eqno(7)
$$
eTOT DATCHIK RABOTAET OBYCHNO BYSTREE, CHEM DATCHIKI, REALIZUYUSHCHIE PREDYDUSHCHIE
METODY, TAK KAK ZDESX NE TREBUETSYA NIKAKOGO UMNOZHENIYA.

sEJCHAS O TAKOM ADDITIVNOM DATCHIKE IZVESTNO NEMNOGO. pREZHDE CHEM EGO MOZHNO
BUDET REKOMENDOVATX, SLEDUET RAZVITX TEORIYU, POZVOLYAYUSHCHUYU USTANOVITX
NEOBHODIMYE POKAZATELI SLUCHAJNOSTI VYRABATYVAEMYH CHISEL, I PROVESTI
SHIROKIE ISPYTANIYA DLYA OTDELXNYH ZNACHENIJ~$k$ I~$X_0$, $X_1$,~\dots,
$X_k$. dLINA PERIODA OBSUZHDAETSYA V UPR.~11; VOOBSHCHE GOVORYA, ONA NE NAMNOGO
BOLXSHE~$m$. v STATXE
%% 43
gRINA, sMITA I kLEMA GOVORITSYA, CHTO PRI~$k\le 15$ POSLEDOVATELXNOSTX NE
UDOVLETVORYAET TESTU "PROVERKA INTERVALOV", OPISANNOMU V P.~3.3.2, HOTYA
PRI~$k=16$ TEST PROHODIT NORMALXNO.

sUSHCHESTVUET POHOZHIJ, NO GORAZDO BOLEE |FFEKTIVNYJ SPOSOB ULUCHSHENIYA
SLUCHAJNOSTI LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ,
ESLI~\emph{$m$---PROSTOE CHISLO.} nAPRIMER, $m$~MOZHNO VYBRATX KAK SAMOE
BOLXSHOE PROSTOE CHISLO, KOTOROE MOZHNO ZAPISATX V MASHINNOM SLOVE. tAKOE
CHISLO MOZHNO VYCHISLITX ZA PRIEMLEMOE VREMYA, PRIMENYAYA TEHNIKU P.~4.5.4.
kOGDA~$m=p$---PROSTOE CHISLO, IZ TEORII KONECHNYH POLEJ SLEDUET, CHTO
SUSHCHESTVUYUT TAKIE MNOZHITELI~$a_1$,~\dots, $a_k$, CHTO POSLEDOVATELXNOSTX,
OPREDELENNAYA FORMULOJ
$$
X_n=(a_1X_{n-1}+\cdots+a_kX_{n-k}) \bmod p,
\eqno(8)
$$
IMEET PERIOD DLINY~$p^k-1$. zDESX~$X_0$,~\dots, $X_{k-1}$ MOGUT BYTX
VYBRANY PROIZVOLXNO, NO NE DOLZHNY BYTX VSE RAVNY NULYU.
(chASTNYJ SLUCHAJ~$k=1$ SOOTVETSTVUET MULXTIPLIKATIVNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI PO PROSTOMU MODULYU, S KOTOROJ MY UZHE ZNAKOMY.) vYBOR
POSTOYANNYH~$a_1$,~\dots, $a_k$ V~(8) TOGDA I TOLXKO TOGDA DAET ZHELAEMYJ
REZULXTAT, KOGDA POLINOM
$$
f(x)=x^k-a_1x^{k-1}-\cdots-a_k
\eqno(9)
$$
YAVLYAETSYA \dfn{"PRIMITIVNYM MNOGOCHLENOM PO MODULYU~$p$",} T.~E.\
IMEET KORENX, YAVLYAYUSHCHIJSYA \emph{PERVOOBRAZNYM |LEMENTOM POLYA IZ~$p^k$} |LEMENTOV\note{1}%
{eTOT |LEMENT---OBRAZUYUSHCHAYA MULXTIPLIKATIVNOJ GRUPPY POLYA gALUA, KOTORAYA, KAK
IZVESTNO, CIKLICHNA.--- {\sl pRIM. RED.\/}} (SM. UPR. 4.6.2-16).

kONECHNO, PROSTOJ FAKT \emph{SUSHCHESTVOVANIYA} PODHODYASHCHIH KONSTANT~$a_1$,~\dots,
$a_k$, OBESPECHIVAYUSHCHIH DLINU PERIODA~$p^k-1$, NEDOSTATOCHEN DLYA
PRAKTICHESKIH CELEJ. mY DOLZHNY UMETX \emph{NAHODITX} IH, NE PEREBIRAYA VSE
$p^k$~VARIANTOV, TAK KAK $p$~IMEET PORYADOK RAZMERA MASHINNOGO SLOVA. k
SCHASTXYU, SUSHCHESTVUET V TOCHNOSTI~$\varphi(p^k-1)/k$ PODHODYASHCHIH
KOMBINACIJ~$(a_1,~\ldots, a_k)$, TAK CHTO IMEETSYA DOVOLXNO BOLXSHOJ SHANS
OBNARUZHITX ODNU IZ NIH POSLE NESKOLXKIH SLUCHAJNYH POPYTOK. nO, KROME
VSEGO PROCHEGO, NAM NUZHNO UMETX BYSTRO OPREDELITX, YAVLYAETSYA LI~(9)
PRIMITIVNYM MNOGOCHLENOM PO MODULYU~$p$. sOVERSHENNO NEMYSLIMO VYRABATYVATX
$p^k-1$~|LEMENTOV POSLEDOVATELXNOSTI V OZHIDANII POVTORENIYA! mETODY
PROVERKI TOGO, YAVLYAETSYA LI MNOGOCHLEN PRIMITIVNYM PO MODULYU~$p$,
OBSUZHDALISX eLANENOM I kNUTOM
(Alanen, Knuth, {\sl Sankhy\=a\/}, Ser.~A, {\bf 26} (1964), 305--328).
mOZHNO ISPOLXZOVATX SLEDUYUSHCHIJ KRITERIJ.

pUSTX~$r=(p^k-1)/(p-1)$.
\medskip
\item{i)}~vELICHINA~$(-1)^{k+1}a_k$ DOLZHNA BYTX PERVOOBRAZNYM KORNEM PO
MODULYU~$p$ (SR.~P.~3.2.1.2).

\item{ii)}~pOLINOM~$x^r$ DOLZHEN BYTX SRAVNIM S~$(-1)^{k+1}a_k$ PO
MODULYU~$f(x)$ I~$p$.

%% 44
\item{iii)}~sTEPENX~$x^{r/q} \bmod f(x)$, GDE PODRAZUMEVAETSYA
POLINOMIALXNAYA ARIFMETIKA PO MODULYU~$p$, DOLZHNA BYTX POLOZHITELXNOJ DLYA
VSYAKOGO PROSTOGO DELITELYA~$q$ CHISLA~$r$.
\medskip
\noindent eFFEKTIVNYE METODY VYCHISLENIYA~$x^n \bmod f(x)$, ISPOLXZUYUSHCHIE
POLINOMIALXNUYU ARIFMETIKU PO MODULYU PROSTOGO~$p$, OBSUZHDAYUTSYA V~P.~4.6.2.

chTOBY SDELATX TAKUYU PROVERKU, NAM NUZHNO ZNATX
FAKTORIZACIYU~$r=(p^k-1)/(p-1)$ S POMOSHCHXYU PROSTYH CHISEL. eTO
OGRANICHIVAET VOZMOZHNOSTI VYCHISLENIJ. zA PRIEMLEMOE VREMYA MOZHNO
FAKTORIZOVATX~$r$ PRI~$k=2$, $3$ I, MOZHET BYTX, $4$, NO S BOLXSHIMI
ZNACHENIYAMI~$k$, ESLI $p$~VELIKO, TRUDNO IMETX DELO. dAZHE PRI~$k=2$ CHISLO
"ZNACHIMYH SLUCHAJNYH CIFR" UDVAIVAETSYA PO SRAVNENIYU S~$k=1$. pO|TOMU
BOLXSHIE ZNACHENIYA~$k$ REDKO NEOBHODIMY.

dLYA OCENKI POSLEDOVATELXNOSTI CHISEL, POLUCHAEMYH S POMOSHCHXYU~(8), MOZHNO
VOSPOLXZOVATXSYA VARIANTOM SPEKTRALXNOGO TESTA, OPISANNYM V P.~3.3.4
(SM.~UPR.~3.3.4-26). iZ IZLOZHENNOGO V |TOM PUNKTE SLEDUET, CHTO
\emph{NECELESOOBRAZNO} OGRANICHIVATXSYA OCHEVIDNYMI ZNACHENIYAMI~$a_1=+1$
ILI~$a_1=-1$, DAZHE ESLI |TO VOZMOZHNO. lUCHSHE VZYATX BOLXSHIE, SUSHCHESTVENNO
"SLUCHAJNYE" CHISLA~$a_1$,~\dots, $a_k$, UDOVLETVORYAYUSHCHIE USLOVIYAM, A ZATEM
PROVERITX VYBOR S POMOSHCHXYU SPEKTRALXNOGO TESTA. dLYA OPREDELENIYA~$a_1$,~\dots,
$a_k$, TREBUETSYA PROVESTI MNOGO VYCHISLENIJ, NO ESTX VSE
OSNOVANIYA SCHITATX, CHTO V REZULXTATE MY POLUCHIM VESXMA UDOVLETVORITELXNYJ
ISTOCHNIK SLUCHAJNYH CHISEL.

oSOBYJ INTERES PREDSTAVLYAET ZNACHENIE~$p=2$. iNOGDA BYVAET NUZHEN DATCHIK,
POROZHDAYUSHCHIJ SLUCHAJNUYU POSLEDOVATELXNOSTX \emph{BITOV}---NULEJ I EDINIC
(V OTLICHIE OT DROBEJ, PRINIMAYUSHCHIH ZNACHENIYA OT NULYA DO EDINICY). sUSHCHESTVUET
PROSTOJ SPOSOB VYRABATYVATX NA DVOICHNOJ MASHINE S $k\hbox{-RAZRYADNYMI}$
SLOVAMI VESXMA SLUCHAJNUYU POSLEDOVATELXNOSTX BITOV. nACHINAEM S
PROIZVOLXNOGO DVOICHNOGO SLOVA~$|Y|=(Y_1 Y_2 \ldots Y_k)_2$, OTLICHNOGO OT
NULYA. chTOBY POLUCHITX OCHEREDNOJ SLUCHAJNYJ BIT POSLEDOVATELXNOSTI, PRODELAEM
SLEDUYUSHCHIE OPERACII, ZAPISANNYE NA YAZYKE~\MIX:
$$
\vcenter{
\mixcode
LDA  & Y   & (pREDPOLAGAEM, CHTO SIGNAL PEREPOLNENIYA VYKLYUCHEN.)
ADD  & Y   & sDVIG VLEVO NA ODIN RAZRYAD.
JNOV & *+2 & pEREHOD, ESLI V STARSHEM RAZRYADE VNACHALE BYL NULX.
XOR  & C   & v PROTIVNOM SLUCHAE KORREKTIRUEM CHISLO OPERACIEJ "ISKLYUCHAYUSHCHEE ILI".
STA  & Y
\endmixcode
}
\eqno(10)
$$

chETVERTAYA PO PORYADKU OPERACIYA, "ISKLYUCHAYUSHCHEE ILI", IMEETSYA POCHTI NA VSEH
DVOICHNYH MASHINAH (SR.~UPR.~2.5-28). oNA IZMENYAET ZNACHENIE KAZHDOGO RAZRYADA,
SOOTVETSTVUYUSHCHEGO TOMU, GDE |C|~SODERZHIT EDINICU, NA OBRATNOE. v
YACHEJKE~|C| NAHODITSYA DVOICHNAYA
%% 45
KONSTANTA~$(a_1\ldots{}a_k)_2$, OPREDELYAYUSHCHAYA PRIMITIVNYJ MNOGOCHLEN
PO MODULYU~$2$: $x^k-a_1x^{k-1}-\cdots-a_k$. pOSLE VYPOLNENIYA
PROGRAMMY~(10) V MLADSHEM RAZRYADE~|Y| SODERZHITSYA SLEDUYUSHCHIJ BIT
POSLEDOVATELXNOSTI (ESLI |TO BOLEE UDOBNO, MOZHNO, NAOBOROT,
ISPOLXZOVATX STARSHIJ RAZRYAD~|Y|). rASSMOTRIM V KACHESTVE PRIMERA RIS.~1,
ILLYUSTRIRUYUSHCHIJ
$$\matrix{
 1011\cr
 0101\cr
 1010\cr
 0111\cr
 1110\cr
 1111\cr
 1101\cr
 1001\cr
 0001\cr
 0010\cr
 0100\cr
 1000\cr
 0011\cr
 0110\cr
 1100\cr
 1011\cr
}
$$
%% eTA MATRICA I ESTX KARTINKA.
\picture{
  rIS.~1. pOSLEDOVATELXNYE SOSTOYANIYA MASHINNOGO SLOVA~|Y| PRI ISPOLXZOVANII
  DVOICHNOGO METODA DLYA~$k=4$ I $c=|CONTENTS|(|C|)= (0011)_2$.
}
POLUCHENIE POSLEDOVATELXNOSTI PRI~$k=4$, $c=(0011)_2$ (|TO, KONECHNO,
NESTANDARTNO MALOE ZNACHENIE~$k$). pRAVYJ STOLBEC TABLICY PREDSTAVLYAET
POSLEDOVATELXNOSTX BITOV, KOTORAYA POVTORYAETSYA S PERIODOM~$2^k-1=15$:
$1101011110001001\ldots\,$. pOSLEDOVATELXNOSTX DOSTATOCHNO SLUCHAJNAYA,
ESLI UCHESTX, CHTO ONA POLUCHENA S POMOSHCHXYU CHETYREH RAZRYADOV PAMYATI. chTOBY
UBEDITXSYA V |TOM, RASSMOTRIM SOSEDNIE CHETVERKI BITOV, POYAVLYAYUSHCHIESYA NA
PROTYAZHENII PERIODA, A IMENNO: $1101$, $1010$, $0101$, $1011$, $0111$,
$1111$, $1110$, $1100$, $1000$, $0001$, $0010$, $0100$, $1001$, $0011$,
$0110$. vOOBSHCHE GOVORYA, TAK KAK DLINA PERIODA RAVNA~$2^k-1$, KAZHDAYA
VOZMOZHNAYA KOMBINACIYA $k$~BITOV VSTRECHAETSYA ZA PERIOD TOCHNO ODIN RAZ, ZA
ISKLYUCHENIEM NABORA IZ VSEH NULEJ. tAKIM OBRAZOM, SOSEDNIE NABORY IZ
$k$~BITOV SUSHCHESTVENNO NEZAVISIMY. v \S~3.5 MY UVIDIM, CHTO SUSHCHESTVUET
OCHENX MOSHCHNYJ KRITERIJ SLUCHAJNOSTI DLYA~$k$, RAVNOGO, SKAZHEM, $30$ ILI
BOLXSHE. tEORETICHESKIE REZULXTATY, ILLYUSTRIRUYUSHCHIE SLUCHAJNOSTX |TOJ
POSLEDOVATELXNOSTI, PRIVODYATSYA V STATXE r.~tAUSVORTA (R.~s.~Tausworthe,
{\sl Math. Comp.,\/} {\bf 19} (1965), 201--209).

pRIMITIVNYE MNOGOCHLENY STEPENI~$\le 100$ PO MODULYU~$2$
BYLI PROTABULIROVANY e.~uOTSONOM (e.~J.~Watson, {\sl Math. Comp.,\/} {\bf 16}
(1962), 368--369). pRI~$k=35$ MOZHNO PRINYATX
$$
c = (00000000000000000000000000000000101)_2,
$$
%% 46
A DLYA~$k=30$ MOZHNO VZYATX
$$
c=(000000000000000000000001010011)_2.
$$
vSE ZHE, KAK SLEDUET IZ UPR.~18 I~3.3.4-26, DLYA OPREDELENIYA PRIMITIVNYH
MNOGOCHLENOV PO MODULYU~$2$ LUCHSHE NAHODITX SUSHCHESTVENNO "SLUCHAJNYE" KONSTANTY~$c$.

\emph{pREDUPREZHDENIE:} nEKOTORYE POPADALISX V LOVUSHKU,
PYTAYASX ISPOLXZOVATX METOD VYRABOTKI SLUCHAJNYH POSLEDOVATELXNOSTEJ BITOV
DLYA POLUCHENIYA SLUCHAJNYH DROBEJ, ZANIMAYUSHCHIH CELOE
SLOVO~$(.Y_0Y_1\ldots{}Y_{k-1})_2$,
$(.Y_kY_{k+1}\ldots{}Y_{2k-1})_2$,~$\ldots\,$. nA SAMOM DELE |TO DOVOLXNO
PLOHOJ SPOSOB, HOTYA OTDELXNYE BITY KAZHDOJ DROBI VPOLNE SLUCHAJNY (SM.~UPR.~18)!

mY UZHE VIDELI, CHTO, KOGDA~$X_n$ OPREDELYAETSYA PODHODYASHCHEJ FUNKCIEJ
OT~$X_{n-1}$,~\dots, $X_{n-k}$, MOZHNO NAJTI TAKIE
POSLEDOVATELXNOSTI S~$0\le X_n < m$ I PERIODOM~$m^k-1$, GDE~$m$---PROSTOE
CHISLO. nAIBOLXSHIJ PERIOD, KOTORYJ MOZHNO POLUCHITX DLYA \emph{PROIZVOLXNOJ}
POSLEDOVATELXNOSTI, OPREDELENNOJ SOOTNOSHENIEM
$$
X_n=f(X_{n-1}, \ldots, X_{n-k}), \rem{$0\le X_n < m$,}
\eqno(11)
$$
KAK MOZHNO VIDETX, RAVEN~$m^k$. m.~mARTIN (m.~H.~Martin
{\sl Bull. Amer. Math. Soc.,\/} {\bf 40} (1934), 859--864) PERVYJ POKAZAL,
CHTO SUSHCHESTVUYUT FUNKCII, POZVOLYAYUSHCHIE DOSTICHX |TOGO MAKSIMUMA DLYA LYUBYH~$m$
I~$k$. eGO METOD LEGKO OBOSNOVATX, NO, K SOZHALENIYU, ON NEUDOBEN DLYA
PROGRAMMIROVANIYA (SM.~UPR.~17). iZ IZVESTNYH FUNKCIJ~$f$, DAYUSHCHIH
MAKSIMALXNYJ PERIOD~$m^k$, SAMOJ PROSTOJ YAVLYAETSYA OPISANNAYA V UPR.~21.
sOOTVETSTVUYUSHCHIE PROGRAMMY, VOOBSHCHE GOVORYA, NE TAK |FFEKTIVNY DLYA VYRABOTKI
SLUCHAJNYH CHISEL, KAK PRI REALIZACII DRUGIH RANEE OPISANNYH METODOV. vSE ZHE
ONI POZVOLYAYUT PRODEMONSTRIROVATX YAVNUYU SLUCHAJNOSTX POSLEDOVATELXNOSTI
(KOGDA RECHX IDET O PERIODE V CELOM).

dRUGOJ VAZHNYJ KLASS METODOV SVODITSYA K \emph{KOMBINACII} DATCHIKOV
SLUCHAJNYH CHISEL DLYA POLUCHENIYA "ESHCHE BOLEE SLUCHAJNYH" POSLEDOVATELXNOSTEJ.
vSEGDA NAJDUTSYA SKEPTIKI, POLAGAYUSHCHIE, CHTO LINEJNYE KONGRU|NTNYE METODY,
ADDITIVNYE METODY I T.~D.\ SLISHKOM PROSTY DLYA VYRABOTKI DOSTATOCHNO
SLUCHAJNYH POSLEDOVATELXNOSTEJ. a TAK KAK NEVOZMOZHNO \emph{DOKAZATX,} CHTO
IH SKEPTICIZM NEOPRAVDAN (HOTYA MY I VERIM, CHTO |TO TAK), DOVOLXNO
BESPOLEZNO OSPARIVATX PODOBNOE MNENIE. sUSHCHESTVUYUT VPOLNE
|FFEKTIVNYE METODY DLYA TOGO, CHTOBY POLUCHATX IZ DVUH
POSLEDOVATELXNOSTEJ NASTOLXKO SLUCHAJNUYU TRETXYU, CHTO TOLXKO SAMYM
OT�YAVLENNYM SKEPTIKAM ONA MOZHET NE PONRAVITXSYA.

pREDPOLOZHIM, CHTO MY IMEEM DVE POSLEDOVATELXNOSTI~$X_0$, $X_1$,~\dots,
I~$Y_0$, $Y_1$,~\dots, SLUCHAJNYH CHISEL, RASPOLOZHENNYH MEZHDU NULEM I~$m-1$,
POLUCHENNYE DVUMYA NEZAVISIMYMI SPOSOBAMI. oDNO IZ PREDLOZHENIJ SVODITSYA K
TOMU, CHTOBY SKLADYVATX CHISLA POPARNO PO
%% 47
MODULYU~$m$, POLUCHAYA POSLEDOVATELXNOSTX~$Z_n=(X_n+Y_n)\bmod m$. v |TOM
SLUCHAE ZHELATELXNO, CHTOBY DLINY PERIODOV~$\<X_n>$ I~$\<Y_n>$ BYLI VZAIMNO
PROSTYMI CHISLAMI (SM.~UPR.~13).

mETOD, PREDLOZHENNYJ mAKLARENOM I mARSALXEJ ZNACHITELXNO LUCHSHE I UDIVITELXNO
UDOBEN DLYA PROGRAMMIROVANIYA.

\alg M.(vPOLNE SLUCHAJNAYA POSLEDOVATELXNOSTX.) pRI ZADANNYH METODAH
VYRABOTKI DVUH POSLEDOVATELXNOSTEJ~$\<X_n>$ I~$\<Y_n>$ |TOT METOD
POZVOLYAET GENERIROVATX CHLENY "ZNACHITELXNO BOLEE SLUCHAJNOJ"
POSLEDOVATELXNOSTI. mY ISPOLXZUEM VSPOMOGATELXNUYU TABLICU~$V[0]$, $V[1]$,~\dots,
$V[k-1]$, GDE~$k$---NEKOTOROE CHISLO, VYBIRAEMOE OBYCHNO DLYA
UDOBSTVA RAVNYM PRIMERNO~$100$. sNACHALA $V\hbox{-TABLICA}$ ZAPOLNYAETSYA
PERVYMI $k$~ZNACHENIYAMI $X\hbox{-POSLEDOVATELXNOSTI}$.

\st[vYRABOTATX~$X$, $Y$.] uSTANOVITX V~$X$  I~$Y$ ZNACHENIYA OCHEREDNYH
CHLENOV POSLEDOVATELXNOSTEJ~$\<X_n>$ I~$\<Y_n>$ SOOTVETSTVENNO.

\st[vYCHISLITX~$j$.] uSTANOVITX~$j\asg \floor{kY/m}$, GDE~$m$---MODULX,
ISPOLXZUYUSHCHIJSYA V POSLEDOVATELXNOSTI~$\<Y_n>$. tAKIM OBRAZOM,
$j$~PRINIMAET SLUCHAJNOE ZNACHENIE, OPREDELYAEMOE S POMOSHCHXYU~$Y$; $0 \le j <k$.

\st[zAMENITX.] vYDATX~$V[j]$ I USTANOVITX~$V[j]\asg X$.
\algend

eTOT METOD MOZHNO USILENNO REKOMENDOVATX. oN POZVOLYAET POLUCHATX
NEVEROYATNO BOLXSHIE PERIODY, ESLI PERIODY POSLEDOVATELXNOSTEJ~$\<X_n>$
I~$\<Y_n>$ VZAIMNO PROSTYE. i DAZHE ESLI DLINA PERIODA NE OCHENX SUSHCHESTVENNA,
SOSEDNIE CHLENY POSLEDOVATELXNOSTI POCHTI NE KORRELIRUYUT DRUG S DRUGOM.
pRICHINOJ TOGO, CHTO |TOT METOD NAMNOGO PREVOSHODIT METOD SEREDINY KVADRATA
ILI METOD, OSNOVANNYJ NA SOOTNOSHENII~(2), YAVLYAETSYA DOSTATOCHNAYA
SLUCHAJNOSTX POSLEDOVATELXNOSTEJ~$X_n$ I~$Y_n$, KOTORYE NE MOGUT
VYROZHDATXSYA. chITATELYU REKOMENDUETSYA RAZOBRATX UPR.~3, CHTOBY UVIDETX,
KAK METOD RABOTAET V CHASTNOM SLUCHAE.

nA MASHINE~\MIX{} MOZHNO REALIZOVATX ALGORITM~M, PRINIMAYA~$k$ NA EDINICU
BOLXSHIM MAKSIMALXNOGO ZNACHENIYA, RAZMESHCHAYUSHCHEGOSYA V ODNOM BAJTE (RAVNYM
RAZMERU BAJTA). shAGI~M2 I~M3 LEGKO PROGRAMMIRUYUTSYA SLEDUYUSHCHIM OBRAZOM:
$$
\vcenter{
\mixcode
LD6 & Y(l:l) & $j\asg \hbox{STARSHIJ BAJT } Y$.
LDA & V, 6   & $|rA|\asg \hbox{SLEDUYUSHCHIJ |LEMENT NOVOJ POSLEDOVATELXNOSTI.}$
LDX & h
STX & V,6    & $V[j]\asg X$.
\endmixcode
}
\eqno(12)
$$

dLYA PRIMERA PREDPOLOZHIM, CHTO ALGORITM~M PRIMENYAETSYA K TAKIM DVUM
POSLEDOVATELXNOSTYAM S~$k=64$:
$$
\matrix{
 X_0=5772156649, & X_{n+1}=(3141592653 X_n + 2718281829) \bmod 2^{35};\cr
 Y_0=1781072418, & Y_{n+1}=(2718281829 Y_n + 3141592653) \bmod 2^{35}.\cr
}
$$
%% 48
mY UTVERZHDAEM, CHTO POSLEDOVATELXNOSTX, POLUCHENNAYA S POMOSHCHXYU ALGORITMA~M,
BUDET UDOVLETVORYATX FAKTICHESKI \emph{LYUBOMU} KRITERIYU SLUCHAJNOSTI DLYA
GENERIRUEMYH VYCHISLITELXNOJ MASHINOJ POSLEDOVATELXNOSTEJ. bOLEE TOGO,
VREMYA VYRABOTKI CHUTX BOLXSHE CHEM VDVOE PREVYSHAET VREMYA POLUCHENIYA ODNOJ
POSLEDOVATELXNOSTI~$<X_n>$.

f.~gEBHARDT POKAZAL [F.~Gebhardt, {\sl Math. Comp.,\/} {\bf 21} (1967),708--709],
CHTO ALGORITM~M POZVOLYAET POLUCHATX UDOVLETVORITELXNYE
REZULXTATY, DAZHE ESLI EGO PRIMENYATX K TAKIM
NESLUCHAJNYM POSLEDOVATELXNOSTYAM, KAK POSLEDOVATELXNOSTX fIBONACHCHI
S~$X_n=F_2 \bmod m$ I~$Y_n=F_{2n+1} \bmod m$. dRUGOJ SPOSOB
KOMBINIROVATX DVE POSLEDOVATELXNOSTI OSNOVAN NA CIKLICHESKOM SDVIGE I
"ISKLYUCHAYUSHCHEM ILI" V DVOICHNOJ MASHINE. eGO PREDLOZHIL
u.~u|STL|JK (W.~J.~Westlake, {\sl JACM,\/} {\bf 14} (1967), 337--340).

\excercises
\rex[12] pRAKTICHESKI MY POLUCHAEM SLUCHAJNYE CHISLA, POLXZUYASX
SOOTNOSHENIEM~$X_{n+1}=(aX_n+c) \bmod m$, GDE~$X_n$---\emph{CELYE.} pOSLE
CHEGO MY OBRASHCHAEMSYA S NIMI, KAK S \emph{DROBYAMI:} $U_n=X_n/m$. rEKURRENTNAYA
FORMULA DLYA~$U_n$ V DEJSTVITELXNOSTI TAKOVA:
$$
U_{n+1}=(aU_n+c/m) \bmod 1.
$$
oBDUMAJTE \emph{PRYAMOE} ISPOLXZOVANIE |TOJ FORMULY DLYA VYRABOTKI SLUCHAJNYH
POSLEDOVATELXNOSTEJ S POMOSHCHXYU OPERACIJ S PLAVAYUSHCHEJ TOCHKOJ, IMEYUSHCHIHSYA V MASHINE.

\rex[m20] dLYA HOROSHEGO ISTOCHNIKA SLUCHAJNYH CHISEL
SOOTNOSHENIE~$X_{n-1}<X_{n+1}<X_n$ DOLZHNO VYPOLNYATXSYA PRIMERNO V TECHENIE
ODNOJ SHESTOJ VSEGO VREMENI, TAK KAK VSE VOZMOZHNYE PORYADKOVYE
KOMBINACII~$X_{n-1}$, $X_n$ I~$X_{n+1}$ RAVNOVEROYATNY. pOKAZHITE, CHTO
UKAZANNYJ VYSHE  PORYADOK TEM NE MENEE \emph{NIKOGDA} NE VSTRECHAETSYA V
POSLEDOVATELXNOSTI fIBONACHCHI~(5).

\ex[21] kAKAYA POSLEDOVATELXNOSTX POLUCHITSYA PRI ISPOLXZOVANII ALGORITMA~M,
ESLI~$X_0=0$, $X_{n+1}=(5X_n+3)\bmod 8$, $Y_0=0$, $Y_{n+1}=(5Y_n+1)\bmod8$
I~$k=4$? (zAMETXTE, CHTO MOSHCHNOSTX RAVNA DVUM, TAK CHTO ISHODNYE~$<X_n>$
I~$\<Y_n>$ NE SLISHKOM SLUCHAJNY.)

\ex[00] pOCHEMU V PERVOJ KOMANDE PROGRAMMY~(12) ISPOLXZUETSYA IMENNO STARSHIJ
BAJT, A NE KAKOJ-NIBUDX DRUGOJ?

\rex[20] rASSMOTRITE VOZMOZHNOSTX ISPOLXZOVANIYA USLOVIYA~$X_n=Y_n$ DLYA
USKORENIYA RABOTY ALGORITMA~M.

\ex[10] v TEKSTE PRI ISSLEDOVANII DVOICHNOGO METODA~(10) UTVERZHDAETSYA, CHTO
MLADSHIJ BIT SLOVA~$X$ SLUCHAEN, ESLI MNOGOKRATNO PRIMENYATX |TOT
METOD. pOCHEMU NE SLUCHAJNO VSE \emph{SLOVO}~$X$?

\ex[20] pOKAZHITE, CHTO MOZHNO POLUCHITX POLNUYU POSLEDOVATELXNOSTX
DLINY~$2^e$ (T.~E.\ KAZHDYJ IZ $2^e$~VOZMOZHNYH VARIANTOV SOSEDNIH $e$~BITOV,
KOTORYJ REALIZUETSYA TOLXKO ODIN RAZ NA PROTYAZHENII PERIODA), ESLI
IZMENITX PROGRAMMU~(10) SLEDUYUSHCHIM OBRAZOM:
%% !!! nEPRIYATNAYA SHTUKA: TAK KAK BLOK \mixcode VHODIT V ARGUMENT MAKROSA \ex,
%% EGO TOKENY POLUCHAYUT KATEGORIYU, DO TOGO, KAK V \mixcode PROIZOJDET
%% VYPOLNENIE \obeylines. v ITOGE KONCY STROK NE SCHITAYUTSYA \cr ? kAK |TO SDELATX?
$$
\vcenter{
\mixcode
LDA  & h   \cr
JANZ & *+2 \cr
LDA  & C   \cr
ADD  & X   \cr
JNOV & *+3 \cr
JAZ  & *+2 \cr
XOR  & C   \cr
STA  & X   \cr
\endmixcode
}
$$
%% 49

\ex[M39] dOKAZHITE, CHTO KVADRATICHNAYA KONGRU|NTNAYA
POSLEDOVATELXNOSTX~$(3)$ IMEET PERIOD DLINY~$m$ TOGDA I TOLXKO TOGDA,
KOGDA VYPOLNYAYUTSYA SLEDUYUSHCHIE USLOVIYA:
\medskip
\item{i)}~$c$ I~$m$---VZAIMNO PROSTYE CHISLA;
\item{ii)}~$d$ I~$a-1$ KRATNY~$p$---VSEM NECHETNYM PROSTYM DELITELYAM~$m$;
\item{iii)}~$d$---CHETNOE I~$d\equiv a-1\pmod{4}$, ESLI~$m$ KRATNO~$4$,
 $d\equiv a-1 \pmod{2}$, ESLI~$m$ KRATNO~$2$;
\item{iv)}~ILI~$d=0$, ILI~$a\equiv 1$ I~$cd\equiv 6\pmod{9}$, ESLI~$m$
KRATNO~$9$. [\emph{uKAZANIE.} pOSLEDOVATELXNOSTX, OPREDELENNAYA
SOOTNOSHENIYAMI~$X_0=0$, $X_{n+1}=dX_n^2+aX_n+c$, IMEET PO MODULYU~$m$ PERIOD
DLINY~$m$, ESLI TOLXKO |TA DLINA PERIODA RAVNA~$d$ PO MODULYU~$d$,
GDE~$d$---PROIZVOLXNYJ DELITELX~$m$.]

\rex[m24] (r.~kOV|YU.) iSPOLXZUJTE REZULXTAT UPR.~8, CHTOBY DOKAZATX, CHTO V
MODIFICIROVANNOM METODE SEREDINY KVADRATA~(4) DLINA PERIODA RAVNA~$2^{e-2}$.

\ex[m29] pOKAZHITE, CHTO ESLI~$X_0$ I~$X_1$ NE YAVLYAYUTSYA OBA CHETNYMI
I~$m=2^e$, TO PERIOD POSLEDOVATELXNOSTI fIBONACHCHI~(5) RAVEN~$3\cdot 2^{e-1}$.

\ex[m36] zADACHA |TOGO UPRAZHNENIYA SOSTOIT V TOM, CHTOBY PROANALIZIROVATX
OPREDELENNYE SVOJSTVA CELOCHISLENNYH POSLEDOVATELXNOSTEJ, UDOVLETVORYAYUSHCHIH
REKURRENTNOMU SOOTNOSHENIYU
$$
X_n=a_1X_{n-1}+\cdots+a_kX_{n-k}, \rem{$n\ge k$.}
$$
eSLI MY MOZHEM VYCHISLITX DLINU PERIODA |TOJ POSLEDOVATELXNOSTI PO
MODULYU~$m=p^e$, GDE~$p$---PROSTOE CHISLO, TO DLINA PERIODA OTNOSITELXNO
PROIZVOLXNOGO MODULYA~$m$ RAVNA NAIMENXSHEMU OBSHCHEMU KRATNOMU DLIN PERIODOV,
VYCHISLENNYH OTNOSITELXNO STEPENEJ PROSTYH SOMNOZHITELEJ~$m$.
\medskip
%
\item{a)}~pUSTX~$f(z)$, $a(z)$, $b(z)$)---POLINOMY S CELOCHISLENNYMI KO|FFICIENTAMI;
BUDEM PISATX~$a(z)\equiv b(z) \pmod{f(z)\hbox{ I } m}$,
ESLI~$a(z)=b(z)+f(z)u(z)+mv(z)$ DLYA NEKOTORYH POLINOMOV~$u(z)$, $v(z)$ S
CELOCHISLENNYMI KO|FFICIENTAMI. dOKAZHITE, CHTO PRI~$f(0)=1$ I~$p^e>2$
SPRAVEDLIVO SLEDUYUSHCHEE: "ESLI~$z^\lambda\equiv 1 \pmod{f(z)\hbox{ I }p^e}$,
$z^\lambda\not\equiv 1\pmod{f(z)\hbox{ I }p^{e+1}}$,
TOGDA~$z^{p\lambda}\equiv 1 \pmod{f(z)\hbox{ I }p^{e+1}}$,
$z^{p\lambda}\not\equiv 1 \pmod{f(z)\hbox{ I } p^{e+2}}$".
%
\item{b)}~pUSTX
$$
\eqalign{
f(z)&=1-a_1z-\cdots-a_kz^k,\cr
G(z)&=1/f(z)=A_0+A_1z+A_2z^2+\ldots\,.\cr
}
$$
oBOZNACHIM SIMVOLOM~$\lambda(m)$ DLINU PERIODA
POSLEDOVATELXNOSTI~$\<A_n\bmod m>$.  dOKAZHITE, CHTO~$\lambda(m)$---NAIMENXSHEE
POLOZHITELXNOE CELOE~$\lambda$, TAKOE, CHTO~$z^\lambda\equiv 1
\pmod{f(z)\hbox{ I } m}$.
%
\item{c)}~pUSTX~$p$---PROSTOE, $p^e>2$ I~$\lambda(p^e)\ne \lambda(p^{e+1})$.
dOKAZHITE, CHTO~$\lambda(p^{e+r})=p^r\lambda(p^e)$ DLYA VSEH~$r\ge0$. (tAKIM
OBRAZOM, CHTOBY NAJTI DLINU PERIODA POSLEDOVATELXNOSTI~$\<A_n \bmod 2^e>$,
MOZHNO VYCHISLYATX~$\lambda(4)$, $\lambda(8)$, $\lambda(16)$,~\dots{}
VRUCHNUYU DO TEH POR, POKA MY NE NAJDEM NAIMENXSHEE~$r\ge2$, TAKOE,
CHTO~$\lambda(2^{r+1})\ne\lambda(4)$. tOGDA DLINA PERIODA OPREDELENA
PO~$\bmod 2^e$ DLYA VSEH~$e$.)
%
\item{d)}~pOKAZHITE, CHTO LYUBAYA POSLEDOVATELXNOSTX CELYH CHISEL,
UDOVLETVORYAYUSHCHAYA REKURRENTNOMU SOOTNOSHENIYU, PRIVEDENNOMU V NACHALE
UPRAZHNENIYA, IMEET PROIZVODYASHCHUYU FUNKCIYU~$g(z)/f(z)$, GDE~$g(z)$---NEKOTORYJ
POLINOM S CELOCHISLENNYMI KO|FFICIENTAMI.
%
\item{e)}~pUSTX POLINOMY~$f(z)$ I~$g(z)$ IZ~(d) VZAIMNO PROSTYE PO
MODULYU~$p$ (SR.~P.~4.6.1). dOKAZHITE, CHTO POSLEDOVATELXNOSTX~$\<X_n \bmod
p^e>$ IMEET DLINU PERIODA V TOCHNOSTI TAKUYU ZHE, KAK I SPECIALXNAYA
POSLEDOVATELXNOSTX~$\<A_n \bmod p^e>$ V~(b). (nIKAKIM VYBOROM~$X_0$,~\dots,
 $X_{k-1}$ NELXZYA POLUCHITX BOLEE DLINNYJ PERIOD, TAK KAK OBSHCHAYA
POSLEDOVATELXNOSTX PREDSTAVLYAETSYA LINEJNOJ KOMBINACIEJ
"SDVIGOV" SPECIALXNOJ POSLEDOVATELXNOSTI.) [\emph{uKAZANIE.} sUSHCHESTVUYUT
POLINOMY, TAKIE, CHTO~$a(z)f(z)+b(z)g(z)\equiv 1 \pmod{p^e}$. eTO SLEDUET
IZ UPR.~4.6.2-22 (LEMMA gENZELYA).]

\rex[m28] nAJDITE CELYE CHISLA~$X_0$, $X_1$, $a$, $b$ I~$c$, TAKIE, CHTO POSLEDOVATELXNOSTX
$$
X_{n+1}=(aX_n+bX_{n-1}+c)\bmod 2^e, \rem{$n\ge 1$,}
$$
%% 50
IMEET SAMYJ BOLXSHOJ PERIOD IZ VSEH POSLEDOVATELXNOSTEJ |TOGO TIPA.
[\emph{uKAZANIE.} $X_{n+2}=((a+1)X_{n+1}+(b-a)X_n-bX_{n-1})\bmod 2^e$ sM.~UPR.~11~(c).]

\ex[m20] pUSTX~$\<X_n>$ I~$\<Y_n>$--- POSLEDOVATELXNOSTI CELYH CHISEL PO
MODULYU~$m$ S PERIODAMI DLINY~$\lambda_1$ I~$\lambda_2$; OBRAZUEM NOVUYU
POSLEDOVATELXNOSTX~$Z_n=(X_n+Y_n)\bmod m$. pOKAZHITE, CHTO, ESLI~$\lambda_1$
I~$\lambda_2$---VZAIMNO PROSTYE CHISLA, POSLEDOVATELXNOSTX~$\<Z_n>$ IMEET
DLINU PERIODA~$\lambda_1\lambda_2$.

\ex[m24] pUSTX~$X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, TAKIE ZHE,
KAK I V PREDYDUSHCHEM UPRAZHNENII. pREDPOLOZHIM,
CHTO~$\lambda_1=2^{e_2}3^{e_3}5^{e_5}\ldots$---RAZLOZHENIE~$\lambda_1$ NA
PROSTYE MNOZHITELI, I ANALOGICHNO~$\lambda_2=2^{f_2}3^{f_3}5^{f_5}\ldots\,$.
pUSTX~$\lambda_0=2^{g_2}3^{g_3}5^{g_5}\ldots$, GDE~$g_p=(\max(e_p, f_p)$,
ESLI~$e_p\ne f_p$, I~$0$, ESLI~$e_p=f_p$). pOKAZHITE, CHTO
PERIOD~$\lambda'$ POSLEDOVATELXNOSTI~$Z_n$  KRATEN~$\lambda_0$, NO
YAVLYAETSYA DELITELEM~$\lambda$---NAIMENXSHEGO OBSHCHEGO KRATNOGO~$\lambda_1$,
$\lambda_2$. v CHASTNOSTI, $\lambda'=\lambda$, ESLI
$(e_p\ne f_p \ror e_p=f_p=0)$ DLYA VSYAKOGO PROSTOGO~$p$.

\ex[m46] chTO MOZHNO SKAZATX PO POVODU DLINY PERIODA POSLEDOVATELXNOSTI,
 VYRABATYVAEMOJ ALGORITMOM~M?

\rex[m28] pUSTX DVOICHNOE PREDSTAVLENIE KONSTANTY~$c$, FIGURIRUYUSHCHEJ V
METODE~(10), IMEET VID~$(a_1 a_2 \ldots a_k)_2$. pOKAZHITE, CHTO
POSLEDOVATELXNOSTX BITOV~$Y_0$, $Y_1$,~\dots{} UDOVLETVORYAET SOOTNOSHENIYU
$$
Y_n=(a_1Y_{n-1}+a_2Y_{n-2}+\cdots+a_kY_{n-k}) \bmod 2.
$$
[eTo MOZHNO RASSMATRIVATX KAK DRUGOJ SPOSOB OPREDELENIYA
POSLEDOVATELXNOSTI. HOTYA NA PERVYJ VZGLYAD SVYAZX MEZHDU |TIM SOOTNOSHENIEM I
|FFEKTIVNOJ PROGRAMMOJ~(10) NE OCHEVIDNA!]

\ex[m33] (m.~mARTIN, 1934.) pUSTX~$m, k\ge 1$---CELYE CHISLA
I~$X_1=X_2=\ldots=X_k=0$. dLYA~$n>0$ POLOZHIM~$X_{n+k}$ RAVNYM NAIBOLXSHEMU
NEOTRICATELXNOMU ZNACHENIYU~$y<m$, TAKOMU, CHTO $k\hbox{-NABOR}$ $(X_{n+1},~\ldots,
X_{n+k-1}, y)$ BOLXSHE NE VSTRECHAETSYA V POSLEDOVATELXNOSTI. dRUGIMI
SLOVAMI, $(X_{n+1},~\ldots, X_{n+k-1}, y)$ NE DOLZHEN SOVPADATX S~$(X_{r+1},~\ldots,
X_{r+k})$ DLYA~$0\le r < n$. v TAKOM SLUCHAE KAZHDYJ VOZMOZHNYJ NABOR
IZ $k$~CHISEL BUDET VSTRECHATXSYA V POSLEDOVATELXNOSTI SAMOE BOLXSHEE ODIN RAZ.
v KONCE KONCOV PROCESS OSTANOVITSYA, KOGDA MY DOSTIGNEM TAKOGO
ZNACHENIYA~$n$, CHTO~$(X_{n+1},~\ldots, X_{n+k-1}, y)$ UZHE VSTRECHALSYA V
POSLEDOVATELXNOSTI DLYA VSEH~$y$, $0\le y < m$. nAPRIMER, ESLI~$m=k=3$,
POSLEDOVATELXNOSTX TAKOVA:
$$
00022212202112102012001110100
$$
I NA |TOM PROCESS OSTANAVLIVAETSYA. a)~dOKAZHITE, CHTO, KOGDA
POSLEDOVATELXNOSTX ZAKANCHIVAETSYA, MY IMEEM~$X_{n+1}=\ldots=X_{n+k-1}=0$.
b)~dOKAZHITE, CHTO \emph{KAZHDYJ} $k\hbox{-NABOR}$ $(a_1, a_2,~\ldots, a_k)$
|LEMENTOV~$a_j$, $0\le a_j<m$, VSTRECHAETSYA V POSLEDOVATELXNOSTI.
sLEDOVATELXNO, ONA ZAKANCHIVAETSYA, KOGDA~$n=m^k$. [\emph{uKAZANIE.}
dOKAZHITE INDUKCIEJ PO~$s$, CHTO POYAVLYAETSYA~$(a_1,~\ldots, a_s, 0,~\ldots, 0)$
S~$a_s\ne0$.] zAMETIM, CHTO ESLI TEPERX
OPREDELITX~$f(X_n,~\ldots, X_{n+k-1})=X_{n+k}$ DLYA~$1 \le n \le m^k$,
POLAGAYA~$X_{m^k+k}=0$, TO POLUCHIM FUNKCIYU S MAKSIMALXNO VOZMOZHNYM PERIODOM.

\ex[m22] pUSTX~$Y_n$---POSLEDOVATELXNOSTX BITOV, POLUCHENNAYA
METODOM~(10) PRI~$k=35$ I~$c=(00000000000000000000000000000000101)_2$.
pUSTX~$U_n$---DVOICHNAYA DROBX~$(.Y_{nk}Y_{nk+1}\ldots{}Y_{nk+k-1})$. pOKAZHITE,
CHTO |TA POSLEDOVATELXNOSTX~$\<U_n>$ NE UDOVLETVORYAET TESTU~3.3.2D PRI~$d=8$.

\ex[M41] nAJDITE DLYA KAZHDOGO PROSTOGO~$p$ IZ PERVOGO STOLBCA TABL.~1 V
P.~4.5.4 PODHODYASHCHIE (V SMYSLE, UKAZANNOM V TEKSTE) KONSTANTY~$a_1$, $a_2$,
TAKIE,  CHTO DLINA PERIODA~(8) PRI~$k=2$ RAVNA~$p^2-1$.

\ex[m40] vYCHISLITE KONSTANTY~$c$, UDOBNYE DLYA ISPOLXZOVANIYA IH V
METODE~(10), IMEYUSHCHIE PRIMERNO ODINAKOVOE CHISLO NULEJ I EDINIC,
DLYA~$1\le k \le 64$.

\ex[m35] (d. rIS.) v TEKSTE OB�YASNYAETSYA, KAK NAHODITX FUNKCII~$f$, TAKIE,
CHTO U POSLEDOVATELXNOSTI~(11) DLINA PERIODA RAVNA~$m^k-1$ PRI USLOVII,
CHTO~$m$---PROSTOE CHISLO, A~$X_0$,~\dots, $X_{k-1}$ OTLICHNY OT NULYA. pOKAZHITE,
CHTO |TI FUNKCII MOZHNO MODIFICIROVATX, CHTOBY POLUCHITX POSLEDOVATELXNOSTI VIDA~(11)
%% 51
S DLINOJ PERIODA~$m^k$ DLYA \emph{VSEH}~$m$. [\emph{uKAZANIE.}
vOSPOLXZUJTESX LEMMOJ~3.2.1.2Q, ISKUSSTVENNYM PRIEMOM UPR.~7 I
POSLEDOVATELXNOSTYAMI VIDA~$\<pX_{2n}+X_{2n+1}>$.]

\rex[m24] v TEKSTE OBSUZHDENIE OBOBSHCHENNYH LINEJNYH
POSLEDOVATELXNOSTEJ~(8) OGRANICHIVAETSYA SLUCHAEM, KOGDA~$m$---PROSTOE CHISLO.
dOKAZHITE, CHTO DOSTATOCHNO BOLXSHIE PERIODY MOZHNO POLUCHITX, KOGDA~$m$
"SVOBODNO OT KVADRATOV", T.~E.\ PREDSTAVLYAETSYA V VIDE PROIZVEDENIYA
RAZLICHNYH PROSTYH CHISEL. (pROVERKA TABL.~3.2.1.1-1 POKAZYVAET,
CHTO~$m=w\pm1$ CHASTO UDOVLETVORYAET |TOJ GIPOTEZE. mNOGIE REZULXTATY,
POLUCHENNYE V TEKSTE, MOZHNO PO|TOMU PRIMENYATX I V |TOM SLUCHAE, NESKOLXKO
BOLEE UDOBNOM DLYA VYCHISLENIJ.)

%% 52
\subchap{statisticheskie testy} % 3.3
nASHA OSNOVNAYA ZADACHA SOSTOIT V POLUCHENII POSLEDOVATELXNOSTEJ, KOTORYE
POHOZHI NA SLUCHAJNYE. mY UZHE VIDELI, KAK DOBITXSYA TAKOGO BOLXSHOGO PERIODA
POSLEDOVATELXNOSTI, CHTOBY V PRAKTICHESKIH ZADACHAH ISKLYUCHITX VOZMOZHNOSTX EE
POVTORENIYA. hOTYA |TO I VAZHNO, NO BOLXSHOJ PERIOD ESHCHE VOVSE NE OZNACHAET, CHTO
POSLEDOVATELXNOSTX HOROSHA DLYA RABOTY. kAK ZHE RESHATX, DOSTATOCHNO LI
SLUCHAJNA POSLEDOVATELXNOSTX?

eSLI DATX LYUBOMU CHELOVEKU KARANDASH I BUMAGU I POPROSITX EGO NAPISATX
100~SLUCHAJNYH DESYATICHNYH CIFR, OCHENX MALO SHANSOV NA TO, CHTO ON
DOSTATOCHNO HOROSHO SMOZHET S |TIM SPRAVITXSYA. lYUDI STREMYATSYA IZBEGATX
KOMBINACIJ, KAZHUSHCHIHSYA IM NESLUCHAJNYMI, TAKIH, KAK PARY ODINAKOVYH
SOSEDNIH CIFR (HOTYA PRIMERNO KAZHDAYA IZ 10~CIFR DOLZHNA SOVPADATX S
PREDYDUSHCHEJ). pO|TOMU, UVIDEV TABLICU DEJSTVITELXNO SLUCHAJNYH CHISEL,
LYUBOJ CHELOVEK SKOREE VSEGO SKAZHET, CHTO ONI SOVSEM NE SLUCHAJNYE, EGO GLAZ
SRAZU ZHE OTMETIT NEKOTORYE VIDIMYE ZAKONOMERNOSTI.

kAK ZAMETIL D-R~mATRICA (CITIRUETSYA PO RABOTE m.~Gardner, {\sl Scientific
American,\/} YANVARX, 1965), "MATEMATIKI RASSMATRIVAYUT DESYATICHNOE
PREDSTAVLENIE CHISLA~$\pi$ KAK SLUCHAJNYJ RYAD, TOGDA KAK DLYA SOVREMENNOGO
TOLKOVATELYA CHISEL---|TO KLADEZX ZAMECHATELXNYH ZAKONOMERNOSTEJ". d-R~mATRICA
UKAZAL, NAPRIMER, CHTO PERVOE POVTORYAYUSHCHEESYA DVUZNACHNOE CHISLO V
RAZLOZHENII~$\pi$---|TO 26, A VTOROE EGO POYAVLENIE PRIHODITSYA TOCHNO
POSEREDINE ODNOJ LYUBOPYTNOJ KONFIGURACII:
\picture{(1) p. 52}
vYPISAV OKOLO DYUZHINY DRUGIH SVOJSTV |TIH CIFR, ON OBNARUZHIL, CHTO, BUDUCHI
PRAVILXNO INTERPRETIROVANO, CHISLO~$\pi$ OTRAZHAET VSYU ISTORIYU CHELOVECHESTVA!

vSE MY VYDELYAEM OSOBENNOSTI TELEFONNYH NOMEROV, NOMERNYH ZNAKOV MASHIN I
T.~D., CHTOBY LEGCHE IH ZAPOMNITX. gLAVNAYA MYSLX VSEGO SKAZANNOGO
ZAKLYUCHAETSYA V TOM, CHTO MY NE MOZHEM DOVERYATX SEBE V OCENKE, SLUCHAJNA ILI
NET DANNAYA POSLEDOVATELXNOSTX CHISEL. nEOBHODIMO ISPOLXZOVATX KAKIE-TO
NEPREDVZYATYE MEHANICHESKIE TESTY.

%% 53

sTATISTICHESKAYA TEORIYA DAET NAM NEKOTORYE KOLICHESTVENNYE KRITERII
SLUCHAJNOSTI. vOZMOZHNYM ZHE TESTAM BUKVALXNO NET KONCA. mY OBSUDIM TOLXKO
TE IZ NIH, KOTORYE, BUDUCHI NAIBOLEE POLEZNYMI I POUCHITELXNYMI,
ODNOVREMENNO LEGKO REALIZUYUTSYA NA VYCHISLITELXNYH MASHINAH.

eSLI POSLEDOVATELXNOSTX VEDET SEBYA UDOVLETVORITELXNO OTNOSITELXNO
TESTOV~$T_1$, $T_2$,~\dots{}, $T_n$, MY NE MOZHEM BYTX \emph{UVERENY} V TOM,
 CHTO ONA VYDERZHIT, I SLEDUYUSHCHEE ISPYTANIE~$T_{n+1}$. oDNAKO KAZHDYJ TEST
DAET NAM VSE BOLXSHE I BOLXSHE UVERENNOSTI V SLUCHAJNOSTI POSLEDOVATELXNOSTI.
oBYCHNO POSLEDOVATELXNOSTX PROVERYAETSYA S POMOSHCHXYU POLUDYUZHINY RAZNYH TESTOV.
eSLI IH REZULXTATY OKAZYVAYUTSYA UDOVLETVORITELXNYMI, MY SCHITAEM EE
SLUCHAJNOJ (ONA SCHITAETSYA NEVINOVNOJ DO TEH POR, POKA NE DOKAZANA EE VINOVNOSTX).

kAZHDUYU POSLEDOVATELXNOSTX, KOTORAYA BUDET INTENSIVNO ISPOLXZOVATXSYA,
SLEDUET TSHCHATELXNO PROVERITX. pO|TOMU V SLEDUYUSHCHIH RAZDELAH OB�YASNYAETSYA,
KAK PRAVILXNO PROVODITX TAKUYU PROVERKU. rAZLICHAYUTSYA DVA SORTA TESTOV:
\dfn{|MPIRICHESKIE TESTY,} KOGDA MASHINA MANIPULIRUET S GRUPPAMI CHISEL
POSLEDOVATELXNOSTI I PROIZVODIT OCENKU S POMOSHCHXYU OPREDELENNYH
STATISTICHESKIH KRITERIEV, I \dfn{TEORETICHESKIE TESTY,} KOGDA MY NAHODIM
NEKOTORYE HARAKTERISTIKI POSLEDOVATELXNOSTI, POLXZUYASX METODAMI
TEORII CHISEL, BAZIRUYUSHCHIMISYA NA REKURRENTNOM SOOTNOSHENII, S
POMOSHCHXYU KOTOROGO VYRABATYVAETSYA POSLEDOVATELXNOSTX. v KNIGE
d.~hAFFA [D.~Huff, How to Lie With Statistics, (Norton, 1954)]
CHITATELX MOZHET NAJTI RYAD DRUGIH REKOMENDACIJ.

\subsubchap{uNIVERSALXNYE TESTY DLYA ANALIZA SLUCHAJNYH POSLEDOVATELXNOSTEJ} % 3.3.1
\section{A. kRITERIJ~$\chi^2$}. kRITERIJ~$\chi^2$ ("HI-KVADRAT"), VEROYATNO,
SAMYJ RASPROSTRANENNYJ IZ VSEH STATISTICHESKIH KRITERIEV. oN ISPOLXZUETSYA
NE TOLXKO SAM PO SEBE, NO I KAK SOSTAVNAYA CHASTX MNOGIH DRUGIH TESTOV.
pREZHDE CHEM PRISTUPITX K OBSHCHEMU OPISANIYU KRITERIYA~$\chi^2$, RASSMOTRIM
SNACHALA V KACHESTVE PRIMERA, KAK MOZHNO BYLO BY PRIMENITX |TOT KRITERIJ DLYA
ANALIZA IGRY V KOSTI. pUSTX KAZHDYJ RAZ BROSAYUTSYA NEZAVISIMO DVE
"PRAVILXNYE" KOSTI, PRICHEM BROSANIE KAZHDOJ IZ NIH PRIVODIT S RAVNOJ
VEROYATNOSTXYU K VYPADENIYU ODNOGO IZ CHISEL~$1$, $2$, $3$, $4$, $5$ I~$6$.
vEROYATNOSTI VYPADENIYA LYUBOJ SUMMY s PRI ODNOM BROSANII PREDSTAVLENY V TABLICE:
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
sUMMA      &   s=&2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\cr
vEROYATNOSTX& p_s=&{1\over 36} & 1\over 18 & 1\over 12 & 1\over 9 & 5\over 36
                & 1\over 6 & 5 \over 36 & 1\over 9 & 1\over 12 & 1 \over 18
                & 1 \over 36 \cr
}}
\eqno(1)
$$(nAPRIMER, SUMMA s=4 MOZHET BYTX POLUCHENA TREMYA SPOSOBAMI:
%% 54
$1+3$, $2+2$, $3+1$; PRI $36$~VOZMOZHNYH ISHODAH |TO SOSTAVLYAET~$3/36=1/12=p_4$.)

eSLI BROSATX KOSTI $n$~RAZ, MOZHNO OZHIDATX, CHTO SUMMA~$s$ POYAVITSYA V
SREDNEM $np_s$~RAZ. nAPRIMER, PRI 144~BROSANIYAH ZNACHENIE~$4$ DOLZHNO
POYAVITXSYA OKOLO 12~RAZ. sLEDUYUSHCHAYA TABLICA POKAZYVAET, KAKIE REZULXTATY
BYLI V \emph{DEJSTVITELXNOSTI,} POLUCHENY PRI 144~BROSANIYAH.
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\bskip&&\bskip\hfil$#$\hfil\bskip\cr
sUMMA  &
     s=& 2 & 3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 \cr
fAKTICHESKOE CHISLO VYPADENIJ&
   Y_s=& 2 & 4 & 10 & 12 & 22 & 29 & 21 & 15 & 14 &  9 &  6\cr
sREDNEE CHISLO VYPADENIJ &
  np_s=& 4 & 8 & 12 & 16 & 20 & 24 & 20 & 16 & 12 &  8 &  4 \cr
}}
\eqno(2)
$$
oTMETIM, CHTO FAKTICHESKOE CHISLO VYPADENIJ OTLICHAETSYA OT SREDNEGO VO VSEH
SLUCHAYAH. v |TOM NET NICHEGO UDIVITELXNOGO. dELO V TOM, CHTO VSEGO IMEETSYA
$36{144}$~VOZMOZHNYH POSLEDOVATELXNOSTEJ ISHODOV DLYA 144~BROSANIJ, I VSE
ONI RAVNOVEROYATNY. oDNA IZ TAKIH POSLEDOVATELXNOSTEJ SOSTOIT, NAPRIMER,
TOLXKO IZ DVOEK ("ZMEINYE GLAZA"), I KAZHDYJ, U KOGO "ZMEINYE GLAZA"
VYPADUT PODRYAD 144~RAZA, BUDET UVEREN, CHTO KOSTI PODDELXNYE. mEZHDU TEM |TA
POSLEDOVATELXNOSTX TAK ZHE VEROYATNA, KAK I LYUBAYA DRUGAYA. kAKIM ZHE OBRAZOM
V TAKOM SLUCHAE MY MOZHEM PROVERITX, PRAVILXNO LI IZGOTOVLENA DANNAYA PARA
KOSTEJ? oTVET ZAKLYUCHAETSYA V TOM, CHTO SKAZATX OPREDELENNO "DA" ILI "NET"
MY NE MOZHEM, NO MOZHEM DATX \emph{VEROYATNOSTNYJ} OTVET, T.~E.~UKAZATX,
NASKOLXKO VEROYATNO ILI NEVEROYATNO DANNOE SOBYTIE.

eSTESTVENNYJ PUTX RESHENIYA NASHEJ ZADACHI SOSTOIT V SLEDUYUSHCHEM. vYCHISLIM
(PRIBEGNUV K POMOSHCHI evm) SUMMU KVADRATOV RAZNOSTEJ FAKTICHESKOGO CHISLA
VYPADENIJ~$Y_s$ I SREDNEGO CHISLA VYPADENIJ~$np_s$ (SM.~(2)):
$$
V=(Y_2-np_2)^2+(Y_3-np_3)^2+\cdots+(Y_{12}-np_{12})^2.
\eqno(3)
$$
dLYA PLOHOGO KOMPLEKTA KOSTEJ DOLZHNY POLUCHATXSYA OTNOSITELXNO VYSOKIE
ZNACHENIYA~$V$. vOZNIKAET VOPROS, NASKOLXKO VEROYATNY TAKIE VYSOKIE ZNACHENIYA?
eSLI VEROYATNOSTX IH POYAVLENIYA OCHENX MALA, SKAZHEM RAVNA~$1/100$,---T.~E.\
OTKLONENIE REZULXTATA OT SREDNEGO ZNACHENIYA NA TAKUYU BOLXSHUYU VELICHINU
VOZMOZHNO TOLXKO V ODNOM SLUCHAE IZ~$100$,---TO U NAS ESTX OPREDELENNYE
OSNOVANIYA DLYA PODOZRENIJ. (nE SLEDUET ZABYVATX, ODNAKO, CHTO DAZHE
\emph{HOROSHIE} KOSTI BUDUT DAVATX TAKOE VYSOKOE ZNACHENIE~$V$ ODIN RAZ
IZ~100, TAK CHTO DLYA BOLXSHEJ UVERENNOSTI SLEDOVALO BY POVTORITX
|KSPERIMENT I POSMOTRETX, POLUCHITSYA LI POVTORNO VYSOKOE ZNACHENIE~$V$.)

v STATISTIKU~$V$ VSE KVADRATY RAZNOSTEJ VHODYAT S RAVNYM VESOM,
HOTYA~$(Y_7-np_7)^2$, NAPRIMER, VEROYATNO, BUDET NAMNOGO BOLXSHE,
CHEM~$(Y_2-np_2)^2$, TAK KAK~$s=7$ VSTRECHAETSYA V SHESTX RAZ CHASHCHE,
%% 55
CHEM~$s=2$. oKAZYVAETSYA, CHTO V "PRAVILXNUYU" STATISTIKU, ILI PO KRAJNEJ MERE
TAKUYU, DLYA KOTOROJ DOKAZANO, CHTO ONA NAIBOLEE ZNACHIMA, CHLEN~$(Y_7-np_7)^2$
VHODIT S MNOZHITELEM, KOTORYJ V SHESTX RAZ MENXSHE MNOZHITELYA
PRI~$(Y_2-np_2)^2$. tAKIM OBRAZOM, SLEDUET ZAMENITX~(3) NA SLEDUYUSHCHUYU FORMULU:
$$
V={(Y_2-np_2)^2 \over np_2}+{(Y_3-np_3)^2\over np_3}+\cdots+{(Y_{12}-np_{12})^2\over np_{12}}.
\eqno(4)
$$
oPREDELENNUYU TAKIM OBRAZOM VELICHINU~$V$ NAZYVAYUT STATISTIKOJ~$\chi^2$,
SOOTVETSTVUYUSHCHEJ ZNACHENIYAM~$Y_2$,~\dots, $Y_{12}$, POLUCHENNYM V |KSPERIMENTE.
pODSTAVLYAYA V |TU FORMULU ZNACHENIYA IZ~(2), POLUCHAEM
$$
V={(2-4)^2\over 4}+{(4-8)^2\over 8}+\cdots+{(9-8)^2\over 8}+{(6-4)^2\over4}=7{7\over 48}.
\eqno(5)
$$
tEPERX, ESTESTVENNO, VOZNIKAET VOPROS, YAVLYAETSYA LI ZNACHENIE~$7{7\over48}$
NASTOLXKO BOLXSHIM, CHTO EGO SLUCHAJNOE POYAVLENIE MOZHNO SCHITATX MALOVEROYATNYM.
pREZHDE CHEM OTVECHATX NA |TOT VOPROS, SFORMULIRUEM KRITERIJ~$\chi^2$ V
BOLEE OBSHCHEM VIDE.

pREDPOLOZHIM, CHTO VSE VOZMOZHNYE REZULXTATY ISPYTANIJ RAZDELENY NA
$k$~KATEGORIJ. pROVODITSYA  $n$~\dfn{NEZAVISIMYH ISPYTANIJ;}
|TO OZNACHAET, CHTO ISHOD KAZHDOGO ISPYTANIYA ABSOLYUTNO NE VLIYAET NA ISHOD
OSTALXNYH. pUSTX~$p_s$---VEROYATNOSTX TOGO, CHTO REZULXTAT ISPYTANIYA POPADET V
KATEGORIYU~$s$, I PUSTX~$Y_s$---CHISLO ISPYTANIJ, KOTORYE DEJSTVITELXNO
\emph{POPALI} V KATEGORIYU~$s$. sFORMIRUEM STATISTIKU
$$
V=\sum_{1\le s\le k} {(Y_s-np_s)^2\over np_s}.
\eqno(6)
$$

v PREDYDUSHCHEM PRIMERE IMELOSX $11$~VOZMOZHNYH ISHODOV PRI KAZHDOM BROSANII
KOSTEJ, TAK CHTO~$k=11$. [fORMULY~(4) I~(6) RAZLICHAYUTSYA TOLXKO
NUMERACIEJ: V ODNOM SLUCHAE ONA PROIZVODITSYA OT~2 DO~12, A V DRUGOM---OT~$1$ DO~$k$.]

iSPOLXZUYA TOZHDESTVO~$(Y_s-np_s)^2=Y_s^2-2np_sY_s+n^2p_s^2$ I RAVENSTVA
$$
\eqalign{
Y_1+Y_2+\cdots+Y_k&=n,\cr
p_1+p_2+\cdots+p_k&=1,\cr
}
\eqno(7)
$$
MOZHNO PREOBRAZOVATX FORMULU~(6) K VIDU
$$
V={1\over n}\sum_{1\le s \le k} \left({Y_s^2\over p_s}\right)-n,
\eqno(8)
$$
PRICHEM V BOLXSHINSTVE SLUCHAEV TAKAYA ZAPISX OBLEGCHAET VYCHISLENIYA.

vERNEMSYA K VOPROSU O TOM, KAKIE ZNACHENIYA~$V$ MOZHNO SCHITATX RAZUMNYMI.
oTVET NA |TO DAET TABL.~1, V KOTOROJ PRIVEDENO "RASPREDELENIE~$\chi^2$ S
$\nu$~STEPENYAMI SVOBODY" PRI RAZNYH ZNACHENIYAH~$\nu$. sLEDUET POLXZOVATXSYA
STROKOJ TABLICY S~$\nu=k-1$; \emph{CHISLO "STEPENEJ SVOBODY" RAVNO~$k-1$,
T.~E.\ NA EDINICU MENXSHE CHISLA KATEGORIJ.}
%% 56
{\everycr={\noalign{\hrule}}
\htable{tABLICA~1}%
{nEKOTORYE DANNYE DLYA RASPREDELENIYA~$\chi^2$}%
{\offinterlineskip
\strut\vrule\bskip$#$\bskip\hfil\vrule&&\bskip\hfil$#$\bskip\hfil\vrule\cr
\noalign{
\embedpar{
\noindent
(bOLEE POLNYE TABLICY SM. V Handbook of Mathematical Functions, ed.\
 by M.~Abramowitz and I.~A.~Stegun, U.~S. Government Printing Office, 1964,
Table~26.8)
}
}
       & p=99\%  & p=95\%  & p=75\% & p=50\% & p=25\%& p=5\% & p=1\% \cr
\nu=1  & 0.00016 & 0.00393 & 0.1015 & 0.4549 & 1.323 & 3.841 & 6.635\cr
\nu=2  & 0.00201 & 0.1026  & 0.5753 & 1.386  & 2.773 & 5.991 & 9.210\cr
\nu=3  & 0.1148  & 0.3518  & 1.213  & 2.366  & 4.108 & 7.815 & 11,34\cr
\nu=4  & 0.2971  & 0.7107  & 1.923  & 3.357  & 5.385 & 9.488 & 13.28\cr
\nu=5  & 0.5543  & 1.1455  & 2.675  & 4.351  & 6.626 & 11.07 & 15.09\cr
\nu=6  & 0.8720  & 1.635   & 3.455  & 5.348  & 7.841 & 12.59 & 16.81\cr
\nu=7  & 1.239   & 2.167   & 4.255  & 6.346  & 9.037 & 14.07 & 18.48\cr
\nu=8  & 1.646   & 2.733   & 5.071  & 7.344  & 10.22 & 15.51 & 20.09\cr
\nu=9  & 2.088   & 3.325   & 5.899  & 8.343  & 11.39 & 16.92 & 21.67\cr
\nu=10 & 2.558   & 3.940   & 6.737  & 9.342  & 12.55 & 18.31 & 23.21\cr
\nu=11 & 3.053   & 4.575   & 7.584  & 10.34  & 13.70 & 19.68 & 24.73\cr
\nu=12 & 3.571   & 5.226   & 8.438  & 11.34  & 14.84 & 21.03 & 26.22\cr
\nu=15 & 5.229   & 7.261   & 11.04  & 14.34  & 18.25 & 25.00 & 30.58\cr
\nu=20 & 8.260   & 10.85   & 15.45  & 19.34  & 23.83 & 31.41 & 37.57\cr
\nu=30 & 14.95   & 18.49   & 24.48  & 29.34  & 34.80 & 43.77 & 50.89\cr
\nu=50 & 29.71   & 34.76   & 42.94  & 49.33  & 56.33 & 67.50 & 76.15\cr
\nu>30 & \multispan{7} \hfil\emph{PRIBLIZITELXNO~$\nu+2\sqrt{\nu}x_p+{4\over3}x^2_p-{2\over3}$\hfil}\vrule\cr
x_p=   & -2.33   & -1.64   & -.675  & 0.00   & 0.675 & 1.64  & 2.33\cr
}}
(nA INTUITIVNOM UROVNE |TO MOZHNO POYASNITX SLEDUYUSHCHIM OBRAZOM:
ZNACHENIYA~$Y_1$, $Y_2$,~\dots, $Y_k$ NE SOVSEM NEZAVISIMY, TAK KAK~$Y_1$,
SOGLASNO~(7), MOZHNO VYCHISLITX, ZNAYA~$Y_2$,~\dots, $Y_k$. sLEDOVATELXNO,
IMEETSYA $k-1$~STEPENEJ SVOBODY. bOLEE STROGAYA ARGUMENTACIYA BUDET
PRIVEDENA NIZHE.)

eSLI V TABLICE V STROKE~$\nu$ I KOLONKE~$p$ NAHODITSYA CHISLO~$x$, TO |TO
OZNACHAET, CHTO ZNACHENIE~$V$, OPREDELYAEMOE PO FORMULE~(8), BUDET BOLXSHE~$x$
S VEROYATNOSTXYU~$p$. nAPRIMER, DLYA~$p=5$\% I~$\nu=10$ TABLICA DAET
ZNACHENIE~$x=18.31$; |TO OZNACHAET, CHTO~$V>18.31$ TOLXKO V~$5$\% VSEH SLUCHAEV.

pREDPOLOZHIM, CHTO OPISANNYJ PROCESS BROSANIYA KOSTEJ MODELIRUETSYA NA evm S
POMOSHCHXYU POSLEDOVATELXNOSTI CHISEL, KOTORYE
%% 57
PREDPOLAGAYUTSYA SLUCHAJNYMI, I CHTO POLUCHENY SLEDUYUSHCHIE REZULXTATY:
$$
\vcenter{
\halign{#\bskip\hfil&\bskip\hfil$#{}$&$#$\bskip\hfil&&\bskip\hfil$#$\bskip\cr
              &   s=& 2 &  3&  4&  5&  6&  7&  8&  9& 10& 11& 12\cr
eKSPERIMENT~1 & Y_s=& 4 & 10& 10& 13& 20& 18& 18& 11& 13& 14& 13\cr
eKSPERIMENT~2 & Y_s=& 3 &  7& 11& 15& 19& 24& 21& 17& 13&  9&  5\cr
}
}
\eqno(9)
$$
vYCHISLYAYA STATISTIKU KRITERIYA~$\chi^2$, POLUCHAEM V PERVOM
SLUCHAE $V_1=29{59\over 120}$, A VO VTOROM SLUCHAE~$V_2=1{17\over 120}$.
tABLICHNYE ZNACHENIYA, SOOTVETSTVUYUSHCHIE $10$~STEPENYAM SVOBODY, POKAZYVAYUT,
CHTO~$V_1$ \emph{YAVNO SLISHKOM, VELIKO;} $V$~BYVAET BOLXSHE, CHEM~$23.2$,
TOLXKO V ODNOM PROCENTE SLUCHAEV! (bOLEE POLNYE TABLICY POKAZYVAYUT, CHTO
VEROYATNOSTX POYAVLENIYA STOLX BOLXSHOGO ZNACHENIYA~$V$ RAVNA~$0.1$\%.)
tAKIM OBRAZOM, V |KSPERIMENTE~1 ZAREGISTRIROVANO ZNACHITELXNOE OTKLONENIE
OT NORMY.

s DRUGOJ STORONY, $V_2$ OCHENX MALO, POTOMU CHTO~$Y_s$ V |KSPERIMENTE~2
OKAZALISX OCHENX BLIZKI K SREDNIM ZNACHENIYAM~$np_s$ [SR.~S~(2)]. iZ TABLICY
RASPREDELENIYA~$\chi^2$ SLEDUET, CHTO V~$99$\% SLUCHAEV $V$~DOLZHNO BYTX
BOLXSHE, CHEM~$2.56$. zNACHENIE~$V_2$ \emph{YAVNO SLISHKOM MALO;} POLUCHENNYE V
|KSPERIMENTE ZNACHENIYA~$V_3$
%% ?? V_s
NASTOLXKO BLIZKI K SREDNEM ZNACHENIYAM, CHTO NEVOZMOZHNO SCHITATX |TOT
|KSPERIMENT SLUCHAJNYM ISPYTANIEM. (v SAMOM DELE, IZ BOLEE POLNYH
TABLIC SLEDUET, CHTO PRI $10$~STEPENYAH SVOBODY TAKIE NIZKIE
ZNACHENIYA~$V$ VSTRECHAYUTSYA TOLXKO V $0.03$\%~SLUCHAEV). nAKONEC, S POMOSHCHXYU
TABLICY RASPREDELENIYA~$\chi^2$ MOZHNO PROVERITX POLUCHENNOE NAMI V~(5)
ZNACHENIE~$V=7{7\over 48}$. oNO POPADAET V INTERVAL MEZHDU~$75$ I~$50$\%,
TAK CHTO MY NE MOZHEM SCHITATX EGO SLISHKOM VYSOKIM ILI SLISHKOM NIZKIM; DANNYE,
PREDSTAVLENNYE V~(2), UDOVLETVORYAYUT KRITERIYU~$\chi^2$.

bOLXSHIM PREIMUSHCHESTVOM RASSMATRIVAEMOGO METODA YAVLYAETSYA TO, CHTO ODNI I TE
ZHE TABLICHNYE ZNACHENIYA ISPOLXZUYUTSYA PRI LYUBYH~$n$ I LYUBYH
VEROYATNOSTYAH~$p_s$. eDINSTVENNOJ PEREMENNOJ YAVLYAETSYA~$\nu=k-1$. nA SAMOM
DELE PRIVEDENNYE V TABLICE ZNACHENIE NE YAVLYAYUTSYA ABSOLYUTNO TOCHNYMI VO VSEH
SLUCHAYAH: \emph{|TO PRIBLIZHENNYE ZNACHENIYA, SPRAVEDLIVYE LISHX PRI DOSTATOCHNO
BOLXSHIH ZNACHENIYAH~$n$.} kAK VELIKO DOLZHNO BYTX~$n$? dOSTATOCHNO
BOLXSHIMI MOZHNO SCHITATX TAKIE ZNACHENIYA~$n$, PRI KOTORYH LYUBOE IZ~$np_s$
NE MENXSHE~$5$; ODNAKO LUCHSHE BRATX~$n$ ZNACHITELXNO BOLXSHIMI, CHTOBY POVYSITX
NADEZHNOSTX KRITERIYA. zAMETIM, CHTO V RASSMOTRENNYH PRIMERAH MY
BRALI~$n=144$, I $np_2$~RAVNYALOSX VSEGO~$4$, CHTO PROTIVORECHIT TOLXKO CHTO
SFORMULIROVANNOMU PRAVILU. eDINSTVENNAYA PRICHINA |TOGO NARUSHENIYA KROETSYA
V TOM, CHTO AVTORU NADOELO BROSATX KOSTI; V REZULXTATE CHISLA IZ TABLICY
OKAZALISX NE OCHENX PODHODYASHCHIMI DLYA NASHEGO SLUCHAYA. bYLO BY GORAZDA LUCHSHE
PROVESTI |TI |KSPERIMENTY NA MASHINE PRI~$n=1000$ ILI~$10\,000$,
ILI DAZHE~$100\,000$.

%% 58

nA SAMOM DELE VOPROS O VYBORE~$n$ NE TAK PROST. eSLI BY KOSTI BYLI
DEJSTVITELXNO NEPRAVILXNYE, |TO PROYAVLYALOSX BY PRI SKOLX UGODNO
BOLXSHIH~$n$ (SM.~UPR.~12). nO PRI BOLXSHIH ZNACHENIYAH~$n$ MOGUT SGLAZHIVATXSYA
\emph{LOKALXNYE} OTKLONENIYA, TAKIE, KAK SLEDUYUSHCHIE DRUG ZA DRUGOM BLOKI
CHISEL S SILXNYM SISTEMATICHESKIM SMESHCHENIEM V PROTIVOPOLOZHNYE STORONY. pRI
DEJSTVITELXNOM BROSANII KOSTEJ |TOGO MOZHNO NE OPASATXSYA, TAK KAK
VSE VREMYA ISPOLXZUYUTSYA ODNI I TE ZHE KOSTI, NO ESLI RECHX IDET
O POSLEDOVATELXNOSTI CHISEL, POLUCHENNYH NA evm, TO TAKOJ TIP OTKLONENIYA OT
SLUCHAJNOGO POVEDENIYA VPOLNE VOZMOZHEN. v SVYAZI
\picture{
 rIS.~2. rEZULXTATY 90~PROVEROK S ISPOLXZOVANIEM KRITERIYA~$\chi^2$ (SR. S~RIS.~5).
}
S |TIM ZHELATELXNO PROVODITX PROVERKU S POMOSHCHXYU KRITERIYA~$\chi^2$ PRI
RAZNYH ZNACHENIYAH~$n$, NO V LYUBOM SLUCHAE |TI ZNACHENIYA DOLZHNY BYTX
DOVOLXNO BOLXSHIMI.

iTAK, PROVERKA S POMOSHCHXYU KRITERIYA~$\chi^2$ ZAKLYUCHAETSYA V SLEDUYUSHCHEM.
pROVODITSYA $n$~NEZAVISIMYH ISPYTANIJ, GDE~$n$---DOSTATOCHNO BOLXSHOE CHISLO.
(sLEDUET IZBEGATX PRIMENENIYA KRITERIYA~$\chi^2$ V SLUCHAYAH, ESLI ISPYTANIYA
NE NEZAVISIMY; SM., NAPRIMER, UPR.~10, GDE RASSMOTREN SLUCHAJ, KOGDA ODNA
POLOVINA SOBYTIJ ZAVISIT OT DRUGOJ.) pODSCHITYVAETSYA CHISLO ISPYTANIJ,
REZULXTAT KOTORYH OTNOSITSYA K KAZHDOJ IZ $k$~KATEGORIJ, I PO FORMULAM~(6)
ILI~(8) VYCHISLYAETSYA ZNACHENIE~$V$. zATEM~$V$ SRAVNIVAETSYA S CHISLAMI
IZ TABL.~1 PRI~$\nu=k-1$. eSLI $V$~MENXSHE ZNACHENIYA,
SOOTVETSTVUYUSHCHEGO~$p=99\%$, ILI BOLXSHE ZNACHENIYA, SOOTVETSTVUYUSHCHEGO~$p=1\%$,
TO REZULXTATY BRAKUYUTSYA KAK NEDOSTATOCHNO SLUCHAJNYE. eSLI~$p$
%% 59
LEZHIT MEZHDU~99 I~95\% ILI MEZHDU~5 I~1\%, TO REZULXTATY SCHITAYUTSYA
"PODOZRITELXNYMI"; PRI ZNACHENIYAH~$p$, POLUCHENNYH INTERPOLYACIEJ PO
TABLICE, ZAKLYUCHENNYH MEZHDU~$95$ I~$90$\% ILI~$10$ I~$5$\%, REZULXTATY
"SLEGKA PODOZRITELXNY". chASTO S POMOSHCHXYU KRITERIYA~$\chi^2$ PROVERYAYUT PO
KRAJNEJ MERE TRI RAZA RAZNYE CHASTI ISSLEDUEMOGO RYADA CHISEL, I, ESLI NE
MENEE DVUH RAZ IZ TREH REZULXTATY OKAZYVAYUTSYA PODOZRITELXNYMI, CHISLA
OTBRASYVAYUTSYA KAK NEDOSTATOCHNO SLUCHAJNYE.

rASSMOTRIM V KACHESTVE PRIMERA RIS.~2, GDE SHEMATICHESKI PREDSTAVLENY
REZULXTATY PROVERKI S POMOSHCHXYU KRITERIYA~$\chi^2$ SHESTI POSLEDOVATELXNOSTEJ
SLUCHAJNYH CHISEL. dLYA KAZHDOJ POSLEDOVATELXNOSTI DELALOSX PYATX RAZNYH
PROVEROK (OSNOVANNYH NA KRITERII~$\chi^2$), KAZHDAYA IZ KOTORYH
POVTORYALASX NA TREH RAZNYH UCHASTKAH POSLEDOVATELXNOSTI. v DATCHIKE~A
ISPOLXZOVAN METOD mAKLARENA-mARSALXI (ALGORITM~3.2.2m), V DATCHIKE~E---METOD
fIBONACHCHI, OSTALXNYE DATCHIKI SOOTVETSTVUYUT LINEJNYM
KONGRU|NTNYM POSLEDOVATELXNOSTYAM SO SLEDUYUSHCHIMI PARAMETRAMI:
\ctable{#\hfil\bskip&\bskip # \hfil\cr
dATCHIK~v:& $X_0=0$, $a=3141592653$, $c=2718281829$, $m=2^{35}$.\cr
dATCHIK~C:& $X_0=0$, $a=2^7+1$, $c=1$, $m=2^{35}$.\cr
dATCHIK~D:& $X_0=47594118$, $a=23$, $c=0$,  $m=10^8+1$.\cr
dATCHIK~F:& $X_0=314159265$, $a=2^{18}+1$, $c=1$, $m=2^{35}$.\cr
}
rEZULXTATY, PRIVEDENNYE NA RIS.~2, POZVOLYAYUT SDELATX SLEDUYUSHCHIE VYVODY.
dATCHIKI~A, B, D PROSHLI ISPYTANIYA UDOVLETVORITELXNO, DATCHIK~C NAHODITSYA
NA GRANI I DOLZHEN BYTX, PO-VIDIMOMU, ZABRAKOVAN, A DATCHIKI~E I~F
OPREDELENNO NE PROSHLI ISPYTANIJ. dATCHIK~F, BEZUSLOVNO, MALOMOSHCHEN;
DATCHIKI~C I~D OBSUZHDALISX V LITERATURE, NO U NIH SLISHKOM MALO
ZNACHENIE~$a$. v DATCHIKE~D REALIZOVAN METOD VYCHETOV V TOM VIDE, V KAKOM
ON BYL VPERVYE PREDLOZHEN lEMEROM V~1948~G., A V DATCHIKE~C---LINEJNYJ
KONGRU|NTNYJ METOD S~$c\ne 0$ TAKZHE V EGO PERVONACHALXNOM VIDE (rOTENBERG, 1960).

nESKOLXKO DRUGOJ PODHOD K SUZHDENIYU O REZULXTATAH PROVERKI PO
KRITERIYU~$\chi^2$, BEZ ISPOLXZOVANIYA TAKIH PONYATIJ, KAK "PODOZRITELXNYJ",
"SLEGKA PODOZRITELXNYJ" I~T.~D., I MENEE POZVOLYAYUSHCHIJ POLAGATXSYA NA
MNENIE ad hoc, OPISYVAETSYA NIZHE V |TOM RAZDELE.

\section{B. kRITERIJ kOLMOGOROVA-sMIRNOVA (ks-KRITERIJ)}. kAK MY
VIDELI, KRITERIJ~$\chi^2$ PRIMENYAETSYA V TEH SLUCHAYAH, KOGDA REZULXTATY
ISPYTANIJ RASPADAYUTSYA NA KONECHNOE CHISLO $k$~KATEGORIJ. oDNAKO NEREDKO
SLUCHAJNYE VELICHINY MOGUT PRINIMATX BESKONECHNO MNOGO ZNACHENIJ. v CHASTNOSTI,
BESKONECHNO MNOGO ZNACHENIJ PRINIMAYUT VESHCHESTVENNYE SLUCHAJNYE CHISLA V
INTERVALE MEZHDU~$0$ I~$1$. hOTYA MNOZHESTVO ZNACHENIJ SLUCHAJNYH CHISEL,
POLUCHENNYH V
%%60
VYCHISLITELXNOJ MASHINE, NEIZBEZHNO OGRANICHENO, HOTELOSX BY, CHTOBY |TO NIKAK NE
SKAZYVALOSX NA REZULXTATAH RASCHETOV.

v TEORII VEROYATNOSTEJ I STATISTIKE PRINYATO ISPOLXZOVATX ODNI I TE ZHE
OBOZNACHENIYA PRI OPISANII DISKRETNYH I NEPRERYVNYH RASPREDELENIJ. pUSTX
TREBUETSYA OPISATX RASPREDELENIE ZNACHENIJ SLUCHAJNOJ VELICHINY~$X$. eTO
DELAETSYA S POMOSHCHXYU \dfn{FUNKCII RASPREDELENIYA~$F(x)$,} GDE
$$
F (x) = \hbox{VEROYATNOSTX TOGO, CHTO~$(X\le x)$.}
$$
nA RIS.~3 PREDSTAVLENY TRI PRIMERA. pERVYJ IZ NIH---FUNKCIYA RASPREDELENIYA
\emph{SLUCHAJNOGO BITA,} T.~E.\ SLUCHAJNOJ VELICHINY~$X$,
\picture{rIS.~3. pRIMERY FUNKCIJ RASPREDELENIYA.}
PRINIMAYUSHCHEJ ZNACHENIYA~$0$ ILI~$1$, KAZHDOE S VEROYATNOSTXYU~$1/2$. nA RIS.~3,~b
POKAZANA FUNKCIYA RASPREDELENIYA \emph{VESHCHESTVENNOJ SLUCHAJNOJ VELICHINY,
RAVNOMERNO RASPREDELENNOJ} MEZHDU NULEM I EDINICEJ, TAK CHTO VEROYATNOSTX
TOGO, CHTO~$X\le x$, PROSTO RAVNA~$x$, ESLI~$0\le x \le 1$. nAPRIMER,
VEROYATNOSTX TOGO, CHTO~$X\le{2\over3}$, RAVNA~$2\over3$.
nA RIS.~3,~c POKAZANO PREDELXNOE RASPREDELENIE ZNACHENIJ~$V$
V KRITERII~$\chi^2$ (PRI 10~STEPENYAH SVOBODY); |TO ZHE RASPREDELENIE, NO V
DRUGOJ FORME, BYLO UZHE PREDSTAVLENO V TABL.~1. zAMETIM, CHTO~$F(x)$ VSEGDA
VOZRASTAET OT~$0$ DO~$1$ PRI UVELICHENII~$x$ OT~$-\infty$ DO~$+\infty$.

iSPOLXZUYA ZNACHENIYA~$X_1$, $X_2$,~\dots, $X_n$ SLUCHAJNOJ VELICHINY~$X$,
POLUCHENNYE V REZULXTATE NEZAVISIMYH ISPYTANIJ, MOZHNO POSTRO-
%% 61
\bye
