Возведение в степень и вычисление дробей по модулю (в конечных полях Галуа) (61, 152)

При изучении современных шифров требуется возводить степень и искать обратные числа в конечных полях. Эти вычисления вручную довольно трудоемки и если возведение в степень по модулю ещё может сделать калькулятор Винды, то деление надо программировать отдельно. Эта программа введенная в РПЗУ МК-52 или МК-152 может быть хорошим подспорьем студенту.

Перед первым запуском нажать [БП] [5] [7]

Деление С = (А / В) mod D
Вводить: [В/О] A [ПП] B [ПП] D [С/П]
Тест: (3 / 18) mod 257 = 43
Результат на экране

Возведение в степень С = (А ^ В) mod D
Вводить: A [ПП] B [ПП] D [С/П]
Ограничение: A, B, D
0 1 2 3 4 5 6 7 8 9
00 ПА П5 ПД Сх П4 ПС П9 ИПД П6 ИП5
10 ИП6 / К{x} Fx!=0 41 FBx K[x] П8 ИП6 *
20 ИП5 XY - П7 ИПС ИП8 ИП9 ПС * +
30 Fx=0 33 1 П9 КИП4 ИП6 П5 ИП7 П6 БП
40 09 ИП4 2 / K{x} Fx=0 51 ИПД ИП9 -
50 П9 ИП9 ИПА * ПП 88 С/П ПА П5 ПД
60 1 ПС ИП5 K[x] Fx!=0 85 2 / П5 K{x}
70 Fx!=0 78 ИПС ИПА * ПП 88 ПС ИПА Fx^2
80 ПП 88 ПА БП 62 ИПС БП 56 ПЕ ИПД
90 / K[x] ИПД * ИПЕ XY - В/О

Комментарии:
/ - деление
* - умножение
!= - не равно
x^2 - возведение в квадрат

Вроде получилось прикрепить программу для Калькулятор-3000! Спасибо за совет.

http://pmk.arbinada.com/system/files/GF_oper.C3

File attachments: 
Прикрепленный файлРазмер
Binary Data GF_oper.C32.97 KB
Undefined

Комментарии

При редактировании надо кликнуть на "Прикрепленные файлы", откроется область ввода для загрузки файлов.

Спасибо за совет!

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

деление дробей. Супер!!!
Работает!!! :)

А как бы узнать алгоритм вычисления дробей по модулю (хотя бы псевдокод)... Никак найти не могу...
Очень нужно реализовать тоже самое в Delphi, может кто подскажет? ;)

Деление в конечном поле. Наверное спросить у меня. Раз я его запрограммироовал, значит знаю как это делается. Это обычная задача из современной криптографии. Мне его тоже пришлось восстанавливать по крохам информации в и-нете и обобщить несколько источников, прежде чем разобрался. Этот алгоритм очень похож на алгоритм Эвклида (поиск наибольшего общего делителя двух или нескольких чисел). Кстати, а для какой задачи Вам это нужно?
Если алгоритм нужен, я его Вам опишу здесь. Вот процедура, реализующая этот алгоритм на Борланд С++ билдер:

//---------------------------------------------------------------------------
long __fastcall TFormEllipticCrypt::sub_div(long a, long b, long c)
{
long d,e,f,g,h,i,j;
d=1; e=0; g=c; j=b;
for (i=0;j>0;i++)
        {
        h = b/g;
        j = b - h*g;
        if (i != 0)
                {
                f=d*h+e;
                e=d;
                d=f;
                }
        b=g;
        g=j;
        }
if (i%2 != 0) e = c - e;
d = (a*e)%c;
return(d);
}
//---------------------------------------------------------------------------

Но у этого алгоритма есть ограничение. Он работает тодько в случаях, когда знаменатель дроби и количество элементов в поле (делитель по модулю) - взаимно простые числа. Взаимно простые - означает, что наибольший общий делитель этих чисел должен быть равен 1. Иначе этот алгоритм даёт некорректные результаты. Однако, если количество элементов поля - простое число, то алгоритм работает всегда. Могу объяснить и почему, но не в двух словах а в гораздо большем их количестве.

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

