класів. Масштабування припускає операцію ділення, тому можна вибрати такий дільник, який дозволить здійснити легку реалізацію. Наприклад, у двійковій системі числення вибираються коефіцієнти масштабування, що є ступенями двійки. Масштабування в системі залишкових класів реалізується найбільш легко, коли коефіцієнт масштабування є один з модулів системи або є твором декількох модулів.
Масштабування припускає операцію ділення. Фундаментальною проблемою, що виникає при масштабуванні, є те, що на відміну від додавання і множення, система в залишкових класах не є замкнутою щодо операції масштабування.
Припустимо, що процедура масштабування здійснюється з округленням шляхом відкидання дробової частини. Нехай є вхідною величиною, - вихідний, а - коефіцієнт масштабування, тоді
(2.7)
Це можна переписати у вигляді
(2.8)
(2.9)
Однак, для швидкого визначення потрібно, щоб він таким був твором деяких модулів. Таким чином, алгоритм високошвидкісного масштабування повинен виводити коефіцієнт масштабування з одного або твори кількох модулів.
Якщо, тоді можна легко отримати безпосередньо з перших залишку; якщо при, то для визначення використовується ітеративний процес масштабування.
Розглянемо алгоритм масштабування числа на число з відкиданням залишку в припущенні, що або ціле позитивне число, попарно просте с, або ціле позитивне число, що представляє собою твір чисел, попарно простих с. Якщо ділиться на без залишку, то операція масштабування є модульною операцією і порівняно просто реалізується в табличному варіанті. Тому перед масштабуванням в якості допоміжної операції виконують операцію знаходження числа, яке ділиться на без залишку. Операція знаходження замінює операцію відкидання залишку від ділення.
Нехай, тоді
(2.10)
де
З (2.10) видно, що ділиться без залишку на.
На підставі того, що
(2.11)
де - ранг числа, - ортогональні базиси, - ціле позитивно число, яке задовольняє порівнянні
можна записати вирази для і:
(2.12)
(2.13)
де
Отже, алгоритм масштабування числа на число з відкиданням залишку можна представити як послідовність наступних операцій:
1. Визначення рангу числа, вираз (2.13).
2.Визначення, вираз (2.12).
.Вичісленіе, вираз (2.10).
.Нахожденіе масштабованого числа від ділення на.
При цьому перебування здійснюється за допомогою сукупності модульних операцій:
(2.14)
У випадку, якщо - просте число
(2.15)
Приклад. Нехай підстави системи,,,,
. Потрібно число промасштабіровать числом.
Згідно з виразом (2.13) в умовах конкретного прикладу знаходимо ранг числа. У відповідності з виразом (2.13) визначаємо а також Отже, вираз (2.13) в умовах прикладу має вигляд:
Далі знаходимо і потім залишок від ділення на величину за формулою (2.12):
За формулою (2.11) знаходимо
На основі формули (2.15) визначаємо і далі визначаємо за формулою (2.14):
тобто
Отримане Масштабированное число можна представити у скороченій, або в розширеній системі підстав.
Запропонований алгоритм масштабування відрізняється від відомих тим, що його реалізація повністю складається з модульних операцій [2].
2.2 Поділ довільних чисел в системі залишкових класів на основі методу Ферма
У попередньому підрозділі було показано як реалізується в СОК поділ без залишку, ділення на один або декілька модулів системи, розподіл на число взаімнопростое з модулями СОК.
Однак найбільший інтерес представляє випадок ділення, при якому на ділене і дільник не накладає ні яких обмежень, крім того, що вони цілі. До недавнього часу цей випадок поділу в СОК був важко реалізованим.
Далі ми розглянемо ефективний і простий у реалізації алгоритм ділення в СОК довільних чисел, метод Ферма.
Припустимо, що ділене і дільник є позитивними числами, і - модулі СОК.
Першим етапом цього алгоритму є вибір приблизного дільника. Для цього дільник представляється в узагальненій позиційній системі числення (ОПСС) у порядку зменшує значущість з підстав, які збігаються з модулями СОК, тобто у вигляді
(2.16)
Далі визначається приблизний дільник за формулою
(2.17)
де можна знайти шляхом використання найбільш значущою ненульовий цифри в ОПСС поданні дільника. Цю ненульову цифру замінюють найближчим модулем або твором модулів СОК так, щоб виконувалася умова
(2.18)
Другим етапом алгоритму є визн...
