Здравствуйте ILY, Вы писали:
ILY>Что конкретно ты хочешь? Арифметические операции с числами размером более четырех байт? Могу написать код на asm с комментариями
Написать я и сам написал. Не устраивает скорость операций деления и получения остатка от деления. Например, если сравнивать с небезызвестным FGInt, то FGInt быстрее на порядок.
А вообще это все задумывалось для реализации RSA, Eliptic Curve, etc ...
Если есть желание и время , можем пообщаться ...
Я вообще-то не специалист по данному вопросу.
Знаю, как быстро реализуются арифметические операции с числами большой величины на ассемблере. Для операции сложення, скажем, нужно вызвать add, затем adc. Вычитние делается через sub/sbb. Умножение, если не ошибаюсь, эмулируется как умножение слов в столбик. Если эти вещи известны, я вряд-ли смогу чем-то помочь. Если ты об этом не знаешь — напишу.
Я как раз за этим сюда и пришел меня тоже интересуют операции с большими числами тоже для RSA.
Меня интересует есть ли какие-нибудь библиотеки на С для работы с ними. Проверка на простоту желательна так как реализовывать алгоритмы которые описаны в книге не очень хочется вспоминать эту алгебру и вникать во все эти вещи.
Изивни, LG. Нет у меня в книжке операции деления. Но ты все-равно почитай сообщение, я напишу свои соображения, может чем поможет.
Пишу алгоритмы команд также и для alex77.
Без assembler-a никуда не деться, поскольку используются специфические команды компьютера
Следующая запись: Eax|Ecx будет означать, что мы имеем число размером 8 байт, причем старшая его часть хранится в регистре Eax, младшая — в Ecx
В процессоре 8086 есть команда adc op1,op2, выполняющая операцию op1=op1+op2+CF. Зачем это нужно?
Пусть нам надо выполнить операцию над двумя 64-х битными числами Eax|Ebx = Eax|Ebx + Ecx|Edx. Делаем это так: Сначала складываем младшие части:
Ebx=Ebx+Edx. Может получиться единица переноса, которую надо учитывать при сложении старших частей (еще не забыли сложение в столбик из начальной школы?)
Эта единица автоматически устанавливается во флаг CF. Таким образом мы учитываем эту единицу путем Eax=Eax+Ecx+CF. Все. На ассемблере вышеописанное выполняется двумя командами:
add Ebx,Edx
adc Eax,Ecx
Все! Сложение выполнено.
Понятно, что по эточу алгоритму можно складывать числа размера больше 64 бит. Нужно каждый раз обращаться к команде adc
С вычитанием ситуация аналогична. Заем бита при вычитании также переносится во флаг CF и учитывается командой sbb
Операция Eax|Ebx = Eax|Ebx — Ecx|Edx будет выглядеть как
sub Ebx,Edx
sbb Eax,Ecx
Операция умножения выполняется сдедующим образом.
Пусть у нас есть число a, размером 32 бита. Запишем его в виде a = c*2^16 + d. Понятно, что в таком случае c-это старшие 16 бит числа a, d-
младшие 16 бит. Также понятно, что в подобном виде можно представить любое 32-х битное число.
Пусть нам надо умножить a*b (32 битные)
Запишем: a*b = (c*2^16+d) * (e*2^16+f). конечно c,d,e,f — это 16-ти разрядные числа.
Раскроем скобки: a*b = (c*2^16+d) * (e*2^16+f) = c*e*2^32 + (f*c + e*d)*2^16 + d*f. Все команды умножения здесь выполняются с 16-ти разрядными
числами, эти команды доступны процессору. Операции умножения на 2^16,2^32 сводятся к помещению результата в соответствующий байт.
Опять-же очевидно, что мы можем аналогичным образом разложить умножение чисел больщей размерности.
Понятно объяснил?
Код на asm приводить не буду, он получится громоздким.
Совершенно аналогично раскладывается операция деления a/b=(c*2^16+d)/(e*2^16+f)=c/e+d/e/2^16+c/f*2^16+d/f
Короче арифметические операции с большими числами можно выразить через операции с числами вдвое меньшей разрядности, которые в свою очередь
можно выразить через числа вчетверо меньшей разрядности, которые в свою очередь ... Пока не получатся числа, доступные коммандам процессора.
(а кто сказал, что будет легко)
Следует также отметить, что сии алгоритмы годятся как для знаковых, так и для беззнаковых чисел.
По-моему это наиболее быстрый алгоритм для работы с числами большой размероности.
Что знал — рассказал. Больше ничем помочь не могу
А с ASCryptoKit5, AecRSA, TMS RSA, Delphi Encryption Compendium Part — II я вообще не знаком.
, можем пообщаться ...
