Кіріспе
Псевдо-көмекейлік сан генераторларының кездейсоқтығын тексеру әдісі. Криптография және есептеу теориясында келесі бит тесті – псевдо-көмекейлік сан генераторларына қарсы тест болып табылады. Біз биттер тізбегі тізбектегі кез келген орында келесі бит тестінен өтеді дейміз, егер бірінші биттерді білетін кез келген шабуылшы (бірақ бастапқы мәнін емес) st-ні ақылға қонымды есептеу мүмкіндіктерімен болжай алмаса.
In cryptography and the theory of computation, the next bit test is a test against pseudo random number generators. We say that a sequence of bits passes the next bit test for at any position in the sequence, if any attacker who knows the first bits (but not the seed) cannot predict the st with reasonable computational power.
Нақты мәлімет
Полином болсын, ал – биттік ұзындығы тізбектерді қамтитын жиындардың жиынтығы болсын. Сонымен қатар, – тізбектердің ықтималдық таралуы болсын. Енді келесі біт сынағын екі түрлі жолмен анықтаймыз.
We now define the next bit test in two different ways.
Яо сынағының толықтығы
Келесі бит тестісі Яоның кездейсоқ тізбектер тестісінің ерекше жағдайы болып табылады, сондықтан оны өту Яо тестісін өтудің қажетті шарты болып табылады. Дегенмен, Яо оның жеткілікті шарт екенін де көрсетті. Біз оны ықтималдық Тьюринг машинасы жағдайында дәлелдейміз, себебі Адлеман өз теоремасында кездейсоқтықты біркелкілікпен алмастыру жұмысын жасаған. Бульдік тізбектердің жағдайы осы жағдайдан туындамайды (өйткені ол потенциалды шешілмейтін мәселелерді шешуді қамтиды), бірақ Адлеман теоремасының дәлелін біркелкі емес Бульдік тізбектер отбасыларына оңай бейімдеуге болады. Яо тестісінің ықтималдық нұсқасы үшін ажыратушы болсын, яғни полиномдық уақытта жұмыс істейтін ықтималдық Тьюринг машинасы, онда белгілі бір полином үшін шексіз көп жағдайда: содан кейін, біз байқағандай, кем дегенде біреуі кем болмауы керек. Келесіде біз және үлестірімдерін қарастырамыз. Үлестірім – бұл бірінші биттерді ықтималдықпен таңдаудың ықтималдық үлестірімі, ал қалған биттерді біркелкі кездейсоқ түрде таңдау. Осылайша бізде: Бізде (бұл қарапайым есептеу арқылы көрсетіледі), сондықтан және үлестірімдерін ажыратуға болады. Жалпылықты жоғалтпай, біз деп аламыз, мұнда – полином. Бұл бізге келесі бит тестісін шешетін Тьюринг машинасының мүмкін құрылысын береді: тізбектің алғашқы биттерін алғаннан кейін, ол кірісті біт болжамымен және содан кейін біркелкі ықтималдықпен таңдалған кездейсоқ биттермен толықтырады. Содан кейін ол іске қосылады, және нәтижесі болса, онда шығарады, әйтпесе .
Let We have: and
Then, we notice that Therefore, at least one of the should be no smaller than
Next, we consider probability distributions and on Distribution is the probability distribution of choosing the first bits in with probability given by , and the remaining bits uniformly at random. We have thus:
We thus have (a simple calculus trick shows this), thus distributions and can be distinguished by Without loss of generality, we can assume that , with a polynomial. This gives us a possible construction of a Turing machine solving the next bit test: upon receiving the first bits of a sequence, pads this input with a guess of bit and then random bits, chosen with uniform probability. Then it runs , and outputs if the result is , and else.