Спосіб піднесення до квадрата цілих чисел

Реферат: Спосіб піднесення до квадрата цілих чисел включає виконання піднесення до квадрата цілого числа, за допомогою використання послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" у двох каналах згідно з алгоритмом піднесення до квадрата цілого числа. В якому додатково включено тимчасові змінні, які зберігаються у відповідних пристроях циклів "РЕЄСТР ЗСУВУ", та виконання над ними послідовної дії пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ" з виключенням повторень. UA 118065 U (12) UA 118065 U UA 118065 U 5 10 Запропонована корисна модель належить до автоматики й обчислювальної техніки і може бути використана в системах криптографічного захисту інформації для розширення їх можливостей. Відомий спосіб піднесення до квадрата двох цілих чисел, який використовує послідовну дію пристроїв "МНОЖЕННЯ" згідно з алгоритмом множення в стовпчик [1]. Піднесення до квадрата є окремим випадком множення, при якому обидва множники однакові. Він може бути використаний для піднесення до квадрата двох чисел довільного розміру. На вхід двох пристроїв "МНОЖЕННЯ" подаються два машинних слова: а=(аn, …, аi, …, а1, а0) тa b=(bn, …, bj, …, b1, b0), де аі і bj - машинні слова чисел а і b, n - кількість машинних слів, необхідних для представлення числа ( log w a ), w - розмір машинного слова в бітах. Далі у першому пристрої 2 "МНОЖЕННЯ" частина машинних слів аі ( I  0, n ) послідовно, рядками, перемножується на всі 15 20 25 частини другого множника bj ( j  1, n ). Проміжний результат множення aі і bj формується з урахуванням всіх переносів. Кожен проміжний результат зміщується вліво на w-біт в пристрої "РЕЄСТР ЗСУВУ", а потім всі проміжні результати послідовно додаються в пристрої "ДОДАВАННЯ". На фіг. 1 зображене множення двох чисел у стовпчик, для n=3. Недоліком цього способу є те, що множення двох цілих чисел, що базується на основі множення в стовпчик, вимагає великої кількості операцій множення в стовпчик, що виконуються за допомогою послідовної дії пристроїв "МНОЖЕННЯ", тому при множеннi великих чисел він буде повільним у часі. Найближчим аналогом до запропонованої корисної моделі вибрано спосіб множення цілих чисел Comba [2], який ґрунтується на виконанні процедури множення в стовпчик, за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТРА ЗСУВУ" та "ДОДАВАННЯ". На вхід пристроїв "МНОЖЕННЯ" подаються два числа а і b, які наведені як набір машинних слів а=(аn, …, аi, …, а1, а0) та b=(bn, …, bj, …, b1, b0), де n - кількість машинних слів, необхідних для представлення числа ( log w a ), w - розмір машинного слова в бітах. На виході пристрою 2 "МНОЖЕННЯ" отримується результат с=аb розміром 2n машинних слів. Даний спосіб реалізує алгоритм множення в стовпчик з невеликою різницею: перемножується частина множника а i 30 ( I  0, n ) на всі частини іншого множника bj ( j  1, n ), в порядку виконання умови (І+j=k) у стовпчиках, а не послідовно по рядках. Основу "МНОЖЕННЯ" складають два канали пристроїв "МНОЖЕННЯ", "РЕЄСТРА ЗСУВУ" та "ДОДАВАННЯ", які реалізують два цикли формування   результату множення. Перший пристрій формує результат в інтервалі k  1, n   реалізацію вкладеного циклу множення в інтервалах I  0, k     та містить тa j  k,0 . Другий пристрій   формує результат в інтервалі k  n2, n  1 з використанням допоміжного інтервалу l  1, n  1 та 35 40 45 50 55     містить реалізацію вкладеного циклу множення в інтервалах i  l, n та j  k  l, n  l . У вкладених пристроях за допомогою пристрою "ДОБУТКУ" обчислюється добуток (2w) (w) (w) (uv) =aі bі , результатом якого є 2w-розрядне ціле число, яке потім розділяється на два w(w) (w) розрядних u і v числа. Накопичення суми відбувається в пристроях "ДОДАВАННЯ" та "РЕЄСТРІ ЗСУВУ" w-розрядних тимчасових змінних r0, r1 і r2 на кожній ітерації: (w) (w) (w) r0 ← r0 + v , (w) (w) (w) r1 ← r1 + u + carry, carry ← 0, (w) (w) r2 ← r2 + carry, carry ← 0. Присвоєння кінцевого результату, а також зміна акумуляторів суми r0, r1 і r2 відбувається в пристрої "ДОДАВАННЯ" на кожній ітерації циклу формування результату: (w) (w) c k ← r0 , (w) (w) r0 ← r1 , (w) (w) r1 ← r2 (w) r2 ← 0. Після завершення циклів формування результату в пристрої "ДОДАВАННЯ" відбувається (w) (w) обчислення c 2n-1 ← r0 . На виході пристрою "МНОЖЕННЯ" формується ціле число с=(с2n-1,…, ck, …, с1, с0). На фіг. 2 зображене множення двох чисел способом Comba, для n=3. Недоліками даного способу є те, що множення цілих чисел вимагає великої кількості операцій в пристроях "МНОЖЕННЯ" й "ДОДАВАННЯ" з накопиченням суми з переносом в wбітних тимчасових змінних r0, r1 i r2 в пристрої "РЕЄСТР ЗСУВУ"; його висока внутрішня зв'язність з урахуванням переносів між r0, r1 i r2, що не дозволяє виконувати спарювання таких операцій на сучасних суперскалярних процесорах. 1 UA 118065 U 5 10 15 20 25 30 В основу корисної моделі поставлена задача створення способу піднесення до квадрата цілих чисел, який дозволить виконувати меншу кількість операцій, що забезпечує зменшення часу на отримання результату обчислення за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТРА ЗСУВУ" та "ДОДАВАННЯ" цілих чисел, згідно з алгоритмом піднесення до квадрата цілих чисел з використанням відкладеного переносу. Технічний результат, що досягається при здійсненні корисної моделі полягає в отриманні можливості зниження обчислювальної складності та зменшення часу на отримання результату піднесення до квадрата цілих чисел завдяки позбуття необхідності враховувати перенос після кожної арифметичної операції за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТРУ ЗСУВУ" та "ДОДАВАННЯ" цілих чисел, згідно з алгоритмом множення цілих чисел. Суть запропонованого способу піднесення до квадрата цілих чисел полягає в виконанні процедури множення, за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТРУ ЗСУВУ" та "ДОДАВАННЯ" згідно з алгоритмом піднесення до квадрата, який відповідно корисної моделі додатково включає тимчасові змінні, що зберігаються у відповідних пристроях "РЕЄСТРАХ ЗСУВУ", та виконанням над ними послідовної дії пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ". В пристроях "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" запропонована реалізація відкладеного переносу, яка дозволяє незалежно проводити складання результатів відповідних добутків у стовпчиках, що дає можливість накопичувати суми старших і молодших розрядів окремо. Після завершення накопичення суми на кожній ітерації циклу, для формування результату необхідно виконати корегування (врахувати перенос) за допомогою пристрою "ДОДАВАННЯ": r1=r1+Hi(r0); r2=r2+Нi(r1); і сформувати результат ci=low(r0). На фіг. 1 наведено множення двох чисел в стовпчик, для n=3. На фіг. 2 наведено множення двох чисел способом Comba, для n=3. На фіг. 3 показана реалізація відкладеного переносу. На вхід пристрою "МНОЖЕННЯ" подається велике число а, яке представляється у вигляді машинних слів а=(аn, …, ai, …, а1, a0) розміром w-біт, n-кількість машинних слів необхідних для 2 представлення чисел а. На виході отримуємо результат с=а розміром 2n машинних слів. Основу вказаного способу піднесення до квадрата складають пристрої "МНОЖЕННЯ", "РЕЄСТРУ ЗСУВУ" та "ДОДАВАННЯ", які реалізують цикли формування результату множення.   Пристрої першого циклу формують результат в інтервалі k  0, n та містять вкладений цикл     множення в інтервалах i  0, k / 2 та j  k, k / 2 . Пристрої другого циклу формують результат в     інтервалі k  n,2n  1 з використанням допоміжного інтервалу l  1, n  1 та містять вкладений 35 40 45 50 55     цикл множення в інтервалах i  l, k / 2  l та j  k  l, k / 2  l . У вкладених пристроях за (2w) (w) (w) допомогою пристрою "МНОЖЕННЯ" обчислюється добуток (uv) =аi aj результатом якого є (w) (w) 2w-розрядне ціле число, яке потім розділяється на два w-розрядних u і v числа. Накопичення суми відкладеного переносу відбувається в пристрої "ДОДАВАННЯ" 2w-розрядних заздалегідь проініціалізованих тимчасових змінних r0, r1 на кожній ітерації. При цьому, при i