Русское народное умножение

 

Содержание

Введение

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

. Феномен русского народного умножения

. Алгоритм RSA шифрования

. Представление длинных чисел

. Операции над длинными числами

.1 Сложение и вычитание

.2 Умножение

.3 Деление

. Проблемы в ходе выполнения курсовой работы

Выводы

Список литературы

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Феномен русского народного умножения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Алгоритм RSA шифрования

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

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

;

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

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

.

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

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

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

,

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

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

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

.

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

.

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

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

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

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

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

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

Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень <#"justify">4. Представление длинных чисел

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

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

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

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

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

,

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

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

.

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

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

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

. Для удобства можно выбрать 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);

}

for (int i = 0; i < first_summand.Length; i++)

{

sum += (int.Parse(first_summand[i].ToString()) + int.Parse(second_summand[i].ToString()) + dop) % 10;

dop = (int.Parse(first_summand[i].ToString()) + int.Parse(second_summand[i].ToString()) + dop) / 10;

if (i == first_summand.Length - 1 && dop != 0)

{

sum += dop;

}

}

reverse(sum, ref sum);

}

5. Операции над длинными числами

Прежде всего, необходимо уточнить интерфейс. Можно определить операторы как части класса, и это будет достаточно удобно в использовании. Однако при вычислении C=A+B оператор не сможет получить доступ к числу C. Поэтому придется создавать временное число Temp = A+B, которое затем будет скопировано в C. Лишних операций и использования дополнительной памяти можно избежать, если записывать результат в C напрямую. Исходя их этого, в качестве интерфейса выберем внешние функции, которые принимают в качестве параметров исходные данные и число для записи результата.

5.1 Сложение и вычитание

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

Вычисление C = A+B, работает вызов вида Add (A, B, C).Максимальный размер C должен быть достаточен для хранения суммы

void Add(BigInt A,BigInt B, ref BigInt C)

{i;temp; // temp здесь и далее играет роль «временной» цифры,

// до выполнения переноса. Возможно, temp > BASE..Coef = new int[A.Size+1];carry = 0;

// Добиваемся B.Size ? A.Size.(A.Size < B.Size)

{(B, A, ref C);;

}

// Теперь B.Size ? A.Size.

// Складываем два числа, i - номер текущей цифры(i = 0; i < B.Size; i++)

{=A.Coef[i]+B.Coef[i]+carry;(temp >= Base) // переполнение. Перенести единицу.

{.Coef[i] = temp - Base; carry = 1;

}

{.Coef[i] = temp; carry = 0;

}

}

// Меньшее число кончилось(; i < A.Size; i++)

{= A.Coef[i] + carry;(temp >= Base) // переполнение. Перенести единицу.

{.Coef[i] = temp - Base; carry = 1;

}

{.Coef[i] = temp; carry = 0;

}

}

// Если остался перенос - добавить его в дополнительный разряд(carry == 1)

{.Coef[i] = carry; C.Size = A.Size + 1;

}C.Size = A.Size;

}

Вычитание осуществляется аналогично, с той лишь разницей, что осуществляется перенос "заимствования". Мы работаем с положительными числами, поэтому если вычитаемое большое по размеру - происходит выход.

Если длины одинаковы, но одно больше другого - это приведет к тому, что в конце процесса останется неиспользованное заимствование, а результат будет дополнением до BaseB.Size. Например, при обычном вычитании 35 - 46 = -11, при описанном выше 35 - 46 = 89, так как выполняется равенство 89 = 100 - 11 (89 - это дополнение 11 до 100).

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

5.2 Умножение

). Обнулить C.

2). Обнулить i.

3). Вычислить временный результат, соответствующий умножению i-й цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции. Если получившаяся цифра C больше Base - сделать перенос.

). Если A не кончилось, увеличить i на единицу и идти на шаг 3.

5.3 Деление

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

Рассмотрим действия, совершаемые при делении A=68971 на B=513 (рисунок 1.5.1). Здесь n=5, m=2.

Рисунок 1.5.1 Пример деления длинных чисел (горизонтальные линии проводятся между шагами)

. i = (индекс старшего коэффициента A) = 4

1.1 "Угадываем" q[0] = 1.

1.2 Вычитаем сдвинутое B*1 = 513 из A (на бумаге при этом пишем только значимую для следующего шага часть A)

2. i = 3.

