Алгоритм умножения

 

СОДЕРЖАНИЕ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

 Моя исследовательская  работа посвящена арифметическому  действию русское народное умножение, у которого обнаружился целый ряд интересных исторических моментов.

Начну издалека:  рассмотрим простую таблицу умножения, которая  знакома каждому еще со школьной скамьи. Таблица умножения, она же таблица Пифагора (Рис. 1.1) — таблица, где строки и столбцы озаглавлены множителями, а в ячейках таблицы находится их произведение.

 

Знаменитая таблица  умножения Пифагора бесспорно названа величайшим в истории человечества интеллектуальным продуктом «ноу-хау». Помимо широко известного применения классической таблицы умножения для выработки практических навыков умножения натуральных чисел, её можно использовать в некоторых математических доказательствах, например, при выводе формулы суммы кубов натуральных чисел или получения подобного выражения для суммы квадратов.

Однако не только великий Пифагор думал и учил окружающих тому, что способов действия с числами – бесконечное множество.

Очень далеко от Греческого города Кротона, где творил Пифагор, а также много лет спустя, причём, вряд ли под непосредственным влиянием Пифагора, в России, были, оказывается творческие личности, которые не были связаны догматами о законченности арифметики. И, вот отличный пример того, как русские люди в очередной раз изобрели «пифагоровский» велосипед. К сожалению, точно неизвестно когда и кем конкретно было открыто сие, на мой взгляд, не менее великое изобретение.

Прежде всего, это –  не Пифагоров способ умножения. Это  – иной способ умножения,  истинное происхождение которого пока не установлено. Здесь нет знаменитой таблицы умножения, но есть манипуляции, которые приводят к нужному результату.

И это – главный  момент в проблеме новой науки  – числонавтики, где именно открытие новых манипуляций с цифрами  и числами открывает действительно  необычные пути к познанию их тайн. Этот способ умножение получил название  русский народный счет или как  еще его называют: русский «крестьянский» способ умножения.

Целью моей работы является изучение и открытие новых возможностей в написании программ используя очень интересный способ умножения - метод русского народного умножения.

 Но почему же  для нас так важен этот малоизвестный  способ умножения, изобретенный  давным-давно? Где его применяют  сейчас? Об этом я напишу далее. А сейчас рассмотрим алгоритм работы русского народного умножения.

 

 

 

 

1 АЛГОРИТМ УМНОЖЕНИЯ

 

 

Рассмотрим принцип действия этого способа:

Перемножим два числа: 987 и 1998.

1. Одно запишем слева, другое – справа в строке (Рисунок2).

2. Левое число будем делить на 2, правое – умножать на 2 и результаты записывать в столбик под ними (если в результате деления возникает остаток, то его отбрасывают и записывают целую часть).

3. Операцию продолжаем, пока слева не останется 1.

4. Затем вычеркнем те строчки, в которых слева стоят четные числа и сложим оставшиеся числа в правом столбце. Полученная сумма и есть искомое произведение.

 

 

2 ФЕНОМЕН РУССКОГО НАРОДНОГО УМНОЖЕНИЯ

 

 

Что это за феномен  и почему он для нас столь важен?

Манипуляции при работе с левым  столбцом таблицы, в котором осуществляется последовательное деление чисел  на 2, реализуются сразу несколько  функций:

1. Деление осуществляется с фиксацией только целой части результата;

2. Процесс деления останавливается на этапе, когда очередное число (делимое) больше не делится нацело на 2;

3. «Вычеркивание»  строк во всей таблице, но по признаку четности чисел левого столбца (эти строки не нужны для дальнейшего счета).

Удивление вызывает и другая деталь, а именно то, что исключения некоторых слагаемых в правом столбце чисел ИНИЦИИРОВАНЫ свойствами чисел другого, ЛЕВОГО столбца, которые вычислялись ПАРАЛЛЕЛЬНО, но по обратному алгоритму.

Поразительным является тот  факт, что оставшиеся в правом столбце  числа после удаления лишних чисел  и сложения оставшихся – дают в  результате правильное умножение. Иными  словами, существует неведомая нам  закономерность (свойство чисел), которой подчинены все числа и на которую опирается этот удивительный русский способ умножения.

По логике вещей здесь  происходит следующее: не все числа (после их сложения) дают правильный результат. Есть некие лишние слагаемые. И эти лишние слагаемые обнаруживаются свойством «четности» из параллельно рассчитанного (совершенно по другой формуле) левого столбца.

Как мы видим, тот способ умножения очень полезен при вычислении огромных чисел. Именно это качество так необходимо в алгоритме  RSA шифровании, ведь в основу криптографической системы с открытым ключем RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа.

Алгоритм RSA был разработан в 1978 году Роном Ривестом, Ади Шамиром и Леонардом Эйдельманом. Собственно и название алгоритма есть аббревиатура фамилий разработчиков. Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо.

