Клод Шеннон в середине прошлого века переложил оценку непрерывной энтропии термодинамики (температуры) на оценку энтропии текстов (дискретных последовательностей). Это сегодня стало классикой. К сожалению, для длинных чисел, например, кодов длинного ключа, оценка энтропии по Шеннону требует тестовых выборок огромного размера. Причина — экспоненциальная вычислительная сложность оценок энтропии по Шеннону. Одним из путей обхода экспоненциальной вычислительной сложности является переход к использованию энтропии Ципфа или в более общем виде энтропии случайных последовательностей языков Мандельброта. Как критерий Ципфа, так и критерий Бенуа Мандельброта, имеют линейную вычислительную сложность и могут быть использованы при оценке качества случайных последовательностей.
< ... >
In the middle of the last century, Claude Shannon shifted the assessment of the continuous entropy of thermodynamics (temperature) to the assessment of the entropy of texts (discrete sequences). This has become a classic today. Unfortunately, for long numbers, such as long key codes, Shannon entropy estimation requires huge test samples. The reason is the exponential computational complexity of Shannon entropy estimates. One way around exponential computational complexity is to use the Zipf entropy or, more generally, the entropy of random sequences of Mandelbrot languages. Both the Zipf criterion and the Benoit Mandelbrot criterion have linear computational complexity and can be used in assessing the quality of random sequences.
Keywords:
Shannon entropy, exponential computational complexity, Zipf entropy, linear computational complexity, small samples, white noise quality assessment
Полную версию статьи смотрите на страницах журнала «Защита информации. Инсайд»
