Насколько я понял из прочитанного мною, генератор случайных чисел может быть записан в виде:
Ii+1 = (a*Ii+b) mod n,
где a и b - взаимно простые числа.
Вопрос такой: есть ли какие - то предпочтения в выборе a и b ? В частности, меня интересует случай n=2^32, те случай 32-х битных чисел. Какие числа обычно используются ?
Да. Никто случаем не знает (или сам не оценивал) мощность генератора паролей APG ("Automated Password Generator") для *nix ?
Биг сенькс.
ответ02.12.02 11:30 Автор: RElf <M> Статус: Member
> Насколько я понял из прочитанного мною, генератор случайных > чисел может быть записан в виде: > > Ii+1 = (a*Ii+b) mod n,
Генератор такого вида называется линейным конгруэнтным.
> где a и b - взаимно простые числа.
Это несущественное требование. Гораздо важнее, чтобы b и n были взаимно просты (см. ниже).
> Вопрос такой: есть ли какие - то предпочтения в выборе a и > b ?
Вот теорема из "Искусства программирования" Кнута:
Длина периода линейной конгруэнтной последовательности (т.е. последовательности, вида X = (a*X+c) % m) равна m тогда и только тогда, когда:
1. HОД(c,m) = 1 (т.е. c и m взаимно просты)
2. b=a-1 кратно p для всех простых p - делителей m
3. b кратно 4, если m кратно 4
> В частности, меня интересует случай n=2^32, те случай > 32-х битных чисел. Какие числа обычно используются ?
Везде разные. Вот например, как выглядит RNG из ANSI стандарта:
// ANSI Standard random number generator
unsigned int ansi_rand()
{
seed = seed * 0x41C64E6Du + 0x3039u;
return (seed>>0x10)&0x7FFF;
}
> Да. Никто случаем не знает (или сам не оценивал) мощность > генератора паролей APG ("Automated Password Generator") для > *nix ?
Где есть его описание?
Сенькс! и "где".02.12.02 11:43 Автор: Chingachguk <Chingachguk> Статус: Member
> > Насколько я понял из прочитанного мною, генератор > > {...} > Генератор такого вида называется линейным конгруэнтным. > {...}
Огромное спасибо ! Я все понял.
> > Да. Никто случаем не знает (или сам не оценивал) > мощность > > генератора паролей APG ("Automated Password > Generator") для > > *nix ? > > Где есть его описание?
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
