СтудЗона - огромная база рефератов, курсовых и шпаргалок на все случаи жизни!

 
 


Лепреконы. Глаз Одина - геолокационная текстово-графическая для telegram
с элементами РПГ
в жанре Diablo, Покемон Го





Бот знакомств в telegram
@youlove_bot

Курсовая работа "(Р - 1) - метод Полларда"

Предмет: Информатика
Оцените материал
(0 голосов)

 

Содержание

 

Введение…………………………………………………………………..3

Цель исследования и применение……………………………………….4

Методы решения…………………………………………………………5

Результаты…………………………………………………………….….8

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

Приложение:

 Исходный текст программы……………………………..............12

 

Цель исследования и применение

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

Ввиду существования (Р — 1)-метода Полларда для алгоритма RSA рекомендуют выбирать простые числа вида р =+1 и q =+ 1, где— тоже простые. Слишком мала вероятность числу    р — 1 оказаться показательно S-гладким с малым S, если р выбрано случайным образом и насчитывает 512 двоичных знаков. Следовательно, выбор случайного 512-значного двоичного простого числа скорее всего сделает (Р — 1)-метод Полларда бесполезным.

просмотреть полностью

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

Односторонняя (однонаправленная) функция (one way function) - это функция f, осуществляющая отображение X->Y, где X и Y - произвольные множества, и удовлетворяющая следующим условиям:

  1. Для каждого x из области определения функции  легко вычислить . Понятие «легко» обычно означает, что существует алгоритм, вычисляющий функцию f(x) за полиномиальное время от длины аргумента x.
  2. Задача нахождения прообраза  для произвольного y, принадлежащего области значений  функции, является вычислительно сложной задачей. Последнее означает, что не существует алгоритма, вычисляющего  существенно быстрее, чем алгоритм полного перебора.

 

Задача разложения натурального числа N на простые множители (факторизация N) явлется задачей вычисления односторонней функции: зная сомножители p и q, нетрудно вычислить их произведение N=p • q, но обратная задача нахождения делителей p и q по известному N является сложной задачей, решение которой требует значительных вычислительных ресурсов.

 

На вычислительной сложности решения этой задачи построен один из самых известных асимметричных методов криптографии – метод RSA.  В 1977 году, когда создатели этого метода Ривест, Шамир и Адлеман объявили о новом методе криптографии, основанном на задаче факторизации, наиболее длинные числа, разложимые на множители, имели длину 40 десятичных цифр, что соответствует, примерно, 132-битовому двоичному числу (число 40 надо домножить на ). Создатели RSA предложили широкой публике расшифровать некую фразу английского языка. Для этого предварительно требовалось факторизовать 129-значное  десятичное число N (длины 428 в битовом представлении), про которое было известно, что оно представимо в виде произведения двух простых сомножителей p и q, которые имели длину 65 и 64 десятичных знака.

 

В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа — экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих параметров (то есть от длины самого числа в бинарном представлении). Вторая группа — субэкспоненциальные алгоритмы, для обозначения сложности которых принята L-нотация:

 

где N — число, подлежащее факторизации, 0 < α < 1 и c — некоторые константы.

 

 

Метод решения

 

 

P-1 метод Полларда — алгоритм разложения натурального числа N на простые множители. Предложен Джоном Поллардом в 1974 году. Алгоритм предназначен для нахождения простых делителей p, у которых p − 1 хорошо раскладывается на множители, то есть имеет небольшой максимальный простой делитель. Если обозначить этот максимальный простой делитель B, то алгоритм требует O(BlogBlog2N) действий. Метод очень быстро находит простые факторы малой и средней величины (до 20-25 десятичных цифр). Актуальным рекордом для P-1 метода является простой делитель числа 960119 − 1, состоящий из 66 десятичных цифр, установленный T. Nohara 29.06.2006.

 

Определение

     Пусть K - положительное целое число. Некоторое положительное целое N называется K-гладким, если все простые делители N меньше, либо равны K.
     N будет называться гладким степени K, если все степени простых чисел, делящие N меньше, либо равны K. 

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

«Шаг 1»

Предположим, дано число N, которое не является степенью какого-либо простого числа и имеет простой делитель p, который заранее неизвестен. Выберем произвольные натуральные  (как правило a = 2) и  (например, B = 106).

