» Вероятность одинакового CRC32

whungry
Совершенно верно. Вывод абсолютно точен. Именно 2**(16+32) и будет вероятность совпадения для двух CRC. При том, что метод CRC16+CRC32 будет быстрее, чем некий
CRC48. А стандартная CRC (2**N) есть всего навсего наблюдатель порядка N с компенсационным звеном порядка N. (которое на каждом отсчете высчитывает воздействие для компенсации возмущения). Можно перейти и к алгебре. А передача данных - всего лишь приложение.

basilevs

Простите за цитирование самого себя, но всётаки:


Цитата:

Что эквивалентно использованию одной CRC. Вплоть до времени расчета CRC-сумм, если у вас конечно программы подсчёта CRC правильные (без наворотов из-за горе-программиста)

Как алгебраически вычисление CRC32+CRC16 быстрее, чем вычисление CRC48 из-за того,что вычисление ОСТАТКА деления на ПОЛИНОМ-48 сложнее и значит дольше.
А вот алгоритмически такие полиномы реализуются через операции сдвига в регистрах, где на каждую операцию требуется одна ассемблерная команда. Возникает вопрос о том, что операнд должен целиком помещаться в регистре, а 48-битный операнд в i386 "пролетает".
Но во-вторых, 64-битные процесоры уже вовсю пошли "в народ".
В-третьих существует ассемблерная инструкция СКВОЗНОГО сдвига ДВУХ регистров.

А во-первых, те программисты, у кого от ума не горе, а только радость, для подсчета
CRC-XX используют табличные подстановки, где на ОДИН входной байт последовательности данных выполняется XX/8 подстановок по XX/8 таблицам соответственно (для CRC32 - по одному байту из 4 таблиц).
Получаем, что для CRC32+CRC16 нужно (32/8)+(16/8)=4+2=6 операций, а для CRC48 потребуется уже (48/8)=6 операций. Почувствуйте разницу.

И снова арифметика рулит!
А "залезать" в алгебру - дык, мы ведь Академиев имени ФСФ не кончали.
В-прочем, если интересно, читай P.S.

P.S. Данную тему в своё время пришлось осваивать методом "научного" тыка (ну не было у меня программисткого образования за иключением одного семетра языка FORTRAN). И даже, не смотря на в целом о-о-очень приличное образование, курса "Теория чисел" у нас не было (самому не понятно почему). Жутко комплексуя, полез я в книги, чтобы самообразованием это как-то поправить. Так вот, оказалось, что всякие университетские курсы и учебники замечательно подходят для .... доказательства теорем. А для понимания МЕХАНИКИ процесса - совсем наоборот. Мой практический опыт программирования оказался нагляднее и понятнее. И читая про знакомые вещи часто ловил себя на мысли "Экак батенька у Вас всё запуще.. то есть запутано!"
Не берусь распространять этот подход на всё программисткое образование, но определённый компромис между теорией и практикой наобходим - это точно. Причём именно компромисс, в смысле его определения - "то, с чем согласны все, но что не устраивает никого".

P.S.S А может пора закрыть ветку - два года никто не интересовался вопросом (я сам - исключение: сначала запостил, потом на дату посмотрел) ?

Цитата:

но алгоритм CRC не является позиционным, то есть при обработке сообщения не учитывается положение содержащихся в нём байт

или я вас не понял, или вы глупость изволить говорить...

байты:
ABCD
crc32:DB1720A5

байты:
BACD
crc32:CBE43112

чтото мне подсказывает, что если и будет в коллекции дубль какогонибудь фильма, то это не приведет к ядерной катострофе, такчто для указанной цели тема сделаных постов не стоит

А чем md5 не устраивает?

md5 - время - размер - файл

