72664

ρ-метод факторизации Полларда на примере 32-битовых целых чисел

Курсовая

Информатика, кибернетика и программирование

Цель работы – рассмотреть основные методы факторизации больших чисел; программная реализация ρ-метода факторизации Полларда; реализация генерации простых чисел; тестирование ускорения ρ-метода факторизации Полларда.

Русский

2014-11-26

289.58 KB

31 чел.

30

Министерство образования и науки Украины

Харьковский национальный университет радиоэлектроники

Факультет Компьютерной инженерии и управления

Кафедра Безопасности информационных технологий

Курсовая работа

Тема: ρ-метод факторизации Полларда на примере 32-битовых целых чисел

Дисциплина: Технологии программирования

Выполнил:

ст. гр. БИКС 12-2

Семиразов Данил Сергеевич

Научный руководитель:

Мельникова О.А.

Харьков 2013

Харьковский национальный университет радиоэлектроники

Факультет: КИУ           

Кафедра: Безопасность информационных технологий

Специальность: “Безопасность информационных и коммуникационных систем”

Дисциплина: “Технологии программирования”

              УТВЕРЖДАЮ

          Зав. кафедры БИТ       

          проф. И.Д. Горбенко

“_____“ _________________ 201__ г.

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ

Студенту Семиразову Данилу Сергеевичу

  1.  Тема работы: ρ-метод факторизации Полларда на примере 32-битовых целых чисел.
  2.  Срок сдачи студентом законченной работы: 04.06.2013
  3.  Выходные данные к проекту:
  4.  Содержание объяснительной записки: необходимо реализовать    

ρ-метод факторизации Полларда на примере 32-битовых целых чисел.

  1.  Перечень графического материала:
  2.  Основная литература и источники: Ρ-алгоритм Полларда [электронный ресурс]: режим доступа www/URL: http://ru.wikipedia.org/ wiki/Ρ-алгоритм_Полларда

7. Дата выдачи задания: 20.02.2013

8. Дата сдачи задания: 04.06.2013

Руководитель работы: Мельникова Оксана Анатольевна

Задание принял к выполнению            _________

                                              (подпись студента)

Студент: Семиразов Данил Сергеевич           _________

                                                                                           (подпись)

РЕФЕРАТ

Курсовая работа содержит 30 стр., 6 рис., 2 табл., 2 прил., 4 ист.

Объект исследования  – ρ-метод факторизации Полларда 

Цель работы – рассмотреть основные методы факторизации больших чисел; программная реализация ρ-метода факторизации Полларда; реализация генерации простых чисел; тестирование ускорения ρ-метода факторизации Полларда.

Суть работы заключается в реализации ρ-метода факторизации Полларда для 32-битовый чисел на языке программирования C++. В работе используются тест простоты методом Миллера-Рабина, а также классический и бинарный метод нахождения НОД двух чисел.

 ПОЛЛАРД, ПРОСТЫЕ ЧИСЛА, ТЕСТ МИЛЛЕРА-РАБИНА, ФАКТОРИЗАЦИЯ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………………..6

1 ОПИСАНИЕ НЕКОТОРЫХ МЕТОДОВ И АЛГОРИТМОВ………………..7

  1.  Метод квадратичных форм Шенкса…………………………………..7
  2.  Факторизация с помощью эллиптических кривых…………………11
  3.  ρ-алгоритм Полларда…………………………………………………12
  4.  Тест простоты Миллера-Рабина……………………………………...14

2 ОПИСАНИЕ ПРОГРАММЫ………………………………………………….16

2.1 Общие сведения……………………………………………………….16

2.2 Функциональное назначение…………………………………………16

2.3 Описание логической структуры…………………………………….17

2.4 Используемые технические средства………………………………..22

2.5 Вызов и загрузка программы…………………………………….…..22

2.6 Входные и выходные данные……………………………………..….23

2.7 Ускорение алгоритма…………………………………………….…...26

ВЫВОДЫ………………………………………………………………….….….27

ПЕРЕЧЕНЬ ССЫЛОК…………………………………………………………...28

ПРИЛОЖЕНИЕ А “Основной текст программы”.……………………….……29

ПРИЛОЖЕНИЕ Б “Бинарный алгоритм Эвклида”.…..………………….……32


ВВЕДЕНИЕ

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

