Мне приснился сон с элементами математики. А когда математика влезает в голову во сне, с этим надо что-то делать. Надо ее из головы извлекать и размазывать по разным доскам.
Занимает мою голову, совершенно необоснованно, арифметика, которая используется в алгоритмах современной криптографии и еще множестве разных алгоритмах обработки данных, таких как: хеш-таблицы, контрольные суммы, алгоритмы коррекции ошибок при передачи данных.
Раздел математики называется арифметика в конечном поле, или арифметика Галуа.
Может это и узкая область знаний, но без нее, без этой математики, не обходится современная электроника, без этих знаний нельзя выпустить специальиста по цифровой электронике. Или как считать человека специалистом по информационной безопасности без знаний в области арифметики в конечном поле. Насколько важна эта арифметика для компьютерной технике стороннему человеку можно судить по тому факту, что в Core i3 отличается от Core i5 и новых серверных процессоров именно наличием аппаратно реализованной поддержки этой арифметики. Там где сети и там где беспроводные сети, где кодирование каналов мобильной связи, где спутниковая связь, где протоволы IP sec, SSL/TLS, сплошь и рядом нужна эта самая арифметика. НО с другой стороны, применяют ее крайне редко, потому что прикладные программисты используют готовые библиотеки.
В англоязычной литературе существует достаточное количество изданий, чтобы самостоятельно изучать данный предмет, а вот на русском языке чего-то не встречал вовсе. Всякий раз когда я встречаю новое приложение для арифметики в конечном поле, мне хочется чтобы эту математику преподавали в университете наравне с линейной алгеброй.
Итак, суть идеи, как преподать данный предмет. Схема.
Традиционный подход -- проведение аналогии между базовыми операциями обычной двоичной арифметикой и арифметикой в конечном поле. Двоичную арифметику можно представить как сложение разрядов, а умножение представляется как сдвиг числа и сложение в столбик. Мы говорим, что можно доказать, что подмена операций сложения и уномжения может дать новый базис операций, которые на множестве чисел будут образовывать арифметическую структуру типа Поле. Поле - это термин обзначающий единственность и обратимость некоторых базовых операций. Аналогия возникает, когда удается доказать что операции в Поле подчиняются тем же законам что и обычные-привычные уножение и сложение.
Итак, основной трюк: операция сложения подменяется на операцию сложения без использования переноса в разрядах, операция нам известна из двоичной арифметики, как побитовая операция исключающее ИЛИ. Операция умножения по сути остается такой же как и была в двоичной арифметике - сдвиг и сложение в столбик. НО чтобы числа отображались в конечное множество чисел, добавляется операция редуцирования числа. Для обычной арифметики в конечном поле - редуцирование может возникать как дополнительная операцию на переполнение числа, чего делать при переносе в старшем разряде.
Основная идея построения эффективных аппаратных решений по обработки данных и аппаратных ускорителей криптографии может быть выражена в перестановке порядка выполнения операций сдвига-сложения-редуцирования. В аппаратуре сдвиг на один разряд не требует логических элементов, а операции исключающее или выполняются очень быстро и за один так процессора можно выполнить множество таких операций. Для чисел с больщой разрядностью (N) надо выполнить N операций сдвиг-сложение-редуцирование. Вместо этого, сначала оптом выполняются все операции сдвиг-сложение, и затем выполняется редуцирование, которое тоже может быть оптимизировано по быстродействию.
Отдельная тема (multiprecision), чего делать с числами в конечном поле с разрядностью заметно больше целого числа (более 32/64 бит).
О чем сон то был... об эффективном редуцировании чисел в конечном поле после выполнения каскада операций "умножения без переноса".
Занимает мою голову, совершенно необоснованно, арифметика, которая используется в алгоритмах современной криптографии и еще множестве разных алгоритмах обработки данных, таких как: хеш-таблицы, контрольные суммы, алгоритмы коррекции ошибок при передачи данных.
Раздел математики называется арифметика в конечном поле, или арифметика Галуа.
Может это и узкая область знаний, но без нее, без этой математики, не обходится современная электроника, без этих знаний нельзя выпустить специальиста по цифровой электронике. Или как считать человека специалистом по информационной безопасности без знаний в области арифметики в конечном поле. Насколько важна эта арифметика для компьютерной технике стороннему человеку можно судить по тому факту, что в Core i3 отличается от Core i5 и новых серверных процессоров именно наличием аппаратно реализованной поддержки этой арифметики. Там где сети и там где беспроводные сети, где кодирование каналов мобильной связи, где спутниковая связь, где протоволы IP sec, SSL/TLS, сплошь и рядом нужна эта самая арифметика. НО с другой стороны, применяют ее крайне редко, потому что прикладные программисты используют готовые библиотеки.
В англоязычной литературе существует достаточное количество изданий, чтобы самостоятельно изучать данный предмет, а вот на русском языке чего-то не встречал вовсе. Всякий раз когда я встречаю новое приложение для арифметики в конечном поле, мне хочется чтобы эту математику преподавали в университете наравне с линейной алгеброй.
Итак, суть идеи, как преподать данный предмет. Схема.
Традиционный подход -- проведение аналогии между базовыми операциями обычной двоичной арифметикой и арифметикой в конечном поле. Двоичную арифметику можно представить как сложение разрядов, а умножение представляется как сдвиг числа и сложение в столбик. Мы говорим, что можно доказать, что подмена операций сложения и уномжения может дать новый базис операций, которые на множестве чисел будут образовывать арифметическую структуру типа Поле. Поле - это термин обзначающий единственность и обратимость некоторых базовых операций. Аналогия возникает, когда удается доказать что операции в Поле подчиняются тем же законам что и обычные-привычные уножение и сложение.
Итак, основной трюк: операция сложения подменяется на операцию сложения без использования переноса в разрядах, операция нам известна из двоичной арифметики, как побитовая операция исключающее ИЛИ. Операция умножения по сути остается такой же как и была в двоичной арифметике - сдвиг и сложение в столбик. НО чтобы числа отображались в конечное множество чисел, добавляется операция редуцирования числа. Для обычной арифметики в конечном поле - редуцирование может возникать как дополнительная операцию на переполнение числа, чего делать при переносе в старшем разряде.
Основная идея построения эффективных аппаратных решений по обработки данных и аппаратных ускорителей криптографии может быть выражена в перестановке порядка выполнения операций сдвига-сложения-редуцирования. В аппаратуре сдвиг на один разряд не требует логических элементов, а операции исключающее или выполняются очень быстро и за один так процессора можно выполнить множество таких операций. Для чисел с больщой разрядностью (N) надо выполнить N операций сдвиг-сложение-редуцирование. Вместо этого, сначала оптом выполняются все операции сдвиг-сложение, и затем выполняется редуцирование, которое тоже может быть оптимизировано по быстродействию.
Отдельная тема (multiprecision), чего делать с числами в конечном поле с разрядностью заметно больше целого числа (более 32/64 бит).
О чем сон то был... об эффективном редуцировании чисел в конечном поле после выполнения каскада операций "умножения без переноса".
Комментариев нет:
Отправить комментарий