Подтвердить что ты не робот

Может ли CRC32 (C) когда-либо вернуться к 0?

Мне интересно, если CRC32 sum и CRC32C, в частности, когда-либо возвращаются к 0? Простым ответом было бы "да" при достаточно большом наборе данных. Тем не менее, мне было интересно, есть ли какие-либо условия в стандарте CRC32C, которые явно предотвратили бы это.

Вариант использования для этого заключается в том, что мне нужно проверить, является ли удаленный файл пустым, и все, что у меня есть, это его контрольная сумма CRC32C. Таким образом, другими словами, могу ли я заключить, что если CRC32C равно 0, то файл, как гарантируется, будет пустым.

Если возможно, укажите любую ссылку на стандарт, где это определено.

4b9b3361

Ответ 1

Ноль имеет такую ​​же вероятность, как любое другое значение контрольной суммы CRC32. CRC - это, по существу, остаток деления всего входа (принятого как одно большое двоичное число) на предварительно выбранное значение. Если вход делится на это значение, остаток и, следовательно, CRC равен нулю.

Ответ 2

@Янек почти полностью прав.

Просто для удовольствия, вот пятисимвольная последовательность, которая дает CRC-32C нуля: DYB|O. Вот четырехбайтная последовательность в шестнадцатеричном формате, которая дает ноль: ab 9b e0 9b. Фактически, это единственная четырехбайтовая последовательность, которая может это сделать. Нет трехбайтовых или более коротких последовательностей, которые дадут вам нуль. Именно здесь @Yanek не совсем прав, поскольку для трехбайтовых или более коротких последовательностей нуль не так вероятен. Вероятность получения нуля равна нулю в этих случаях.

Ответ 3

Как насчет этого, а не 32-разрядного CRC, хотя:

1011 | 110011001010.000
       1011
       ----
        1111
        1011
        ----
         1001
         1011
         ----
           1000
           1011
           ----
             1110
             1011
             ----
              1011
              1011
              ----
                  0000 (...)
                  1011
                  ----
                  1011
                  1011
                  ----
                  0000

Или:

1100 | 11001010.000
       1100
       ----
           1010
           1100
           ----
            1100
            1100
            ----
            (...) 0