Во время реализации схемы RSA создаются 2 вида ключей: открытый ключ и закрытый ключ. В свою очередь открытый ключ содержит 2 элемента: некоторое число E (открытая экспонента), а также модуль N. N является произведением двух простых чисел P и Q. Зная эти числа, можно вычислить Fn = (P-1)*(Q-1) и подобрать мультипликативно обратный элемент для E, т.е. вычислить секретную экспоненту D. Этот элемент D является секретной составляющей. С помощью него можно расшифровать зашифрованную информацию. Т.е. чтобы расшифровать информацию достаточно факторизовать N.

В математике факторизация — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. Например, число 15 факторизуется на простые числа 3 и 5, а полином x2 − 4 факторизуется на (x − 2)(x + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.

Чаще всего N – очень большое число, что и составляет трудность для его факторизации. В своей курсовой работе я беру в качестве N 32-битовое число, хотя на пракрите используются числа намного больше 32 бит. Для факторизации таких небольших чисел, удобно пользоваться алгоритмом, предложенным Джоном Поллардом, так называемым ρ-алгоритмом Полларда. Также для реализации простых чисел я буду пользоваться методом Миллера-Рабина.

1 РАЗЛИЧНЫЕ АЛГОРИТМЫ ФАКТОРИЗАЦИИ БОЛЬШИХ ЧИСЕЛ И ИХ АКТУАЛЬНОСТЬ

1.1 Метод квадратичных форм Шенкса

Метод квадратичных форм Шенкса – это метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма. Для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами среди алгоритмов факторизации для чисел от до и, вероятно, таковыми останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду. Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел типа чисел Ферма [1].

Описание алгоритма:

Вход: Нечетное составное число , которое требуется факторизовать. Если  , заменим на . Теперь   или .

Выход: Нетривиальный делитель .

1. Определим исходную квадратичную форму , с дискриминантом , где  .

2. Выполним цикл редуцирований , пока форма  не станет квадратной.

3. Вычислим квадратный корень из  .

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

Реализация алгоритма:

Вход: Составное число 

Выход: Нетривиальный делитель 

  1.  Инициализация алгоритма:
  2.  Проверим, является ли  полным квадратом. Если да, то вычислим  , и завершим вычисление. Иначе, перейдем к следующему пункту.

б) Если , заменим на . Определим ,

    

в) Определим исходные значения параметров 

             

             

  1.  Первый цикл:

a)   

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

  1.  Второй цикл:

а) Начнем цикл вычислений новых параметров  

Формулы для реализации второго цикла останутся такими же, как раньше. Изменятся только начальные значения параметров 

б)   

      

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

Пример факторизации числа:

Применим данный метод для факторизации числа . Приведем решение в виде двух таблиц (табл. 1.1, табл. 1.2).

Таблица 1.1 – Реализация первого цикла для факторизации числа N

Таблица 1.2 – реализация второго цикла для факторизации числа N

Теперь можно увидеть во втором цикле, что   Следовательно число 

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

1.2 Факторизация с помощью эллиптических кривых

Факторизация с помощью эллиптических кривых – алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.

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

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

Пример факторизации числа:

Допустим, нам нужно факторизовать число n = 455839.  Возьмем эллиптическую кривую и точку, лежащую на этой кривой

Попробуем вычислить 10!P:

  1.   Для начала вычислим координаты точки  .
  2.  Тангенс угла наклона касательной в точке P равен:

б) Находим координаты точки :

.

в) Проверяем, что точка 2P действительно лежит на кривой:

    

2) Теперь вычислим .

   а) Тангенс угла наклона касательной в точке 2P составляет

   .

   б) Учитывая вычисленное s, мы можем вычислить координаты точки   

    2(2P), так же, как это было сделано выше: 4P = (259851, 116255).  

   Проверяем, что точка действительно лежит на нашей эллиптической   

   кривой.

   в) Суммируя 4P и 2P находим .

3) Аналогичным образом можно вычислить , и так далее. Когда дойдем до 8!P заметим, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, то мы нашли искомое разложение: 455839 = 599·761.

  1.   ρ-алгоритм Полларда

ρ-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основывается на алгоритме Флойда. В конце 60х годов 20 века Роберт Флойд придумал достаточно эффективный алгоритм поиска длины цикла в последовательности, также известный, как алгоритм "черепаха и заяц". Джон Поллард, Дональд Кнут и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма [3].