Далее вычислим число k как произведение степеней всех простых чисел , не превосходящих выбранную границу B, где ei > 0 максимальные натуральные числа, удовлетворяющие . Если простой делитель p заданного числа N обладает свойством, что p − 1 раскладывается на простые делители меньшие либо равные B, то заведомо p − 1 | k.

Согласно малой теореме Ферма в группе  справедливо , что равносильно НОД(ak − 1,N) > 1. Заметим, что . Если граница B выбрана удачно, скорее всего НОД будет равен p. В некоторых случаях можно получить НОД равным N. Это означает, что метод нашёл сразу все делители. В этом случае надо просто уменьшить значение B. Также заметим, что так как ak может быть достаточно большим числом, то все вычисления производятся по модулю N.

Можно использовать некоторые трюки, например не вычислять НОД каждый раз заново, а хранить результаты по модулю N и вычислять НОД только время от времени.

Если НОД(ak − 1,N) = 1, это означает, что алгоритм завершился неудачно и p − 1 имеет делители большие чем B. Возможным планом действий могут быть:

  • Увеличить значение B (в этом случае не стоит начинать алгоритм заново. Можно пересмотреть значение k согласно новой границе B).
  • Применить метод для другого a (алгоритм надо начать заново. Надежда найти простой делитель основывается на том, что новое a может быть большой степенью порождающего элемента в ).
  • Использовать другой метод факторизации (например P+1 или метод эллиптических кривых)
  • Перейти к «шагу 2» алгоритма

 

Даже в такой простой форме поведение p-1 алгоритма довольно впечатляюще. Разумеется, он не претендует на получение полного разложения ( например, когда N = ( 2 * p + 1 ) * ( 2 * q + 1 ), где p, q, 2 * p + 1 и 2 * q + 1 простые, причем p и q примерно одного размера, время работы алгоритма будет O( N1/2+e ), если мы хотим разложить N полностью, не лучше простого деления ). С другой стороны, его можно удачно использовать для нахождения даже очень больших делителей N, так как на время работы влияет не размер делителя p, а гладкость p-1.

Размер B зависит, в основном, от времени, которое мы можем потратить. Кроме того, на него влияет существование второй стадии алгоритма. Обычные значения B - где-то от 105 до 106.
p-1 метод, стадия 2.      А теперь - существенное улучшения P-1 алгоритма. Требование существования простого делителя N, такого что p - 1 - гладкое степени B, - слишком строгое. Более рационально положить условие полной разложимости p - 1 при простом делении до B. То есть сделаем возможным существование одного простого делителя, большего B. Но это значит, что p - 1 = f * q, где f - B-гладкое, а q - простое число, возможно, гораздо большее B ( но не B2 ). Для наших целей мы несколько усилим условие и предположим, что у N есть простой делитель р, такой что p - 1 \ f * q, где f - гладкое степени B1 , и q - такое простое, что B1 < q <= B2, где B1 - cтарое B и B2 - гораздо большая константа.

     Покажем, как мы будем искать такое p. Очевидно, p - 1 - гладкое степени B2, таким образом мы могли бы использовать стадию 1 с B1замененным на В2, однако, это нереально, так как B2 - гораздо большая константа, чем В1.

     Тем же путем получаем

НОД ( аq*НОК(1..В) - 1 , N ) > 1


и поступаем так: в конце первой стадии у нас будет вычислено b := aНОК(1..В) mod N. Мы храним таблицу разностей простых от B1 до B2. Теперь эти разности малы и у нас их немного. Таким образом мы можем легко вычислить bd для всех возможных разностий d и получить все bdумножая начальную степень b на эти заранее вычисленные bd. Следовательно, для каждого простого, мы заменяем возведение в степень простым умножением, которое гораздо быстрее, и поэтому мы можем пойти много дальше.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Результаты

При написании программы использовалась библиотека длинных чисел MPIR, которая была подключена к MS Visual Studio 2008.

При тестировании программы использовались различные наборы произведений простых p и q для вычисления n и дальнейшей факторизации. Представляются некоторые из них:

 

 Первая серия тестов при B1=10 и В2=108 :

    

            В виду того, что второй шаг алгоритма вычисляется намного быстрее, чем первый, в первом случае выбраны именно такие В1 и В2.

 

1)Возьмем число (р - 1) гладкое степени = 5.

    p= 52489; q= 15361; n= 806283529 ;

 

 

 

