KISS (алгоритм)

KISS ( Keep it Simple Stupid ) — семейство генераторов псевдослучайных чисел, представленное Джорджем Марсальей . [1] [2] [3] Начиная с 1998 года Марсалья публиковал в различных группах новостей, включая sci.math, comp.lang.c , comp.lang.fortran и sci.stat.math, несколько версий генераторов. Все генераторы KISS объединяют три или четыре независимых генератора случайных чисел с целью улучшения качества случайности. Генераторы KISS вырабатывают 32-битные или 64-битные случайные целые числа, из которых при желании можно построить случайные числа с плавающей точкой. Оригинальный генератор 1993 года основан на комбинации линейного конгруэнтного генератора и двух линейных генераторов регистров сдвига с обратной связью . Он имеет период 2 95 , хорошую скорость и хорошие статистические свойства; однако он не проходит тест LinearComplexity в тестах Crush и BigCrush пакета TestU01 . [4] Более новая версия 1999 года основана на линейном конгруэнтном генераторе, 3-сдвиговом линейном регистре сдвига с обратной связью и двух генераторах умножения с переносом. Она на 10–20% медленнее версии 1993 года, но имеет больший период 2 123 и проходит все тесты в TestU01. В 2009 году Марсалья представил версию, основанную на 64-битных целых числах (подходит для 64-битных процессоров), которая объединяет генератор умножения с переносом , генератор Xorshift и линейный конгруэнтный генератор. [5] Она имеет период около 2 250 (около 10 75 ).

Ссылки

  1. ^ Марсалья, Джордж; Заман, Ариф (1993). «Генератор KISS». Технический отчет, Департамент статистики, Университет штата Флорида, Таллахасси, Флорида, США .
  2. ^ Роуз, Грег (2018). «KISS: A Bit Too Simple» (PDF) . Криптография и связь . 10 : 123–137 . doi : 10.1007/s12095-017-0225-x .
  3. ^ Кнойзель, Рональд Т. (2018). Случайные числа и компьютеры . Springer. ISBN 978-3-319-77696-5.
  4. ^ L'Ecuyer, Pierre; Simard, Richard (2007). "TestU01: Библиотека AC для эмпирического тестирования генераторов случайных чисел". ACM Transactions on Mathematical Software . 33 (4): 22–es. doi :10.1145/1268776.1268777. S2CID  273446.
  5. ^ "64-битные генераторы случайных чисел KISS". 28 февраля 2009 г.

Дальнейшее чтение

  • Баклью, Джеймс (2013). "1.1 Генераторы унифицированных событий". Введение в моделирование редких событий . Springer. стр.  1– 8. ISBN 978-1-4757-4078-3.
  • Роберт, Кристиан; Джордж Каселла (2013). "2.1.2 Генератор поцелуев". Статистические методы Монте-Карло . Springer. стр.  39–43 . ISBN 978-1-4757-3071-5.
  • Роуз, Грегори Г. (2017). «KISS: Слишком просто». Криптография и связь . 10 : 123–137 . doi : 10.1007/s12095-017-0225-x . ISSN  1936-2447.
Взято с "https://en.wikipedia.org/w/index.php?title=KISS_(алгоритм)&oldid=1128781820"