ЭЛЕКТРОННОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ЗАМАСКИРОВАННЫХ АРИФМЕТИЧЕСКИХ ДЕЙСТВИЙ

1. Электронное вычислительное устройство (100) для выполнения замаскированной арифметики в коммутативном кольце (
), кольцо имеет конечное количество элементов кольца, сложение в кольце и умножение в кольце определены на элементах кольца, вычислительное устройство обрабатывает целочисленные списки (
), кодирующие элементы кольца (
), целочисленные списки содержат по меньшей мере два целых числа, причем целочисленный список (
) кодирует элемент кольца (
) таким образом, что элемент кольца равен линейной комбинации степеней (
;
;
) основного элемента кольца (
), основной элемент кольца имеет порядок (
) в кольце, причем степени имеют экспоненты, определенные посредством целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
),
вычислительное устройство содержит
запоминающее устройство (110), выполненное с возможностью хранить инкрементную таблицу (), определенную для инкрементного элемента кольца (1;),
инкрементная таблица отображает целочисленный список, представляющий входной элемент кольца (
) на выходной целочисленный список (
), кодирующий выходной элемент кольца (
), таким образом, что выходной элемент кольца равен инкрементному элементу кольца, добавленному посредством сложения в кольце к входному элементу кольца (
), выходной элемент кольца равен линейной комбинации степеней основного элемента кольца (
), причем степени имеют экспоненты, определенный посредством выходного целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
).
2. Вычислительное устройство по п. 1, в котором размер списка разрешенных разностей составляет менее чем 50% порядка, более предпочтительно менее чем 20% порядка, еще более предпочтительно менее чем 10% порядка, еще более предпочтительно менее чем 5% порядка.
3. Вычислительное устройство по любому из предыдущих пунктов, в котором основной элемент кольца имеет порядок, причем порядок (
), умноженный на размер списка разрешенных разностей минус один (
), разделенный на размер кольца минус один (
), меньше 2, более предпочтительно равен 1 (
.
4. Вычислительное устройство по п. 1 или 2, в котором основной элемент кольца имеет порядок, причем порядок (
), умноженный на размер списка разрешенных разностей минус один (
), разделенный на размер кольца минус один (
), больше или равен двум (
.
5. Вычислительное устройство по любому из предыдущих пунктов, в котором инкрементная таблица берет в качестве входных данных входные целочисленные списки (
), представляющие входной элемент кольца,
в котором
арифметическая разность между первым целым числом (
) из входных целочисленных списков (
) и вторым целым числом (
) из целочисленного списка содержится в списке разрешенных разностей, или
целое число (
) из входных целочисленных списков (
) содержится в списке разрешенных разностей.
6. Вычислительное устройство по любому из предыдущих пунктов, содержащее
блок (130) сложения в кольце, выполненный с возможностью
принимать первый входной для сложения целочисленный список (
), кодирующий первый входной для сложения элемент кольца, и второй входной для сложения целочисленный список (
), кодирующий второй входной для сложения элемента кольца,
определять выходной для сложения целочисленный список, кодирующий выходной для сложения элемент кольца, посредством применения инкрементной таблицы к элементам кольца, определенным из первого и второго входных для сложения целочисленных списков, выходной для сложения элемент кольца равен сложению в кольце первого входного для сложения элемента кольца и второго входного для сложения элемента кольца.
7. Вычислительное устройство по п. 6, в котором определение выходного для сложения целочисленного списка содержит
определение целочисленного списка промежуточного сложения (
), кодирующего элемент кольца промежуточного сложения, посредством первого применения инкрементной таблицы к элементу кольца (
), являющегося линейной комбинацией степеней одного или более основных элементов, причем степени определены из первого и второго входных для сложения целочисленных списков, (
),
определение выходного для сложения целочисленного списка, содержащее второе применение инкрементной таблицы к элементам кольца, определенным из целочисленного списка промежуточного сложения и определенным из второго входного для сложения целочисленного списка.
8. Вычислительное устройство по любому из предыдущих пунктов, содержащее
блок (140) умножения в кольце, выполненный с возможностью
принимать первый входной для умножения целочисленный список (
), кодирующий первый входной для умножения элемент кольца, и второй входной для умножения целочисленный список (
), кодирующий второй входной для умножения элемент кольца,
определять выходной для умножения целочисленный список, кодирующий выходной для умножения элемент кольца, посредством применения инкрементной таблицы к элементам кольца, определенным из первого и второго входных для умножения целочисленных списков, выходной для умножения элемент кольца равен умножению в кольце первого входного для умножения элемента кольца и второго входного для умножения элемента кольца.
9. Вычислительное устройство по любому из предыдущих пунктов, в котором
коммутативное кольцо представляет собой кольцо, сформированное целыми числами по модулю целого числа (
), и/или
коммутативное кольцо представляет собой кольцо, сформированное целочисленными полиномами по модулю целочисленного полинома (
).
10. Устройство (170) кодирования в кольце для кодирования элемента кольца коммутативного кольца () как целочисленного списка для использования с вычислительным устройством по п. 1, при этом устройство кодирования в кольце содержит
- запоминающее устройство (172), выполненное с возможностью хранить таблицу кодирования, определенную для основного элемента кольца (
), причем таблица кодирования отображает элемент кольца (
) на целочисленный список (
) таким образом, что элемент кольца равен линейной комбинации степеней основного элемента кольца (
), причем степени имеют экспоненты, определенные посредством целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
).
11. Устройство (160) декодирования в кольце для декодирования целочисленного списка (
) в элемент кольца (
) коммутативного кольца (
) для использования с вычислительным устройством по п. 1, причем устройство декодирования в кольце выполнено с возможностью определять для одного или более основных элементов кольца (
) элемент кольца (
) таким образом, что элемент кольца равен линейной комбинации степеней одного или более основных элементов кольца (
), причем степени имеют экспоненты, определенные посредством целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
).
12. Устройство (200) вычисления таблицы для вычисления инкрементной таблицы для использования в вычислительном устройстве для выполнения замаскированных арифметических действий в коммутативном кольце (
), кольцо имеет конечное количество элементов кольца, сложение в кольце и умножение в кольце определены на элементах кольца, вычислительное устройство обрабатывает целочисленные списки (
), кодирующие элементы кольца (
), целочисленные списки содержат по меньшей мере два целых числа, при этом устройство вычисления таблицы содержит
блок (210) создания таблицы, выполненный с возможностью строить инкрементную таблицу, причем блок создания таблицы выполнен с возможностью
многократно выбирать входной элемент кольца,
определять выходной элемент кольца, который равен инкрементному элементу кольца, добавленному с помощью сложения в кольце ко входному элементу кольца,
определять кодирование выходного целочисленного списка для выходного элемента кольца как линейную комбинацию степеней (
;
;
) основного элемента кольца (
), основной элемент кольца имеет порядок (
) в кольце, причем степени имеют экспоненты, определенные посредством выходного целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
),
добавлять запись в инкрементную таблицу, отображающую входной элемент кольца на выходной целочисленный список.
13. Электронное устройство конфигурации для конфигурации электронного вычислительного устройства (100) для выполнения замаскированных арифметических действий в коммутативном кольце () по п. 1,
обеспечивающее кольцо, имеющее конечное количество элементов кольца,
обеспечивающее основной элемент кольца
, имеющий порядок
,
определяющее такое отношение эквивалентности на
, что два элемента
и
эквивалентны, если и только если
в кольце для некоторого элемента
, отношение эквивалентности порождает классы эквивалентности на
,
определяющее список разрешенных разностей посредством выбора по меньшей мере одного элемента из каждого класса эквивалентности.
14. Способ электронных вычислений для выполнения замаскированных арифметических действий в коммутативном кольце (), причем кольцо имеет конечное количество элементов кольца, сложение в кольце и умножение в кольце определены на элементах кольца, при этом способ вычислений обрабатывает целочисленные списки (), кодирующие элементы кольца (), целочисленные списки содержат по меньшей мере два целых числа, причем целочисленный список () кодирует элемент кольца () таким образом, что элемент кольца равен линейной комбинации степеней (; ; ) основного элемента кольца (), основной элемент кольца имеет порядок () в кольце, причем степени имеют экспоненты, определенные посредством целочисленного списка, разность между первой экспонентой () и второй экспонентой () содержится в списке разрешенных разностей (), и причем размер списка разрешенных разностей меньше, чем порядок (), при этом способ вычислений содержит этапы, на которых
сохраняют инкрементную таблицу (
), заданную для инкрементного элемента кольца (1;
), причем инкрементная таблица отображает целочисленный список, представляющий входной элемент кольца (
) на выходной целочисленный список (
), кодирующий выходной элемент кольца (
), таким образом, что выходной элемент кольца равен инкрементному элементу кольца, добавленному посредством сложения в кольце к входному элементу кольца (
), выходной элемент кольца равен линейной комбинации степеней основного элемента кольца (
), причем степени имеют экспоненты, определенный посредством выходного целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
).
15. Способ электронных вычислений по п. 14, содержащий этапы, на которых
выполняют сложение в кольце, сложение в кольце содержит этапы, на которых
принимают первый входной для сложения целочисленный список (
), кодирующий первый входной для сложения элемент кольца, и второй входной для сложения целочисленный список (
), кодирующий второй входной для сложения элемент кольца,
определяют выходной для сложения целочисленный список, кодирующий выходной для сложения элемент кольца, посредством применения инкрементной таблицы к элементам кольца, определенным из первого и второго входных для сложения целочисленных списков, выходной для сложения элемент кольца равен сложению в кольце первого входного для сложения элемента кольца и второго входного для сложения элемента кольца,
16. Компьютерная программа, содержащая компьютерные программные инструкции, выполненные с возможностью выполнять способ по п. 14 или 15, когда компьютерная программа выполняется на программируемом устройстве.
17. Машиночитаемый носитель, содержащий
компьютерную программу по п. 16 и/или
инкрементную таблицу для выполнения замаскированных арифметических действий в коммутативном кольце (
), кольцо имеет конечное количество элементов кольца, сложение в кольце и умножение в кольце определены на элементах кольца, целочисленные списки (
), кодирующие элементы кольца (
), целочисленные списки содержат по меньшей мере два целых числа, причем целочисленный список (
) кодирует элемент кольца (
) таким образом, что элемент кольца равен линейной комбинации степеней (
;
;
) основного элемента кольца (
), основной элемент кольца имеет порядок (
) в кольце, причем степени имеют экспоненты, определенные посредством целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
), и причем размер списка разрешенных разностей меньше, чем порядок (
),
инкрементная таблица () задается для инкрементного элемента кольца (1;),
инкрементная таблица отображает целочисленный список, представляющий входной элемент кольца (
) на выходной целочисленный список (
), кодирующий выходной элемент кольца (
), таким образом, что выходной элемент кольца равен инкрементному элементу кольца, добавленному посредством сложения в кольце к входному элементу кольца (
), выходной элемент кольца равен линейной комбинации степеней основного элемента кольца (
), причем степени имеют экспоненты, определенный посредством выходного целочисленного списка, разность между первой экспонентой (
) и второй экспонентой (
) содержится в списке разрешенных разностей (
).