Из результатов выполнения видно, что при выборе р – 1 малой степени гладкости отыскание p и q, происходит практически мгновенно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2)Возьмем число (р - 1) гладкое степени = 23.

     p=71761;q=18401;n=1320474161;

 

 

 

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

 

3)Возьмем число (р - 1) с большой степенью гладкости.

    p=53759 ; q=24859 ; n=1336394981 ;

 

 

 

 

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

 

 

Вторая серия тестов при B1=106 и В2=108 :

 

   Произведём серию тестов для тех же значений, но при увеличении В1 на первом шаге.

 

1)Возьмем число (р - 1) гладкое степени = 5.

    p= 52489; q= 15361; n= 806283529 ;

 

Результат не был найден на первом шаге.

 

2)Возьмем число (р - 1) гладкое степени = 23.

               p=71761;q=18401;n=1320474161;

 

Результат не был найден на первом шаге.

 

3)Возьмем число (р - 1) с большой степенью гладкости.

    p=53759 ; q=24859 ; n=1336394981 ;

 

 

 

Замечание.

  При вычислении первого и второго чисел результат не был найден при заданном В1, данную проблему можно решить путём изменения числа а (вычисления производились при а=2).

 

 

 

 

 

 

 

 

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

 

1)Методы факторизации натуральных чисел: учебное пособие.

[Ш.Т. Ишмухаметов – Казань, 2011]

2) Методические указания и варианты заданий к выполнению лабораторных работ по дисциплине «Информационная безопасность в сетях»

[д.ф.м.н, доцент.каф.САИТ Ишмухаметов Ш.Т.]

3) http://algolist.manual.ru/maths/teornum/factor/p-1.php

4) http://ru.wikipedia.org/wiki/P-1_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

5) http://masteroid.ru/content/view/1298/49/

6) http://www.exploringbinary.com/how-to-install-and-run-gmp-on-windows-using-mpir/

7) http://mpir.org/

8)http://oeis.org/search?q=prime+divisors+are+all+%3C%3D+10&sort=&language=english&go=Search

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

 

Исходный текст программы:

 

#include <iostream>

#include <math.h>

#include <time.h>

using namespace std;

 

#pragma warning(disable: 4800)

#include <mpirxx.h>

#pragma warning(default: 4800)

 

void main (int argc, char *argv[])

{ bool v=0;

  mpz_class n,a1,a2,p1,p2,b1,b2,g,i,k,t,j,del,c,g2;

 

   cout<<"enter n"<<endl;

   cin>>n;

   cout<<”step 1:”<<endl;

   clock_t start=clock();

    a2=2;p1=2;

  

    b1=10;

    b2=1000000;

 

         for(i=1;p1<b1;i++){

               if(i>1)mpz_nextprime(p1.get_mpz_t(),p1.get_mpz_t());

                k=1;

                t=1;

                   while(k<b1)

                                 {

                                    k=k*p1;

                                 }

 

                    for(j=0;j<p1;j++)t=t*a2;

                     a1=(t%n)-1;

                     mpz_gcd(g.get_mpz_t(),a1.get_mpz_t(),n.get_mpz_t());

                        if((g<n)&&(g>1))

                                 {

                                   cout<<"p="<<g<<"q="<<(n/g)<<endl;

                                   break;

                                 }

                                         }

  

 

printf(“work time step 1: %f\n”,(long double)(clock()-start)/CLOCKS_PER_SEC);

if(v) exit(0);

cout<<"step 2"<<endl;

mpz_nextprime(p1.get_mpz_t(),b1.get_mpz_t());

 

del=p1;

 for(i=0;p1<b2;i++)

   {

   if(i>1){p2=p1;mpz_nextprime(p1.get_mpz_t(),p1.get_mpz_t());del=p1-p2;}   

                                 /*k=1;*/g=1;

                                 while(g<del)

                                  {

                                    k=k*t;g++;

                                  }

                                 c=k%n;

                                 a1=c-1;

                                 mpz_gcd(g2.get_mpz_t(),a1.get_mpz_t(),n.get_mpz_t());

 

    if((g2<n)&&(g2>1))

                                  {

                                    cout<<"p="<<g2<<"q="<<(n/g2)<<endl;

                                    break;

                                 }

 

 } 

 

printf(“work time step 2: %f\n”,(long double)(clock()-start)/CLOCKS_PER_SEC);

 

 system("pause");

  }