Pull to refresh

Comments 23

В микроэлектронике всегда хотят умножение заменить на что попроще, в том числе на таблицы и сложение. Умножение на константу скорее всего заменяется как раз серией сложений со сдвигами. )
стесняюсь спросить — а для чего это может понадобиться?
(например я понимаю, зачем менять вычисления с плавающей точкой на целочисленные — в смысле понимаю, зачем нужно сложение и умножение, как часто оно нужно и какие бенефиты от «выполнения на низком уровне»)
А какие типичные применения «индексного умножения по модулю»?
Ну стесняться незачем. =) Эта статья узкоспециализирована. Теоертически умножение по модулю может возникнуть и просто так в какой-то обыденной задаче. Но вообще этот математический аппарат обычно используется в модулярной арифметике, где все операции выполняются над вычетами (остатками от деления). А модулярная арифметика в свою очередь используется в приборах где требуется высокая скорость арифметических операций (типа DSP) или высокая помехоустойчивость с контролем ошибок.
Ну их обычно такими и стараются выбирать (за исключением разве что случаев 2n, 2n+1, 2n-1). Поскольку вcе модули в базисе должны быть взаимно простыми.
Мне, не зная специфики применения действительно трудно понять почему «их обычно такими и стараются выбирать» :) Но сам метод интересный
Кольцо вычетов является полем только если модуль простой. На деле это как раз означает существование первообразного корня, отсутствие делителей нуля (a != 0, b !=0, a * b = 0) и прочие радости.
А такой вопрос: для данного алгоритма подойдут только простые модули p или любые, которые имеют первообразный корень (2, 4, p^a, 2p^a, где p>2)?
Точно не уверен, но, по всей видимости, хватит только наличия первообразного корня.
Вопрос интересный, надо будет проверить.
Добавлю, что статью писал больше для тех кто впоследствие прийдет с поисковиков. Туго с этим материалом в рунете…
Вычисления по простому модулю используются в шифровании, избыточном кодировании (самовосстанавливающиеся коды как на компакт-дисках и т.п.) и других подобных приложениях.
Для реализации вычислений над конечными полями, которые используются, среди прочего, в теории кодов, исправляющих ошибки (см., например, Коды Рида-Соломона, используемые при записи данных на компакт-диски и еще много где).

Сама идея сходна использованию логарифмов: вместо умножения двух вещественных чисел можно складывать их логарифмы (именно на этом основан принцип работы логарифмической линейки).
В статье не указано главное — то, что речь идет о «железном» вычислении, а не о программном.
Извиняюсь, нашел где это написано.
Стыдно-то как…
Спасибо за статью, но вообще это арифметика для 8-ого класса физмат. школы.
Вероятно я учился в неправильной физ-мат школе. =) ИМХО, тут слишком большой математический аппарат задействован (см. ключевые слова), что бы додуматься до чего-то подобного в 8 классе. Разве что ПРО-олимпиадники справятся.
Задействованный «математический аппарат» как раз и называется арифметикой остатков. В моей гуманитарной гимназии города зажопинска это был годичный курс по 1 уроку в неделю, так и назывался «арифметика». Как в других школах — не знаю.
Что до ключевых слов, то они абстрактны и мне ничего не говорят. Про «логарифметику» ничего не знает даже яндекс.
> Как искать первообразный корень? Я использую полный перебор, начиная с 2 до p

Можно ускорить проверку числа на первообразность. Пусть p-1 = k1a1k2a2k3a3… — разложение на простые множители, тогда если g(p-1)/ki mod p не равно 1 для всех i, а gp-1 равно 1, то g — первообразный корень.
Всего таких k для каждого числа очень мало. Разложить все числа от 2 до p на простые множители можно тоже относительно быстро с помощью решета Эратосфена.

Таким образом можно перебрать за приемлемое время первообразный хоть для p порядка 109 :)
Спасибо. Это какая-то известная теорема?
Не знаю, это не сложно придумать.

Пусть i наименьшее число, что gi равно 1, тогда если i = p-1, то g первообразный иначе нет.
Очевидно, что gi*x равно 1 для целых x и только они (из-за наименьшести i). Тогда из того что мы проверили gp-1 = 1 следует что p-1=i*x, то есть i делит p-1, что тоже самое что «i равно p-1, или i делит хоть что-то из (p-1)/ki». Если i = p-1 — все отлично, иначе если i делит (p-1)/ki то g(p-1)/ki тоже будет равно 1, что мы собственно и проверяем.
Можно тупо обойтись одной таблицей полуквадратов {i -> i*i/2}, тремя запросами в эту таблицу, и тремясложениями: ab = ((a+b)^2-a^2-b^2)/2
Sign up to leave a comment.

Articles