Xreferat.com » Рефераты по математике » Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Размещено на /


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Ефективний шлях багаторазового зведення за модулем – використання методу Монтгомері, який було запропоновано в 1985 році. Цей метод особливо ефективний при апаратній реалізації алгоритмів. Дуже зручно відмовитися від операцій множення і ділення та замінити їх операціями додавання. Метод полягає в наступному.

Нехай Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень – непарне число, потрібно помножити лишки.

Розглянемо алгоритм: R = 0;


for i = 0 until i < n do begin

if ai = 1 then R = R + B;

if R - непарне then R = R + N;

R = R / 2;

end

if R і N then R = R - N.


Суть даного алгоритму в тому, що в силу рівності


A = Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


множення числа В на число А зводиться до обчислення


AB = Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

зведення модуль многочлен множення

Воно виконується за Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень кроків, на кожному з яких здійснюється додавання до поточного значення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень значення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень з наступним діленням на Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Завдяки цьому діленню отримані значення завжди знаходяться в інтервалі Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. У результаті роботи даного алгоритму виходить число Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Тепер для одержання числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень необхідно застосувати ще один раз даний алгоритм до чисел Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень і Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Оскільки число Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень обчислюється за допомогою зрушень і відрахувань зі складністю Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень двійкових операцій (його можна обчислити заздалегідь і зберігати отримане значення), а алгоритм також виконується за Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень операцій, тo загальна трудомісткість обчислення добутку оцінюється величиною Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень двійкових операцій.

Наприклад:


А = 1ґ20 + 0ґ21 + 1ґ22 + 0ґ23 + 1ґ24 = 1 + 4 + 16 = 21 (10101) У = 18 N = 41


Зрозуміло, що АВ(mod N) = 21ґ18 (mod 41) = 9.

Обчислимо добуток цих чисел за допомогою вищезазначеного алгоритму.


R = 0 a0 = 1 R = R + B = 0 + 18 = 18;

R - парне;

R = R / 2 = 9.

a1 = 0;

R - непарне;

R = R + N = 9 + 41 = 50;

R = R / 2 = 25;

a2 = 1 R = R + B = 25 + 18 = 43;

R – непарне;

R = R + N = 43 + 41 = 84;

R = R / 2 = 42;

a3 = 0; R – непарне; R = R + N = 1 + 41 = 42;

R = R / 2 = 21;

a4 = 1 R = R + B = 21 + 18 = 39;

R - непарне;

R = R + N = 39 + 41 = 80;

R = R / 2 = 40.


Це ми одержали 2-n AB(mod N)

Тепер ми повинні ще раз скористатися цим алгоритмом для обчислення АВ (mod N).


A’ = 22n (mod N) = 22 ґ5(mod N) = 1024(mod 41) = 40 = 0ґ20 + 0ґ21 + 0ґ22 + 1ґ23 + 0ґ24 + 1ґ25

B ’= 40;

N = 41.

R = 0 a0 = 0 R - парне;

R = R / 2 = 0.

a1 = 0; R - парне;

R = R / 2 = 0;

a2 = 0 R - парне;

R = R / 2 = 0;

a3 = 1; R = R + B = 0 + 40 = 40;

R - парне;

R = R / 2 = 20;

a4 = 0; R - парне;

R = R / 2 = 10;

6. a5 = 1; R = R + B = 10 + 40 = 50;

R = R - N = 50 - 41 = 9.

Звертання

Для заданого числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, знаходимо за допомогою розширеного алгоритму Евкліда числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень і Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, що задовольняють рівності Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Якщо Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, тo як зворотний можна взяти Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Таким чином, звертання в кільці лишків можна виконати за Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень бітових операцій.

Ділення

Оскільки Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, то ділення у кільці лишків виконується зі складністю Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Обчислення з многочленами

Між обчисленнями в кільці многочленів над довільним кільцем Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень і в кільці цілих чисел, записаних у будь-якої системи числення багато спільного. Вони виконуються за схожими формулами, а різниця лише в тому, що для чисел необхідно враховувати знаки переносу від молодших розрядів до старших, у той час як у випадку многочленів ніяких переносів при операціях з коефіцієнтами не виникає – і вихідні величини і значення лежать у кільці Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Складність операцій з многочленами, звичайно, оцінюють кількістю ариф-метичних операцій кільця Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, які виконуються над його коефіцієнтами. Якщо відомо бітову складність операцій у полі, то можна оцінити результуючу бітову складність операцій з многочленами. Щоб відрізняти арифметичну складність від бітової в оцінках ми використовуватимемо символи Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень і Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Обчислення значень многочленів.

Нехай Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень – довільне кільце. Розглянемо добре відомий алгоритм Руфіні - Горнера для обчислення значень многочлена над кільцем Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень у точціВикористання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Останнє число Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, і буде шуканим значенням многочлена. Арифметична складність алгоритму, мабуть, дорівнює Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Бітову складність у випадку, коли кільце Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень розглядається як кільце цілих чисел, можна оцінити виразом Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, де через Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень позначений максимум із двох чисел: числа двійкових знаків у запису найбільшого з коефіцієнтів і числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень , а число Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень означає число двійкових знаків у запису найбільшого з чисел Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень . У такий спосіб виходить оцінка Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Алгоритм Руфіні-Горнера дозволяє отримати не тільки значення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень. Як показує наступна теорема, величини Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень є в точності коефіцієнтами многочлена, що є лишком від ділення многочлена Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень на Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Теорема 1

Справедлива рівність


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


Доведення

Маємо


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


Методи множення

Для зручності ми думатимемо, що ми оперуємо із цілими числами, вираженими у двійковій системі числення. У нас є два Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень-розрядних числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень і Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, то можна записати


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


де Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень – Інайбільш значуща половинаІ числа Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, а Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень – Інайменш значуща половинаІ; подібним же чином Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Ця формула зводить задачу множення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень- розрядних чисел до трьох операцій множення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень розрядних чисел: Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень плюс деякі прості операції зсуву і додавання. Цю формулу можна використовувати для множення з подвійною точністю, коли результат потрібно отримати із четверною точністю. За допомогою цієї формули можна визначити деякий рекурсивний процес для множення, значно більш швидкий, ніж уже знайомий нам метод, коли Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень– велике та час виконання порядку Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень.

Якщо Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень– час, необхідне для виконання множення Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень-розрядних чисел, то ми маємо

Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень для деякої константи Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, оскільки в правій частині співвідношення потрібно виконати тільки три операції множення плюс деякі операції додавання і зрушення. З останнього співвідношення за індукцією випливає, що


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень,

якщо вибрати Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень– достатньо великим, для того, щоб ця нерівність виконувалася при Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, отримаємо


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


Тобто час, затрачуваний на множення, можна скоротити з величини порядку Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень до величини порядку Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень, і, звичайно, при великому Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень цей алгоритм набагато швидше.

Схожий, але більш складний метод виконання множення із часом порядку Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень був уперше запропонований А. Карацубою.

Час виконання можна скоротити ще більше, якщо помітити, що тільки що розглянутий метод є окремим випадком (при Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень) більш загального методу, що дає


Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень


для будь-якого фіксованого Використання модульної арифметики. Обчислення з многочленами.
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: