\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)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$, $y0$.} $$ 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~$\$ 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~$q2$. 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~$11$ 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~$12$,\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~$11$, 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~$\$ I~$\$ 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~$\$ I~$\$ |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~$\$ I~$\$ SOOTVETSTVENNO. \st[vYCHISLITX~$j$.] uSTANOVITX~$j\asg \floor{kY/m}$, GDE~$m$---MODULX, ISPOLXZUYUSHCHIJSYA V POSLEDOVATELXNOSTI~$\$. tAKIM OBRAZOM, $j$~PRINIMAET SLUCHAJNOE ZNACHENIE, OPREDELYAEMOE S POMOSHCHXYU~$Y$; $0 \le j $ I~$\$ 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~$$. 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}$ I~$\$ 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~$\$. 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~$\$, 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~$\$ IMEET DLINU PERIODA V TOCHNOSTI TAKUYU ZHE, KAK I SPECIALXNAYA POSLEDOVATELXNOSTX~$\$ 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~$\$ I~$\$--- 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~$\$ 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$ 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~$\$.] \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