Лінійний конгруентний метод — один із методів генерації псевдовипадкових чисел. Застосовується в простих випадках і не володіє криптографічною стійкістю. Входить в стандартні бібліотеки різних компіляторів.
Опис
Лінійний конгруентний метод був запропонований в 1949 році. Суть методу полягає в обчисленні послідовності випадкових чисел , вважаючи
де — модуль (натуральне число, відносно якого обчислюють остачу від ділення; ), — множник (), — приріст (), — початкове значення ().
Ця послідовність називається лінійною конгруентною послідовністю. Наприклад, для отримаємо послідовність :21—37</ref>
Властивості
Лінійна конгруентна послідовність, визначена числами , , і періодична з періодом, не більшим за . При цьому довжина періоду рівна тоді і тільки тоді, коли:21—37:
- Числа і взаємно прості;
- кратно для кожного простого , що є дільником ;
- кратно , якщо кратно .
Наявність цієї властивості для випадку , де — число бітів в машинному слові, було доведено М. Грінбергом (англ. M. Greenberg). Наявність цієї властивості для загального випадку і достатність умов були доведені Т. Е. Халлом (англ. T. E. Hull) і А. Р. Добеллом (англ. A. R. Dobell).
Метод генерації лінійної конгруентної послідовності при називають мультиплікативним конгруентним методом, а при — змішаним конгруентним методом. При згенеровані числа будуть мати менший період, ніж при , але при певних умовах можна отримати період довжиною , якщо — просте число. Той факт, що умова може призводити до появи більш довгих періодів, був встановлений В. Е. Томсоном (англ. W. T. Thomson) і незалежно від нього А. Ротенбергом (англ. A. Rotenberg). Щоб гарантувати максимальність циклу повторення послідовності при , необхідно в якості значення параметра обирати просте число. Найвідомішим генератором подібного типу є так званий мінімальний стандартний генератор випадкових чисел, запропонований Стівеном Парком (англ. Stephen Park) і Кейтом Міллером (англ. Keith Miller) в 1988 році. Для нього , а .
Методом генерації послідовностей псевдовипадкових чисел, що найчастіше використовують є змішаний конгруентний метод.
Параметри, що часто використовуються
При виборі числа необхідно враховувати наступні умови:
- число повинно бути достатньо великим, так як період не може мати більше ніж елементів;
- значення числа повинно бути таким, щоб обчислювалось швидко.
На практиці при реалізації методу виходячи з вказаних умов частіше всього обирають , де — число бітів в машинному слові. При цьому варто враховувати, що молодші двійкові розряди згенерованих таким чином випадкових чисел демонструють поведінку, далеку від випадкової, тому рекомендується використовувати лише старші розряди. Подібна ситуація не виникає, коли , де — довжина машинного слова. В такому випадку молодші розряди поводять себе так же випадково, як і старші. Вибір множника і приросту зазвичай обумовлений необхідністю виконання умови досягнення періоду максимальної довжини.
Всі наведені константи забезпечують роботу генератора з максимальним періодом. Таблиця упорядкована по максимальному добутку, яке не викликає переповнення в слові заданої довжини.
Переповнюється при | a | c | m |
---|---|---|---|
220 | 106 | 1283 | 6075 |
221 | 211 | 1663 | 7875 |
222 | 421 | 1663 | 7875 |
223 | 430 | 2531 | 11979 |
223 | 936 | 1399 | 6655 |
223 | 1366 | 1283 | 6075 |
224 | 171 | 11213 | 53125 |
224 | 859 | 2531 | 11979 |
224 | 419 | 6173 | 29282 |
224 | 967 | 3041 | 14406 |
225 | 141 | 28411 | 134456 |
225 | 625 | 6571 | 31104 |
225 | 1541 | 2957 | 14000 |
225 | 1741 | 2731 | 12960 |
225 | 1291 | 4621 | 21870 |
225 | 205 | 29573 | 139968 |
226 | 421 | 17117 | 81000 |
226 | 1255 | 6173 | 29282 |
226 | 281 | 28411 | 134456 |
227 | 1093 | 18257 | 86436 |
227 | 421 | 54773 | 259200 |
227 | 1021 | 24631 | 116640 |
228 | 1277 | 24749 | 117128 |
228 | 2041 | 25673 | 121500 |
229 | 2311 | 25367 | 120050 |
229 | 1597 | 51749 | 244944 |
229 | 2661 | 36979 | 175000 |
229 | 4081 | 25673 | 121500 |
229 | 3661 | 30809 | 145800 |
230 | 3877 | 29573 | 139968 |
230 | 3613 | 45289 | 214326 |
230 | 1366 | 150889 | 714025 |
231 | 8121 | 28411 | 134456 |
231 | 4561 | 51349 | 243000 |
231 | 7141 | 54773 | 259200 |
232 | 9301 | 49297 | 233280 |
232 | 4096 | 150889 | 714025 |
233 | 2416 | 374441 | 1771875 |
234 | 17221 | 107839 | 510300 |
234 | 36261 | 66037 | 312500 |
235 | 84589 | 45989 | 217728 |
Відомий «невдалий» (с точки зору якості вихідної послідовності) алгоритм , що протягом багатьох десятиліть використовували в різних компіляторах.
Для покращення статистичних властивостей числової послідовності в багатьох генераторах псевдовипадкових чисел використовується лише частина бітів результату. Наприклад, в стандарті ISO/IEC 9899 на мові Сі приведений (але не вказаний в якості обов'язкового) приклад функції rand(), що примусово відкидає молодші 16 і один старший розряд.
#define RAND_MAX 32767 static unsigned long int next = 1; int rand(void) { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % (RAND_MAX + 1); } void srand(unsigned int seed) { next = seed; }
Саме в такому вигляді функція rand() використовується в компіляторах . Відомі числові параметри інших алгоритмів, що застосовуються в різних компіляторах і бібліотеках.
Source | m | множник a | доданок c | використані біти |
---|---|---|---|---|
Numerical Recipes | 232 | 1664525 | 1013904223 | |
Borland C/C++ | 232 | 22695477 | 1 | bits 30..16 in rand(), 30..0 in lrand() |
glibc (used by GCC) | 231 | 1103515245 | 12345 | bits 30..0 |
ANSI C: , Digital Mars, , IBM VisualAge C/C++ | 231 | 1103515245 | 12345 | bits 30..16 |
C99, C11: Suggestion in the ISO/IEC 9899 | 232 | 1103515245 | 12345 | bits 30..16 |
Borland Delphi, | 232 | 134775813 | 1 | bits 63..32 of (seed * L) |
232 | 214013 (343FD16) | 2531011 (269EC316) | bits 30..16 | |
Microsoft Visual Basic (6 and earlier) | 224 | 1140671485 (43FD43FD16) | 12820163 (C39EC316) | |
RtlUniform from | 231 − 1 | 2147483629 (7FFFFFED16) | 2147483587 (7FFFFFC316) | |
, 's minstd_rand0 | 231 − 1 | 16807 | 0 | see |
's minstd_rand | 231 − 1 | 48271 | 0 | see |
MMIX by | 264 | 6364136223846793005 | 1442695040888963407 | |
264 | 6364136223846793005 | 1 | bits 63...32 | |
VAX's MTH$RANDOM, old versions of glibc | 232 | 69069 | 1 | |
Java | 248 | 25214903917 | 11 | bits 47...16 |
Раніше в багатьох компіляторах: | ||||
231 | 65539 | 0 |
Можливість використання в криптографії
Хоча лінійний конгруентний метод породжує статистично хорошу псевдовипадкову послідовність чисел, він не є криптографічно стійким. Генератори на основі лінійного конгруентного методу передбачувані, тому їх не можна використовувати в криптографії. Вперше генератори на основі лінійного конгруентного методу були зламані Джимом Рідсом (Jim Reeds), а потім Джоан Бояр (Joan Boyar). Їй вдалося також виявити недоліки квадратичних і кубічних генераторів. Інші дослідники розширили ідеї Бояр, розробивши способи виявлення недоліків будь-якого поліноміального генератора. Таким чином, було доведено, що генератори на основі конгруентних методів не підходять для використання в криптографії. Однак генератори на основі лінійного конгруентного методу зберігають свою корисність для некриптографічних додатків, наприклад, для моделювання. Вони ефективні і в найбільш використовуваних емпіричних тестах демонструють хороші статистичні характеристики.
Див. також
Джерела
- D. H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141—146. MR 0044899 (13,495f)[1] [ 24 грудня 2013 у Wayback Machine.]
- Дональд Кнут. Искусство программирования = The Art of Computer Programming. — 3-е изд. — Москва : Вільямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 прим. — (рус.) (англ.).
- M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179.[2] [ 24 грудня 2013 у Wayback Machine.]
- T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254 [3] [ 24 грудня 2013 у Wayback Machine.]
- Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. — Delphi Informant Magazine, 2002.
- Stephen K. Park; Keith W. Miller (1988). (PDF). Communications of the ACM (англ.). 31 (10): 1192—1201. Архів оригіналу (PDF) за 20 березня 2018. Процитовано 26 грудня 2017.
- Брюс Шнайєр. Прикладная криптография. — Триумф, 2002. — С. 275. з джерела 28 лютого 2014
- Numerical recipies in C. The art of scientific computing (вид. 2-nd edition). Cambridge University Press. 1992.
- The GNU C library's rand() in uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator and the period increases. See the simplified code [ 2 лютого 2015 у Wayback Machine.] that reproduces the random sequence from this library.
- . Архів оригіналу за 5 червня 2013. Процитовано 16 червня 2012.
- (PDF). Архів оригіналу (PDF) за 29 березня 2018. Процитовано 21 грудня 2014.
- . Microsoft Support. Microsoft. Архів оригіналу за 17 квітня 2011. Процитовано 17 червня 2011.
- In spite of documentation on MSDN [ 8 березня 2016 у Wayback Machine.], RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
- . ISO. 2 September 2011. Архів оригіналу за 29 січня 2013. Процитовано 3 September 2011.
- . Архів оригіналу за 11 грудня 2014. Процитовано 26 грудня 2017.
Посилання
- Л. Бараш. . — Безопасность информационных технологий, 2005. — № 2. — С. 27-38.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Linijnij kongruentnij metod odin iz metodiv generaciyi psevdovipadkovih chisel Zastosovuyetsya v prostih vipadkah i ne volodiye kriptografichnoyu stijkistyu Vhodit v standartni biblioteki riznih kompilyatoriv OpisLinijnij kongruentnij metod buv zaproponovanij v 1949 roci Sut metodu polyagaye v obchislenni poslidovnosti vipadkovih chisel X n displaystyle X n vvazhayuchi X n 1 a X n c mod m displaystyle X n 1 aX n c bmod m de m displaystyle m modul naturalne chislo vidnosno yakogo obchislyuyut ostachu vid dilennya m 2 displaystyle m geqslant 2 a displaystyle a mnozhnik 0 a lt m displaystyle 0 leqslant a lt m c displaystyle c pririst 0 c lt m displaystyle 0 leqslant c lt m X 0 displaystyle X 0 pochatkove znachennya 0 X 0 lt m displaystyle 0 leqslant X 0 lt m Cya poslidovnist nazivayetsya linijnoyu kongruentnoyu poslidovnistyu Napriklad dlya m 10 X 0 a c 7 displaystyle m 10 X 0 a c 7 otrimayemo poslidovnist 7 6 9 0 7 6 9 0 displaystyle 7 6 9 0 7 6 9 0 dots 21 37 lt ref gt VlastivostiLinijna kongruentna poslidovnist viznachena chislami m displaystyle m a displaystyle a c displaystyle c i X 0 displaystyle X 0 periodichna z periodom ne bilshim za m displaystyle m Pri comu dovzhina periodu rivna m displaystyle m todi i tilki todi koli 21 37 Chisla c displaystyle c i m displaystyle m vzayemno prosti b a 1 displaystyle b a 1 kratno p displaystyle p dlya kozhnogo prostogo p displaystyle p sho ye dilnikom m displaystyle m b displaystyle b kratno 4 displaystyle 4 yaksho m displaystyle m kratno 4 displaystyle 4 Nayavnist ciyeyi vlastivosti dlya vipadku m 2 e displaystyle m 2 e de e displaystyle e chislo bitiv v mashinnomu slovi bulo dovedeno M Grinbergom angl M Greenberg Nayavnist ciyeyi vlastivosti dlya zagalnogo vipadku i dostatnist umov buli dovedeni T E Hallom angl T E Hull i A R Dobellom angl A R Dobell Metod generaciyi linijnoyi kongruentnoyi poslidovnosti pri c 0 displaystyle c 0 nazivayut multiplikativnim kongruentnim metodom a pri c 0 displaystyle c neq 0 zmishanim kongruentnim metodom Pri c 0 displaystyle c 0 zgenerovani chisla budut mati menshij period nizh pri c 0 displaystyle c neq 0 ale pri pevnih umovah mozhna otrimati period dovzhinoyu m 1 displaystyle m 1 yaksho m displaystyle m proste chislo Toj fakt sho umova c 0 displaystyle c neq 0 mozhe prizvoditi do poyavi bilsh dovgih periodiv buv vstanovlenij V E Tomsonom angl W T Thomson i nezalezhno vid nogo A Rotenbergom angl A Rotenberg Shob garantuvati maksimalnist ciklu povtorennya poslidovnosti pri c 0 displaystyle c 0 neobhidno v yakosti znachennya parametra m displaystyle m obirati proste chislo Najvidomishim generatorom podibnogo tipu ye tak zvanij minimalnij standartnij generator vipadkovih chisel zaproponovanij Stivenom Parkom angl Stephen Park i Kejtom Millerom angl Keith Miller v 1988 roci Dlya nogo a 16807 displaystyle a 16807 a m 2147483647 displaystyle m 2147483647 Metodom generaciyi poslidovnostej psevdovipadkovih chisel sho najchastishe vikoristovuyut ye zmishanij kongruentnij metod dzherelo ne vkazane 2530 dniv Parametri sho chasto vikoristovuyutsyaPri vibori chisla m displaystyle m neobhidno vrahovuvati nastupni umovi chislo m displaystyle m povinno buti dostatno velikim tak yak period ne mozhe mati bilshe nizh m displaystyle m elementiv znachennya chisla m displaystyle m povinno buti takim shob a X n c mod m displaystyle aX n c mod m obchislyuvalos shvidko Na praktici pri realizaciyi metodu vihodyachi z vkazanih umov chastishe vsogo obirayut m 2 e displaystyle m 2 e de e displaystyle e chislo bitiv v mashinnomu slovi Pri comu varto vrahovuvati sho molodshi dvijkovi rozryadi zgenerovanih takim chinom vipadkovih chisel demonstruyut povedinku daleku vid vipadkovoyi tomu rekomenduyetsya vikoristovuvati lishe starshi rozryadi Podibna situaciya ne vinikaye koli m w 1 displaystyle m w pm 1 de w displaystyle w dovzhina mashinnogo slova V takomu vipadku molodshi rozryadi X n displaystyle X n povodyat sebe tak zhe vipadkovo yak i starshi Vibir mnozhnika a displaystyle a i prirostu c displaystyle c zazvichaj obumovlenij neobhidnistyu vikonannya umovi dosyagnennya periodu maksimalnoyi dovzhini Tablicya horoshih konstant dlya linijnih kongruentnih generatorivVsi navedeni konstanti zabezpechuyut robotu generatora z maksimalnim periodom Tablicya uporyadkovana po maksimalnomu dobutku yake ne viklikaye perepovnennya v slovi zadanoyi dovzhini Perepovnyuyetsya pri a c m 220 106 1283 6075 221 211 1663 7875 222 421 1663 7875 223 430 2531 11979 223 936 1399 6655 223 1366 1283 6075 224 171 11213 53125 224 859 2531 11979 224 419 6173 29282 224 967 3041 14406 225 141 28411 134456 225 625 6571 31104 225 1541 2957 14000 225 1741 2731 12960 225 1291 4621 21870 225 205 29573 139968 226 421 17117 81000 226 1255 6173 29282 226 281 28411 134456 227 1093 18257 86436 227 421 54773 259200 227 1021 24631 116640 228 1277 24749 117128 228 2041 25673 121500 229 2311 25367 120050 229 1597 51749 244944 229 2661 36979 175000 229 4081 25673 121500 229 3661 30809 145800 230 3877 29573 139968 230 3613 45289 214326 230 1366 150889 714025 231 8121 28411 134456 231 4561 51349 243000 231 7141 54773 259200 232 9301 49297 233280 232 4096 150889 714025 233 2416 374441 1771875 234 17221 107839 510300 234 36261 66037 312500 235 84589 45989 217728 Vidomij nevdalij s tochki zoru yakosti vihidnoyi poslidovnosti algoritm sho protyagom bagatoh desyatilit vikoristovuvali v riznih kompilyatorah Dlya pokrashennya statistichnih vlastivostej chislovoyi poslidovnosti v bagatoh generatorah psevdovipadkovih chisel vikoristovuyetsya lishe chastina bitiv rezultatu Napriklad v standarti ISO IEC 9899 na movi Si privedenij ale ne vkazanij v yakosti obov yazkovogo priklad funkciyi rand sho primusovo vidkidaye molodshi 16 i odin starshij rozryad define RAND MAX 32767 static unsigned long int next 1 int rand void next next 1103515245 12345 return unsigned int next 65536 RAND MAX 1 void srand unsigned int seed next seed Same v takomu viglyadi funkciya rand vikoristovuyetsya v kompilyatorah Vidomi chislovi parametri inshih algoritmiv sho zastosovuyutsya v riznih kompilyatorah i bibliotekah Source m mnozhnik a dodanok c vikoristani biti Numerical Recipes 232 1664525 1013904223 Borland C C 232 22695477 1 bits 30 16 in rand 30 0 in lrand glibc used by GCC 231 1103515245 12345 bits 30 0 ANSI C Digital Mars IBM VisualAge C C 231 1103515245 12345 bits 30 16 C99 C11 Suggestion in the ISO IEC 9899 232 1103515245 12345 bits 30 16 Borland Delphi 232 134775813 1 bits 63 32 of seed L Microsoft Visual Quick C C 232 214013 343FD16 2531011 269EC316 bits 30 16 Microsoft Visual Basic 6 and earlier 224 1140671485 43FD43FD16 12820163 C39EC316 RtlUniform from 231 1 2147483629 7FFFFFED16 2147483587 7FFFFFC316 C 11 s minstd rand0 231 1 16807 0 see C 11 s minstd rand 231 1 48271 0 see MMIX by 264 6364136223846793005 1442695040888963407 264 6364136223846793005 1 bits 63 32 VAX s MTH RANDOM old versions of glibc 232 69069 1 Java 248 25214903917 11 bits 47 16 Ranishe v bagatoh kompilyatorah 231 65539 0Mozhlivist vikoristannya v kriptografiyiHocha linijnij kongruentnij metod porodzhuye statistichno horoshu psevdovipadkovu poslidovnist chisel vin ne ye kriptografichno stijkim Generatori na osnovi linijnogo kongruentnogo metodu peredbachuvani tomu yih ne mozhna vikoristovuvati v kriptografiyi Vpershe generatori na osnovi linijnogo kongruentnogo metodu buli zlamani Dzhimom Ridsom Jim Reeds a potim Dzhoan Boyar Joan Boyar Yij vdalosya takozh viyaviti nedoliki kvadratichnih i kubichnih generatoriv Inshi doslidniki rozshirili ideyi Boyar rozrobivshi sposobi viyavlennya nedolikiv bud yakogo polinomialnogo generatora Takim chinom bulo dovedeno sho generatori na osnovi kongruentnih metodiv ne pidhodyat dlya vikoristannya v kriptografiyi Odnak generatori na osnovi linijnogo kongruentnogo metodu zberigayut svoyu korisnist dlya nekriptografichnih dodatkiv napriklad dlya modelyuvannya Voni efektivni i v najbilsh vikoristovuvanih empirichnih testah demonstruyut horoshi statistichni harakteristiki Div takozhGenerator psevdovipadkovih chiselDzherelaD H Lehmer Mathematical methods in large scale computing units Proceedings of a Second Symposium on Large Scale Digital Calculating Machinery 1949 Harvard University Press Cambridge Mass 1951 pp 141 146 MR 0044899 13 495f 1 24 grudnya 2013 u Wayback Machine Donald Knut Iskusstvo programmirovaniya The Art of Computer Programming 3 e izd Moskva Vilyams 2000 T 2 Poluchislennye algoritmy 832 s 7000 prim ISBN 5 8459 0081 6 rus ISBN 0 201 89684 2 angl M Greenberger Method in randomness Comm ACM 8 1965 177 179 2 24 grudnya 2013 u Wayback Machine T E Hull and A R Dobell Random Number Generators SIAM Review 4 3 1962 230 254 3 24 grudnya 2013 u Wayback Machine Baknell D M Fundamentalnye algoritmy i struktury dannyh v Delphi Biblioteka programmista Delphi Informant Magazine 2002 Stephen K Park Keith W Miller 1988 PDF Communications of the ACM angl 31 10 1192 1201 Arhiv originalu PDF za 20 bereznya 2018 Procitovano 26 grudnya 2017 Bryus Shnajyer Prikladnaya kriptografiya Triumf 2002 S 275 z dzherela 28 lyutogo 2014 Numerical recipies in C The art of scientific computing vid 2 nd edition Cambridge University Press 1992 The GNU C library s rand in uses a simple single state linear congruential generator only in case that the state is declared as 8 bytes If the state is larger an array the generator becomes an additive feedback generator and the period increases See the simplified code 2 lyutogo 2015 u Wayback Machine that reproduces the random sequence from this library Arhiv originalu za 5 chervnya 2013 Procitovano 16 chervnya 2012 PDF Arhiv originalu PDF za 29 bereznya 2018 Procitovano 21 grudnya 2014 Microsoft Support Microsoft Arhiv originalu za 17 kvitnya 2011 Procitovano 17 chervnya 2011 In spite of documentation on MSDN 8 bereznya 2016 u Wayback Machine RtlUniform uses LCG and not Lehmer s algorithm implementations before Windows Vista are flawed because the result of multiplication is cut to 32 bits before modulo is applied ISO 2 September 2011 Arhiv originalu za 29 sichnya 2013 Procitovano 3 September 2011 Arhiv originalu za 11 grudnya 2014 Procitovano 26 grudnya 2017 PosilannyaL Barash Bezopasnost informacionnyh tehnologij 2005 2 S 27 38