Отправлено Oldring 27 января 2003 г. 15:19 В ответ на: да, алгебре все-равно какими объектами она оперирует отправлено yes 27 января 2003 г. 10:31

Операции GF(2) очень легко реализуемы. Только какой в этом толк для решения Вашей задачи от этого?

Поля могут быть либо конечными (Галуа), либо бесконечными. Структура полей Галуа хорошо известна. Бесконечные поля можно представлять в железе только приближенно целыми числами.

Что касается более эффективного представления GF(256) - есть метод. Элементы поля рассматриваются как вычеты многочленов над GF(16) по модулю немриводимого над GF(16) многочлена второй степени. В этом случае такие операции, как умножение и взятие обратного по умножению, выражаются достаточно просто через операции GF(16). Сами элементы GF(16) можно представить в "оптимальном нормальном базисе". В нем возведение в квадрат, необходимое для реализации взятия обратного по умножению GF(256), является циклическим сдвигом, а умножение тоже упрощается по сравнению с полиноминальным представлением. Сложение во всех случаях является XOR битовых векторов. Только такими методами невозможно упрощать вычисления в простом поле.

Эти алгоритмы описаны в литературе и запатентованы в Америке, по крайней мере. Вообще, видел кучу свежих Американских патентов по поводу вычислений в полях Галуа, в том числе и покрывающих старые давно известные методы :).

Если рассматривать эффективные представления полей Галуа, нельзя забыть про логарифмическое. Только очень уж сложно складывать становится :).

• я хотел оптимизировать вычисление свертки одним из способов, мне предложили другие — yes   (27.01.2003 16:59, 481 байт)
  • Ну, не знаю. Думаю, что если бы было известо что-то существенно более простое, об этом бы писали в первую очередь :) — Oldring   (27.01.2003 18:10, пустое)