ρ-алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Во всех ρ-методах Полларда строится числовая последовательность, элементы которой образуют цикл (рис.1.1), начиная с некоторого номера n, что может быть проиллюстрировано расположением чисел в виде греческой буквы ρ. Это и послужило названием семейству методов.

Рисунок 1.1 – Числовая последовательность зацикливается, начиная с некоторого n. Цикл может быть представлен в виде греческой буквы ρ.

Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод все-таки получил своё современное название – ρ-aлгоритм Полларда.

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма  при .

Так, , где  - простое число, состоящее из 62 десятичных цифр.

В рамках проекта "Cunningham project" алгоритм Полларда помог найти делитель длиной 19 цифр числа . Большие делители также могли бы быть найдены, однако открытие метода факторизации с помощью эллиптических кривых сделало алгоритм Полларда неконкурентоспособным.

Описание данного алгоритма приводится в подразд. 2.3.

  1.   Текст простоты Миллера-Рабина

Тест Миллера-Рабина – вероятностный полиномиальный тест простоты. Тест Миллера-Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера-Рабина часто используется в криптографии для получения больших случайных простых чисел.

Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году [4].

Свидетели простоты и теорема Рабина:

Пусть  – нечётное число большее 1. Число  однозначно представляется в виде , где  нечётно. Целое число ) называется свидетелем простоты числа , если выполняется одно из условий:

  1.  
  2.  существует целое число ) такое, что

Теорема Рабина утверждает, что составное нечётное число  имеет не более  различных свидетелей простоты, где  — функция Эйлера.

Описание алгоритма:

Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту; r — количество раундов.

Вывод: составное, означает, что m является составным числом; вероятно простое, означает, что m с высокой вероятностью является простым числом.

Представим m − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.

Цикл А: повторить r раз:

  1.  Выбрать случайное целое число a в отрезке [2, m − 2]

    б) xat mod m

    если x = 1 или x = m − 1, то перейти на следующую итерацию A         

  Цикл B: повторить s − 1 раз

  1.  xx2 mod m

        если x = 1, то вернуть составное

        если x = m − 1, то перейти к след. итерации цикла А

   вернуть составное

вернуть вероятно простое

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того, что m составное, не превосходит .

  1.  ОПИСАНИЕ ПРОГРАММЫ

2.1 Общие сведения

Для реализации факторизации 32-битного числа ρ-методом Полларда была разработана программа с названием “Pollard”. Для генерации простых чисел используется функция, примыкающая к данной программе, основанная на тесте простоты Миллера-Рабина.

Программа написана на языке программирования С++ в среде Microsoft Visual Studio 2012.

Запускается как консольное приложение и не требует дополнительно установленного программного обеспечения. Для ее работы достаточным является наличие операционной системы Windows XP или более новой версии. Для компиляции кода вам потребуется программная среда Microsoft Visual Studio 2012.

2.2 Функциональное назначение

Данная программа предназначена для факторизации больших чисел размер которых не превышает 32-бита. Программа сама генерирует пары псевдослучайных 16-битовых простых чисел и записывает 32-битовый результат их перемножения в файл “number.txt”.

Программа работает в двух режимах. В первом режиме она генерирует 100 пар псевдослучайных 16-битовых простых чисел и записывает результат их попарного перемножения в файл “number.txt”, во втором – программа считывает числа из указанного выше файла и факторизует их. Результат факторизации проверяется путем перемножений полученных чисел и сравнения их с исходным.

  1.   Описание логической структуры

Программа содержит 5 основных функций (unsigned int StepMod(…), bool Test(…), unsigned int GenPrime(),unsigned int GCD(…),unsigned  int Pollard(…)), а также главную функцию int main().

Рассмотрим эти функции:

  1.  Функция unsigned int StepMod (unsigned int A, unsigned int B,unsigned

int N) (Приложение А).

 Назначение: Данная функция выполняет возведение числа A в степень B по модулю N.

 Вход: Функция принимает 3 значения с типом unsigned int. Первое значение (unsigned int A) – число, которое необходимо возвести в степень по модулю, второе (unsigned int B) – показатель  степени, третье   (unsigned int N) –  модуль, по которому берут результат.

Выход: Функция возвращает число A в степень B по модулю N.

Алгоритм: В данной работе используется бинарный метод возведения в степень по модулю.

а) Создадим некую переменную y, которой присвоим значение основания степени: y=A;

б) Измерим длину показателя степени. Для этого можно воспользоваться побитовым умножением на 1, начиная со старших бит. Т.к. показатель степени не превосходит 32 бита, начинаем проверку со сдвигом на 31 бит влево. Результат присвоим переменной t.

в) Цикл: повторить t-2 раз (причем, от i = t-2 до i = 0).

 y = y*y mod(N)

 Если i-й бит основания степени равен 1, то

 y = y*x mod(N)

г) Вернуть y.

  1.  Функция  bool Test (unsigned int m) (Приложение А).

Назначение: Данная функция выполняет проверку числа на простоту.

Вход: Число с типом unsigned int, которое необходимо проверить на

простоту.

 Выход: 0 – число составное, 1 – число вероятно простое.

 Алгоритм: Для проверки простоты числа используется метод Миллера-Рабина, описанный в подразд. 1.4.

а) Представим m − 1 в виде 2s·t, где t нечётно. Это можно сделать последовательным делением m - 1 на 2.

б) Цикл А: повторить r раз:

Выберем случайное целое число a в отрезке [2, m − 2]

     xat mod (m)

    Если x = 1 или x = m − 1, то перейдем на следующую итерацию A         

  Цикл B: повторить s − 1 раз

xx2 mod m

        Если x = 1, то вернуть 0

        Если x = m − 1, то перейти к след. итерации цикла А

   Вернуть 0

в) Вернуть 1

 

  1.  Функция unsigned int GenPrime () (Приложение А).

Назначение: Данная функция генерирует простое 16-битовое число.

Вход: Функция не принимает параметров.

Выход: 16-битное простое число.

Алгоритм: Данная функция использует функцию bool Test(…) для

проверки числа на простоту

а) Создаем переменную k и присваиваем ей псевдослучайное 16-битное

нечетное число. Чтобы сделать число нечетным достаточно воспользоваться бинарной операцией |, т.е. k = k|1.

б) С помощью функции bool Test() проверим сгенерированное число на

простоту. Если функция вернет значение 0, то увеличим k на 2. Выполнять это необходимо до тех пор, пока k не станет простым, т.е. пока функция bool Test() не вернет значение 1. Чтобы это реализовать, можно воспользоваться циклом с предусловием while.

в) Вернуть k.


4)
Функция unsigned int GCD (unsigned int a, unsigned int b) (Приложение А).

Назначение: Данная функция находит наименьший общий делитель двух чисел.

Вход: Два положительных целых числа, НОД которых необходимо найти.

Выход: НОД(a,b).

Алгоритм: В данной работе я воспользовался классическим алгоритмом

Эвклида для нахождения НОД двух чисел.

а) Создадим некую переменную c, необходимую для временного

хранения результатов вычисления.

б) Цикл while: выполнять, пока переменная b не обнулится.

 с = a mod b

         a = b

         b = с

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

в) Вернуть b.

5) Функция unsigned int Pollard (unsigned int n) (Приложение А).

Назначение: Данная функция факторизует 32-битовое число.

Вход: Целое число n типа unsigned int.

Выход: Нетривиальный делитель числа n.

Алгоритм: Приведенный ниже алгоритм является улучшением оригинального алгоритма Полларда. Данная вариация ρ-метода Полларда была разработана Робертом Флойдом.

а) Зададим некую функцию F(x). Функция должна быть не слишком

сложной для вычисления, но в то же время не должна быть линейным многочленом, а также не должна порождать взаимно однозначное отображение. Обычно в качестве F(x) берут F(x)=(x2+1)mod(N)

б) Сгенерируем псевдослучайное числа в диапазоне от 1 до n, где n – факторизуемое число, и присвоим его переменной x0. Также создадим переменную y0 = x0 .

в) Цикл while: выполнять пока НОД ( N, |xi - yi|) = 1

 xi  = F(xi-1)

 yi = F(F(yi-1))

 г) Вернуть НОД ( N, |xi - yi|)

 Обоснование алгоритма:

Алгоритм основывается на известном парадоксе дней рождения:

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

Пусть последовательность  состоит из разностей , проверяемых в ходе работы алгоритма. Определим новую последовательность , где  — меньший из делителей числа . Все члены последовательности  меньше . Если рассматривать её как случайную последовательность целых чисел, меньших , то, согласно парадоксу дней рождения, вероятность того, что среди  её членов попадутся два одинаковых, превысит  при , тогда   должно быть не меньше . Если , тогда , то есть,  для некоторого целого . Если  , что выполняется с большой вероятностью, то искомый делитель  числа  будет найден как  . Поскольку , то с вероятностью, превышающей 0.5, делитель  будет найден за  итераций.

 Пример факторизации числа:

Пусть .

Ниже приведены вычисления (табл. 2.1).

Таблица 2.1 – Результаты вычислений для факторизации числа N = 8051

i

xi

yi

НОД(|xi − yi|, 8051)

1

5

26

1

2

26

7474

1

3

677

871

97

Таким образом, 97 – нетривиальный делитель числа 8051

6)  Функция int main () (Приложение А).

 Назначение: Данная функция выполняет объединение всех вышеописанных функция для достижения главной цели программы.

 Алгоритм: Данная функция работает в двух режимах: первый – генерация 100 пар простых чисел запись их попарного произведения в файл, второй – чтение чисел из файла и факторизация. Программа предлагает пользователю выбрать один из режимов работы. Режим определяется путем введения соответствующего числа с клавиатуры.

 Режим №1:       

а) С помощью функции GenPrime() программа генерирует простые числа, находит их произведения, записывает полученные

произведения    в массив  и выводит результат на экран.

б) С помощью функции fwrite() программа побитово записывает массив полученных произведений в файл “number.txt”.

 Режим №2:

  1.  С помощью функции fread() программа побитово считывает числа

из файла “number.txt” и записывает их в массив.

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

2.4 Используемые технические средства

Обязательным условием работы программы является наличие операционной системы Windows XP или более поздней версии. Программа тестировалась и прошла проверку на работоспособность на ОС Windows XP, Windows 7 и Windows 8.

Программа разрабатывалась в среде Microsoft Visual Studio 2012 на ОС Windows 8.

2.5 Вызов и загрузка программы

Для того чтобы запустить программу нужно открыть соответствующий файл под названием «Курсовая работа.exe» на съемном носителе. Для возможности редактирования необходимо запустить файл “Курсовая работа.sln” из папки “Курсовая работа”. Программа занимает 76 КБ памяти на диске.

2.6 Входные и выходные данные

Чтобы начать работать с программой, ее необходимо запустить. При первом запуске программы пользователь увидит на экране следующее окно (рис. 2.1):

Рисунок 2.1 – Первый запуск программы (выбор режима)

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

Рисунок 2.2 – Сообщение об ошибке ввода

При выбора режима 0 пользователь увидит на экране результат генерации 100 пар простых чисел (рис. 2.3), а также сообщение о записи или ошибки при записи чисел в файл “number.txt”.

 ………………………………………………………………………………………

Рисунок 2.3 – Демонстрация работы первого режима

При выбора режима 1 пользователь увидит на экране результат факторизация 100 чисел (рис. 2.4). Также программа производит проверку результата факторизации путем перемножения полученных при факторизации чисел и сравнения полученного произведения с исходным считанным числом. При совпадении или несовпадении программа выводит на экран соответствующее сообщение.

……………………………………………………………………………………….

 

Рисунок 2.4 – Демонстрация работы второго режима

Если пользователь запустит сперва первый режим, то он увидит (рис. 2.5) соответствующее сообщение об ошибке, т.к. файл “number.txt” не был создан и программе неоткуда считывать числа.

Рисунок 2.5 – Файл “number.txt” не был создан

2.7 Ускорение алгоритма

Для ускорения алгоритма я воспользовался бинарным алгоритмом нахождения НОД двух чисел (Приложение Б). Тестировались 100 разных чисел. При каждом новом испытании числа генерировались заново. Ниже приведены результаты испытаний (табл. 2.2).

Таблица 2.2 – Результаты тестирования

Номер

испытания

Классический метод

время, с

Бинарный алгоритм

время, с

 1

0.015

0.014

2

0.014

0.014

3

0.016

0.01

4

0.015

0.009

5

0.02

0.015

6

0.03

0.018

7

0.015

0.009

8

0.015

0.01

9

0.014

0.009

10

0.015

0.014

Среднее время

0.0169

0.0122

Исходя из полученных результатов, использование бинарного алгоритма Эвклида ускоряет факторизацию чисел на 28%.

ВЫВОДЫ

При выполнении курсовой работы были рассмотрены основные алгоритмы факторизации чисел, а также их актуальность; рассмотрены особенности реализации поставленной задачи факторизации 32-битовых чисел методом Джона Полларда; рассмотрен алгоритм генерации простых чисел с помощью теста простоты Миллера-Рабина.

Также в данной работе был рассмотрен один из способов ускорения алгоритма: использование бинарного алгоритма Эвклида для нахождения НОД двух чисел. Результаты тестирования показали, что данных способ ускоряет работу алгоритма на 28%.

В целом, при разработке данной программы, я ознакомился с правилами оформления программной документации, приобрел опыт работы с программами и программными продуктами, получил новые навыки по разработке прикладных программных продуктов на языке программирования С++.

ПЕРЕЧЕНЬ ССЫЛОК

1. Метод квадратичных форм Шенкса [электронный ресурс]: режим

доступа www/URL:http://ru.wikipedia.org/wiki/Метод_Шенкса

2. Факторизация с помощью эллиптических кривых [электронный ресурс]: режим доступа www/URL: http://ru.wikipedia.org/ wiki/Факторизация_Ленстры_с_помощью_эллиптических_кривых

3. Ρ-алгоритм Полларда [электронный ресурс]: режим доступа www/URL: http://ru.wikipedia.org/ wiki/Ρ-алгоритм_Полларда

4. Тест Миллера — Рабина [электронный ресурс]: режим доступа www/URL: http://ru.wikipedia.org/ wiki/Тест_Миллера_—_Рабина

ПРИЛОЖЕНИЕ А

Основной текст программы

#include <iostream> //подключение библиотек

#include <math.h>

#include <time.h>

#include <conio.h>

using namespace std;

unsigned int StepMod(unsigned int A,unsigned int B, unsigned int N) //функция нахождения   числа А в степени B по модулю N

{

 unsigned __int64 y=A;

 int t=31;

 while((B&(1<<t))==0) //нахождение длины степени в битах

 t--;

t--;

 for(;t>=0;t--) //непосредственно возведение в степень

{

 y=(y*y)%N;

 if((B&(1<<t))!=0) //проверка i-го бита степени на равенство единице

  y=(y*A)%N;

}

 return y;

}

bool Test (unsigned int m) //функция проверки числа на простоту

{

 

 int s=0,t=m-1,a;     //представляем число m-1 в виде m-1=(2^s)*t

 unsigned long x;

 while(t%2==0)

    {s++;

        t=t/2;}

int r=0; //создадим переменную количества раундов

loop:

r++;

 if (r>50) goto loop1; //после 50 раунда компилятор переходит к флажку loop1

 a=(rand()%(m-4))+2;

x=StepMod(a,t,m);

 if ((x==1) || (x==(m-1)))

 goto loop;

 for(int j=0;j<(s-1);j++)

 {x=StepMod(x,2,m);

 if (x==1) return 0; //число составное

 if (x==(m-1)) goto loop; //при выполнении условия компилятор переходит к флажку loop, т.е на следующую итерацию цикла А

}

 return 0; //число составное

loop1: //число вероятно простое

return 1;

}

unsigned int GenPrime() //функция генерации простого числа

{

unsigned int k=rand()|(1<<15)|1; //генерируем нечетное число длиной 16 бит

while(Test(k)==0) //если число составное, рассматривается следующее нечетное число

     k=k+2;

return k; //функция возвращает полученное простое число}

unsigned int GCD(unsigned int a,unsigned int b) //функция нахождения НОД

{

   unsigned int с;

   while( b != 0 )

   {

       с = a % b;

       a = b;

       b = с;

   }

   return a; //функция возвращает НОД

}

unsigned  int Pollard (unsigned int n) //функция нахождения нетривиального делителя

{

srand(time(NULL));

unsigned __int64 y=(rand()|(1<<15))%(n-1)+1; //генерируем числа в диапазоне от 1 до n-2

unsigned int x=1;

int i = 1;

int stage = 2;

while (GCD(n,(y-x)) == 1)

{if (i == stage ) //x-у присваивается значение y на каждой второй итерации (см.

                   2.3 Описание логической структуры)

 {x = y;

       stage = stage*2;}

 y = (y*y + 1)%n;

 i++;

  }

return GCD(n,(y-x)); //функция возвращает нетривиальный делитель

}

int main()

