Рекурсивная модулярная арифметика

Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями $p_1,p_2,\ldots,p_n$ посредством сведения модульных операций по каждому рабочему основанию $p_j$, $i<=j<=n$ к модульным вычислениям по предшествующим рабочим основаниям $p_1,p_2,\ldots,p_{i-1}$, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю $p_j$ с вычислительными диапазонами по соответствующим комплексам базисных оснований. Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код). Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.

Принцип рекурсивных модулярных вычислений

Пример

Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа $p_1=2, p_2=3$. Очевидно, что вычетами по модулям 2 и 3 можно однозначно представить любой вычет по модулю 5. В то же время вычетами по модулям 2, 3 и 5, где вычеты по модулю 5 представимы по модулям 2 и 3, можно однозначно представить любой вычет по модулю 29. Вычетами по модулям 2, 3, 5 и 29 можно однозначно представить любой вычет по модулю 863. И так далее пока не получим нужный набор рабочих оснований: 2, 3, 5, 29, 863,… Данный пример наглядно иллюстрирует 4 факта:

1) Аппаратные и временные затраты на представление чисел по базовым модулям 2 и 3 примерно одинаковы (оба базисных модуля двухбитные);

2) Наблюдается более высокая степень распараллеливаемости;

3) Появляется регулярность (все вычисления проводятся по модулям 2 и 3);

4) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.