Ковэю мен Макферсонның спектралды тестi кездейсоқтық талаптарын қандай мөлшерде қанағаттандырса, сондай дәрежеде кездейсоқ болатын Лехмердiң сызықты конгруэнттi тiзбегiнiң элементарлы құрылуы

Аңдатпа

Бiр қарағанда өз-өзiнен түсiнiктi болып көрiнетiн кездейсоқ сан мен кездейсоқ тiзбек ұғымдарының –
не қиындығы бар, бiрi бiрiнен кейiн ойға келген сандарды тiзiп жаза берсе болмай ма – дәл есептелiнетiн анықтамалары
берiлмей келедi. Осы жағдайда iс-жүзiнде әртүрлi кездейсоқ сандарды қатын ережелер – Генераторлар ұсынылады
да, соларды кездейсоқтыққа тексеретiн (тестiлейтiн) әдiстер жасалады. Мұндай «емтиханнан» өткен тiзбектер кездейсоқ
тiзбек деп, ал оның әрбiр мүшесi кездейсоқ сан деп жарияланады, нәтижесiнде қаншама тексеру тестi бар болса, соншама
кездейсоқтық түрi бар болып шығады.
Мақалада қойылымы және оның зерттеу тарихы Компьютерлiк ғылымдарының жоғары сатыларынан табылатын
десе де болатын мәселе зерттелiп, ғылыми тақырып ретiнде толығымен жабылған. Бұл қойылымда қарастырылатын ең
танымалыларының бiрi, тiптi ең танымаласы да болуы мүмкiн - 1949 жылғы Лехмер генераторы және «қолданыстағы
тестiлердiң ең нәтижелiсi» болып табылатын 1965 жылы берiлген Ковею мен Макферсонның спектралдық тестi.
Осылардың өзара байланыста 1969 жылдан бастап бүгiнгi күнге дейiн толықтырылып отырылған зерттеу жолы Дональд
Эрвин Кнуттың «Программалау өнерi» атты монографиясының барлық басылымдарында кеңiнен ашылған. Демек, бұл
тақырып әрдайым iзденiс үстiнде болып келедi.
Мiне, 50 жылдық тарихы бар уақыт өлшемiнде үнемi жетiлу жолында болып келсе және де осы уақытқа дейiнгi
белгiлi жетiстiк, νs кездейсотықтың негiзгi сандық сипаттамасына жасалған айтарлықтай мәлiмет бермейтiн бiржақты
жоғарыдан бағалауы ғана. Мақалада пессимистiк « s ≥ 10 болғанда νs дәлдiгiн есептеу өте қиын» деген болжамға
қарамастан күтiлмеген асимптотикалық теңдiк алынған. Бұл мәселенiң дұрыс қойылымы мен оның әрi қарай зерттеудi
қажет етпейтiн шешiмiн құрайды.
Максималды периодты Лехмердiң кездейсоқ сандарының генераторы немесе сызықтық конгруэнттi тiзбек деп бүтiн
терiс емес hXni сандардың
Xn+1 = (aXn + c) mod N, n ≥ 0, (0.1)
рекурренттi тiзбегi аталады. Мұндағы
N − модуль 0 < N, a − көбейткiш 0 ≤ a < N,
c − өсiмше 0 ≤ A < N, X0 − бастапқы мән 0 ≤ X0 < N.
Және де (0.1) рекурренттi тiзбегiне оны максималды периодты ететiн келесi шартар қойылады:
a > 1 , N > a , τ (a, N) ≥ 2 және 1 ≤ λ (a, N) ≡
(a−1)τ(a,N)
N < (a − 1)τ(a,N)−1
) бүтiн сандары (a − 1)τ(a,N) ≡ 0 (modN)
және (a − 1)τ(a,N)−1
6≡ 0 (modN) салыстыруларымен өзара байланысқан.
Әдеттегiдей, бұл жағдайда да, мәселе толығымен дәл қойылған математикалық есепке келтiрiледi (барлық
түсiндiрмелер мен талқылаулар мақала мәтiнiнде келтiрiлген): берiлген s ≥ 2 және τ ≥ 2 сандары мен өспелi N
үшiн (барлық параметрлер – оң бүтiн сандар)
νs (a, N) = inf



q
m2
1 + ... + m2
s
: m = (m1, ..., ms) ∈ Z
s
, m 6= 0,
Xs
j=0
mja
j−1 ≡ 0 (modN)



болғандағы
sup
νs (a, N) : 2 ≤ a < N, (a − 1)τ ≡ 0(modN), (a − 1)τ−1
6≡ 0(modN)

(0.2)
шамасының асимтотикасын табу.
Сонымен, мәселе барлық a, N және s үшiн νs(a, N) ≤ γ(s)N
1
s теңсiздiгi-ақ белгiлi болғанда, νs(a, N) шамасының
мәнi неғұрлым үлкен болатындай a = a(N) санын табу болып табылады. Әрине, кез келген жоғарғы баға сияқты бұл
да аса көтерiңкi болуы мүмкiн, сол себептi мәселенi шешпейдi.
Осы жұмыста барлық мүмкiндердi қамтып, сондықтан да зерттелудегi мәселенiң толық шешiмiмен қамтамасыз ететiн
s, τ және λ параметрлерiнiң қатынастарына тәуелдi асимптотикалық сипаттағы спектралдi тестiлеу (ST) бойынша жаңа
және оны толығымен жабатын нәтижелер алынды:
ST : ν2

a, N; (a − 1)2 = N

= (a − 1) s
1 − 2
a − 2
(a − 1)2 =
√
N
s
1 − 2
√
N − 1
N
,
ST (2 ≤ s = τ) : N
1
s