О благодарности. Андрей, хотя бы "спасибо" сказал.

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

Спасибо большое!!! Спасибо, вы меня здорово выручили. Сочиняю (не за деньги, для себя) систему защиты данных на компакт-дисках, DVD, flash'ках и прочем от сбоев (этакий forward error correction на весь носитель), пробую для скорострельности вместо двоичных полиномов идею отсюда - http://www.lshift.net/blog/2006/11/29/gf232-5 - но пока получается сильно медленно, да и в криптографии я не силён; 16-разрядную версию делал табличными методами по мотивам 8-разрядной "козы", а для 32-битной таблицы ну никак не годятся. :(
Кстати, если я правильно понял,
h = b/g;
j = b - h*g;
- это частное и остаток. На Си тут можно ещё немножко ускорить - обойтись без умножения:
__asm {
mov eax, b // младшая половина делимого
mov edx, 0 // старшая половина
idiv g // или div, если для беззнаковых
mov h, eax // частное
mov j, edx // остаток
}
(правда, это на микрософтовском жаргоне - для борланда точной грамматики не помню).
И если вас не затруднит - не могли бы вы выложить ещё описание возведения в степень по модулю? А то у меня и с этим сложности... :(

Возводить в степень по модулю так:. Вычисляем: С=BD(mod N) = 143241(mod 323)
В=143
D = 241 = 128+64+32+16+1 = 111100012
B1=143
B2=1432(mod 323) = 100
B4=1434(mod 323) = 1002(mod 323) = 310
B8=1438(mod 323) = 3102(mod 323) = 169
B16=14316(mod 323) = 1692(mod 323) = 137
B32=14332(mod 323) = 1372(mod 323) = 35
B64=14364(mod 323) = 352(mod 323) = 256
B128=143128(mod 323) = 2562(mod 323) = 290

С=BD(mod N) = 143241(mod 323) = 143128*14364*14332*14316*143(mod 323) = 290*256*35*137*143(mod 323) = 262

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

Ага,понятно. Спасибо!

Кстати, я попытался применить пример с делением для модуля (2^32-5) - оказалось, что 32-битной арифметики не хватает, похоже, что косячит разрядность в сишном умножении (32бит * 32бит = 32бит), а переводить всю арифметику на 64-битную - будет слишком медленно работать. Буду дальше подпиливать ассемблером... :( Или тут вместо простого умножения можно использовать умножение по модулю?

Разрядность. Чтобы вычислять произведения по 32 разрядному модулю нужны 64 битные промежуточные данные, иначе вычислять умножение в цикле сложением по модулю, а это о-о-о-о-чень долго.
Попробуйте промежуточные переменные в 64 бита длиной. Простое умножение по модулю в C не поможет. Будет риск ошибки при длине данных больше 216

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

С переполнением я борюсь! > Попробуйте промежуточные переменные в 64 бита длиной. Простое умножение по модулю в C не поможет.
Угу. Пришлось преименять ассемблер - в нём как раз удобно: умножение удваивает разрядность, деление уполовинивает. Я сначала слепил функцию "умножение по модулю" - (a * b ) mod c:
#define uint32 unsigned long
uint32 multiply( uint32 a, uint32 b, uint32 c ) {
__asm {
mov eax, a
mul b // в edx:eax - 64-битное произведение
div c // в eax - частное, в edx - остаток
mov eax, edx // возвращаем остаток
}
}
А в функции sub_div() умножение встречается трижды: в начале - просто для получения остатка (замену я привёл позавчера); в самом конце - умножение делимого на инверсию делителя, с этим я вчера разобрался, тут как раз удобно вызвать multiply( a, e, c ); и в середине - f=d*h+e - тут пока неясно, никаких неприятностей вроде не нашёл, временно заменил строку на вот такое:
int overflow;
__asm {
mov eax, d
mul h
add eax, e
mov overflow, edx
mov f, eax
}
if ( overflow )
DebugBreak();
- если вдруг переполнится, то я это сразу увижу.