A15AD4ADC2419CD17CFBDACE7F64044E 12.50 s 509411328 b for Terminator 3 (hobbit edition).avi
7CFF6AB689F5EB253B99B954BB4A71E5 33.11 s 1469149184 b for Бой с тенью.(Россия).avi
BF796534364C476AD9D728737B4AC463 16.52 s 721246208 b for Достучаться до небес.avi
B105603CC672F5BADDE0E0CC0EE76D8B 16.84 s 734447616 b for Игры мотыльков.avi
4FE73D33710298D7C5D5AB5DEF201004 13.86 s 604792320 b for Один в темноте (Alone in the dark).avi
A646A5A83B978E7C878306F9B4F4F28F 16.38 s 714821632 b for Электра.avi
F89BE64B9212ADD14D50781CB0B7EEC6 33.43 s 1506340864 b for Пираты Карибского моря.avi
C5077C9980D06DF2A384D4B6E846FF1E 16.14 s 730875904 b for СФЕРА.avi
01F2DAF81DAFC2CF289F14211FBB5DE9 15.62 s 706471936 b for Ночной дозор.avi
1A26D117095514C13DAC5A4729B3199C 14.96 s 712239104 b for 40 дней, 40 ночей.avi
6740533BD0EC5A321D50A09E5E62F3E7 14.84 s 706191360 b for 50 Первых поцелуев.avi
B92A9BAE6474C457012A461C13862201 13.82 s 685217792 b for Мартовские коты (Tom cats).avi
FCD8FB77275177857FCEC276D1B207BF 16.29 s 780216320 b for Мимино.avi
6621701EB621C39612D2495864BC6CFD 15.02 s 715808768 b for Одиночество крови.avi
329042B71F645A116814E05C1BC7C293 18.53 s 882573312 b for Паспорт.avi
72EDC1771CC39A388028C215E5773EE6 20.71 s 986814464 b for Приключение итальянцев в России.avi
70B399CDDB1A42014A50ADEE0BF2501A 14.88 s 708194304 b for Свадьба.avi
DBAAAC4B2DC21B0B8A76E9F972C949BA 26.58 s 1265868800 b for Служебный роман.avi
4F694A374974B154100073AC5631EA1D 15.41 s 733796352 b for Troi2.cd1.avi
137FA36068CC23D07190DB25F1C218F6 15.59 s 733863936 b for Troi2.cd2.avi
7BFA92206D73B633793901E70E1D5303 15.38 s 732409856 b for Spider-Man2_CD1.avi
A03D922F1615F088211128051ABC7D78 15.43 s 735313920 b for Spider-Man2_CD2.avi

Никто не знает, какой алгоритм используют в пиринговых сетях ? Просто md5 от файла?

basilevs
Простите за мою неопытность, а можно поподробнее про вероятность и степень двойки?
Эта вероятность того, что текущий CRC совпадает с CRC пакета данных, или это вероятность того что такой CRC может быть у такого пакета данных?

Честно говоря я не понимаю некоторых технических тонкостей. А именно как можно говорить о вероятности при приёме двухбайтового CRC отвечающего за двухбайтовую посылку? Например если я буду просто удваивать данные, то вполне понятно, что 0x0123h соответствует именно $0123, а не $1230. Таким образом вероятность попадания искажающего сигнала на двухбайтный CRC одновременно c попаданием искажения на двухбайтную посылку идущую перед CRC не такая же, как если бы посылка была двухкилобайтной?
Если так то знание аббревиатуры CRC не спасает вероятность в случае с короткими посылками или при переходе в аналоговую форму происходит расширение двух байт и сужение CRC соответствующим уровню модуляции/демодуляции? Думаю что мои домыслы слабо понятны, а вопрос тем не менее понятен.

Pinocchio
Вообще не понял вопроса. Введение CRCm есть внесение некоторой избыточности в передаваемой информации. Для пакета длиной в N-байт избыточность можно оценить
как (N+lb(m))/N. (для CRC16 = (N+2)/N)
При искажении в посылке произвольного количества бит вероятность совпадения CRC
в точности равна обраному от числа возможных значений, принимаемых CRC16. (т.е. =1/2**16)
Другое дело, что для стандартных CRC16 ($A001 и $1021) искажающий сигнал, сохраняющий целостность посылки, должен представлять собой суперпозицию из набора единичных возмущений и их следов.

Подводя итог, скажу, чудес не бывает, только повышение избыточности сигнала до приемлемого соотношения сигнал/шум.

По моему,нет алгоритма для создания строки,однозначно идентифицирующей данные,так как кол-во однозначно идентифицирующих комбинаций не будет>2^<длина данных в битах>

Думал, что тема заглохла.

Цитата:

По моему,нет алгоритма для создания строки,однозначно идентифицирующей данные,так как кол-во однозначно идентифицирующих комбинаций не будет>2^<длина данных в битах>

Еще раз повторю, что избыточность - вот ключевое слово. Если исходная комбинация -избыточна - возможно сжатие без потерь. Все сигнатуры - всего навсего есть способы сжатия с потерями. И дают возможность сравнивать два комбинации с некоторой вероятностью, которую можно оценить как P=1/2^^LenghtSignature в пределе.

Кстати,нет ни у кого алгоритма(желательно на Васике,можно на Асме) рассчёты ЦэРэЦэ произвольной длины?

На мой взгляд, вот это совершенно точное утверждение. Чтобы однозначно идентифицировать данные нужно их однозначно сравнить.


Цитата:

По моему,нет алгоритма для создания строки,однозначно идентифицирующей данные,так как кол-во однозначно идентифицирующих комбинаций не будет>2^<длина данных в битах>

привет всем! помогите пожалуйста подобрать 3 пароля к значениям CRC 32:
F4A31042
AD50C816
08D81125
ПЛИЗ, ПОМОГИТЕ КТО МОЖЕТ! ПАРОЛЬ ПРОДАЮТ ЗА 270 РУБЛЕЙ, НО ОН ЛАЖА!!!

Хоттабыч, а что означает "подобрать пароль к CRC32" ????! o_0
СКС32 - это контрольная сумма набора байт!!
Как к ней можно пароль подобрать?! ;(

на каком-то из форумов я читал, что мона подобрать пароль по crc32. что есть программы, способные по етой гадости подобрать слово с такойже контрольой!!!

XOTTABbICH

Цитата:

на каком-то из форумов я читал, что мона подобрать пароль по crc32

глупости читали. какое отношение пароль имеет к CRC32?

не знаю! а пароля к chets_lineageC5_C4.rar никто не знает?

XOTTABbICH
при чем тут прикладной программинг? спрашивайте там, откуда скачивали
читайте
http://allcheats.ru/t41398/

XOTTABbICH
поискать не пробовали?
судя по поиску - поиск в Гугле — это просто "кидалово"...

А паралельный вопрос - насколько выше вероятноть уникального хеша состоящего из восьми байт? Первые четыре байта - обычный crc32, следующие четыре байта adler32. Я использую такие комбинации. Думал назвать crc64, но как-то нету формул чтобы посчитать вероятность. Думаю простым перемножением нельзя.

Пришла на ум задачка - одно яйцо варится 20 минут, сколько минут будут вариться два яйца?

delover
если одновременно - то 20 минут. если последовательно - то 40 минут... :)
а это к чему этот вопрос в данной теме?!

SERGE_BLIZNUK
Думаю ответ немного другой. Важно не сколько они будут вариться, а сколько человек будет их есть. CRC64, про который писал состряпать легко. Вероятность совпадения коллосально ниже. Но почему-то лёгкий вариант не выбирается. Всё надо оптимизировать сразу. А про то что удобно ли будет писать Int64 пока думать рано? Просто внедрять такие штучки надо постепенно.

зы
Не моё мнение, но часто слышу, что уже почти все переходят на 64-битный хеш. Не буду рассказывать как он делается.

Добавлено:
забыл. кажется у CRC32 не очень показатели для большого количества маленьких файлов.

delover
CRC это контрольная сумма, а не хэш. Задача уникальности и сложности подбора, как в MD5, SHA, etc. там принципиально не ставится.

CRC применяется, например, для быстрой оценки целостности переданного блока данных - CRC32 целого блока и CRC32 того же блока с каким-нибудь случайным дефектом с очень большой вероятностью будут различаться. Тут фактически сравниваются CRC всего двух файлов (до и после передачи), а не "большого количества маленьких".

dmka
Спасибо, весьма квалифицировано.

Цитата:

Задача уникальности и сложности подбора, как в MD5, SHA, etc. там принципиально не ставится.

И не ставилась. Что такое хеш? В переводе - мусор, который позволяет выполнять задачи быстро.


Цитата:

CRC32 целого блока и CRC32 того же блока с каким-нибудь случайным дефектом

Вы хотели сказать что длинна одинаковая, а CRC разные? А вместо длинны можно Adler передавать, чтобы усилить вероятность?


Цитата:

а не "большого количества маленьких".

Как это? В операции сравнения есть место для большего количества компонентов? Не знал.

1. Для востановления частично утраченных данных при имеющемся даром CRC, можно использовать контрольную сумму. Например: у меня есть Raid массив, не полноценная зеркалка, а хранящий только важные пакеты.

2. Ко мне пришли "битые данные" из категории важных только для скорости работы пользователя. Я однозначно уверен, что если у меня есть уже такой CRC на рейде, то это именно такой пакет... И я должен отказаться?

3. Но! Есть ещё два программиста которые спорят, один знает adler32 и говорит что он лучше, другой вообще не слышал про adler, но знает CRC быстрый и точный. Что мне делать? Леплю из обоих 64 байта... Больших подробностей сообщить не могу. Думайте сами.

Так как вопросов не возникло, я предположу, что теперь уже совсем просто. Данные не потерялись, их просто никто не сохранял. Сохранялся только CRC. Если есть строка с определённым CRC, то значит у этой строки есть определённое свойство. Если нет строки с таким CRC, то это значит что сохранённое свойство не удалось востановить. Трудно?