Create: Update:
def paradox(n):
def f(x):
return ((x * x) % n + x) % n
slow = fast = 0
while True:
slow = f(slow)
fast = f(f(fast))
if slow == fast:
return slow
print(paradox(31337))
На первый взгляд — простой цикл с двумя указателями: slow и fast.
Но на деле это алгоритм Флойда ("заяц и черепаха"), используемый для нахождения цикла в псевдослучайной последовательности.
📌 Функция f(x):
Простая квадратичная функция, по сути — генератор псевдослучайных чисел по модулю n.
📌 Что происходит:
slow движется на 1 шаг за итерацию: f(x)
fast — на 2 шага: f(f(x))
Как только slow == fast, цикл найден — значит, последовательность начала повторяться.
🔍 Почему это парадокс?
Потому что вы начинаете с 0, вычисляете кучу якобы "случайных" значений, и внезапно обнаруживаете цикличность в хаосе.
Вы не знаете длину цикла, период или точку входа, но находите пересечение без хранения всей истории.
💡 Эта техника используется в:
криптографии (Pollard's rho для факторизации),
генерации чисел,
распознавании псевдопериодов,
хаотических системах.
🎯 Челлендж для продвинутых:
Измените f(x) на pow(x, 3, n) — как это повлияет на цикл?
Реализуйте поиск начала цикла и длины периода, используя Флойда + Брента.
Придумайте, как использовать это для взлома слабых генераторов случайных чисел.
🧠 Эта задача не просто про числа — она про границу между случайным и детерминированным.