.1 "Угадываем" q[1] = 3.

2.2Вычитаем сдвинутое B*3 = 1539 из A.

3. i = 2.

.1 "Угадываем" q[3] = 4.

.2 Вычитаем сдвинутое B*4 = 2052 из A.

4. i < m = 2, процесс закончен. То, что осталось от A после вычитаний, является остатком деления.

Все очевидно, за исключением одного "творческого" шага - "угадывания". Как заставить компьютер генерировать правильное частное q? Или хотя бы достаточно близкое к нему число?

Пусть очередной шаг представляет собой деление некоторого U = (u0, u1, …, un) на B=(b0, b1, …, bn-1). Если bn-1 ?Base/2, то можно доказать следующие факты.

. Если положить qGuess = (un*Base + un-1)/bn-1, то qGuess-2 ? q?qGuess. Иначе говоря, вычисленная таким способом «догадка» будет не меньше искомого частного, но может быть больше на 1 или 2.

. Если же дополнительно выполняется неравенство qGuess*bn-2 > Base*r + un-2, где r - остаток при нахождении qGuess и qGuess ? Base (условие 2), то qGuess-1 ? q ? qGuess, причем вероятность события qGuess = q+1 приблизительно равна 2/Base.

Таким образом, если bn-1 ? Base/2, то можно вычислить qGuess = (un*Base + un-1) / bn-1 и уменьшать на единицу до тех пор, пока не станут выполняться условия (2). Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/Base, на единицу большим числом.

6. Проблемы в ходе выполнения курсовой работы

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

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

Изначально результаты деления и умножения чисел на 2 сразу записывались в listbox (в процессе подсчета) и после каждой следующей операции дописывались туда из-за чего умножение длинных чисел происходило значительно дольше из-за того, что вывод информации на экран занимает относительно много времени (речь идет о долях секунд и даже меньше, но при большем объеме вывода информации это очень заметно)!

После долгих экспериментов, я нашла, наконец решение проблемы. А именно: записывать результаты вычислений в строку (в тип string) - это позволяет не тратить лишнее время. А после всех вычислений надо было вывести эту строку.

Кодовая часть решения проблемы:

public void div_2_1(string a, ref int count, ref int[] chetn)

{= 0;b = "";[] str = { a };div2 = "";k = 0, q = 1, q1 = 0;(int.Parse(a[a.Length - 1].ToString()) % 2 == 1)

{.Resize(ref chetn, chetn.Length + 1);[0] = 0;++;

}_na_2.Text = str[0] + "\n";(a.ToString() != "1")

{= div_2(a, k, b);.Resize(ref str, str.Length + 1);= delete_0(angel);[q] = a;(int.Parse(a[a.Length - 1].ToString()) % 2 == 1)

{.Resize(ref chetn, chetn.Length + 1);[q1] = q;++;

}

//delenie_na_2.Text += str[q] + "\n"; было+= str[q] + "\n"; //стало++;++;

}_na_2.Text = div2; //стало

}

Выводы

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

В математической логике русский народный счет тесно связан с алгоритмом шифрования RSA из-за способности работать с длинными числами.

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

В общем, это очень интересный и оригинальный способ, показывающий нам, что не все свойства чисел до конца исследованы человеком.

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

умножение пифагор математический алгоритм

Список литературы

1. Липский, В. Перестановки // Комбинаторика для программистов [Текст]. - М.: "Мир", 1988. - С. 214.

. Морозова, О. И. Применение ЭВМ для решения задач математической логики и теории алгоритмов [Текст]: учеб. пособие / О. И. Морозова, Ю. К. Чернышев; Нац. аэрокосм. ун-т "Харьк. авиац. ин-т", 2010.- С. 71.

. Генерация перестановок в лексикографическом порядке // "Генерация перестановок в лексикографическом порядке" [Электронный ресурс] / Режим доступа: \www/ URL: #"justify">4. Томас Кормен, Чарльз Лэйзерстон, Рональд Ривест "Алгоритмы построения и анализ" // Алгоритмы и структуры данных, анализ алгоритмов [Электронный ресурс] / Режим доступа: \www/ URL: http://e-maxx.ru/bookz/files/cormen.pdf - 10.04.13.

Содержание Введение . Алгоритм умножения . Феномен русского народного умножения . Алгоритм RSA шифрования . Представление длинных чисел .

Больше работ по теме: