ЭЛЕКТРОННОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО, ВЫПОЛНЕННОЕ С ВОЗМОЖНОСТЬЮ ВЫЧИСЛЕНИЯ ПРОИЗВЕДЕНИЯ ЦЕЛЫХ ЧИСЕЛ

1. Электронное вычислительное устройство (100; 200), выполненное с возможностью вычисления произведения целых чисел, причем устройство содержит:
- хранилище (110), выполненное с возможностью хранения целых чисел (210, 220) в представлении многослойной системы остаточных классов (RNS), причем представление многослойной RNS имеет по меньшей мере RNS верхнего слоя и RNS нижнего слоя, причем RNS верхнего слоя является системой остаточных классов для последовательности нескольких верхних модулей (), причем RNS нижнего слоя является системой остаточных классов для последовательности нескольких нижних модулей (), причем целое число () представляется в хранилище посредством последовательности нескольких верхних вычетов (; 211, 221) по модулю последовательности верхних модулей (), причем верхние вычеты (; 210.2, 220.2) для по меньшей мере одного конкретного верхнего модуля () дополнительно представляются в хранилище посредством последовательности нескольких нижних вычетов (; 212, 222) верхнего вычета () по модулю последовательности нижних модулей (), при этом по меньшей мере один из нескольких нижних модулей () не делит модуль из нескольких верхних модулей (),
- схему (120) процессора выполненную с возможностью вычисления произведения первого целого числа (; 210) и второго целого числа (; 220), причем первое и второе целое число хранится в хранилище в соответствии с представлением многослойной RNS, причем процессор сконфигурирован c по меньшей мере нижней процедурой (131) умножения и верхней процедурой (132) умножения, причем
- нижняя процедура умножения вычисляет произведение двух дополнительно представленных верхних вычетов (), соответствующих одному и тому же верхнему модулю (), по модулю упомянутого верхнего модуля (),
- верхняя процедура умножения вычисляет произведение первого и второго целого числа посредством покомпонентного умножения верхних вычетов первого целого числа () и соответствующих верхних вычетов второго целого числа () по модулю соответствующего модуля (), при этом верхняя процедура умножения вызывает нижнюю процедуру умножения для умножения верхних вычетов, которые являются дополнительно представленными, при этом верхняя процедура умножения выполнена с возможностью приема верхних вычетов (), которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль (), и выполнена с возможностью создания верхних вычетов () произведения принятых верхних вычетов (), которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль ().
2. Вычислительное устройство по п. 1, в котором верхняя процедура умножения дополнительно выполнена с возможностью вычисления произведения первого () и второго () целого числа по модулю дополнительного модуля ().
3. Вычислительное устройство по п. 1 или 2, в котором коэффициент расширения составляет 2 или больше 2.
4. Вычислительное устройство по любому из предшествующих пунктов, в котором нижняя процедура умножения выполнена с возможностью вычисления арифметического произведения () двух дополнительно представленных верхних вычетов по модулю верхнего модуля () посредством покомпонентного умножения нижних вычетов первого верхнего вычета и соответствующих нижних вычетов второго верхнего вычета с последующим модульным сокращением по модулю соответствующего модуля ().
5. Вычислительное устройство по п. 4, в котором модульное сокращение содержит вычисление деления  с округлением в меньшую сторону арифметического произведения () и соответствующего модуля ().
6. Вычислительное устройство по любому из предшествующих пунктов, содержащее хранилище таблиц, при этом нижняя процедура умножения содержит поиск произведения нижних вычетов в поисковой таблице результатов модульного умножения, хранящейся в хранилище таблиц, и при этом поисковая таблица для нижних модулей по меньшей мере такая же большая, как наибольший нижний модуль.
7. Вычислительное устройство по любому из пп. 1-6, в котором дополнительно представленный верхний вычет () представляется в представлении () Монтгомери, причем представление () Монтгомери является упомянутым верхним вычетом (), умноженным на предварительно определенную константу () Монтгомери, по модулю соответствующего модуля (), причем нижняя процедура умножения выполнена с возможностью приема двух дополнительно представленных верхних вычетов в представлении Монтгомери в качестве двух последовательностей нижних вычетов, и выполнена с возможностью создания произведения в представлении Монтгомери.
8. Вычислительное устройство по п. 7, в котором нижняя процедура умножения выполнена с возможностью вычисления целого числа , удовлетворяющего , для некоторого , при этом , и вычисления .
9. Вычислительное устройство по п. 8, в котором RNS нижнего слоя является расширенной системой остаточных классов, при этом последовательность из нескольких нижних модулей () является последовательностью основания, а расширенная RNS имеет последовательность расширения из дополнительных нескольких нижних модулей (), причем константа () Монтгомери является произведением последовательности основания из нескольких нижних модулей, причем вычисление  выполняется для последовательности расширения с последующим расширением основания для последовательности основания.
10. Вычислительное устройство по п. 9, в котором сначала вычеты для  вычисляются в отношении дополнительных нескольких нижних модулей (), и впоследствии вычеты для  в отношении последовательности основания нижних модулей () вычисляются посредством расширения основания.
11. Вычислительное устройство по одному из предшествующих пунктов, в котором нижняя процедура умножения выполнена с возможностью вычисления модульной суммы-произведений () по модулю верхнего модуля () посредством сначала вычисления суммы произведений (; с ) путем покомпонентного умножения и сложения нижних вычетов, представляющих верхние вычеты () и () с последующим итоговым модульным сокращением по модулю соответствующего модуля ().
12. Вычислительное устройство по любому из предшествующих пунктов, в котором последовательность верхних модулей содержит избыточный модуль для расширения основания, причем избыточный модуль является произведением одного или более нижних модулей последовательности нескольких нижних модулей.
13. Вычислительное устройство по любому из предшествующих пунктов, в котором последовательность констант  определяется для модулей  по меньшей мере для верхнего слоя так, что вычет  представляется в качестве псевдо-вычета  так, что , при этом по меньшей мере один  отличается от .
14. Электронный способ вычисления (400) для вычисления произведения целых чисел, причем способ, содержащий этапы, на которых:
- сохраняют (410) целые числа (210, 220) в представлении многослойной системы остаточных классов (RNS), причем представление многослойной RNS имеет по меньшей мере RNS верхнего слоя и RNS нижнего слоя, причем RNS верхнего слоя является системой остаточных классов для последовательности нескольких верхних модулей (), причем RNS нижнего слоя является системой остаточных классов для последовательности нескольких нижних модулей (), причем целое число () представляется в хранилище посредством последовательности нескольких верхних вычетов (; 211, 221) по модулю последовательности верхних модулей (), причем верхние вычеты (; 210.2, 220.2) для по меньшей мере одного конкретного верхнего модуля () дополнительно представляются в хранилище посредством последовательности нескольких нижних вычетов (; 212, 222) верхнего вычета () по модулю последовательности нижних модулей (), при этом по меньшей мере один из нескольких нижних модулей () не делит модуль из нескольких верхних модулей (),
- вычисляют (420) произведение первого целого числа (; 210) и второго целого числа (; 220), причем первое и второе целое число хранится в хранилище в соответствии с представлением многослойной RNS, причем этап, на котором вычисляют, содержит по меньшей мере нижнюю часть (424) умножения и верхнюю часть (422) умножения, причем
- нижняя часть умножения вычисляет (424) произведение двух дополнительно представленных верхних вычетов (), соответствующих одному и тому же верхнему модулю (), по модулю упомянутого верхнего модуля (),
- верхняя часть умножения вычисляет (422) произведение первого и второго целого числа посредством покомпонентного умножения верхних вычетов первого целого числа () и соответствующих верхних вычетов второго целого числа () по модулю соответствующего модуля (), при этом верхняя процедура умножения вызывает нижнюю процедуру умножения для умножения верхних вычетов, которые являются дополнительно представленными, при этом верхняя часть умножения выполнена с возможностью приема верхних вычетов (), которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль (), и выполнена с возможностью создания верхних вычетов () произведения принятых верхних вычетов (), которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль ().
15. Машиночитаемый носитель (1000) информации, содержащий временные или не временные данные (1020), представляющие собой инструкции, чтобы предписывать процессорной системе выполнять способ по п. 14.