В криптографической системе с  открытым ключом каждый участник располагает  как открытым ключом (англ. public key), так и закрытым ключом (англ.private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными.

В зависимости от структуры  используемых ключей методы шифрования подразделяются на:

1) симметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации — ключа, одинакового для отправителя и получателя сообщения; Примеры: DES, 3DES, AES, Blowfish, Twofish, ГОСТ 28147-89;

2) асимметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, и, возможно открытый ключ, но неизвестен закрытый ключ, известный только получателю. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), а так же SSH, PGP, S/MIME и т. д. Российский стандарт, использующий асимметричное шифрование - ГОСТ Р 34.10-2001.

На данный момент асимметричное  шифрование на основе открытого ключа RSA (расшифровывается, как Rivest, Shamir and Aldeman - создатели алгоритма) использует большинство  продуктов на рынке информационной безопасности.

Его криптостойкость основывается на сложности разложения на множители больших чисел, а именно - на исключительной трудности задачи определить секретный ключ на основании открытого, так как для этого потребуется решить задачу о существовании делителей целого числа. Наиболее криптостойкие системы используют 1024-битовые и большие числа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. АЛГОРИТМ RSA ШИФРОВАНИЯ

 

 

1. Выбирают взаимно простые числа p и q.

2. По ним вычисляют

 

;

 

n – это первая часть ключа.  

3. Определяют – функцию Эйлера от аргумента n, т.е. количество  чисел, взаимно простых с n и меньших n. Легко видеть, что в данном случае

 

  .

 

4. Выбирают число e – взаимно простое с , e – вторая часть открытого ключа.

 Открытый ключ – пара чисел (n, e).

5. Вычисляют число d такое, что

 

,

 

 где k – целое число.

Число d – секретная часть ключа.

6. Шифрование осуществляется по схеме:

 

.

 

7. Дешифрование выполняется по схеме (рис. 3.1 ):

 

.

 

Простые делители p и q можно либо уничтожить, либо сохранить вместе с секретным ключом.

Если бы существовали эффективные  методы разложения на сомножители, то, разложив n на множители p и q, можно было бы получить секретный  ключ d.

Таким образом, надёжность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения  n на сомножители, так как в настоящее время эффективного способа поиска сомножителей не существует.

В рассмотренном примере все входящие числа невелики. На практике числа p и q могут содержать порядка 50 – 100 значащих цифр в десятичной записи. Следовательно, при реализации метода RSA необходимо привлекать средства «длинной арифметики».

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления дешифрования, например:

 

 

представляет  основную вычислительную сложность.

Эта задача может быть разрешена  с помощью алгоритма быстрого возведения в степень или автоматов, но мы рассматриваем другой, не менее интересный, способ вычисления больших чисел с помощью русского народного счета.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 ПРЕДСТАВЛЕНИЕ ДЛИННЫХ ЧИСЕЛ

 

 

Для большинства приложений предоставляемых процессором базовых  типов вполне хватает. Однако встречается  много задач, исходные данные которых слишком велики (например, алгоритм RSA). Число из 1000 цифр не поместится ни в один регистр. Поэтому компьютерное представление таких чисел и операции над ними приходится реализовывать самостоятельно. При этом время выполнения внешнего алгоритма, использующего такие числа, очень сильно зависит от эффективности их реализации.

Один из вариантов  хранения длинных чисел можно  реализовать в виде массива целых  чисел, где каждый элемент — это  одна цифра числа в b-й системе счисления.

Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).

Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.

Неотрицательное целое  число N длины n так же можно представить в виде:

 

,

 

где Base – основание системы счисления,  все коэффициенты .

Например, число 12345₁₀  в этой интерпретации будет имеет вид:

 

.

 

Длинное число хранится в массиве, где i-й элемент соответствует  коэффициенту числа при Baseⁱ. В качестве примера, рассмотрим массив для 12345₁₀: (5, 4, 3, 2, 1). Как видно, цифры хранятся в обратном порядке.  Основание системы счисления Base  зависит от максимального размера базового типа данных на компьютере и выбирается, исходя из следующих соображений:

1. Основание должно подходить под один из базовых типов данных.

2. Base должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных.

3. Для удобства можно выбрать Base как степень 10 (вывод информации, отладка ). Base – степень двойки позволяет проводить быстрые операции на низком уровне.

В своей программе  я использовала другой метод для  представления больших чисел. Записывала числа типом string:

 

public void long_addition(string first_summand, string second_summand, ref string sum)

        {

            int dop = 0;

            sum = "";

            reverse(first_summand, ref first_summand);

            reverse(second_summand, ref second_summand);

            if (first_summand.Length > second_summand.Length)

            {

                second_summand = add_0(first_summand, second_summand);

            }

            else

            {

                first_summand = add_0(second_summand, first_summand);