{  

 

srand(time(NULL));

 setlocale(0,""); //подключение русского языка

 int a;

cout<<"Генерация простых чисел - 0\nФакторизация - 1\nВведите необходимое значение: ";

cin>>a;

 

 if(a==0) //генерация простых чисел и запись их в файл

 {

 unsigned int p,q;

      unsigned int n;

 unsigned int N[100];

 

 cout<<"\nСгенерированы 100 пар 16-битных чисел и вычеслены их произведения:\n";

 for (int i=0;i<100;i++)

{

      p=GenPrime();

q=GenPrime();

n=p*q;

N[i]=n;

cout<<"P"<<(i+1)<<"="<<p<<"  "<<"Q"<<(i+1)<<"="<<q<<" "<<"N"<<(i+1)<<"="<<n<<"\n";

      }     //вывод чисел 

     

 FILE *num=fopen("number.txt","wb");

 if(num!=0)

{

fwrite(N,4,100,num); //запись N в файл

 cout<<"\nЧисла успешно записаны в файл number.txt";

}

 else

 {cout<<"Ошибка при открытии файла number.txt";

        getch();}

 

fclose(num);

 

}

if(a==1) //факторизация

{

 unsigned int N[100],N1[100],p,q;

      FILE *num=fopen("number.txt","rb");

 if(num!=0)

 fread(N,4,100,num);// считывание N из файла

 else

 {cout<<"\nОшибка при открытии файла number.txt";

getch();}

fclose(num);

cout<<"Факторизовав данные числа получим:\n";

 

 for (int i=0;i<100;i++)

{

 do

{p=Pollard(N[i]);}

while(p==1 || p==N[i]); //функция Pollard с некой вероятностью может

 вернуть 1 или исходное число

 q=N[i]/p;

 N1[i]=p*q;

cout<<"P"<<(i+1)<<"="<<p<<"   "<<"Q"<<(i+1)<<"="<<q<<"\n"; //вывод результата

 }

 

for(int i=0;i<100;i++) //проверка правильности факторизации

 if (N1[i]!=N[i])

  {cout<<"Числа факторизованы неверно.";

  getch();

  return 0;}

cout<<"\nФакторизация прошла успешно. Числа факторизованы верно.";

 

}

if (a!=1 && a!=0) //введено неверное значение

{

cout<<"Ошибка ввода.";

}

getch();

return 0;

}

ПРИЛОЖЕНИЕ Б

Бинарный алгоритм Эвклида

unsigned int gcd(unsigned int u, unsigned int v) //бинарный алгоритм Эвклида

{

    int shift;

 

    if (u == 0 || v == 0)

      return u | v;

 

    

    for (shift = 0; ((u | v) & 1) == 0; ++shift) {

        u >>= 1;

        v >>= 1;

    }

 

    while ((u & 1) == 0)

      u >>= 1;

 

   

    do {

        while ((v & 1) == 0)  

          v >>= 1;

 

      

        if (u < v) {

            v -= u;

        } else {

            unsigned int diff = u - v;

            u = v;

            v = diff;

        }

        v >>= 1;

    } while (v != 0);

 

    return u << shift;

 }


 

А также другие работы, которые могут Вас заинтересовать

51002. Основні тенденції розвитку країни Австралія в міжнародному економічному інтеграційному простору 138.01 KB
  Базою міжнародної економіки є теорія ринкової економіки, мікро- і макроекономіка. Поєднання їх з прикладними економічними дисциплінами, такими, як міжнародний маркетинг, фінанси, облік тощо, дало змогу створити універсальну теорію міжнародної відкритої економіки
51004. Проектирование вторичного источника электропитания 3.83 MB
  Изучить структуру и основные типы промышленных источников питания. По заданию составить структурную схему ИП, рассчитать и выбрать основные элементы: общая компоновка, трансформатор или преобразователь, выпрямитель, фильтр, электронный стабилитрон. Составить общую электрическую схему ИП и рассмотреть принцип действия его элементов...
51005. Изучение газовых законов. Определение показателя адиабаты и политропы 55 KB
  Цель работы: изучение газовых законов, опытное определение показателя адиабаты и политропы воздуха. Приборы и принадлежности: баллон, манометр, насос Камовского.
51007. Изучение распределения Больцмана 44 KB
  Цель работы: изучение распределения Больцмана определение постоянной Больцмана. Компьютер выдал: Вывод: изучили распределение Больцмана определили постоянную Больцмана.