Недавно мне попалась интересная задачка, хочу поделиться. У меня решение заняло много времени, может кто-то найдет более простое или быстрое.
Есть хеш-функция, преобразующая строку длиной Size бит в хеш такой же длины:
void simpleHash(
const unsigned input[Size / 32], // Входная строка
unsigned output[Size / 32] // Возвращаемый хеш
)
{
for (int i = 0; i < Size / 32; i++)
output[i] = 0;
for (int i = 0; i < Size / 2; i++)
for (int j = 0; j < Size / 2; j++)
output[(i + j) / 32] ^= ((input[i / 32] >> (i % 32)) &
(input[j / 32 + Size / 32 / 2] >> (j % 32)) & 1) << ((i + j) % 32);
}
Подразумевается, что sizeof(unsigned) = 4.
Задача: написать программу, находящую все прообразы заданной строки. T.е. по заданному output найти все такие input, что simpleHash(input) = output.
Задача подразумевает несколько уровней сложности, для Size = 64, 128, 256, 512, ну и далее. Ограничения: программа должна завершить вычисления на обычном современном компьютере за одну секунду, используя 1 процессор; нельзя использовать много внешних данных: пусть все исходники занимают не более 3Мб.
Пример для Size = 64:
Вход: 00007891 00000000
Выход:
00000001 00007891
00000073 0000013f
0000013f 00000073
00007891 00000001
Для Size = 128:
Вход: 12345678 aaaaaaaa 0987654 321bbbb7
Выход:
3e461484 52ae91c0 ba82385e f2c3d99a
5d411c2f 7961eccd 7c8c2908 a55d2380
7c8c2908 a55d2380 5d411c2f 7961eccd
ba82385e f2c3d99a 3e461484 52ae91c0
Чтобы придать задаче немного азарта, попробуйте разгадать сообщение, хеш которого
71dc95f0 7e5d3665 08673bdd 0a65eeaa 6a6c3aca de8c4c4a b9dfc8e2 ea2fc2ea 97affa53 a7135a87 2ecabcb3 84ff2c7d 8e3523de b25606a9 76186114 0c3709f8
Здравствуйте, ineaugh, Вы писали:
I>Чтобы придать задаче немного азарта, попробуйте разгадать сообщение, хеш которого
I>71dc95f0 7e5d3665 08673bdd 0a65eeaa 6a6c3aca de8c4c4a b9dfc8e2 ea2fc2ea 97affa53 a7135a87 2ecabcb3 84ff2c7d 8e3523de b25606a9 76186114 0c3709f8
056f6b78 fd9ea41d 2df5b45b 2322266e 3949319c bcb822c4 f4e653b1 387c750d 9b0b56a2 54ca332b c9848495 051238ab 7be258f2 2f91ae78 392bed76 5a84f86f
0aded6f0 fb3d483a 5beb68b7 46444cdc 72926338 79704588 e9cca763 70f8ea1b cd85ab51 aa651995 e4c2424a 02891c55 3df12c79 17c8d73c 9c95f6bb 2d427c37
109029ba b0b73231 3c903337 b9103a39 b0b739b6 34b9b9b4 37b71717 17101717 90cad8d8 de40cce4 deda4082 d8e0d0c2 5c86cadc e8c2eae4 d25840d0 eadac2dc
19e59508 948eaaa1 33e15d1d e1eead0e c781917d a240a2d5 adb2677e 3fe17ada b230be7e ad4e26d4 19cf2233 734f010c 52b1f1b7 c1718e41 33b15151 514faeae
21205374 616e6462 7920666f 72207472 616e736d 69737369 6f6e2e2e 2e202e2e 48656c6c 6f206672 6f6d2041 6c706861 2e43656e 74617572 692c2068 756d616e <<
2432b636 b7903339 b7b69020 36383430 1721b2b7 3a30bab9 34961034 3ab6b0b7 4240a6e8 c2dcc8c4 f240ccde e440e8e4 c2dce6da d2e6e6d2 dedc5c5c 5c405c5c
33cb2a10 291d5542 67c2ba3b c3dd5a1c 8f0322fb 448145ab 5b64cefd 7fc2f5b5 59185f3f d6a7136a 0ce79119 b9a78086 a958f8db e0b8c720 19d8a8a8 28a7d757
3616ad44 a9946657 9309092a 0a247157 f7c4b1e4 5f235cf0 7257daec b509f0de 82b7b5bc fecf520e 16fada2d 11911337 1ca498ce de5c1162 fa7329d8 1c3e3a86
4240a6e8 c2dcc8c4 f240ccde e440e8e4 c2dce6da d2e6e6d2 dedc5c5c 5c405c5c 2432b636 b7903339 b7b69020 36383430 1721b2b7 3a30bab9 34961034 3ab6b0b7
48656c6c 6f206672 6f6d2041 6c706861 2e43656e 74617572 692c2068 756d616e 21205374 616e6462 7920666f 72207472 616e736d 69737369 6f6e2e2e 2e202e2e <<
568efdf3 feaf2abe 2d46c6df 079b24fe 4613748b 38597944 a5be1bcd 77c68458 f9b5b250 a914c7e9 c9592792 3dc3c44b 2e71dee8 d72fc378 a74462de 2fa859f6
59185f3f d6a7136a 0ce79119 b9a78086 a958f8db e0b8c720 19d8a8a8 28a7d757 33cb2a10 291d5542 67c2ba3b c3dd5a1c 8f0322fb 448145ab 5b64cefd 7fc2f5b5
64617cfc 5a9c4da9 339e4467 e69e0218 a563e36e 82e31c82 6762a2a3 a29f5d5c 8cf2ca84 ca475550 19f0ae8e f0f75687 e3c0c8be 5120516a 56d933bf 1ff0bd6d
6c57da5a d8b0554b d8dbb061 5a485c51 3962d7d9 4e51cfcb 5dba305c 4fdbd1d9 c1c06258 be4bb843 ae3fbbb5 5c3fa7a3 41b45db6 4e5da24e b5b43434 343fcbcb
82b7b5bc fecf520e 16fada2d 11911337 1ca498ce de5c1162 fa7329d8 1c3e3a86 3616ad44 a9946657 9309092a 0a247157 f7c4b1e4 5f235cf0 7257daec b509f0de
8380c4b0 7c977087 5c7f776b b87f4f47 8368bb6c 9cbb449c 6b686868 687f9797 b62bed2d ec582aa5 ec6dd830 ad242e28 9cb16bec 2728e7e5 aedd182e 27ede8ec
84814dd0 85b99188 e48199bd c881d1c9 85b9cdb5 a5cdcda5 bdb8b8b9 b880b8b9 92195b1b 5bc8199c 5bdb4810 9b1c1a18 8b90d95b 1d185d5c 9a4b081a 1d5b585b
8cf2ca84 ca475550 19f0ae8e f0f75687 e3c0c8be 5120516a 56d933bf 1ff0bd6d 64617cfc 5a9c4da9 339e4467 e69e0218 a563e36e 82e31c82 6762a2a3 a29f5d5c
90cad8d8 de40cce4 deda4082 d8e0d0c2 5c86cadc e8c2eae4 d25840d0 eadac2dc 109029ba b0b73231 3c903337 b9103a39 b0b739b6 34b9b9b4 37b71717 17101717
92195b1b 5bc8199c 5bdb4810 9b1c1a18 8b90d95b 1d185d5c 9a4b081a 1d5b585b 84814dd0 85b99188 e48199bd c881d1c9 85b9cdb5 a5cdcda5 bdb8b8b9 b880b8b9
9b0b56a2 54ca332b c9848495 051238ab 7be258f2 2f91ae78 392bed76 5a84f86f 056f6b78 fd9ea41d 2df5b45b 2322266e 3949319c bcb822c4 f4e653b1 387c750d
ad1dfbe6 fd5e557c 5a8d8dbf 0f3649fc 8c26e916 70b2f288 4b7c379a ef8d08b1 fcdad928 548a63f4 e4ac93c9 1ee1e225 1738ef74 6b97e1bc 53a2316f 17d42cfb
b230be7e ad4e26d4 19cf2233 734f010c 52b1f1b7 c1718e41 33b15151 514faeae 19e59508 948eaaa1 33e15d1d e1eead0e c781917d a240a2d5 adb2677e 3fe17ada
b62bed2d ec582aa5 ec6dd830 ad242e28 9cb16bec 2728e7e5 aedd182e 27ede8ec 8380c4b0 7c977087 5c7f776b b87f4f47 8368bb6c 9cbb449c 6b686868 687f9797
c1c06258 be4bb843 ae3fbbb5 5c3fa7a3 41b45db6 4e5da24e b5b43434 343fcbcb 6c57da5a d8b0554b d8dbb061 5a485c51 3962d7d9 4e51cfcb 5dba305c 4fdbd1d9
cd85ab51 aa651995 e4c2424a 02891c55 3df12c79 17c8d73c 9c95f6bb 2d427c37 0aded6f0 fb3d483a 5beb68b7 46444cdc 72926338 79704588 e9cca763 70f8ea1b
d651c282 f7d26b7d 2a516654 95d10314 f7d212d9 439292c3 54d3f3f2 f3d0f3f2 f75c8cf8 8c7a6660 115f34f4 5f5a64fa 42808f2b 61c061b3 6491dd2a 155f29b6
d8afb4b4 b160aa96 b1b760c3 b490b8a3 72c5afb2 9ca39f96 bb7460b8 9fb7a3b2 e0e0312c df25dc21 d71fddda 2e1fd3d1 20da2edb 272ed127 dada1a1a 1a1fe5e5
e0e0312c df25dc21 d71fddda 2e1fd3d1 20da2edb 272ed127 dada1a1a 1a1fe5e5 d8afb4b4 b160aa96 b1b760c3 b490b8a3 72c5afb2 9ca39f96 bb7460b8 9fb7a3b2
eb28e141 7be935be 1528b32a cae8818a fbe9096c 21c94961 2a69f9f9 79e879f9 eeb919f0 18f4ccc1 22be69e9 beb4c9f4 85011e56 c380c366 c923ba54 2abe536c
eeb919f0 18f4ccc1 22be69e9 beb4c9f4 85011e56 c380c366 c923ba54 2abe536c eb28e141 7be935be 1528b32a cae8818a fbe9096c 21c94961 2a69f9f9 79e879f9
f75c8cf8 8c7a6660 115f34f4 5f5a64fa 42808f2b 61c061b3 6491dd2a 155f29b6 d651c282 f7d26b7d 2a516654 95d10314 f7d212d9 439292c3 54d3f3f2 f3d0f3f2
f9b5b250 a914c7e9 c9592792 3dc3c44b 2e71dee8 d72fc378 a74462de 2fa859f6 568efdf3 feaf2abe 2d46c6df 079b24fe 4613748b 38597944 a5be1bcd 77c68458
fcdad928 548a63f4 e4ac93c9 1ee1e225 1738ef74 6b97e1bc 53a2316f 17d42cfb ad1dfbe6 fd5e557c 5a8d8dbf 0f3649fc 8c26e916 70b2f288 4b7c379a ef8d08b1
Маркером
<< отмечены строки с текстом в ascii.
I>Задача: написать программу, находящую все прообразы заданной строки. T.е. по заданному output найти все такие input, что simpleHash(input) = output.
I>Задача подразумевает несколько уровней сложности, для Size = 64, 128, 256, 512, ну и далее. Ограничения: программа должна завершить вычисления на обычном современном компьютере за одну секунду, используя 1 процессор;
Factorization of polynomials over finite fields
Здравствуйте, watchmaker, Вы писали:
W>Factorization of polynomials over finite fields
Круто. Я вот далеко не сразу догадался.
А как именно ты решил? Реализовал один из алгоритмов? Я использовал библиотеку NTL.
Здравствуйте, watchmaker, Вы писали:
W>Factorization of polynomials over finite fields
Так это сводится к многочлену от одной переменной? Или к многочленам от нескольких (и тогда результант и факторизация)?
Здравствуйте, FireHose, Вы писали:
FH>Здравствуйте, watchmaker, Вы писали:
W>>Factorization of polynomials over finite fields
FH>Так это сводится к многочлену от одной переменной?
Да. Идея в том, что если рассматривать исходные данные побитово, то от кода программы останется только одна формула:
Где h — хеш, а u,v — два полуслова исходных данных.
А формула задаёт обычное умножение двух чисел, но без переноса переполнения в следующий разряд. И вся задача переформулируется в виде: дано число, разложить его на множители.
Вместо чисел можно рассматривать многочлены в GF(2) — будет то же самое.
