Псевдококустук сан – бул атайын генератор тарабынан түзүлгөн өзгөчө сан. Детерминисттик Random Bit Generator (PRNG), ошондой эле Deterministic Random Bit Generator (DRBG) катары белгилүү, касиеттери кокустук сандар тизмегинин мүнөздөмөлөрүнө жакын келген сандардын ырааттуулугун түзүү үчүн алгоритм. Түзүлгөн PRNG ырааттуулугу чындап эле кокустук эмес, анткени ал толугу менен PRNG үрөнү деп аталган урук мааниси менен аныкталат, ал чыныгы кокустуктарды камтышы мүмкүн. Аппараттык кокустук сан генераторлорунун жардамы менен кокустукка жакын ырааттуулуктарды түзүүгө мүмкүн болсо да, псевдококустук сан генераторлору практикада сандарды түзүү ылдамдыгы жана алардын кайра жаралышы үчүн маанилүү.
Колдонмо
PRNG'лер симуляция (мисалы, Монте-Карло үчүн), электрондук оюндар (мисалы, процедуралык генерация үчүн) жана криптография сыяктуу колдонмолордун борбордук бөлүгү болуп саналат. Криптографиялык колдонмолор чыгарууну талап кылатмаалыматтар мурунку маалыматтардан алдын ала болгон эмес. Жөнөкөй PRNGлердин сызыктуулугун мурастабаган татаалыраак алгоритмдер талап кылынат.
Жоболор жана шарттар
Жакшы статистикалык касиеттер PRNG алуу үчүн негизги талап болуп саналат. Жалпысынан алганда, RNG максаттуу колдонууга ылайыктуу болушу үчүн кокустукка жакын сандарды чыгараарына ынануу үчүн кылдат математикалык анализ керек.
Джон фон Нейман PRNGди чыныгы кокустук генератор катары туура эмес чечмелөөдөн сактанууну эскертип, "Кокус сандарды чыгаруу үчүн арифметикалык ыкмаларды караган адам, албетте, күнөө абалында болот" деп тамашалаган.
Колдонуу
PRNG ыктыярдуу баштапкы абалдан иштетилиши мүмкүн. Бул абал менен инициализацияланганда ал ар дайым бирдей ырааттуулукту жаратат. PRNG мезгили төмөнкүчө аныкталат: кайталанбаган ырааттуулук префиксинин узундугунун бардык баштапкы абалдары боюнча максималдуу. Мезгил штаттардын саны менен чектелген, адатта бит менен ченелет. Ар бир "абал" бит кошулган сайын мезгилдин узундугу эки эсеге көбөйгөндүктөн, көптөгөн практикалык колдонмолор үчүн жетишерлик чоң мезгилдер менен PRNG түзүү оңой.
Эгер PRNGдин ички абалы n битти камтыса, анын мезгили 2n натыйжадан ашпашы мүмкүн, ал бир топ кыскараак. Кээ бир PRNGs үчүн узактыгы бүткүл мезгилди айланып өтпөстөн эсептелиши мүмкүн. Сызыктуу пикир алмашуу регистрлери (LFSRs) адатта болуп саналат2n − 1ге барабар чекиттерге ээ болуп тандалган.
Сызыктуу конгруциалдык генераторлор факторинг аркылуу эсептелүүчү мезгилдерге ээ. МЖӨ өз натыйжаларын мезгил аяктагандан кийин кайталайт да, кайталанган жыйынтык мезгилдин акырына жетти дегенди билдирбейт, анткени анын ички абалы чыгарылгандан көбүрөөк болушу мүмкүн; Бул өзгөчө бир бит чыгаруусу бар PRNG'лер үчүн айкын көрүнүп турат.
Мүмкүн каталар
Бузулган PRNG'лер тарабынан табылган каталар тымызындан (жана белгисиз) ачыкка чейин. Мисал RANDU кокустук сандар алгоритми, ал ондогон жылдар бою негизги фреймдерде колдонулуп келет. Бул олуттуу кемчилик болчу, бирок анын жетишсиздиги көпкө байкалбай келген.
Көптөгөн аймактарда кокус тандоо, Монте-Карло симуляциясы же RNGге негизделген башка ыкмаларды колдонгон изилдөөлөр сапатсыз GNPG натыйжасы болушу мүмкүн болгон ишенимден алда канча азыраак. Бүгүнкү күндө да кээде этияттык талап кылынат, муну Эл аралык статистикалык илим энциклопедиясындагы (2010) эскертүү тастыктап турат.
Ийгиликтүү изилдөө
Мисал катары кеңири колдонулган Java программалоо тилин карап көрөлү. 2017-жылга карата Java дагы эле PRNG үчүн Сызыктуу конгруенциялык генераторго (LCG) таянат.
Тарых
Биринчи PRNG олуттуу көйгөйлөрдөн качуу үчүн жана дагы эле абдан тез иштейт,1998-жылы басылып чыккан Mersenne Twister (төмөндө талкууланат) болгон. Ошондон бери башка жогорку сапаттагы PRNG'лер иштелип чыкты.
Бирок псевдококустук сандардын тарыхы муну менен эле бүтпөйт. 20-кылымдын экинчи жарымында PRNG үчүн колдонулган алгоритмдердин стандарттык классына сызыктуу конгрюциалдык генераторлор кирген. LCG сапаты адекваттуу эмес экени белгилүү болгон, бирок жакшыраак ыкмалар болгон эмес. Press et al (2007) натыйжаны төмөнкүчө сүрөттөгөн: "Эгерде [LCG жана ага байланыштуу] натыйжалары күмөн жараткан бардык илимий макалалар китепкана текчелеринде жок болуп кетсе, анда ар бир текчеде муштумдай боштук болмок."
Псевдококустук генераторлорду түзүүдөгү негизги жетишкендик эки элементтүү талаада сызыктуу рекуррентке негизделген методдорду киргизүү болду; мындай осцилляторлор сызыктуу пикир алмашуу регистрлери менен бириктирилет. Алар псевдо-кокус сандар сенсорлорун ойлоп табуу үчүн негиз болгон.
Атап айтканда, 1997-жылы Mersen Twister ойлоп табуусу мурунку генераторлордогу көптөгөн көйгөйлөрдөн качкан. Mersenne Twister 219937−1 итерация мезгилине ээ (≈4,3 × 106001). Ал 623 өлчөмгө (32 биттик маанилер үчүн) бирдей бөлүштүрүлгөнү далилденген жана аны киргизүү учурунда псевдококустук сандар тизмегин чыгарган статистикалык жактан ишенимдүү генераторлорго караганда ылдамыраак болгон.
2003-жылы Джордж Марсаглиа сызыктуу кайталанууга негизделген xorshift генераторлорунун үй-бүлөсүн киргизген. Бул генераторлор өзгөчөтез жана - сызыктуу эмес операция менен айкалышкан - алар катуу статистикалык сыноолордон өтүшөт.
2006-жылы WELL генератордук үй-бүлөсү иштелип чыккан. WELL генераторлору кандайдыр бир мааниде Twister Mersenne сапатын жакшыртат, анын абалы өтө чоң жана алардан өтө жай калыбына келип, көптөгөн нөлдөрү бар псевдо-кокус сандарды жаратат.
Криптография
Криптографиялык колдонмолорго ылайыктуу
PRNG криптографиялык жактан коопсуз PRNG (CSPRNG) деп аталат. CSPRNG үчүн талап - үрөндү билбеген чабуулчу генератордун чыгуу ырааттуулугун кокус ырааттуулуктан айырмалоодо бир аз гана артыкчылыкка ээ. Башкача айтканда, PRNG белгилүү бир статистикалык тесттерден өтүү үчүн гана талап кылынса, CSPRNG үрөн өлчөмүндөгү полиномдук убакыт менен чектелген бардык статистикалык тесттерден өтүшү керек.
Бул касиеттин далили эсептөө татаалдыгы теориясынын учурдагы деңгээлинен жогору болсо да, CSPRNGди бүтүн санды факторизация сыяктуу кыйын деп эсептелген маселеге кыскартуу менен күчтүү далилдерди келтирүүгө болот. Жалпысынан, алгоритм CSPRNG катары тастыкталганга чейин бир нече жыл текшерүү талап кылынышы мүмкүн.
NSA NIST тарабынан тастыкталган Dual_EC_DRBG псевдококустук сандар генераторуна асимметриялык арткы эшикти киргизген болушу мүмкүн.
Псевдококустук алгоритмдерсандар
Көпчүлүк PRNG алгоритмдери бир нече сыноолордун каалаганы менен бирдей бөлүштүрүлгөн ырааттуулуктарды чыгарышат. Бул ачык суроо. Бул криптографиянын теориясында жана практикасында борбордук элементтердин бири: жогорку сапаттагы PRNG чыгышын чыныгы кокустук ырааттуулуктан айырмалоонун жолу барбы? Бул жөндөөдө чечүүчү белгилүү PRNG алгоритми колдонулганын (бирок анын инициализацияланган абалы эмес) же чыныгы кокус алгоритм колдонулганын билет. Ал алардын ортосундагы айырманы билиши керек.
PRNG'лерди колдонгон криптографиялык алгоритмдердин жана протоколдордун көбүнүн коопсуздугу ылайыктуу PRNGди колдонуу менен чыныгы кокустук ырааттуулукту колдонууну айырмалоо мүмкүн эмес деген божомолго негизделген. Бул көз карандылыктын эң жөнөкөй мисалдары агымдык шифрлер болуп саналат, алар көбүнчө PRNG чыгышы менен ачык тексттик билдирүүнү калтырып же жөнөтүп, шифрленген текстти чыгарышат. Криптографиялык жактан адекваттуу PRNGдерди долбоорлоо өтө кыйын, анткени алар кошумча критерийлерге жооп бериши керек. Анын мезгилинин өлчөмү PRNGдин криптографиялык ылайыктуулугунун маанилүү фактору болуп саналат, бирок жалгыз эмес.
1946-жылы Жон фон Нейман тарабынан сунушталган алгачкы компьютердик PRNG орточо квадраттар ыкмасы катары белгилүү. Алгоритм төмөнкүчө: каалаган санды алып, аны квадратка түшүрүп, пайда болгон сандын ортоңку сандарын "кокустук сан" катары алып сал, андан кийин бул санды кийинки итерация үчүн баштапкы сан катары колдон. Мисалы, 1111 санын квадраттоо1234321, 01234321 деп жазылышы мүмкүн, 8 орундуу сан 4 орундуу сандын квадраты. Бул "кокус" сан катары 2343 берет. Бул процедураны кайталоонун натыйжасы 4896 ж.б. Фон Нейман 10 орундуу сандарды колдонгон, бирок процесс бирдей болгон.
"Орто квадраттын" кемчиликтери
"Орто квадрат" ыкмасынын көйгөйү - бардык ырааттуулуктар акырында кайталанат, кээ бирлери абдан тез, мисалы: 0000. Фон Нейман бул жөнүндө билген, бирок ал өзүнүн максаттары үчүн жетиштүү ыкманы таап, тынчсызданган. математикалык "түзөтүүлөр" каталарды алып салбастан, аларды жашырып коёт.
Вон Нейман аппараттык кокустук жана псевдо-кокус сандар генераторлорун жараксыз деп тапты: эгерде алар өндүрүлгөн чыгарууну жазбаса, аларды кийинчерээк каталарды текшерүү мүмкүн эмес. Эгерде алар өз натыйжаларын жазышса, алар компьютердин чектелген эс тутумун, демек, компьютердин сандарды окуу жана жазуу жөндөмүн түгөтөт. Эгерде сандар карталарга жазылса, аларды жазууга жана окууга көп убакыт талап кылынмак. Ал ENIAC компьютеринде "орто чарчы" ыкмасын колдонуп, перфокарталардан сандарды окууга караганда псевдококустук сандарды алуу процессин бир нече жүз эсе тез жүргүзгөн.
Орто квадрат андан кийин татаалыраак генераторлор менен алмаштырылды.
Инновациялык ыкма
Жакынкы инновация – бул орточо квадратты Вайл ырааттуулугу менен айкалыштыруу. Бул ыкма ичинде жогорку сапаттагы буюмдарды камсыз кылатузак мөөнөт. Бул эң жакшы псевдококустук сандар формулаларын алууга жардам берет.
