Рассмотрим группу по умножению по модулю 2^32 она изоморфна декартову произведению двух групп по сложению по модулям 2^30 и 2. В исходной группе ровно 2^31 элемент, все нечётные. Видно, что самый длинный цикл в ней равен 2^30, такой элемент не сложно найти перебором, их там очень много, пусть такое число - A.
Далее случайное число формируется по формуле: (A^k)*B.
B - это какой то любой элемент группы (нечёное число), имеют смысл только 1 и 3, остальные получаются сдвигом степени.
Его легко посчитать используя разложение степени на сумму степеней двойки, просто анализируя двоичное представление.
k=53=(110101)
A^53=A*A^52=A*(A*A)^26=A*((A*A)^2)^13=...
Сепени равные 0, 1, 2, 4, 8, 16, 32, ... 2^29 можно заранее посчитать и записать в таблицу. Потом согласно битам k перемножить.
В качестве случайного числа взять 30 старших битов (или их подстроку), потому что младший бит всегда 1, а не самый младший тоже вроде постоянен.
Сообщение отредактировал Task Solver - Jan 30 2014, 19:04
|