По словам Шнаера, среди финалистов нет кандидата с явным преимуществом: некоторые быстрее других, но не на порядки
Я думаю, там все-таки сравнение идет с SHA-2 (конкретно SHA-512).
По поводу системы уравнений:
Сейчас перечитал и заметил, что даны X0, X1, X2, X3. До этого подумал что даны только X1, X2, X3 — придумал небольшую хитрость для вычисления a, c, m по трем выходам:
Допустим даны
X0
X1 = X0 * a + c (mod m),
X2 = X1 * a + c (mod m).
Если при выборе a, c, m для максимизации периода следовали условиям (в частности, (a — 1) делит все простые делители m), то (a — 1) ** n = s*m для некоторых n > n_0 и s=s(n). При этом n_0 не больше максимальной степени простого числа в разложении m.
Обозначим Q = (X2 — X1) — (X1 — X0). Тогда Q**n == z * m. Если взять достаточно большое n, можно вычислить z * m и высчитать c' и a' по этому модулю. Если выходное число X_i' не совпадает с соответствующим известным выходом X_i,
то можно уменьшить модуль с помощью НОД: new_mod = gcd(mod, X_i' — X_i) и пересчитать a' и c'. Опять же, если получить 4й, 5й,… выходы, то очень быстро можно восстановить реальный m, а следовательно, a и c. Есть еще куча способов быстрее восстановить m (например в в z может быть много небольших простых делителей, на которые можно поделить с помощью небольшого перебора). Кроме того, перед возведением в степерь Q можно умножить на специальным образом сформированное число, чтобы необходимое n было не слишком велико для вычислений.
Проверил на нескольких случайных a, c, m с m до 1024 — бит — восстанавливается достаточно быстро.
По словам Шнаера, среди финалистов нет кандидата с явным преимуществом: некоторые быстрее других, но не на порядкиЯ думаю, там все-таки сравнение идет с SHA-2 (конкретно SHA-512).
Сейчас перечитал и заметил, что даны X0, X1, X2, X3. До этого подумал что даны только X1, X2, X3 — придумал небольшую хитрость для вычисления a, c, m по трем выходам:
Допустим даны
X0
X1 = X0 * a + c (mod m),
X2 = X1 * a + c (mod m).
(X2 — X1) — (X1 — X0) = a * (X1 — X0) — (X1 — X0) (mod m)
X2 + X0 — 2*X1 = (a — 1) * (X1 — X0) + k*m
Если при выборе a, c, m для максимизации периода следовали условиям (в частности, (a — 1) делит все простые делители m), то (a — 1) ** n = s*m для некоторых n > n_0 и s=s(n). При этом n_0 не больше максимальной степени простого числа в разложении m.
Обозначим Q = (X2 — X1) — (X1 — X0). Тогда Q**n == z * m. Если взять достаточно большое n, можно вычислить z * m и высчитать c' и a' по этому модулю. Если выходное число X_i' не совпадает с соответствующим известным выходом X_i,
то можно уменьшить модуль с помощью НОД: new_mod = gcd(mod, X_i' — X_i) и пересчитать a' и c'. Опять же, если получить 4й, 5й,… выходы, то очень быстро можно восстановить реальный m, а следовательно, a и c. Есть еще куча способов быстрее восстановить m (например в в z может быть много небольших простых делителей, на которые можно поделить с помощью небольшого перебора). Кроме того, перед возведением в степерь Q можно умножить на специальным образом сформированное число, чтобы необходимое n было не слишком велико для вычислений.
Проверил на нескольких случайных a, c, m с m до 1024 — бит — восстанавливается достаточно быстро.
Лучше уж классический вариант