будемо ділити на 2, праве - множити на 2 і результати записувати в стовпчик під ними (якщо в результаті поділу виникає залишок, то його відкидають і записують цілу частину).
3. Операцію продовжуємо, поки зліва не залишиться 1.
4. Потім викреслимо ті рядки, в яких зліва стоять парні числа і складемо залишилися числа в правому стовпчику. Отримана сума і є шукане твір.
2. Феномен російського народного множення
Що це за феномен і чому він для нас настільки важливий?
Маніпуляції при роботі з лівим стовпцем таблиці, в якому здійснюється послідовний розподіл чисел на 2, реалізуються відразу кілька функцій:
. Розподіл здійснюється з фіксацією тільки цілої частини результату;
. Процес ділення зупиняється на етапі, коли чергове число (ділене) більше не ділиться без остачі на 2;
. «Викреслювання» рядків у всій таблиці, але за ознакою парності чисел лівого стовпця (ці рядки не потрібні для подальшого рахунку).
Подив викликає й інша деталь, а саме те, що виключення деяких доданків у правому стовпчику чисел ініційовані властивостями чисел іншого, лівого стовпця, які обчислювалися паралельно, але по зворотному алгоритмом.
Вражаючим є той факт, що залишилися в правому стовпчику числа після видалення зайвих чисел і додавання залишилися - дають в результаті правильне множення. Іншими словами, існує невідома нам закономірність (властивість чисел), якій підпорядковані всі числа і на яку спирається цей дивовижний російський спосіб множення.
За логікою речей тут відбувається наступне: не всі числа (після їх додавання) дають правильний результат. Є якісь зайві доданки. І ці зайві доданки виявляються властивістю « парності » з паралельно розрахованого (абсолютно за іншою формулою) лівого стовпця.
Як ми бачимо, той спосіб множення дуже корисний при обчисленні величезних чисел. Саме ця якість так необхідно в алгоритмі RSA шифруванні, адже в основу криптографічного системи з відкритим ключем RSA покладена складність завдання факторизації твори двох великих простих чисел. Для шифрування використовується операція зведення в ступінь по модулю великого числа.
Алгоритм RSA був розроблений в 1978 році Роном Рівестом, Аді Шамір і Леонардом Ейдельманом. Власне і назва алгоритму є абревіатура прізвищ розробників. Вони скористалися тим фактом, що знаходження великих простих чисел в обчислювальному відношенні здійснюється легко, але розкладання на множники добутку двох таких чисел практично нездійсненно.
В криптографічного системі з відкритим ключем кожен учасник має в своєму розпорядженні як відкритим ключем (англ. public key), так і закритим ключем (англ. private key). У криптографічного системі RSA кожен ключ складається з пари цілих чисел. Кожен учасник створює свій відкритий і закритий ключ самостійно. Закритий ключ кожен з них тримає в секреті, а відкриті ключі можна повідомляти кому завгодно або навіть публікувати їх. Відкритий і закритий ключі кожного учасника обміну повідомленнями в криптосистеме RSA утворюють «узгоджену пару», в тому сенсі, що вони є взаємно зворотними.
Залежно від структури використовуваних ключів методи шифрування поділяються на:...
