Клод Шеннон в середине прошлого века переложил энтропию термодинамики на тексты (дискретные последовательности). Это сегодня стало классикой. К сожалению, для длинных чисел, например, для кодов, зашифрованных на длинном ключе текстов, оценка энтропии по Шенонну требует выборки данных огромного размера. Причина — экспоненциальная вычислительная сложность оценок энтропии по Шеннону. Одним из путей обхода экспоненциальной вычислительной сложности является упорядочивание хаоса длинных последовательностей до последовательностей с меньшим уровнем случайности. В статье рассматривается выполнение упорядочивания независимых данных до почти детерминированной функции. Предложено использование процедур упорядочивания данных для синтеза еще одной упрощенной оценки энтропии, имеющей квадратичную вычислительную сложность. При этом шкала значений энтропии может оказаться близкой к шкале значений энтропии Шеннона — Хэмминга, имеющей линейную вычислительную сложность.
< ... >
Claude Shannon in the middle of the last century transferred the entropy of thermodynamics to texts. Unfortunately, for long numbers, for example, for codes encrypted on a long key of texts, estimating Shannon entropy requires a huge data sample size. One way around exponential computational complexity is to streamline the chaos of long sequences into sequences with less randomness. The article discusses the implementation of ordering independent data into an almost deterministic function. It is proposed to use data ordering procedures to synthesize another simplified entropy estimate that has quadratic computational complexity. In this case, the scale of entropy values may be close to the scale of Shannon — Hamming entropy values, which has linear computational complexity.
Keywords:
Shannon entropy, chaos ordering, quadratic computational complexity, small samples
Полную версию статьи смотрите на страницах журнала «Защита информации. Инсайд»