1 − (bs − 1) N
− 1
s

= a − bs ≤ νs (a, N; (a − 1)s = N) ≤
≤
p
a
2 + 1 = N
1
s
q
1 + 2N
− 1
s + 2N
− 2
s ,
ST (2 ≤ s < τ, λ ≥ 1) : (Nλ)
1
τ

1 − (bs − 1) (Nλ)
− 1
τ

= (a − bτ ) ≤
≤ νs

a, N; (a − 1)τ = Nλ, 1 ≤ λ ≤ (a − 1)τ−s

≤
p
a
2 + 1 = (Nλ)
1
τ
q
1 + 2 (Nλ)
− 1
τ + 2 (Nλ)
− 2
τ ,
ST (s > τ ≥ 2, λ ≥ 1) : νs (a, N; (a − 1)τ = Nλ, λ ≥ 1) ≤
vuutXτ
k=0
τ
k
2
,
мұндағы (−bm) оң бүтiн саны a -ның дәрежелерi бойынша жiктелген (a − 1) m көпмүшелiгiнiң терiс мәндi
биноминалдық коэффициенттерiнiң абсолюттi шамаларының ең үлкенi: b2 = 2, b3 = 3, b4 = 4, b5 = 10, b6 = 20, b7 = 35 ,
b8 = 56, b9 = 126, b10 = 252, b11 = 462, b12 = 792, b13 = 1716, b14 = 3432, b15 = 6435 және т.с.с.

Д. Кнуттың «Программалау өнерi» атты монографиясындағы осы тақырып бойынша берiлген барлық құрылымдар
жартылай эмпирикалық сипатта – онда теориялық қағидалар ұсынылады да, соның негiзiнде статистикалық
эксперименттер жүргiзiледi. Сонымен қатар, Д.Кнут кездейсоқ тiзбек құрудың фон Нейманның «орта квадраттар»
әдiсiндегi параметрлердi кездейсоқ түрде таңдаудың күмән тудыратын көрiнiсiне сүйенiп, күллi эксперименттiк
iздеулердiң сенiмдi емес екендiгiн және кандай да болсын теория әрдайым қажет екендiгi туралы қорытындыға келген.
Бiз таза теориялық зерттеулер жүргiздiк.
Барлық ST-тұжырымдарында төменгi бағалаулары N өскен сайын 1 санына ұмтылатын айқын түрде (практикалық
қолданыста шешушi мағынаға ие) жазылатын γN көбейткiшi үшiн γN · N
1
s ≤ νs(a, N) түрiнде болады.
Бұл қатарымен екi мәселенi шешедi (жалғыз ғана кедергi - компьютерлiк техниканың есептеу мүмкiндiктерi)
а) кездейсоқ сандардың саны N таңдауымызша үлкен болуы мiндеттi және мүмкiн де;
b) кездейсоқтықтың негiзгi сипаттамасы νs (a, N) барлық s ≥ 2 үшiн қалауымызша үлкен болуы мiндеттi және
мүмкiн.
hXni генераторының s өлшемдi νs дәлдiгiнiң «өлшем қарғысы» ретiнде белгiлi N
1
s негiзгi бөлiгi 1/s көрсеткiшiнiң
кiшiлiгiне байланысты N -нен оған керi s -ке сай Ns дәрежесi үлкен болуын талап етедi (осымен сандық
интегралдаудағы бiрқалыпты торлы және бiрдей салмақты квадратуралық формулаларымен жуықтау жылдамдығының
шамасы қайталанылады).
Бұның бәрiнен жаңа мәселе туындайды: (0.1)-(0.2) кездейсоқ сандар генераторы қолданылатын әр жағдай үшiн « N
және νs(a, N) қаншалықты үлкен болуы керектiгiн анықтау қажет». Әрине, бұл тiптi тривиалды болмауы да мүмкiн,
өз алдына жеке мәселе.
νs (a, N) ≤ γN · N
1
s

γN → 1

түрiндегi асимптотикалық дәл жоғарғы баға N мен νs(a, N) шамаларын жүзеге
асыру кезiнде орасан артық жұмыстарды қоса алып жүретiн қисынсыз үлкен етiп алмауға кепiл болады.
s = 2 жағдайынан басқа барлық ST- түжырымдар дәл емес, асимптотикалық қана. Бiрақ бұл жәйт қолданысты еш
шектемейдi - N мен νs(a, N) -тiң дәл мәндерi емес, қажеттi шекарадан шықпайтын жуық мәндерi қажет етiледi.
Егер кездейсоқтық әсерi тiкелей сезiлмейтiн νs(a, N) -тiң бағасынан кездейсоқтықты «жиiлiк» арқылы тексеруге
көшсек (бұл қасиет бiрқалыпты таралым деп аталады, кездейсоқтықтан әлде көп шарттар талап етiледi), 0, 1, . . ., N − 1
сандарын [0, 1] сегментiнен алынған кез келген [α, β] сегментi үшiн онда жататын Xn
N
сандарының саны (β − α) -ға
жуық болатындай етiп, өз-өзiне биективтi бейнелеу арқылы басқа X0, . . . , XN−1 ретiмен берiлуi қажет болады, яғни
кез келген максимал периодты Лехмер тiзбегiнiң әуел басынан-ақ 1
N жақсартылмайтын ауытқу ретiмен бiрқалыпты
таралатындығы аңгарылады. Бұл қасиеттi осы тiзбектiң тамаша қасиеттерiнiң бiрiне жатқызуға болады. Сөйтiп,
мәселенiң тек νs(a, N) кездейсоқтық көрсеткiшiнде болатындығы туралы қорытындыға келемiз