Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью

1 Предпосылки создания изобретения Настоящее изобретение относится к арифметическим вычислениям с большими целыми числами, и в частности, к способу выполнения умножения и модульного приведения больших целых чисел. Описание уровня техники Настоящее изобретение мотивировано применением шифрования с открытым ключом с использованием схемы RSA, (RSA Laboratories, "The Public-Key Cryptography Standards,"DSA, ("Digital Signature Standard," FIPS Publication 186, National Institute of Standards and Technology, U.S. Department of Commerce, 18 May 1994). Такое применение требует вычислительного шага модульного возведения в степень, то есть вычисления формы "АВ по модулю Р", где А, В, и Р - большие целые числа. Модульное возведение в степень - это необходимая для вычислений процедура, выполнение которой может потребовать длительного времени, в особенности на недорогих вычислительных устройствах. Как правило, вычислительные устройства предназначены для обработки данных в основных единицах заданного размера. Основной блок данных называется "слово" и содержит "b" битов. Значение b выбирают при разработке устройства. Типичные значения для b - это 8, 16,32, или 64 бита. Слово используется для того,чтобы представить неотрицательное целое число х в диапазоне от 0xW-1, где W=2b. Для того чтобы представить целое числоX, которое больше, чем W-1, используют представление многократной точности. Если 0 ХWn-1, где n - некоторое положительное целое число, то Х может быть представлено какX=xn-1Wn-1+xn-2Wn-2+x1W+х 0,где каждый xj находится в диапазоне 0xjW-1, j=0, 1 n-1. Таким образом, целое число Х представлено n словами х 0, х 1 хn-1, причем слово хj представляет целое число, которое является коэффициентом W. Для заданного размера слова b и заданного числа слов n представление многократной точности Х является уникальным. Модульное возведение в степень требует нескольких операций с целыми числами многократной точности. Одна из таких операций умножение. Имея два заданных целых числа Х иY, каждое с представлением многократной точности из n слов, можно непосредственно запрограммировать вычислительное устройство для вычисления произведения Z=ХY. Такая процедура представляет собой нечто большее, чем способ "умножения и сложения", преподавае 002183 2 мый в средней школе для умножения многозначных чисел. Сложность процедуры квадратична, то есть число "внутренних произведений", которые должны быть вычислены составляет n2. Для представления произведения Z требуется 2n слов. При практическом применении открытых ключей единичное модульное возведение в степень требует сотен или тысяч таких умножений,каждое из которых использует целые числа длиной в десятки или сотни слов. В простом вычислительном устройстве время вычисления для единичного возведения в степень может составлять несколько минут. Во многих случаях применения, например в электронной торговле,это слишком долго, т.е. непригодно. Умножение - не единственная операция,иcпользуемая при модульном возведении в степень. Другая операция - это модульное приведение, то есть приведение произведения Z из 2n слов к n словам с помощью операции по модулю Р. Сложность модульного приведения почти идентична сложности умножения, и эти две операции почти в равной степени составляют полное время модульного возведения в степень. Краткое изложение существа изобретения Настоящее изобретение основывается на следующем факте: как умножение с многократной точностью, так и модульное приведение могут быть быстро произведены, если вычислительное устройство способно эффективно выполнять следующую операцию:ZZ(XY) В этой операции Х - это целое число, представленное m словами, а Y и Z - каждое является целым числом, представленным n словами. Предполагается, что n является числом слов в блоке, для которого производится модульное возведение в степень, причем m имеет меньшее значение, чем n. Умножение с многократной точностью и модульное приведение можно выполнять, используя приблизительно n/m выполнений этой операции, при общей сумме 2n/m операций для модульного возведения в степень. В настоящем изобретении описывается сопроцессор, который можно добавлять к вычислительному устройству для того, чтобы дать вычислительному устройству возможность эффективно выполнять эту операцию. Когда вычислительное устройство получает команду на такое действие, сопроцессор выполняет операцию ZZ(XY), считывая слова X, Y и Z из памяти, и записывая новые слова Z обратно в память. Вычислительное устройство транслирует эти операции в умножение многократной точности, модульное приведение, и в конечном счете, в модульное возведение в степень. Компоновочный блок для сопроцессора предстaвляет собой блок больших чисел (ББЧ). Сопроцессор содержит один или более ББЧ,каждый из которых идентичен друг другу. Каж 3 дый ББЧ включает умножитель, сумматор, регистр и логический элемент ИЛИ. Множества ББЧ могут быть соединены для образования матрицы ББЧ, которая включает схему дополнения, регистр-фиксатор и схему выхода. Чем большее число ББЧ входит в массив, тем быстрее производится возведение в степень. Дополнительные задачи и преимущества изобретения частично сформулированы в нижеследующем описании, и, большей частью, очевидны из описания, либо могут быть выявлены путем использования изобретения. Задачи и преимущества изобретения также можно понять и осуществить с помощью средств и комбинаций, подробно изложенных в прилагаемой формуле изобретения. Краткое описание чертежей Прилагаемые чертежи, составляющие часть описания, поясняют предпочтительные варианты осуществления изобретения, и вместе с описанием служат для объяснения принципов,на которых основано изобретение. На фиг. 1 представлен сопроцессор с вычислительным устройством; на фиг. 2 показан блок больших чисел(ББЧ); фиг. 3 - блок-схема, изображающая четыре ББЧ, связанные между собой для формирования матрицы ББЧ; на фиг. 4 показана матрица ББЧ, объединенная с контроллером и оперативным запоминающим устройством (ОЗУ); на фиг. 5 представлена матрица ББЧ, объединенная с контроллером, и ОЗУ, выполняющей функцию "чтение-преобразование-запись"; на фиг. 6 изображена матрица ББЧ, объединенная с контроллером, первым ОЗУ и вторым ОЗУ; на фиг. 7 представлен конвейерный блок больших чисел (ББЧ); на фиг. 8 представлена блок-схема, изображающая четыре конвейерных ББЧ, связанные между собой для формирования матрицы ББЧ; на фиг. 9 показано двухпортовое ОЗУ; и на фиг. 10 представлена блок-схема, изображающая устройство для "чтения - преобразования - записи", используемое с двухпортовым ОЗУ. Подробное описание предпочтительных вариантов осуществления изобретения Далее подробно излагаются существующие предпочтительные варианты осуществления изобретения, примеры которых представлены на прилагаемых чертежах, где подобными цифрами обозначены подобные элементы на нескольких видах. В настоящем описании обозначение "Xn слов" используется для указания, что целое число Х представлено с использованием представления многократной точности в только что описанном формате. Для удобства введено несколь 002183 4 ко операторов. Оператор "/" используется для представления целочисленного деления с отбрасыванием остатка. Оператор "%" используется для представления целочисленной операции по модулю, то есть, остатка, получаемого в результате деления. При этой системе счисления,X/W=xn-1Wn-2+xn-2Wn-3+x2W+х 1, иX % W=x0. В настоящем изобретении описывается сопроцессор, который можно добавить к вычислительному устройству, чтобы дать возможность вычислительному устройству эффективно выполнять эту операцию. Устройство, включающее сопроцессор 14 с вычислительным устройством 11, показано на фиг. 1. Сопроцессор 14 использует ту же шину, которая используется в вычислительном устройстве для связи с его памятью 12. Шина соответствует размеру слова b вычислительного устройства. Когда вычислительное устройство получает соответствующую команду, сопроцессор выполняет операциюZZ(XY), считывая слова X, Y и Z из памяти 12, и записывает новые слова Z обратно в память 12. Вычислительное устройство транслирует эти операции в умножение многократной точности, в модульное приведение, и в конечном счете, в модульное возведение в степень. На фиг. 2 представлен блок больших чисел(ББЧ) 21. Сопроцессор 14 содержит m ББЧ, каждый из которых идентичен друг другу. Число ББЧ определяет число слов в операнде Х операции ZZ(XY). Время выполнения модульного возведения в степень приблизительно пропорционально 1/m. Проектировщик системы предлагает архитектуру с возможностью модульного наращивания, которая позволяет компромиссно решить проблему сложности относительно скорости: чем больше количество ББЧ,тем быстрее возведение в степень. Блок больших чисел (ББЧ) На фиг. 2 представлен блок больших чисел(ББЧ) 21. Сигналы шириной в один бит показаны пунктирными линиями, а сигналы шириной более, чем один бит, показаны сплошными линиями, при этом указано число битов. Число битов может быть различным в разных вариантах осуществления изобретения, причем настоящее изобретение охватывает такие варианты. Первый вход m1 умножителя 22 и второй вход m2 умножителя 22, являются входами множимых чисел в блок больших чисел 21. Каждый первый вход m1 умножителя 22 и каждый второй вход m2 умножителя 22 является словом, представляющим целое число из b битов. Сигнал с первого входа m1 умножителя и сигнал со второго входа m2 умножителя поступает на умножитель 22, который вырабатывает сигнал произведения р=m1m2. Поскольку 0m1(W-1), и 0m2(W-1), то диапазон сигнала произведения р составляет 0 р(W-1)2. Это означает, что для представления сигнала произведения р требуется 2b битов. Сигнал произведения р разделяют на сигнал старшей части произведения ph, и сигнал младшей части произведения р 1. Сигнал старшей части произведения ph формируется как верхние b битов сигнала произведения р, а сигнал младшей части произведения pl формируется как низшие b битов. Таким образом, р=phW+pl,где 0ph(W-1) и 0 рl(W-1). Сигнал старшей части произведения ph является выходным сигналом блока больших чисел 21, причем сигнал младшей части произведения pl, используется внутри блока. Первый сигнал а 1 сумматора и второй сигнал а 2 сумматора являются входными сигналами сумматора для блока больших чисел 21. Каждый из них является словом, представляющим целое число из b битов. Первый сигнал а 1 сумматора и второй сигнал а 2 сумматора подаются на сумматор 23. На сумматор 23 также поступает сигнал младшей части прозведения pl, и сигнал переноса с, величиной в 2 бита. Сумматор 23 вырабатывает первый сигнал суммы qd, гдеqd=а 1+а 2+pl+с. Наибольшее возможное значение для первого сигнала а 1 сумматора, второго сигнала а 2 сумматора, или сигнала младшей части произведения рl составляет W-1. Наибольшее возможное значение для сигнала переноса с равняется 3. Таким образом, наибольшее возможное значение для первого сигнала суммыqd равно 3(W-1)+3=3W, при этом для представления сигнал суммы qd требуются значения вb+2 бита. Первый сигнал суммы qd на выходе сумматора 23 фиксируется в регистре 24. Регистр 24 имеет ширину b+2 бита. Значение первого сигнала суммы qd переносится на выход регистра 24, когда синхронизирующий сигнал clk поступает на вход блока больших чисел 21. Выходной сигнал регистра 24 представляет собой второй сигнал суммы q. Значение второго сигнала суммы q сохраняется до поступления очередного синхронизирующего входного сигналаclk или до поступления сигнала сброса clr на вход блока больших чисел 21. Регистр 24 можно очистить, подав входной сигнал сброса clr с блока больших чисел 21. При поступлении входного сигнала clr, выходные биты регистра 24 очищаются до 0. Выход остается на 0 до момента поступления очередного входного сигнала сброса clk, во время которого значение сигнала первой суммы qd поступает на выход. Второй сигнал суммы q на выходе регистра 24 разделяется на сигнал переноса с и сигнал суммы s. Сигнал переноса с сформирован как два верхних бита второго сигнала суммы q, в то время как сигнал суммы s сформирован как низшие b биты. Таким образом, q=cW+s, при 0sW-1, и 0c3. Сигнал суммы s является выходным сигналом блока больших чисел 21. Входной сигнал переноса ci является входным сигналом переноса к модулю больших чисел 21, а выходной сигнал переноса со является выходным сигналом переноса. Каждый из этих сигналов имеет значение 1 бит. Выходной сигнал переноса со вычисляют как "логическое ИЛИ" входного сигнала переноса ci с помощью логического элемента ИЛИ 29 и битов, которые составляют второй сигнал суммы q. Другими словами, выходной сигнал переноса со имеет нулевое значение, если входной сигнал переноса ci равен 0, и каждый бит второго сигнала суммы q равен 0; в противном случае, выходной сигнал переноса со имеет значение 1. С помощью логического элемента 25 вспомогательный сигнал переноса са вычисляют как "логическое ИЛИ" из двух битов, которые составляют сигнал переноса с. Другими словами, вспомогательный сигнал переноса са имеет значение 0, если каждый бит сигнала переноса с имеет нулевое значение; в противном случае вспомогательный сигнал переноса са равен 1. Матрица блоков больших чисел (ББЧ) Описание Как показано на фиг. 3, несколько блоков больших чисел могут быть связаны между собой для формирования матрицы ББЧ. В частном случае матрица ББЧ может включать только один ББЧ. На фиг. 3 каждый сигнал имеет ширину один бит (разряд) или b битов. Сигналы шириной в один бит показаны пунктирными линиями, а сигналы шириной b битов показаны сплошными линиями. На фиг. 3 представлен вариант из четырех блоков больших чисел: ББЧ 0, ББЧ 1,ББЧ 2, ББЧ 3, связанных между собой для формирования матрицы ББЧ 39. В общем случае, любое число блоков больших чисел может быть связано между собой. Для простоты вначале здесь рассматривается вариант из четырех блоков больших чисел, как показано на фиг. 4, а затем - варианты с другим количеством блоков больших чисел. Первый сигнал данных у является входным для матрицы ББЧ 39, и подается на первый вход умножителя m1 каждого блока больших чисел ББЧ 0, ББЧ 1, ББЧ 2, ББЧ 3. Второй сигнал данных имеет множество элементов х 0, х 1, х 2, и х 3. Каждый элемент соответственно связан со вторым входом умножителя m2 каждого блока больших чисел матрицы ББЧ 39, то есть, каждый элемент связан со вторым входом умножителя m2, соответственно ББЧ 0, ББЧ 1, ББЧ 2 и ББЧ 3. Третий сигнал данных z является входным сигналом для матрицы ББЧ 39, и связан со входом схемы дополнения 35. Схема дополнения 35 представляет собой схему "исключающего или"(XOR) GATE0, комбинирующую каждый бит третьего сигнала данных z с сигналом вычита 7 ния, причем сам сигнал вычитания является входным сигналом для матрицы ББЧ 39. Когда сигнал вычитания неактивен, т.е. представляет собой логический 0, тогда биты третьего сигнала данных z не подвергаются воздействию во время их прохождения через схему дополнения 35. Когда сигнал вычитания активен, т.е. представляет собой логическую 1, тогда каждый бит третьего сигнала данных z заменяется его логическим дополнением при прохождении бита через схему дополнения 35; то есть каждый 1 бит заменяется на 0-бит, и наоборот. Выход схемы дополнения 35 связан с первым входом сумматора а 1 первого блока больших чисел ББЧ 0. Выходной сигнал а является выходным сигналом матрицы ББЧ 39 и снимается с выхода схемы выхода 36. Схема выхода 36 предстaвляет собой схему "исключающего или" (XOR) логический элемент (GATE1), который комбинирует каждый бит сигнала суммы s - выходного сигнала первого блока больших чисел ББЧ 0 с сигналом вычитания sub. Когда сигнал вычитания неактивен, то биты сигнала суммы s первого блока больших чисел не подвергаются воздействию при их прохождении через схему выхода 36. Когда сигнал вычитания активен,тогда каждый бит сигнала суммы s первого блока больших чисел замещается его логическим дополнением. Регистр-фиксатор 34 - это регистр REG0,который имеет ширину b бит. Вход регистрафиксатора 34 связан с выходом четвертого блока больших чисел ББЧ 3 сигнала старшей части произведения ph, а выход регистрафиксатора 34 связан со входом четвертого блока больших чисел ББЧ 3 второго сигнала сумматора а 2. Таким образом, регистр-фиксатор 34 фиксирует значение сигнала старшей части произведения ph, поступающее от четвертого блока больших чисел до поступления синхронизирующего сигнала, и подает это значение обратно на вход а 2 второму сигналу сумматора четвертого блока больших чисел после поступления синхронизирующего сигнала. Регистрфиксатор 34 имеет вход сброса clr, который работает аналогично входу сброса clr регистра 24 в блоке больших чисел 21 на фиг. 2. Синхронизирующий сигнал clk является входным сигналом для матрицы ББЧ 39, и связан со входом сброса clk каждого блока больших чисел, ББЧ 0, ББЧ 1, ББЧ 2, ББЧ 3, а также со входом сброса clk регистра-фиксатора 34. Когда генерируется синхронизирующий импульс, то одновременно модифицируется содержание регистра в каждом блоке больших чисел и содержание регистра-фиксатора 34. Сигнал сброса clr является входным сигналом для матрицы ББЧ 39, и связан со входом clr каждого блока больших чисел ББЧ 0, ББЧ 1,ББЧ 2, ББЧ 3 и со входом clr регистрафиксатора 34. Когда на вход сброса поступают 8 импульсы, содержание регистра в каждом блоке больших чисел и содержание регистрафиксатора 34 одновременно очищаются до 0. Сигнал переноса потока су является выходным сигналом для матрицы ББЧ 39 и связан с выходом со четвертого блока больших чисел,ББЧ 3. Сигнал переноса потока указывает на наличие переполнения или антипереполнения. Для того, чтобы связать между собой более четырех блоков больших чисел в матрице ББЧ,дублируется логика взаимосвязи третьего блока больших чисел. В приведенной ниже табл. 1 детально представлена логика соединения m блоков больших чисел в матрице ББЧ, где m4: Таблица 1 В табл. 1: "ББЧk:x" обозначает сигнал х ББЧk, "REG0:x" обозначает сигнал х REG0, и т.д.; "N/C" означает, что сигнал несвязан. В крайней левой колонке приводится сигнал в kом блоке больших чисел ББЧk, а в остальных колонках представлена логика взаимосвязи для такого сигнала при k=0, 1 m-1. Наглядно показано, что данные в табл. 1 соответствуют логике взаимосвязи, представленной на фиг. 3,если m=4. Для того чтобы связать между собой менее четырех блоков больших чисел в матрице ББЧ,сжимают логику взаимосвязи некоторых блоков больших чисел. В табл. 2, 3 и 4 подробно представлена логика для соединения m блоков больших чисел в матрице ББЧ, если m=3, m=2 и Сигналы матрицы ББЧ, которые не представлены в табл. 2-4, имеют ту же самую логику взаимосвязи для любого значения m. Для ясности в табл. 5 приводятся подробные данные для таких сигналов. Сигнал Работа устройства Общая функция, выполняемая массивом ББЧ - следующая: АZ(XY),где Хm слов; Yn слов; Z - n слов; и Аn слов. Целые числа X, Y, и Z - входные операнды для данной функции, а целое число А - выходной операнд. Слова Х подаются в матрицу ББЧ одновременно на входы х 0, х 1 хm-1. Слова Y и Z подаются в матрицу ББЧ по одному слову одновременно, соответственно на входы у и z. Слова считываются из матрицы ББЧ по одному слову одновременно на выходе а. Вход вычитания в матрице ББЧ выбирает сложение либо вычитание в операции . Активизируя вход вычитания, то есть устанавливая вход вычитания в логическое состояние 1, выбирают вычитание, а дезактивизируя вход вычитания, то есть очищая вход вычитания до логического состояния 0, выбирают сложение. Сигнал переноса потока су матрицы ББЧ указывает на наличие переполнения или антипереполнения. Переполнение происходит во время операции сложения, если вычисленное значение слишком велико для представления nслов. Антипереполнение происходит во время операции вычитания, если вычисленное значение является отрицательным. В конце этой операции выход сигнала переноса потока су активен, если происходит переполнение либо антипереполнение. Если ни переполнения, ни антипереполнения не происходит, то выход сигнала переноса потока су неактивен. 10 Матрицу ББЧ можно использовать для выполнения общей функции, используя следующую процедуру: 1. Генерирование импульса clr. 2. Активизирование либо дезактивизирование сигнала sub. 3. Подача сигнала на входы данных х 0,х 1 хm-1. 4. Для j=0, 1 n-1, выполняется следующее: а. Подача сигнала на вход данных у. б. Подача сигнала на вход данных z. в. Генерирование импульса clk. г. Считывание данных с выхода а. На шаге 1 очищают регистры ББЧ и регистр-фиксатор 34 (REG0). Это убирает любое накопление от предыдущих операций. На шаге 2 выбирают сложение либо вычитание в операции . При неактивном значении сигнала на входе вычитания выбирается сложение, а при активном значении сигнала выбирается вычитание. На шаге 3 используются значения слов операнда X. Эти значения сохраняются для всей процедуры. На шаге 4 управляют циклом, который выполняют n раз. Каждую итерацию нумеруют индексом j, при j=0, 1 n-1. На шаге 4 а используют слово j операнды Y. На шаге 4b используют слово j операнды Z. На шаге 4 с генерируют сигнал clk. Этим модифицируют регистры ББЧ и регистрфиксатор 34 (REG0) новыми значениями, и новое слово появляется на выходе а. На шаге 4d считывают слово j операнды А. Анализ синхронизации матрицы ББЧ Можно проанализировать работу матрицы ББЧ для одного цикла, то есть для генерирования одного импульса входного синхронизирующего сигнала. К примеру, рассмотрим случай использования матрицы, состоящей из четырех ББЧ. В результате будет очевидно, как применять этот анализ при любом другом количестве ББЧ. Ниже будет рассмотрен только такой случай, когда входной сигнал вычитания в матрице ББЧ является неактивным. Случай с активным сигналом вычитания будет проанализирован позже. На фиг. 3 и 2 целое число Q определяют,имея значениеq3W +rW , где qj - значение, сохраненное в регистре ББЧj, и r - значение, которое хранится в регистре REG0 матрицы ББЧ. Каждое qj состоит из b+2 битов, a W=2b. Когда генерируется импульс синхронизирующего сигнала, изменяется значение Q. Новое значение можно обозначить как Q+. Значение Q+ получают с выхода сумматора в каждом ББЧ и с выхода умножителя в ББЧ 3. Для определения значения Q+, можно использовать суперпозицию следующим образом. 11 Вначале допустим, что значение Q равно 0,и значение входного сигнала у равняется 0. В этом случае Q+ содержит только входной сигналz. Значение z проходит через сумматор в ББЧ 0 и появляется на выходе регистра ББЧ 0. На каждом другом регистре в матрице ББЧ выходное значение равно 0. Таким образом, в этом случае(i) Затем допустим, что значение Q равно 0 и значение z равно 0. В этом случае Q+ будет содержать выходные сигналы с умножителя от каждого ББЧ. Младшая часть выходного сигнала умножителя заносится в регистр в том же самом ББЧ. Старшая часть выходного сигнала умножителя заносится в регистр в следующий старший ББЧ, либо в случае сигнала умножителя в ББЧ 3 - в REG0. Таким образом, при занесении значения Q+ младшая часть выходного сигнала умножителя в ББЧj взвешивается с помощьюWj, а старшая часть взвешивается с помощьюWj+1. Это означает, что полный выходной сигнал умножителя в ББЧj взвешивается при помощи Wj при занесении в Q+. Поскольку на двух входах в умножитель в ББЧj находятся соответственно входные сигналы у и xj, из этого следует, что, в данном случаеQ+=ух 0+ух 1W+yx2W2+yx3W3 (ii) Затем предположим, что значение z равно 0 и значение у равно 0. В этом случае в Q+ заносится только текущее значение Q. В пределах ББЧj, значение qj может быть записано какcjW+sj, где cj) состоит из верхних двух битов qj, a sj состоит из оставшихся битов. Таким образом, значение Q может быть записано как(с 2+s3)W +rW4. Каждое cj заносится в новое значение регистра в ББЧj, придавая ему взвешиваниеWj при занесении в Q+. Каждое sj вносится в регистр в ББЧj-1, для j=1, 2, и 3, придавая ему взвешивание Wj-1. Значение r вносится в регистр в ББЧ 3, придавая ему взвешивание W3. Таким образом, в этом случае Q+=(с 0+s1)+(с 1+s2)W+(с 2+s3)W2+rW3. Следует заметить,что это можно также записать какQ+=Q/W,(iii) где "/" обозначает целочисленное деление с отброшенным остатком. Уравнения (i), (ii), и (iii) содержат все внесения в новое значение Q+. Объединение этих внесений через суперпозицию даетQ+=z+у(х 0+х 1W+x2W2+x3W3)+Q/W. (iv) После поступления синхронизирующего импульса, значение выходного сигнала матрицы ББЧ равняется+ где a означает значение импульса после синхронизации, а "%" означает операцию с модулем целых чисел. Другими словами, a+ - остаток при делении Q+ нa W. 12 Уравнения (iv) и (v) суммируют операцию матрицы ББЧ во время синхронизирующего импульса. Анализ процедуры вычисления общей функции В этом разделе будет рассмотрена работа матрицы ББЧ в течение процедуры, используемой для вычисления общей функции. Эта процедура была описана в предыдущем разделе. Будет показано, что матрица ББЧ правильно вычисляет общую функцию, если используется эта процедура. При этом рассматривается только тот случай, когда входной сигнал вычитания к матрице у ББЧ является неактивным. Случай с активным сигналом вычитания будет проанализирован позже. Общая функция - это А(Z+XY)%Wn,гдеA=a0+a1W+a2W2+ +аn-1Wn-1; где: m - число ББЧ в матрице ББЧ и число слов в операнде X; и n - число слов в операндах Y, Z,и А. Операция по модулю "% Wn" отражает тот факт, что получаемое значение Z+XY округлено, чтобы вписаться в n слов А. Если(Z+XY)Wn, тогда А состоит из низших n словZ+XY; это случай "переполнения" общей функции. Процедура вычисления общей функции была описана в предыдущем разделе. Объединив эту процедуру с предшествующим анализом матрицы ББЧ, вычисление общей функции можно описать следующей рекурсией: Для k=0, 1 n-1:Sk=Qk/W; где S-1=0; "%" представляет операцию с модулем целых чисел; и "/" представляет деление целых чисел с округленным остатком. Очевидно, что по завершению n шагов рекурсии следующее уравнение включает а 0+a1W+a2W2+an-1Wn-1+Sn1Wn=z0+z1W+z2W2+zn-1Wn-1+X(y0+y1W+y2W2 +yn-1Wn-1) (vi) Правая сторона этого уравнения составляет Z+XY. Левая сторона уравнения составляет А+Sn-1Wn. Применяя операцию "%Wn" к каждой стороне уравнения,получаем А=(Z+XY)%Wn. Таким образом, поскольку доказана истинность уравнения (vi), будет показано, что процедура фактически вынуждает матрицу ББЧ вычислять общую функцию должным образом. Уравнение (vi) может быть доказано методом индукции. Вначале показано, что уравнение выполняется для случая n=1. Затем показано,что, если уравнение выполняется для n=t, оно 13 также выполняется для n=t+1. Это доказывает,что уравнение выполняется для любого значения n1. Рассмотрим случай, если n=1. ПосколькуQk на W. Вычисление его при k=0 дает а 0+WS0=Q0=z0+у 0 Х, что доказывает уравнение (vi) для случая n=1. Теперь рассмотрим случай для n=t+1. Допуская, что уравнение (vi) выполняется для n=t,получаем а 0+a1W+a2W2+аt-1Wt-1+St-1Wt=+z2W2+ztWt+X(y0+у 1W+у 2W2+уtWt). Это подтверждает уравнение (vi) для случая n=t+1, завершая доказательство. Анализ активного сигнала вычитания Когда входной сигнал вычитания матрицы ББЧ активен, каждое слово операнда Z дополняется прежде, чем оно подается к массиву ББЧ. В цифровом выражении это эквивалентно заменеZ на (Wn-Z-1). Аналогичным образом каждое слово операнда А дополняется прежде, чем оно поступает на выход из матрицы ББЧ. Это эквивалентно замене А на (Wn-A-1). Таким образом,когда сигнал вычитания активен, общая функция вычисляется следующим образом:Z=Wn-Z-1; А'=(Z'+XY)%Wn; А=Wn-А'-1. Поскольку 0Z'Wn и 0 А'Wn, можно свободно добавить к уравнениям операцию "%"% Wn" можно пренебречь, уравнения можно объединить, а операцию "% Wn" добавить в конце следующим образом: А=(Wn-Wn-Z-1)+XY)-1)%Wn. Упрощая уравнения, получаем А=(Z-XY)%Wn Это и есть искомая формула вычитания общей функции. Устройство с одним ОЗУ Матрицу ББЧ можно объединять с контроллером и оперативной памятью (ОЗУ) для формирования устройства, способного выполнять вычисления, основанные на общей функ 002183 14 ции, описанной выше. Такое устройство представлено на фиг. 4. Комбинация контроллера 41 и матрицы ББЧ 39 включает сопроцессор, который можно использовать с вычислительным устройством. В таком случае, оперативное запоминающее устройство (ОЗУ) 42 может использоваться совместно с вычислительным устройством 11, как на фиг. 1. Контроллер 41 обрабатывает сигналы матрицы ББЧ 39 для того, чтобы матрица выполняла требуемую операцию. Контроллер 41 считывает входные операнды из ОЗУ 42 и передает их матрице ББЧ 39 и вычислительному устройству. Контроллер 41 считывает выходные операнды из матрицы ББЧ 39 и записывает их на ОЗУ 42. Имеется много способов реализации контроллера 41, один из которых - это использование конечного автомата. ОЗУ 42 - это обычное устройство. ОЗУ имеет шину данных шириной b бит,соответствующей размеру слова матрицы ББЧ 39. Контроллер 41 считывает слово из ОЗУ 42,подавая соответствующее значение к адресной шине, активизируя сигнал считывания, считывая значение слова, подаваемого из ОЗУ 42 на шину данных, и затем дезактивизируя сигнал считывания. Контроллер 41 записывает слово в ОЗУ 42, подавая соответствующее значение к адресной шине, подавая значение слова на шину данных, и затем генерируя импульс сигнала записи. Количество времени, которое требуется для считывания или записи слова, называют циклом ОЗУ. Например, когда контроллер 41 считывает или записывает целое число X, состоящее из n слов, требуемое время составляет n циклов ОЗУ. Контроллер 41 дает команду устройству на выполнение общей функции АZ(XY), где Хm слов, Yn слов, Zn слов, и Аn слов, используя следующую процедуру: 1. Контроллер 41 подает импульс на вход сlr матрицы ББЧ 39. 2. Контроллер активизирует или дезактивизирует вход вычитания матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 3. Контроллер считывает m значений из ОЗУ 42 и подает их на входы х 0, х 1 хm-1 матрицы ББЧ. Контроллер поддерживает это значение постояннным для оставшейся процедуры. 4. Для j=0, 1 n-1, выполняется следующее: а. Контроллер считывает значение а из ОЗУ и подает его на вход у матрицы ББЧ. б. Контроллер считывает значение а из ОЗУ и подает его на вход z матрицы ББЧ. в. Контроллер подает импульсы на вход clk матрицы ББЧ. г. Контроллер считывает значение с выхода а матрицы ББЧ и записывает его в ОЗУ. 15 На шаге 3 контроллер 41 считывает m слов операнда Х из ОЗУ 42. На это требуется m циклов ОЗУ. На шаге 4 а контроллер 41 считывает n слов операнда Y из ОЗУ 42. На это требуется n циклов ОЗУ. На шаге 4 б контроллер 41 считывает n слов операнда Z из ОЗУ 42. На это требуется n циклов ОЗУ. На шаге 4 в контроллер 41 записывает n слов операнда А в ОЗУ 42. На это требуется n циклов ОЗУ. Общее количество циклов ОЗУ, требуемых для процедуры, равно m+3n. Их получают путем суммирования циклов на шагах 3, 4 а, 4 б и 4 г. Устройство с одним ОЗУ с функцией "чтение-преобразование-запись" Как показано на фиг. 5, число циклов ОЗУ,требуемых для выполнения общей функции,можно сократить путем использования ОЗУ 43,которое способно выполнять операцию "чтениепреобразование-запись". Такая операция позволяет контроллеру 41 считывать слово из ОЗУ 43, преобразовывать значение слова и записывать новое значение обратно в ОЗУ 43, и все это за один цикл ОЗУ. Комбинация контроллера 41 и матрицы ББЧ 39 включает сопроцессор, который можно использовать с вычислительным устройством. В таком случае ОЗУ 43 можно использовать совместно с вычислительным устройством 11, как на фиг. 1. Контроллер 41 выполняет операцию "чтение-преобразование-запись" в ОЗУ 43 следующим образом. Вначале контроллер подает соответствующее значение на адресную шину и активизирует сигнал "rmw " - "чтение- преобразование-запись". Затем контроллер активизирует сигнал считывания, считывает значение, подаваемое ОЗУ на шину данных, и дезактивизирует сигнал считывания. После этого контроллер подает преобразованное значение на шину данных и выдает импульс сигнала записи. И наконец, контроллер дезактивизирует сигнал rmw. Полная операция происходит за один цикл ОЗУ. ОЗУ 43 также имеет возможность выполнять обычные операции чтения и записи, как уже описано. Контроллер выбирает обычные операции чтения и записи путем дезактивизирования сигнала rmw. Каждая из этих трех операций - чтение и запись и чтениепреобразование-запись требует одного цикла ОЗУ. Для осуществления возможности "чтениепреобразование-запись", общая функция становится ZZ(XY), где Хm слов, Yn слов, иZn слов. Таким образом, операнд Z преобразовывается, путем сложения или вычитания величины ХY. Контроллер 41 дает устройству команду для выполнения этой функции, используя следующую процедуру: 16 1. Контроллер 41 подает импульс на вход сlr матрицы ББЧ 39. 2. Контроллер активизирует или дезактивизирует вход вычитания матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 3. Контроллер считывает m значений из ОЗУ 43 и подает эти значения на входы х 0,х 1 хm-1 матрицы ББЧ. Контроллер поддерживает эти значения постоянными для оставшейся процедуры. 4. Для j=0, 1 n-1, выполняется следующее: а. Контроллер считывает значение а из ОЗУ и подает его на вход у матрицы ББЧ. б. Контроллер считывает значение а из ОЗУ и подает его на вход z матрицы ББЧ; генерирует импульс для сигнала clk матрицы ББЧ; считывает значение с выхода а матрицы ББЧ и записывает его в ОЗУ. На шаге 3 контроллер считывает m слов операнда Х из ОЗУ. На это требуется m циклов ОЗУ. На шаге 4 а контроллер считывает n слов операнда Y из ОЗУ. На это требуется n циклов ОЗУ. На шаге 4 б, контроллер выполняет операцию "чтение-преобразование-запись" на каждом из n слов операнда Z из ОЗУ. На это требуется n циклов ОЗУ. Общее количество циклов ОЗУ, требуемых для процедуры, m+2n. Их получают, складывая циклы на шагах 3, 4 а, и 4 б. Устройство с двойным ОЗУ Число циклов ОЗУ, необходимых для выполнения общей функции, можно далее сократить путем добавления второго ОЗУ к устройству, как показано на фиг. 6. В первом ОЗУ 44,обозначенном как "Z-ОЗУ", хранится операнд Z;Z-ОЗУ 44 способно выполнять операцию "чтение-преобразование-запись". Во втором ОЗУ 45,обозначенном как "Y-ОЗУ", хранится операндY; для Y-ОЗУ 45 нет необходимости в выполнении операции "чтение-преобразование-запись". С двойной оперативной памятью контроллер 41 способен одновременно считывать слово операнда Y, и "считывать-преобразовыватьзаписывать" слово А операнда Z. Одновременные операции осуществляются за время одного цикла ОЗУ. Комбинация контроллера 41, матрицы ББЧ 39 и Z-ОЗУ 44 включает сопроцессор, который можно использовать с вычислительным устройством 11 на фиг. 1. В таком случае Y-ОЗУ 45 можно использовать совместно с вычислительным устройством 11, как на фиг. 1. Устройство с двойным ОЗУ выполняет общую функциюZZ(XY), где Хm слов, Yn слов, и Zn слов, используя следующую процедуру: 1. Контроллер 41 подает импульс на вход сlr матрицы ББЧ 39. 17 2. Контроллер активизирует или дезактивизирует вход вычитания матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 3. Контроллер считывает m значения из YОЗУ 45 или Z-ОЗУ 44 и подает эти значения на входы х 0, х 1 хm-1 матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 4. Для j=0, 1 n-1, выполняют следующее: а. Контроллер считывает значение а из YОЗУ и подает его на вход у матрицы ББЧ; считывает значение а из Z-ОЗУ и подает его на вход z матрицы ББЧ; генерирует импульс сигнала clk для матрицы ББЧ; считывает значение с выхода а матрицы ББЧ и записывает его в ZОЗУ. На шаге 3 контроллер считывает m слов операнда Х из ОЗУ. На это требуется m циклов ОЗУ. На шаге 4 а контроллер считывает n слов операнда Y из ОЗУ и выполняет операцию"чтение-преобразование-запись" на каждом из n слов операнда Z из ОЗУ. На это требуется n циклов ОЗУ. Общее количество циклов ОЗУ, необходимых для процедуры, равно m+n. Их получают,складывая циклы на шагах 3 и 4 а. Конвейерный блок больших чисел Критический маршрут в ББЧ происходит в первом n-1 ББЧ в матрице как операция умножения-накопления. Здесь сигнал старшей части произведения ph умножителя проходит в сумматор в следующем старшем ББЧ через вход а 1. Этот путь далее продолжается через сумматор и выходит из ББЧ в виде сигнала суммы s и возвращается первоначальному ББЧ через вход а 2 второго сигнала сумматора. Рабочая частота ББЧ может быть увеличена путем создания конвейерного режима логики. Конвейерный ББЧ показан на фиг. 7. Путем введения другого регистра REG1 сокращается задержка на критическом пути. Новый регистр помещают на выходе умножителя для сигнала старшей части произведения. Это сокращает критический путь от задержки умножителя плюс задержки суммирования только до задержки умножителя. Взаимосвязи в матрице изменяются в результате введения этого регистра. Матрица ББЧ с конвейерными ББЧ показана на фиг. 8. Следует заметить, что сигнал старшей части произведения ph каждого ББЧ теперь имеет обратную связь с самим собой на входах а 1. Сигнал ph задерживается на один цикл на входе а 1 сигнала первого сумматора. Специалистам в данной области техники известно, что умножители также можно устанавливать в конвейерном режиме. Каждая конвейерная стадия вводит другой цикл ожидания,который можно скомпенсировать благодаря 18 увеличенной рабочей частоте. Кроме того, имеется программное обеспечение для автоматизации проектирования электронных схем, которое может оптимально размещать эти регистры. Контроллер можно настроить на прогрессивные вычисления XY так, чтобы AZ(XY) мог быть правильно рассчитан. Двухпортовое устройство ОЗУ Помимо операции умножения-накопления,другим критическим путем при проектировании является операция "чтение-преобразованиезапись". Этот путь можно сократить, заменив однопортовое ОЗУ на двухпортовое ОЗУ. Следует заметить, что это не полное двухпортовое ОЗУ, а скорее ОЗУ с одним портом записи и одним портом чтения. Этот тип ОЗУ позволяет одновременно осуществлять считывание из одного адреса при записи на другой адрес. На фиг. 9 показано скорректированное устройство. Используя двухпортовое ОЗУ, операцию"чтение-преобразование-запись" можно разбить на три части. Это показано на фиг. 10. Первая часть - это операция чтения (Zi); вторая часть- это операция чтения, которая происходит при формировании (Zi-1=Zi-1+/-Xi-1Yi-1. Третья часть - это запись Ai-2 обратно в ОЗУ. Действительный адрес считывания никогда не равен адресу записи; разность между ними всегда точно равняется двум. Этим гарантируется то, что запись а не повлияет на данные, считываемые на z. Таким образом, каждая из этих трех частей имеет полный цикл, для завершения которого значительно улучшается максимальная рабочая частота. Эффективный вариант представляет собой объединение операций преобразования и записи в один цикл. Это сокращает время ожидания на один цикл, и может быть настолько быстрым для некоторых типов оперативной памяти, насколько это необходимо для записи данных в ОЗУ, и, как правило, должно быть эффективным только для последней части цикла. При этом следует соблюдать требование, заключающееся в том, что адрес чтения и адрес записи должны быть различными. Конкретные арифметические действия В предыдущих разделах рассмотрено применение устройства для выполнения общей функции ZZ(XY), где Y и Z - операнды nслов, и Х -операнд m-слов, при m не больше,чем число ББЧ в массиве ББЧ. Эта функция может быть специально выделена для выполнения арифметических действий, требуемых для арифметического устройства для работы с многократной точностью и для модульного приведения. Специализацию осуществляют с помощью контроллера, обрабатывающего сигналы управления и данных матрицы ББЧ. Далее приводятся некоторые примеры таких арифметических действий. Эти примеры только несколько из тех операций, которые мо 19 гут быть выполнены и не представляют все арифметические действия, которые являются возможными. Умножение: устройство можно использовать для выполнения вычисленияZХY,где Хm слов; Yk слов; Zn слов, nk. Переполнение происходит, если значение ХY слишком велико, для соответствия в пределах представления n-слов. Если nk+m, тo XY будет всегда соответствующим. Если nk+m, то значение ХY может либо соответствовать, либо нет, в зависимости от значений Х и Y. Значение выхода су матрицы ББЧ в конце вычисления указывает на наличие или отсутствие переполнения. Процедура, использующая устройство с одним ОЗУ, заключается в следующем: 1. Контроллер генерирует импульс на входе clr матрицы ББЧ. 2. Контроллер дезактивизирует вход вычитания матрицы ББЧ и подает 0 на вход z матрицы ББЧ. Контроллер поддерживает эти значения постоянными для оставшейся процедуры. 3. Контроллер считывает значения m из ОЗУ и подает эти значения на входы х 0,х 1 хm-1 матрицы ББЧ. Контроллер подает 0 на все другие входы х матрицы ББЧ. Контроллер поддерживает эти значения постоянными для оставшейся процедуры. 4. Для j=0, 1 k-1, выполняется следующее: а. Контроллер считывает значение а из ОЗУ и подает это значение на вход у матрицы ББЧ. б. Контроллер генерирует импульс на входе clk матрицы ББЧ. в. Контроллер считывает значение на выходе а матрицы ББЧ и записывает его в ОЗУ. 5. Контроллер подает 0 на вход у матрицы ББЧ. Контроллер поддерживает эти значения постоянными для оставшейся процедуры. 6. Для j=k, k+1, , n-1 выполняют следующее: а. Контроллер генерирует импульс на входе clk матрицы ББЧ. б. Контроллер считывает значение на выходе а матрицы ББЧ и записывает его в ОЗУ. Значения, записанные в ОЗУ на шагах 4 в и 6 б - это слова искомого результата Z. Для того, чтобы убедиться, что эта процедура дает правильный ответ, следует учитывать,что она эквивалентна вычислению общей функции ZZ(XY'), где начальным значением Z является представление из n-слов для 0, а Y' является представлением из n-слов для Y. Процедура для одиночного ОЗУ с устройством чтения-преобразования-записи является идентичной. Возможность производить чтение-преобразование-запись не дает преимуще 002183 20 ства, поскольку операнд Z только записывается,но не считывается. Процедура для устройства с двойным ОЗУ подобна, за исключением того, что шаг 4 а происходит одновременно с шагом 4 в. В табл. 6 приводится список количества циклов ОЗУ, которые требуются для каждого устройства. Таблица 6 Одиночное ОЗУ с операОдиночное цией чтение- преобразо- Двойное ОЗУ ОЗУ вание-запись Шаг 3 Умножение-накопление. Устройство может использоваться для выполнения вычисления ZZ+(XY),где Хm слов; Yk слов; и Zn слов, nk. Переполнение происходит, если получаемое значение слишком велико, чтобы вместиться в n слов. На переполнение указывает активное значение на выходе су матрицы ББЧ по окончанию вычисления. Процедура при использовании устройства с одним ОЗУ состоит в следующем: 1. Контроллер генерирует импульс clr на входе матрицы ББЧ. 2. Контроллер дезактивизирует вход вычитания матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 3. Контроллер считывает m значения из ОЗУ и подает эти значения на входы х 0,х 1 хm-1 матрицы ББЧ. Контроллер подает 0 на все другие входы х матрицы ББЧ. Контроллер поддерживает эти значения постоянными для оставшейся процедуры. 4. Для j=0, 1 k-1 выполняется следующее: а. Контроллер считывает значение а из ОЗУ и подает его на вход у матрицы ББЧ. б. Контроллер считывает значение а из ОЗУ и подает его на вход z матрицы ББЧ. в. Контроллер генерирует импульс clk на входе матрицы ББЧ. г. Контроллер считывает значение а на выходе матрицы ББЧ и записывает его в ОЗУ. 5. Контроллер подает 0 на вход у матрицы ББЧ. Контроллер поддерживает это значение постоянным для оставшейся процедуры. 6. Для j=k, k+1, , n-1 выполняется следующее: а. Контроллер считывает значение на выходе су матрицы ББЧ. Если значение является неактивным, контроллер прекращает процедуру. б. Контроллер считывает значение а из ОЗУ и подает его на вход z матрицы ББЧ. в. Контроллер генерирует импульс на входе clk матрицы ББЧ. 21 г. Контроллер считывает значение на выходе а матрицы ББЧ и записывает его в ОЗУ. Значения, записанные в ОЗУ на шагах 4 в и 6 г - это слова искомого результата Z. Для того, чтобы убедиться, что эта процедура дает правильный ответ, следует учитывать,что она эквивалентна вычислению общей функции ZZ+(XY'), где Y' является представлением n-слов Y. Эта процедура может быть завершена на шаге 6 а до того, как все n слова Z заменены новыми значениями. Это происходит тогда, когда процедура определяет, что заменяемые значения будут идентичны первоначальным значениям. Завершение процедуры сокращает общее количество циклов ОЗУ путем исключения циклов,которые не имеют никакого действия. Процедура для одиночного ОЗУ с устройством "чтения-преобразования-записи" является аналогичной за исключением того, что шаги 4 в и 4 г происходят за один цикл "чтенияпреобразования-записи", а шаги 6 б и 6 г происходят за один цикл "чтения-преобразованиязаписи". Процедура для устройства с двойным ОЗУ аналогична процедуре для одиночного ОЗУ с устройством "чтения-преобразования-записи" за исключением того, что шаг 4 а происходит одновременно с циклом "чтения-преобразованиязаписи" шагов 4 б и 4 г. Перечень количества циклов ОЗУ, требуемых для каждого устройства, приводится в табл. 7. Таблица 7 Одиночное ОЗУ с Одиночное операцией чтениеДвойное ОЗУ ОЗУ преобразованиезапись Шаг 3m+n символ указывает на возможность прекращения процедуры уже на шаге 6 а."Умножение-отрицание-накопление". Устройство можно использовать для выполнения вычисленияZZ-(XY),где Хm слов; Yk слов; и Zn слов, nk. Отрицательное переполнение происходит,если следующее значение отрицательно. На отрицательное переполнение указывает активное значение на выходе су матрицы ББЧ в конце вычисления. Эта процедура идентична процедуре при операции умножения-накопления, за исключением того, что вход вычитания не дезактивируют, а активизируют на шаге 2. Процедуру прекращают досрочно, если установлено, что значения замены для слов Z будут идентичны первоначальным значениям. Число циклов ОЗУ такое же, как и для операции умножениянакопления. 22 Прикладная программа для модульного возведения в степень Допустим, что А, В, и Р - целые числа из n слов. Модульное возведение в степень - это задача вычисления АВ%Р. Известной методикой для выполнения модульного возведения в степень является метод Монтгомери. (Р. Montgomery, "Modular Multiplication without Trial Division", Mathematics of Computation, 44 (1985), pp. 519-521.) Метод хорошо подходит для настоящего устройства, основанного на матрице ББЧ. Этот патент не предназначен для того,чтобы служить обучающей программой по методу Монтгомери. Здесь только предполагается показать, как осуществить этот метод, используя настоящее изобретение, а также проанализировать скорость выполнения в зависимости от циклов ОЗУ. Метод Монтгомери основан на функции,называемой "произведением Монтгомери". Произведение Монтгомери из двух целых чисел Х и Y по модулю Р определяется как(GWn)%Р=1, и k - малое целое число. Такое целое число G существует, если Р - нечетное число, и не существует, если Р - четное число. Таким образом, метод Монтгомери используется только для случаев, когда Р - нечетное число. Термин "kP" включен для ослабления требования к расположению значения f( ) в диапазоне от 0 до Р - 1. Это желательно по причинам,которые станут ясными позже. Процедура выполнения модульного возведения в степень, используя метод Монтгомери,заключается в следующем: 1. ТW2n%Р 2. Af(T, A, P) 3. Tf(T,1,P) 4. Для каждого бита в В, в первую очередь наиболее важно выполнить следующее: а. T(T, T, P) б. если этот бит в В равен 1, то Тf(Т, А, Р) 5. Tf(T, 1, P) 6. ТТ%Р Т - целое число из n слов. В конце процедуры Т содержит значение АВ%Р. Цикл на шаге 4 повторяется для каждого бита в экспоненте В. Поскольку В имеет n слов,и каждое слово имеет b битов, то цикл повторяется nb раз. Произведение Монтгомери на шаге 4 а рассчитывается для каждого повторения цикла. Произведение Монтгомери на шаге 4 б рассчитывается только для того случая, если соответствующий бит экспоненты представляет собой 1-бит. Если бы половину разряда в экспоненте составляли 1-биты, то тогда произведение Монтгомери на шаге 4 б рассчитывали бы для половины повторений циклов. При таком предположении, общее количество произведений 23 Монтгомери, выполненных в течение цикла составляет 1.5nb. В криптографии с открытым ключом число битов в экспоненте велико, как правило, сотни или тысячи битов. Это означает, что для возведения в степень требуются сотни или тысячи вычислений произведения Монтгомери. Таким образом, для быстрого вычисления при возведении в степень необходимо быстро вычислить произведение Монтгомери. Устройство на основе матрицы ББЧ согласно настоящему изобретению способно эффективно вычислять произведение Монтгомери. В следующих разделах описывается, как это выполняется. Шаги 1, 2, и 3 - это шаги "предварительного вычисления", а шаги 5 и 6 - это шаги "поствычисления". Эти шаги требуют очень немного вычислительных усилий по сравнению с вычислениями в шаге 4 и ими можно пренебречь. Ответственность за управление этой процедурой может быть возложена на контроллер и вычислительное устройство, к которому устройство присоединено как сопроцессор. Проектировщик системы имеет гибкие средства для разделения такой ответственности. В крайнем случае, контроллер может быть разработан с достаточным интеллектом, чтобы выполнять все шаги процедуры, а вычислительное устройство будет только начинать процедуру и обеспечивать контроллер местом в памяти для операндов. В другом случае, контроллер может предназначаться только для обработки общей функции ZZ+(XY), а вычислительное устройство отвечает только за построение произведений Монтгомери и трансляцию их в модульное возведение в степень через вышеупомянутую процедуру. Умножение многократной точности Первый шаг в вычислении произведения Монтгомери f(X, Y, Р) заключается в вычислении произведения Х и Y. Это обычная процедура умножения и сложения из программы средней школы. Для представления получаемого произведения требуется 2n слов, где n - число слов в каждом из X, Y, и Р. Для упрощения формулировки введем систему обозначений. Допустим, что Х - целое число из n слов. Можно сказать, что обозначение Х=xj, 0jn, подразумевает, что значение Х равно х 0+x1W+x2W2 +xn-1Wn-1. Используются "подцелые числа" X, то есть, целочисленные части X, состоящие из подмножества последовательных слов X. Например, целое число X'=xj, 2j5 - это подцелое число из 3-х слов X, имеющее значение х 2+x3W+x4W2. Операция X'X'+1 замещает х 2 на х 2+1 (допустим, что х 2 малое значение, так что не оно переполняется). Это воздействует на увеличение Х на W2, поскольку х 2 взвешивается в Х с помощью W2. 24 Допустим, что m - это число ББЧ в массиве ББЧ. Предположим, что n - это кратное m. Это предположение может быть сделано без потери общности, так как длину целого числа всегда можно увеличить, добавляя 0-слов к старшему концу, чтобы делать его кратным m. Целые числа Z, Zi и Xi можно определить следующим образом:Z - целое число из 2n+1 слов, которое используется для запоминания вычисленного произведения. Это целое число Z на одно слово длиннее, чем оно должно быть, по причинам,которые будут пояснены в следующем разделе.Zi - это подцелое число Z, содержащее n+m слов, начинающихся с zi. Xi - подцелое числоX, содержащее m слов, начинающихся с xi. Произведение Х и Y можно вычислить по следующей процедуре: 1. Z0 2. i0 3. При (in) выполняется следующее: а. Zi Zi+(XiY) б. i=i+m. Шаг 1 очищает Z до 0. Затем цикл на шаге 3 выполняет операцию "умножение и сложение". При каждом повторении цикла обрабатывается m слов операнда X. Эти слова формируют Xi, которое умножается на операнд Y и накапливается в Zi. Zi смещается в пределах Z на то же самое число слов, на которое Xi смещено в пределах X. После последней итерации Z содержит искомое произведение ХY. Рассмотрим значение Z после операцииi+m слов из X. SiY вписывается в n+m+i слов. Поскольку Zi смещено в Z на i слов и имеет длину n+m, операция ZiZi+(XiY) не переполняется. Цикл повторяется в целом n/m раз. В табл. 8 приводится число циклов ОЗУ, требуемых на шаге 3 а для каждой итерации цикла, а также общее количество требуемых циклов ОЗУ. Таблица 8 Одиночное ОЗУ с Одиночное операцией чтениепреобразованиеОЗУ запись Шаг 3 а 3m+3n 2m+2n Всего 3n+3n2/m 2n+2n2/m Для шага 3 а может потребоваться меньшее количество циклов, чем указано в таблице. Это происходит, когда сигнал на выходе су матрицы ББЧ указывает, что досрочное завершение приемлемо. Практически, сокращение циклов с этой целью составляет только очень малую часть общего количества требуемых циклов. 25 Приведение Монтгомери Если произведение из 2n слов содержится в Z, то второй шаг произведения Монтгомери предназначен для его приведения по модулю Р к значению n слов. Приведение Монтгомери производится справа налево: соответствующий множитель Р добавляется к Z таким образом,что из Z аннулируются крайние справа слова (то есть, наименее значимые слова). Приведение требует целого числа Q, которое удовлетворяетQ - целое число из m слов. Такое Q всегда существует, если Р - нечетное число. Вычисление Q производится прямым методом. Q вычисляется один раз в начале возведения в степень, а затем используется для каждого шага приведения при возведении в степень. Поскольку Q вычисляется только один раз, то вычислительные затраты на него несущественны. Подцелое число Zi, может быть определено иным путем, отличающимся от того, как оно определялось на шаге умноженияzi и содержащее все слова Z налево от zi,включительно. Zi состоит из 2n+1-i слов. Необходимо также определить целое числоV из m слов, где V - временная переменная. Шаг приведения можно выполнить, используя следующую процедуру: 1. i0 2. При (in) выполняется следующее: а. VQZi б. ZiZi+(VP) в. i=i+m В каждой итерации цикла на шаге 2 шаг 2 б очищает m слов из Z. То есть слова zi,zi+1 zi+m-1 заканчиваются со значением 0. Такая операция сброса осуществляется следующим образом. На шаге 2 а Q умножают на Zi, а результат помещают в V. Поскольку Q и V - каждое представляет собой целое число из m слов, то значение имеют только самые низшие m слов из Zi(то есть, zj, iji+m); другие слова Zi не оказывают никакого действия на результат, после того, как их округляют до m слов, чтобы вписать в V. Таким образом, шаг 2 а выполняют как "умножение наполовину", где два целых числа из m слов умножают, но вычисляют только низшие m слова произведения. На шаге 2 б V умножают на модуль по Р и накапливают в Zi. Значение V, вычисленное на шаге 2 а, таково, что в результате низшие m слов из Zi имеют значение 0. При накоплении в Zi гарантируется отсутствие переполнения, и с высокой вероятностью, накопление завершается досрочно благодаря тому, что выход су матрицы ББЧ, становится неактивным. Точное время осуществления завершения зависит от данных,но, поскольку V имеет m слов, а Р имеет n слов, 002183 26 завершение обычно происходит после накопления n+m слов из Zi. Цикл выполняет итерации всего n/m раз. На табл. 9 показано число циклов ОЗУ, требуемых на шагах 2 а и 2 б для каждой итерации цикла, и общее количество требуемых циклов ОЗУ. Одиночное ОЗУ Шаг 2 а Шаг 2 б Всего В конце цикла низшие n слов из Z (т.е.zj, 0jn) имеют значение 0; а наивысшее слово из Z (т.е. z2n) имеет значение 0 или 1. Если наивысшее слово равно 1, оно должно быть очищено путем вычитания Р из верхних слов Z следующим образом:ZnZn-(1P) Здесь устройство по настоящему изобретению также используется для выполнения операции "умножение-вычитание-накопление", при этом один из операндов установлен на единице. В результате этой операции гарантируется, что наивысшее слово из Z имеет значение 0. Действительно ли необходима эта операция (то есть,действительно ли z2n=1 до операции), зависит от данных. Независимо от этого количество используемых циклов ОЗУ незначительно по сравнению с количеством циклов, требуемых для циклов умножения и приведения. В этой точке Z - это целое число из 2n слов, причем низшие n слов имеют значение 0. Для завершения произведения Монтгомери,выполняют следующее:ZZn/Wn. Это - просто сдвиг вправо старших n слов из Z к низшим n словам. Получаемое значение представляет собой целое число из n слов; получаемое значение - это искомое произведение Монтгомери. Процедура приведения гарантирует соответствие Z в пределах n слов, однако это не гарантирует то, что ZР. Для осуществления цикла на шаге 4 процедуры возведения в степень,приведение Z необходимо настолько, чтобы обеспечить соответствие Z в пределах n слов. Процедура возведения в степень включает шаг 6 поствычисления для выполнения приведения конечного результата до значения, меньшего,чем Р. Общее количество циклов ОЗУ Результаты, полученные в предыдущем разделе для количества циклов ОЗУ, требуемых на шаге умножения и шаге приведения, сведены в табл. 10 в один результат для произведения Монтгомери. Это значение умножается на 1.5nb для получения общего числа циклов ОЗУ, необходимых для вычисления модульного возведения в степень. Одиночное ОЗУ с Одиночное операцией чтение- преобразоваОЗУ ние-запись Произведение Монтгомери Возведение в степень Формулы для возведения в степень пренебрегают циклами ОЗУ, необходимыми в течение шага предварительного вычисления и шага поствычисления, то есть в течение шагов 1, 2, 3, и 5 процедуры возведения в степень. Эти шаги требуют очень малого числа циклов ОЗУ по сравнению с шагом 4 и ими можно пренебречь. Если операнды являются большими по сравнению с числом ББЧ, то n/m имеет большое значение. Это часто имеет место при практическом использовании шифрования с открытым ключом. В таком случае число циклов ОЗУ приблизительно составляет Kbn3/m, где К равно 9, 6 или 3 для трех типов устройств, соответственно. Таким образом, общее количество циклов ОЗУ приблизительно пропорционально 1/m; например при удваивании количества ББЧ число циклов ОЗУ сокращается почти наполовину. Для устройства с двойным ОЗУ требуется приблизительно одна третья часть количества циклов,которые требуются для устройства с одним ОЗУ, а для двойного ОЗУ требуется приблизительно половина циклов, необходимых для одиночного ОЗУ с устройством"чтениепреобразование-запись". Для специалистов в данной области техники понятно, что могут быть внесены различные изменения в способ вычисления и в арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по настоящему изобретению в пределах объема и существа изобретения и что настоящее изобретение охватывает модификации и изменения способа вычисления и устройства для целочисленной арифметики многократной точности,которые не выходят за пределы объема прилагаемой формулы изобретения и эквивалентных им способов и устройств. ФОРМУЛА ИЗОБРЕТЕНИЯ 1. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных y со вторым сигналом данных х, включающее множество блоков больших чисел (ББЧ),ББЧ 0, ББЧ 1, ББЧ 2, , ББЧn-1, где n общее количество блоков больших чисел во множестве блоков больших чисел, причем каждый блок больших чисел содержит умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей 28 части произведения и выходом младшей части произведения; сумматор с первым входом сумматора,вторым входом сумматора, третьим входом сумматора, четвертым входом сумматора и выходом сумматора, причем указанный третий вход сумматора соединен с умножителем для приема выхода младшей части произведения; и регистр ББЧ со входом регистра ББЧ и выходом регистра ББЧ, причем указанный вход регистра ББЧ связан с сумматором для приема выхода сумматора, указанный регистр ББЧ,фиксирующий значение выхода сумматора до получения синхронизирующего импульса и передающий значение на указанный выход регистра ББЧ после получения синхронизирующего импульса, указанный выход регистра ББЧ разделяют на старший выход регистра ББЧ и младший выход регистра ББЧ, указанный старший выход регистра ББЧ содержит два верхних бита указанного выхода регистра ББЧ, указанный младший выход регистра ББЧ содержит все биты указанного выхода регистра ББЧ, кроме тех, которые находятся в указанном старшем выходе регистра ББЧ, указанный старший выход регистра ББЧ связан с четвертым входом сумматора, указанный регистр ББЧ также имеет вход сброса регистра ББЧ для сброса указанного выхода регистра ББЧ до нуля при активизировании указанного входа сброса регистра ББЧ; первый логический элемент ИЛИ, связанный с регистром ББЧ для приема выходного сигнала регистра ББЧ и входного сигнала переноса ci и для генерирования выходного сигнала переноса со, причем указанный выходной сигнал переноса со активизируется любым одним битом либо с выхода регистра ББЧ, который является активным, либо из входного сигнала переноса ci, который является активным; второй логический элемент ИЛИ, связанный с регистром ББЧ для приема выходного старшего сигнала регистра ББЧ и для генерирования вспомогательного выходного сигнала переноса са, причем указанный вспомогательный выходной сигнал переноса са активизируется,если активен любой бит выходного старшего сигнала регистра ББЧ; причем на первый вход умножителя каждого блока больших чисел указанного множества блоков больших чисел поступает первый сигнал данных у,на вторые входы умножителей каждого блока больших чисел указанного множества блоков больших чисел (ББЧ), ББЧ 0, ББЧ 1,ББЧ 2, , ББЧn-1 поступает соответственно каждый элемент из множества элементов х 0,х 1, х 2, , хn-1 второго сигнала данных х; первый вход сумматора каждого i-го блока больших чисел ББЧi указанного множества блоков больших чисел для i больше нуля связан с выходом старшей части произведения i-1-го блока больших чисел ББЧi-1; 29 младший выход регистра ББЧ каждого i-го блока больших чисел ББЧi для i больше нуля связан со вторым входом сумматора i-1-го блока больших чисел ББЧi-1; первую схему дополнения, связанную с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен; вторую схему дополнения, связанную с младшим выходом регистра ББЧ первого блока больших чисел ББЧ 0 для дополнения указанного младшего выхода регистра ББЧ, когда указанный сигнал вычитания активен, причем указанная вторая схема дополнения генерирует четвертый сигнал данных а; регистр-фиксатор с входом регистрафиксатора и выходом регистра-фиксатора, причем вход указанного регистра-фиксатора связан с выходом старшей части произведения указанного n-го блока больших чисел ББЧn-1, а вход указанного регистра-фиксатора связан со вторым входом сумматора указанного n-го блока больших чисел ББЧn-1 для фиксирования значения n-ной старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ной старшей части произведения ко второму входу сумматора указанного n-го блока больших чисел после поступления синхронизирующего импульса; указанный первый блок больших чисел ББЧ 0, вход ci которого связан с логическим значением 0; указанный второй блок больших чисел ББЧ 1, вход ci которого связан с выходом са первого блока больших чисел ББЧ 0; каждый i-тый блок больших чисел ББЧi указанного множества блоков больших чисел для i более чем один, у которого вход ci связан с выводом со i-1-го блока больших чисел ББЧi-1, а выход со n-го блока больших чисел ББЧn-1 является пятым сигналом данных,сигналом переноса потока су; указанный регистр-фиксатор имеет вход для сигнала сброса регистра-фиксатора и каждый ББЧ имеет вход сброса регистра ББЧ, причем множество входов сброса регистра ББЧ и указанный вход сигнала сброса регистрафиксатора связаны вместе для формирования сигнала сброса данных сlr; и указанный регистр-фиксатор имеет вход синхронизации и каждый ББЧ имеет вход синхронизации, причем множество входов синхронизации соединены вместе для формирования синхронизирующего сигнала clk. 2. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных у со вторым сигналом данных х, включающее множество блоков больших чисел (ББЧ),ББЧ 0, ББЧ 1, ББЧ 2, , ББЧn-1, где n002183 30 общее количество блоков больших чисел в множестве блоков больших чисел, причем каждый блок больших чисел содержит умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора,вторым входом сумматора, причем указанный сумматор соединен с умножителем для приема выходного сигнала младшей части произведения; и регистр ББЧ, имеющий выход сигнала суммы, причем указанный регистр ББЧ связан с указанным сумматором; на первый вход умножителя каждого блока больших чисел указанного множества блоков больших чисел поступает первый сигнал данных у,на вторые входы умножителей каждого блока больших чисел указанного множества блоков больших чисел (ББЧ), ББЧ 0, ББЧ 1,ББЧ 2, , ББЧn-1 поступает соответственно каждый элемент из множества элементов х 0,х 1, х 2, , хn-1 второго сигнала данных х; каждый i-ый блок больших чисел ББЧi указанного множества блоков больших чисел для i больше нуля, у которого первый вход сумматора связан с выходом старшей части произведения i-1-ого блока больших чисел ББЧi1; каждый i-ый блок больших чисел ББЧi для i больше нуля, у которого выходной сигнал суммы связан со вторым входом сумматора i1-ого блока больших чисел ББЧi-1; схему дополнения, связанную с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен; и регистр-фиксатор, связанный с выходом старшей части произведения указанного n-ого блока больших чисел ББЧn-1 и со вторым входом сумматора указанного n-ого блока больших чисел ББЧn-1 для фиксирования значения n-ой старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ой старшей части произведения на второй вход сумматора указанногоn-ого блока больших чисел после поступления синхронизирующего импульса. 3. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных у со вторым сигналом данных х, включающее блок больших чисел (ББЧ), имеющий умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора и вторым входом сумматора, причем указанный 31 сумматор связан с умножителем для приема выходного сигнала младшей части произведения и для вывода первого сигнала суммы; и регистр ББЧ, связанный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы, причем на первый вход умножителя указанного блока больших чисел поступает первый сигнал данных у; на второй вход умножителя указанного блока больших чисел поступает второй сигнал данных х; схему дополнения, связанную с первым входом сумматора указанного блока больших чисел для дополнения третьего сигнала данныхz, когда сигнал вычитания активен; и регистр-фиксатор, связанный с выходом старшей части произведения указанного блока больших чисел и со вторым входом сумматора указанного блока больших чисел для фиксации значения старшей части произведения до поступления синхронизирующего импульса и для подачи значения старшей части произведения к второму входу сумматора указанного блока больших чисел после поступления синхронизирующего импульса. 4. Устройство по п.3, в котором указанный блок больших чисел дополнительно включает логический элемент ИЛИ, соединенный с выходом указанного регистра ББЧ, для приема верхних битов второго сигнала суммы из указанного регистра ББЧ в качестве сигнала переноса, причем указанный второй логический элемент ИЛИ выводит логическое ИЛИ сигнала переноса в качестве сигнала переноса потока. 5. Устройство по п.3 или 4, дополнительно включающее множество блоков больших чисел, ББЧ 0,ББЧ 1, ББЧ 2 ББЧn-1, где n - общее количество блоков больших чисел во множестве блоков больших чисел; каждый i-ый блок больших чисел ББЧi указанного множества блоков больших чисел для i больше нуля, у которого первый вход сумматора связан с выходом старшей части произведения i-1-ого блока больших чисел ББЧi1; и каждый i-ый блок больших чисел ББЧi для i больше нуля, у которого выход сигнала суммы связан со вторым входом сумматора i1-ого блока больших чисел ББЧi-1. 6. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных х со вторым сигналом данных у, включающее множество блоков больших чисел (ББЧ), в котором каждый блок больших чисел имеет умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения, выходом младшей части произведения; 32 сумматор с первым входом сумматора и вторым входом сумматора, причем сумматор соединен с умножителем для приема выходного сигнала младшей части произведения и вывода сигнала суммы; регистр ББЧ, соединенный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы; на первый вход умножителя каждого блока больших чисел указанного множества блоков больших чисел подается первый сигнал данных у; с каждым вторым входом умножителя каждого блока больших чисел указанного множества блоков больших чисел соответственно связан каждый элемент второго сигнала данных х,имеющего множество элементов; каждый i-ый блок больших чисел ББЧi указанного множества блоков больших чисел для i, отличного от исходного блока больших чисел, имеет первый вход сумматора, связанный с выходом старшей части произведения i-1 ого блока больших чисел ББЧi-1; каждый i-ый блок больших чисел ББЧi для i, отличного от исходного блока больших чисел, имеет выход сигнала суммы, связанный со вторым входом сумматора i-1-ого блока больших чисел ББЧi-1. 7. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6, дополнительно включающее схему дополнения, связанную с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен; и регистр-фиксатор, связанный с выходом старшей части произведения n-ого блока больших чисел ББЧn-1 и со вторым входом сумматора указанного n-ого блока больших чисел ББЧn-1, где n - общее количество блоков больших чисел, для фиксирования значения nого выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ого выхода старшей части произведения на второй вход сумматора указанного n-ого блока больших чисел после поступления синхронизирующего импульса. 8. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6, дополнительно включающее схему дополнения, связанную с первым входом сумматора первого блока больших чисел ББЧ 0, для дополнения третьего сигнала данных z, когда сигнал вычитания активен. 9. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6 или 8, дополнительно включающее регистр-фиксатор, связанный с выходом старшей части произведения n-ого блока больших чисел ББЧn-1 и со вторым входом сумматора указанного n-ого блока больших чисел ББЧn-1, где n - общее количество блоков 33 больших чисел во множестве блоков больших чисел, для фиксирования значения n-ого выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ого выхода старшей части произведения на второй вход сумматора указанного nого блока больших чисел после поступления синхронизирующего импульса. 10. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6, дополнительно включающее логическое средство, связанное с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен; и средство регистра, связанное с выходом старшей части произведения n-ого блока больших чисел ББЧn-1 и со вторым входом сумматора указанного n-ого блока больших чисел ББЧn-1, где n - общее количество блоков больших чисел во множестве блоков больших чисел, для фиксирования значения n-ого выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ого выхода старшей части произведения на второй вход сумматора указанного nого блока больших чисел после поступления синхронизирующего импульса. 11. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6, далее включающее логическое средство, связанное с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен. 12. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.6 или 11, дополнительно включающее средство регистра, связанное с выходом старшей части произведения n-ого блока больших чисел ББЧn-1 и со вторым входом сумматора указанного n-ого блока больших чисел ББЧn-1, где n - общее количество блоков больших чисел во множестве блоков больших чисел для фиксирования значенияn-ого выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения n-ого выхода старшей части произведения на второй вход сумматора указанного n-ого блока больших чисел после поступления синхронизирующего импульса. 13. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.2, дополнительно включающее выходную схему, связанную с выходом сигнала суммы первого блока больших чисел ББЧ 0 для вывода выходного сигнала. 14. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.3, дополнительно включающее выходную схему, связанную с выходом 34 сигнала суммы указанного блока больших чисел для вывода выходного сигнала. 15. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных х со вторым сигналом данных у, включающее блок больших чисел (ББЧ), имеющий умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора и вторым входом сумматора, причем указанный сумматор связан с умножителем для приема выходного сигнала младшей части произведения и предназначен для вывода первого сигнала суммы; и регистр ББЧ, связанный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы; логический элемент ИЛИ, соединенный с выходом указанного регистра ББЧ для приема верхних битов второго сигнала суммы из указанного регистра ББЧ в качестве сигнала переноса, а также для вывода логического ИЛИ сигнала переноса в качестве сигнала переноса потока; на первый вход умножителя указанного блока больших чисел подается первый сигнал данных у; ко второму входу умножителя указанного блока больших чисел подается второй сигнал данных х. 16. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.15, дополнительно включающее схему дополнения, связанную с первым входом сумматора указанного блока больших чисел для дополнения третьего сигнала данныхz, когда сигнал вычитания активен; и регистр-фиксатор, связанный с выходом старшей части произведения указанного блока больших чисел и вторым входом сумматора указанного блока больших чисел для фиксирования значения выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения выхода старшей части произведения на второй вход сумматора указанного блока больших чисел после поступления синхронизирующего импульса. 17. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.15, дополнительно включающее схему дополнения, связанную с первым входом сумматора указанного блока больших чисел для дополнения третьего сигнала данныхz, когда сигнал вычитания активен. 18. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.15 или 17, далее включаю 35 щее регистр-фиксатор, связанный с выходом старшей части произведения указанного блока больших чисел и со вторым входом сумматора указанного блока больших чисел, для фиксирования значения выхода старшей части произведения до поступления синхронизирующего импульса и для подачи значения выхода старшей части произведения на второй вход сумматора указанного блока больших чисел после поступления синхронизирующего импульса. 19. Способ обработки первого сигнала данных у со вторым сигналом данных х, использующий матрицу блоков больших чисел(ББЧ), имеющую, по крайней мере, один блок больших чисел, причем каждый блок больших чисел имеет умножитель, сумматор и регистр ББЧ, умножитель имеет первый вход умножителя, второй вход умножителя, выход старшей части произведения, выход младшей части произведения, сумматор имеет первый вход сумматора и второй вход сумматора, а указанный сумматор соединен с умножителем для приема выхода младшей части произведения и вывода первого сигнала суммы, а также регистр ББЧ,соединенный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы, причем матрица больших чисел имеет вход сброса, вход вычитания,вход синхронизации, вход данных z и выход данных а,указанный метод включает следующие шаги: подачу импульса на вход сброса для сброса регистра ББЧ и регистра-фиксатора в пределах матрицы ББЧ; установку входа вычитания на одну из логических единиц для вычитания и на логический ноль для сложения; подачу значения для второго сигнала данных х в массив ББЧ; подачу значения для первого сигнала данных у в массив ББЧ; подачу значения для ввода данных z в массив ББЧ; подачу импульса на вход синхронизации для обновления множества регистров ББЧ и регистра-фиксатора новыми значениями; считывание выхода данных а. 20. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью, включающее матрицу блоков больших чисел (ББЧ) из множества блоков больших чисел, которая имеет вход сброса, вход вычитания, множество входов данных х 0, х 1, , хm-1, вход у,вход z, вход синхронизации и выход а; причем каждый блок больших чисел указанной матрицы (ББЧ) имеет умножитель с первым входом умножителя, вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; 36 сумматор с первым входом сумматора и вторым входом сумматора, причем указанный сумматор связан с умножителем для приема выходного сигнала младшей части произведения и для вывода первого сигнала суммы; и регистр ББЧ, связанный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы; контроллер, соединенный с указанным блоком больших чисел (ББЧ) для подачи импульса на вход сброса, для выбора значения активизации и дезактивизации на входе вычитания, для считывания и подачи m значений на множество входов данных х 0, х 1 хm-1 соответственно для считывания и подачи значения у на вход у, для считывания и подачи значения z на вход z, подачи импульса на вход синхронизации, считывания значения с выхода а и для записи значения выхода а в оперативную память; и оперативное запоминающее устройство(ОЗУ), соединенное с указанным контроллером для хранения m значений, считываемых контроллером, для хранения значения у, считываемого контроллером, для хранения значения z,считываемого контроллером, и для хранения значения выхода а, записанного контроллером. 21. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью, включающее матрицу блока больших чисел (ББЧ) множества блоков больших чисел, имеющую вход сброса, вход вычитания, вход данных х, вход у,вход z, вход синхронизации и выход а; причем каждый блок больших чисел имеет умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора и вторым входом сумматора, причем указанный сумматор связан с умножителем для приема выходного сигнала младшей части произведения и для вывода первого сигнала суммы; и регистр ББЧ, связанный с указанным сумматором для приема первого сигнала суммы и для вывода второго сигнала суммы; контроллер, соединенный с указанным блоком больших чисел (ББЧ) для подачи импульса на вход сброса, для выбора значения активизации и дезактивизации на входе вычитания, для считывания и подачи m значений на вход данных х, для считывания и подачи значения у на вход у, для считывания и подачи значения z на вход z, подачи импульса на вход синхронизации, считывания значения с выхода а и для записи значения выхода а в оперативное запоминающее устройство; и оперативное запоминающее устройство(ОЗУ), соединенное с указанным контроллером для хранения m значений, считываемых контроллером, хранения значения у, считываемого 37 контроллером, хранения значения z, считываемого контроллером, и хранения значения выхода а, записанного контроллером. 22. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.20 или 21, в котором оперативное запоминающее устройство способно выполнять операцию "чтение-преобразованиезапись" таким образом, что по сигналу контроллера значение а считывается из оперативного запоминающего устройства, преобразовывается и записывается назад в оперативное запоминающее устройство за один цикл. 23. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.20 или 21, в котором оперативное запоминающее устройство дополнительно включает первое оперативное запоминающее устройство для хранения значения z, которое способно выполнять операцию"чтениепреобразование-запись", второе оперативное запоминающее устройство для хранения значения у, в котором контроллер одновременно считывает значение у и выполняет операцию "чтение-преобразование- запись" со значением z за один цикл оперативного запоминающего устройства. 24. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью по п.20 или 21, у которого оперативное запоминающее устройство имеет один порт записи и один порт чтения, так что по сигналу контроллера первое значение считывается с первого адреса, в то время как одновременно второе значение записывается во второй адрес. 25. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных у со вторым сигналом данных х, включающее: множество блоков больших чисел (ББЧ),ББЧ 0, ББЧ 1, ББЧ 2, , ББЧn-1, где "n" общее количество блоков больших чисел во множестве блоков больших чисел, причем каждый блок больших чисел имеет умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора и вторым входом сумматора, третьим входом сумматора, четвертым входом сумматора и входом сумматора причем указанный третий вход сумматора соединен с умножителем для приема выходного сигнала младшей части произведения; и первый регистр ББЧ со входом регистра ББЧ и выходом регистра ББЧ, причем указанный вход регистра ББЧ связан с сумматором для приема выхода сумматора, указанный первый регистр ББЧ фиксирует значение выхода сумма 002183 38 тора до поступления синхронизирующего импульса и передает значение на указанный выход регистра ББЧ после поступления синхронизирующего импульса, причем выходной сигнал указанного регистра ББЧ разделяется на старший выходной сигнал регистра ББЧ и младший выходной сигнал регистра ББЧ, причем указанный старший выходной сигнал регистра ББЧ,содержит два верхних бита указанного выходного сигнала регистра ББЧ, а указанный младший выходной сигнал регистра ББЧ содержит все биты указанного выходного сигнала регистра ББЧ, кроме тех, которые находятся в указанном выходном сигнале регистра ББЧ, указанный выходной сигнал регистра ББЧ связан с четвертым входом сумматора, причем указанный первый регистр ББЧ также имеет вход сброса регистра ББЧ для сброса указанного выхода регистра ББЧ до нуля, когда активизируется указанный вход сброса регистра ББЧ; второй регистр ББЧ для приема выхода старшей части произведения умножителя; первый логический элемент ИЛИ, связанный с первым регистром ББЧ для получения выхода регистра ББЧ и входного сигнала переноса сi и для генерирования выходного несущего сигнала со, который активизируется в ответ на один сигнал любого бита с выхода регистра ББЧ, являющегося активным, и указанного сигнала ci, являющегося активным; второй логический элемент ИЛИ, связанный с первым регистром ББЧ для приема выходного старшего сигнала регистра ББЧ и для генерирования вспомогательного входного сигнала переноса са, причем указанный вспомогательный входной сигнал переноса са активизируется, если активен любой бит выходного старшего сигнала регистра ББЧ; первый сигнал данных у, который поступает на первый вход умножителя каждого блока больших чисел указанного множества блоков больших чисел; второй сигнал данных х, имеющий множество элементов х 0, х 1, х 2, , хn-1, причем каждый элемент соответственно связан со вторым входом умножителя каждого блока больших чисел указанного множества блоков больших чисел; каждый i-тый блок больших чисел ББЧi указанного множества блоков больших чисел, у которого первый вход сумматора связан с выходом старшей части произведения соответствующего i-ого блока больших чисел ББЧi; каждый i-тый блок больших чисел ББЧi для i больше нуля имеет младший выход регистра ББЧ, связанный со вторым входом сумматора i-1-го блока больших чисел ББЧi-1; первую схему дополнения, связанную с первым входом сумматора первого блока больших чисел ББЧ 0 для дополнения третьего сигнала данных z, когда сигнал вычитания активен; 39 вторую схему дополнения, связанную с младшим выходом регистра ББЧ первого блока больших чисел ББЧ 0 для дополнения указанного младшего выхода регистра ББЧ, когда указанный сигнал вычитания активен, причем указанная вторая схема дополнения генерирует четвертый сигнал данных а; указанный первый блок больших чисел ББЧ 0, вход ci которого связан с логическим значением 0; указанный второй блок больших чисел ББЧ 1, вход ci которoго связан с выходом са первого блока больших чисел ББЧ 0; каждый n-ый блок больших чисел ББЧn1, у которого второй вход сумматора связан с логическим значением 0; каждый i-тый блок больших чисел ББЧi указанного множества блоков больших чисел для i более единицы, у которого вход ci связан с выходом со i-1-го блока больших чисел ББЧi-1, причем со выход n-го блока больших чисел ББЧn-1 является пятым сигналом данных - сигналом переноса потока су. 26. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных у со вторым сигналом данных х, включающее блок больших чисел (ББЧ), имеющий умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора и вторым входом сумматора, третьим входом сумматора, четвертым входом сумматора и входом сумматора причем указанный третий вход сумматора соединен с умножителем для приема выходного сигнала младшей части произведения; и первый регистр ББЧ со входом регистра ББЧ и выходом регистра ББЧ, причем указанный вход регистра ББЧ связан с сумматором для приема выхода сумматора, указанный первый регистр ББЧ фиксирует значение выхода сумматора до поступления синхронизирующего импульса и передает значение на указанный выход регистра ББЧ после поступления синхронизирующего импульса, причем выходной сигнал указанного регистра ББЧ разделяется на старший выходной сигнал регистра ББЧ и младший выходной сигнал регистра ББЧ, указанный старший выходной сигнал регистра ББЧ содержит два верхних бита указанного выходного сигнала регистра ББЧ, а указанный младший выходной сигнал регистра ББЧ содержит все биты указанного выходного сигнала регистра ББЧ, кроме тех, которые находятся в указанном выходном сигнале регистра ББЧ, указанный выходной старший сигнал регистра ББЧ связан с четвертым входом сумматора, причем указанный первый регистр ББЧ также имеет вход 40 сброса регистра ББЧ для сброса указанного выхода регистра ББЧ до нуля, когда активизируется указанный вход сброса регистр ББЧ; второй регистр ББЧ для приема выхода старшей части произведения умножителя; первый логический элемент ИЛИ, связанный с первым регистром ББЧ для получения старшего выхода регистра ББЧ и для генерирования сигнала переноса потока су, который активизируется, когда сигнал любого бита с выхода регистра ББЧ является активным,на первый вход умножителя указанного блока больших чисел поступает первый сигнал данных у; на второй вход умножителя указанного блока больших чисел поступает второй сигнал данных х,первую схему дополнения, связанную с первым входом сумматора указанного блока больших чисел для дополнения третьего сигнала данных z, когда сигнал вычитания активен; вторую схему дополнения, связанную с младшим выходом регистра ББЧ указанного блока больших чисел, для дополнения указанного младшего выхода регистра ББЧ, когда указанный сигнал вычитания активен, указанная вторая схема дополнения генерирует четвертый сигнал данных а. 27. Арифметическое устройство для работы с целыми числами с многократно увеличенной точностью для обработки первого сигнала данных у со вторым сигналом данных х, включающее блок больших чисел (ББЧ), имеющий умножитель с первым входом умножителя,вторым входом умножителя, выходом старшей части произведения и выходом младшей части произведения; сумматор с первым входом сумматора,вторым входом сумматора, третьим входом сумматора, четвертым входом сумматора и выходом сумматора, причем указанный третий вход сумматора соединен с умножителем для приема сигнала выхода младшей части произведения; и регистр ББЧ со входом регистра ББЧ и выходом регистра ББЧ, указанный вход регистра ББЧ связан с сумматором для приема выхода сумматора, указанный регистр ББЧ фиксирует значение выхода сумматора до поступления синхронизирующего импульса и передает это значение на указанный выход регистра ББЧ после поступления синхронизирующего импульса,указанный выход регистра ББЧ разделяют на старший выход регистра ББЧ и младший выход регистра ББЧ, указанный старший выход регистра ББЧ содержит два верхних бита указанного выхода регистра ББЧ, указанный младший выход регистра ББЧ содержит все биты указанного выхода регистра ББЧ, кроме тех, которые находятся в указанном старшем выходе регистра ББЧ, указанный старший выход регистра ББЧ 41 связан с четвертым входом сумматора, указанный регистр ББЧ такжеимеет вход сброса регистра ББЧ для сброса указанного выхода регистра ББЧ до нуля при поступлении на указанный вход сигнала сброса регистра ББЧ; логический элемент ИЛИ, связанный с регистром ББЧ, для получения старшего выходного сигнала регистра ББЧ и для генерирования сигнала переноса потока су, причем указанный сигнал переноса потока су, активизируется при поступлении любого бита, когда старший выход регистра ББЧ является активным; первый сигнал данных у, который поступает на первый вход умножителя указанного блока больших чисел; второй сигнал данных, х, связанный со вторым входом умножителя блока больших чисел; первую схему дополнения, связанную с первым входом сумматора указанного блока больших чисел для дополнения третьего сигнала данных z, когда сигнал вычитания активен; вторую схему дополнения, связанную с младшим выходом регистра ББЧ указанного блока больших чисел ББЧ 0 для дополнения указанного младшего выхода регистра ББЧ, когда указанный сигнал вычитания активен, причем указанная вторая схема дополнения генерирует четвертый сигнал данных а; 42 регистр-фиксатор с входом регистрафиксатора и выходом регистра-фиксатора, причем вход указанного регистра-фиксатора связан с выходом старшей части произведения указанного блока больших чисел, а вход указанного регистра-фиксатора связан со вторым входом сумматора указанного блока больших чисел для фиксирования значения старшей части произведения до поступления синхронизирующего импульса и для подачи значения старшей части произведения на второй вход сумматора указанного блока больших чисел после поступления синхронизирующего импульса; указанный регистр-фиксатор, имеющий вход сигнала сброса регистра-фиксатора, и каждый блок больших чисел, имеющий вход сброса регистра ББЧ, причем вход сброса регистра ББЧ и указанный сигнал сброса регистра-фиксатора связаны вместе для формирования сигнала сброса данных сlr; и указанный регистр-фиксатор, имеющий вход синхронизации, и каждый блок больших чисел, имеющий вход синхронизации, которые соединены вместе для формирования синхронизирующего сигнала clk.