Обратите внимание, что
вещь - пол (вещь / потолок) * ceil
такая же, как (вещь% ceil), где% является оператором по модулю (остатокпосле деления).В вашем случае,
$ dec = ($ num * $ prime)% $ ceil
Обратите внимание, что это всегда между 0 и $ ceil-1, поэтомуВы не можете получить значение $ dec, равное $ ceil.С другой стороны, для данного $ dec между 0 и $ ceil-1 вы можете эффективно найти решение $ num между 0 и $ ceil-1.
(наблюдение состоит в том, что если $ num являетсярешение, чем $ num + i * $ ceil для любого i, также является решением.)
Вот как вы поступите для $ dec = 42.
Мы будем использовать тот факт, что $ ceil= 2 ^ 5 * 31 ^ 5.Таким образом, уравнение дает
42 = ($ num * 566201239)% (2 ^ 5 * 31 ^ 5)
Сначала давайте найдем ($ num% 2)другими словами, является ли $ num нечетным или четным.Мы берем обе части уравнения по модулю 2:
0 = 42% 2 = (($ num * 566201239)% (2 ^ 5 * 31 ^ 5))% 2.
Поскольку 2 делит $ ceil, правая часть равна ($ num * 566201239)% 2.Если это должно быть 0, $ num должен быть четным (поскольку $ prime не является).Таким образом, мы имеем ($ num = 2 * $ a) для некоторых $ a и
2 * 21 = 42 = (2 * $ a * 566201239)% (2 ^ 5 * 31 ^ 5),
после деления на 2 получаем
21 = ($ a * 566201239)% (2 ^ 4 * 31 ^ 5).
Обратите внимание, что часть после знака% также была разделена на 2.Продолжаем, взяв это по модулю 2. Мы получаем, что $ a нечетно, то есть $ a = 2 * $ b + 1 для некоторого $ b.
21 = ((2 * $ b +1) * 566201239)% (2 ^ 4 * 31 ^ 5),
349931614 ≡ 21-566201239 ≡ (2 * $ b * 566201239)% (2 ^ 4 * 31 ^ 5),
(я начал использовать конгруэнтную запись ≡; под x ≡ y% z я имею в виду x% z = y% z).
174965807 ≡ ($ b * 566201239)% (2 ^ 3 * 31 ^ 5)
Продолжаем ...
174965807 ≡ ((2 * $ c + 1) * 566201239)% (2^ 3 * 31 ^ 5)
174965807 - 566201239 ≡ (2 * $ c * 566201239)% (2 ^ 3 * 31 ^ 5)
66830984 ≡ 2 * $ c * 566201239)% (2 ^ 3 * 31 ^ 5)
33415492 ≡ ($ c * 566201239)% (2 ^ 2 * 31 ^ 5)
33415492 ≡ (2 * $ d * 566201239)% (2 ^ 2 * 31 ^ 5)
16707746 ≡ ($ d * 566201239)% (2 * 31 ^ 5)
16707746 ≡ (2 * $ e * 566201239)% (2 * 31 ^ 5)
8353873 ≡ ($ e * 566201239)% (31 ^ 5).
Чтобы суммировать подстановки, напомним, что
$ num = 2 *$ a = 2 * (2 * $ b + 1) = 4 * $ b + 2 = 4 * (2 * $ c + 1) +2 = 8 * $ c + 6 = 8 * 2 * $ d + 6 =8 * 2 * 2 * $ e + 6 = 32 * $ e + 6
Кстати, мы также можем уменьшить $ простое число в уравнении по модулю 31 ^ 5 (мы можем продолжать сокращатьэто по текущему модулю на каждом шаге, но кого это волнует?):
8353873 ≡ ($ e * 22247370)% (31 ^ 5).
Мы можемвидим, что множитель не является простым, но на самом деле это не имеет значения.
Теперь мы рассмотрим последнее уравнение по модулю 31.
8353873 ≡ ($ e * 22247370)% (31 ^ 5).
24 8353873 ≡ ($ e * 22247370)% (31 ^ 5) ≡ ($ e * 22247370) ≡ ($ e * 3)% 31
В таблице поиска, кратной 3 по модулю 31, мы находим, что $ e≡8% 31 или $ e = 31 * $ f + 8:
8353873 ≡ ((31* $ f + 8) * 22247370)% (31 ^ 5).
8353873 - 8 * 22247370 ≡ (31 * $ f * 22247370)% (31 ^ 5).
21498198353873 - 8 * 22247370 70 (31 * $ f * 22247370)% (31 ^ 5).
69349 = 2149819/31 ≡ ($ f * 22247370)% (31 ^ 4)
и мы продолжаем ...
2 69349% 31 ≡ ($ f * 22247370)% (31 ^ 4) ≡ ($ f * 3)% 31
$ f ≡ 11% 31
$ f = 31 * $ g + 11
69349 ≡ ((31 * $ g + 11) * 22247370)% (31 ^ 4)
81344 69349 - 11 * 22247370 ≡ (31 * $ g * 22247370)% (31 ^ 4)
2624 ≡ ($ g * 22247370)% (31 ^ 3)
Давайте снова уменьшим множитель ...
2624 ≡ ($ g * 23284)% (31 ^ 3)
20 ≡ 2624 ≡ ($ g * 23284)% (31 ^ 3) = ($ g * 3)% 31
$ g = 31 * $ h + 17
2624 ≡ ((31 *$ h + 17) * 23284)% (31 ^ 3)
23870 ≡ 2624 - 17 * 23284 ≡ (31 * $ h * 23284)% (31 ^ 3)
770 ≡($ h * 23284)% (31 ^ 2)
26 ≡ 770 ≡ ($ h * 23284)% (31 ^ 2) = ($ h * 3)% 31
$h = 31 * $ i + 19
770 ≡ ((31 * $ i + 19) * 23284)% (31 ^ 2)
434 ≡ 770 - 19 * 23284 ≡ (31* $ i * 23284)% (31 ^ 2)
14 = ($ i * 3)% 31
$ i = 15
и обратноПодстановка мы получаем $ h = 31 * 15 + 19 = 484, $ g = 31 * $ h + 17 = 15021, $ f = 31 * $ g + 11 = 465662, $ e = 31 * $ f + 8 = 14435530,$ num = 32 * e + 6 = 461936966.
Осталось только проверить результат:
. >>> (461936966 * 566201239)% 916132832
42
Ух ты!: -)
Парень из блога должен был использовать md5.