ачення округленно приватного. Для цього спочатку визначається. Знайдене таким чином значення далі використовується в рекурсивних співвідношеннях
і (2.19)
для отримання, і так далі.
Ця повторювана процедура продовжується до тих пір, поки або.
Якщо це виникає на r-му повторенні, то
(2.20)
Так як є або модулем або твором модулів СОК, то знаходження величини являє собою розподіл на модуль або твір модулів СОК [9].
Розглянемо приклад.
Приклад. Нехай модулі СОК і - діапазон. Розділимо на і знайдемо округлене приватне.
Уявімо у вигляді (2.16) в ОПСС в порядку зменшує значущість:
,
де Тоді приблизний дільник з урахуванням (2.17) і (2.18) буде дорівнює.
Знайдемо і виконаємо дії з урахуванням рекурсивних співвідношень (2.19)
З (2.20) так як,, то. Тоді округлене приватне буде Дійсно
2.3 Програмна реалізація і аналіз методу Ферма в системі комп'ютерної алгебри Maple
Реалізувати метод Ферма ділення довільних чисел в СОК можна, виконавши послідовно описані в підрозділі 2.2 дії, які й будуть основними кроками алгоритму відповідної програми:
) введення діленого і дільника представлених в десяткового позиційній системі числення;
) вибір відповідної системи підстав;
) переклад дільника в систему залишкових класів;
) переклад дільника до узагальненої позиційну систему числення;
) визначення наближеного дільника;
) знаходження частки від розподілу на наближений дільник методом Ферма.
Складемо таблицю залежності числа ітерацій, необхідних для знаходження приватного методом Ферма, від розрядності діленого і дільника, використовуючи розроблену програму:
Таблиця 2.5
ДелімоеДелітель 8152128354148 161014182227 1159121619 111691317 1111469 11111712 1111116
У таблиці 2.5 ділене і дільник представлені ступенями числа. Число розташоване на перетині діленого і дільника означає число ітерацій, необхідних для знаходження округленого приватного методом Ферма.
За даними таблиці 2.5 можна зробити висновок, що зі збільшенням розриву між діленим і дільником (за умови, що ділене більше дільника), кількість ітерацій зростає. Тобто число ітерацій буде нескінченно зростати при збільшенні розриву між діленим і дільником.
Висновки по другому розділу
У даному розділі були розглянуті основні види ділення чисел в системі залишкових класів: поділ без залишку, ділення на твір модулів СОК, ділення на число взаімнопростое з модулями СОК; наведені способи реалізації. Було відзначено, що поділ довільних цілих чисел тільки даними способами пов'язано з великими складнощами, і розглянуто альтернативний алгоритм знаходження округленого приватного довільних чисел на основі методу Ферма. Був проведений обчислювальний експеримент, аналіз результатів якого виявив істотний недолік даного методу, що полягає в тому, що в деяких випадках для обчислення округленого приватного може знадобитися багато ітерацій; це відбувається в тих випадках, коли ділене - велике число, дільник - відносно мале число. Причому число ітерацій буде нескінченно зростати при збільшенні розриву між діленим і дільником.
ВИСНОВОК
У рамках даної випускної кваліфікаційної роботи були вирішені наступні завдання:
. Розглянуто способи подання та обробки цілих чисел у різних системах числення.
. Розглянуто деякі випадки ділення в системі залишкових класів: формальне поділ, поділ на твір модулів системи залишкових класів, масштабування.
. Досліджено метод поділу Ферма довільних чисел в системі залишкових класів.
. Реалізовано в системі комп'ютерної алгебри Maple та проаналізовано метод поділу Ферма довільних чисел в системі залишкових класів.
СПИСОК ЛІТЕРАТУРИ
maple позиційний числення поділ
1. Акрітас А. Основи комп'ютерної алгебри з додатками.- М .: Світ, 1994. 544 с.
. Акушський І.Я., Юдицький Д.М. Машинна арифметика в залишкових класах.- М .: Сов. радіо, 1968. 440 с.
. Виноградов І.М. Основи теорії чисел.- М .: Наука, 1972. 168 с.
. Каган Б.М., Канівський М.М. Цифрові обчислювальні машини і системи.- М .: Енергія, 1973.
. Копиткове Л.Б. Математичні моделі нейромережевої реалізації модулярних обчислювальних структур для високошвидкісної цифрової фільтрації: дисертація.- Ставрополь: СГУ, 2001, 264 с.
. Лобесил М.В. Розробка методів і алгоритмів модулярних обчис...
