Функция r[i+1]=(r[i]*A+C)(mod M), найти А, С, М, для известн. r1..r6.

Автор темы reachless (rich) 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеИщем преподавателя для углубленного обучения статистическим методам29.05.2020 13:22
07.07.2006 03:07
Функция r[i+1]=(r[i]*A+C)(mod M), найти А, С, М, для известн. r1..r6.
Привет. Помогите пожалуйста решить задачу.

Дано:

1) Ri+1 = (Ri*A+C)(mod M) - линейно-конгруентный датчик псевдослучайных чисел.
2) шесть целых чисел, d1, d2, d3, d4, d5, d6.
3) R0 = d1.

Найти такие A, C, M, при которых будет сгенерирована последовательность d1..d6.

Это частный случай задачи которую мне нужно решить, а в общем случае последовательность d1, d2..dN, где N >= 6. Но для начала хотябы с частным случаем разобраться, для N=6.
07.07.2006 09:10
достаточно пяти чисел
В общем случае будет достаточно 5 чисел.

Сначала явно расписываем:
d2 = (d1*A+C) mod M
d3 = (d2*A+C) mod M
d4 = (d3*A+C) mod M

Рассмотрим эти уравнения как систему уравнений по модулю M с неизвестными A и C.
Так эта (переопределенная) система имеет решение, то определитель матрицы
( d1 1 d2 )
( d2 1 d3 )
( d3 1 d4 )
должен быть равен 0 по модулю M. Другими словами, M является делителем определителя этой матрицы, который равен
D = d1*d4 + d3^2 + d2^2 - d2*d3 - d2*d4 - d1*d3

Пробуем в качестве M различные делители D. При известном значении M, мы легко решаем систему уравнений отностильно A и C. Чтобы установить истинное значение, используем d5 для проверки равенства:
d5 = (d4*A+C) mod M.
В большинстве случаев этой проверки будет достаточно, чтобы установить значение M (а значит, также и A, C) однозначно. Если же этой проверки все-таки недостаточно, то проверяем с помощью d6,d7 и т.д.

07.07.2006 10:18
Необходимое требование : для однозначности генереции должно быть целое M > 1
При M = 1 генерируется любая последовательность независимо от любых A, C
:))

----

(c) Математика – это то, что невозможно преодолеть :D // Тарасов Борис /



С уважением,
Борис
07.07.2006 12:33
точнее: M > max{ d1, d2, ..., dN } (-)
07.07.2006 18:01
принцип понял. ещё один вопрос, если можно.
Спасибо!
Как я понял, для любых целых положительных d1,..,d4 существует по крайней
мере одно решение системы уравнений, относительно A, C, M:

(1)
d2 = (d1*A+C) mod M
d3 = (d2*A+C) mod M
d4 = (d3*A+C) mod M

где А, С, М - целые положительные числа. При условии, что определитель D > Max{d1,..,d4} (!)

Находим D и все его делители Mi (i=1..n). Для каждого Mi
решаем систему уравнений (1) и проверяем для оставшихся d5..dN.

"При известном значении M, мы легко решаем систему уравнений отностильно A и C"
К сожалению, я не силён в модулярной арифметике, может быть подскажете
ещё как решить систему с модулем?

08.07.2006 00:50
лекции по теории чисел
Цитата

rich писал(а) :
"При известном значении M, мы легко решаем систему уравнений отностильно A и C"
К сожалению, я не силён в модулярной арифметике, может быть подскажете
ещё как решить систему с модулем?
Почитайте эти лекции по теории чисел. Особенно "§4. Теория сравнений".
09.07.2006 01:44
сомнения в том, что система всегда имеет решение
d2 = (d1*A+C) mod M
d3 = (d2*A+C) mod M
d4 = (d3*A+C) mod M

d1..d4 принадлежат Z+

Пусть нам известен М, тогда:

d2 = (d1*A+C) mod M
d3 = (d2*A+C) mod M

=>

C = (d3-d2*A) mod M

=>

A*(d1-d2) = (d2-d3) mod M (*)
_____________________________

в качестве М можно взять собственно определитель D.
k = НОД((d1-d2),D), сравнение (*) выполняется если k делит (d2-d3).
И тут возникает вопрос, а всегда ли это так ? Потому что в противном
случае, система не имеет решений.
Скажите плиз, на каком основании вы сделали вывод, что система
всегда имеет решение(очень приятное свойтсво для моей задачи).

09.07.2006 06:51
всегда при условии, что d1,d2,d3,... являются выходом линейного конгруэнтного генератора
Цитата

rich писал(а) :
в качестве М можно взять собственно определитель D.
Для рассмтриваемой системы - да, но M должно также удовлетворять следующим соотношениям для d5,d6,...

Цитата

rich писал(а) :
Скажите плиз, на каком основании вы сделали вывод, что система
всегда имеет решение(очень приятное свойтсво для моей задачи).
На основании того, что d1,d2,d3,... являются выходом линейного конгруэнтного генератора. Если же взять произвольные числа, то система может и не иметь решений, но при этом в большинстве случаев неразрешимость также можно будет установить по первым 5 числам.

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти