51418

Факторизация больших чисел

Доклад

Математика и математический анализ

2 Пусть S – множество содержащее r элементов – функция выбранная случайным образом из конечного числа функций.4 Существует взаимнооднозначное соответствие между представлением числа n в виде и в виде а именно: ; . Тогда мы будем подбирать такие числа t и s чтобы было квадратом небольшого числа s. Если полученные таким образом числа и не делят n то берется или .

Русский

2014-02-11

386.5 KB

14 чел.

Раздел VІII

Факторизация больших чисел

Проблема факторизации заключается в разложении чисел на простые множители.

  1.  Метод Монте-Карло (Полларда, r-метод)

Пусть nнекоторое число, и задано отображение ZZn (Znкольцо вычетов по модулю n). Построим следующее множество элементов :

Znпроизвольное,

,

Утверждение 8.1 (Метод Монте-Карло) Если для некоторых j и k ()  таковы, что , где , то  является делителем n.

Пример. .

Пусть . Полагаем

,

, , , … и т.д.

, ,  .

Утверждение 8.2 Пусть Sмножество, содержащее r элементов,  – функция, выбранная случайным образом из конечного числа функций. Тогда если множество X содержит  элементов, где lположительное действительное число, то вероятность того, что все элементы множества X различны, не превосходит .

Утверждение 8.3 Оценка трудоемкости метода Монте-Карло Если nнечетное составное число, нетривиальный делитель n, то трудоемкость метода составляет .

Модификация метода. Пусть k (количество элементов множества X) имеет  двоичных разрядов. Тогда рассматриваются разности , где  (т.е. j имеет h двоичных разрядов).

Пример. При k, равном 10, оно имеет 4 двоичных разряда, тогда j имеет 3 двоичных разряда, и по модификации равно 7.

  1.  Метод Ферма и его простейшие модификации

Предположим, что составное число n представимо в виде произведения простых чисел , . Задача состоит в нахождении этих простых чисел.

Утверждение 8.4 Существует взаимно-однозначное соответствие между представлением числа n в виде  и в виде , а именно:

,  ;

,  .

Из утв. 8.4 следует, что если a и b близки, то s – небольшое. Тогда мы будем подбирать такие числа t и s, чтобы  было квадратом небольшого числа s. В этом случае удобно взять или близкое к нему.

Примеры.

  1.  

.

– не является квадратом.

Возьмем : , т.е. .

Итак, , .

Проверка: .

  1.  . Если действовать так, как было показано в примере 1, то мы достигнем успеха только на 38-м шаге, поэтому стоит рассмотреть модификации данного метода.

Модификация метода 1. Если не удается быстро подобрать t, то можно рассматривать , где N, или близкие к нему. Тогда . Если полученные таким образом числа  и  не делят n, то берется  или .

Пример. .

Рассмотрим :  – не является квадратом. Возьмем : , т.е. . . Таким образом .

Модификация метода 2. Рассмотрим сравнение , вытекающее из представления n в виде разности квадратов. Его можно переписать в виде . Можно подбирать числа t и s в соответствии с этим сравнением.

Пример.

Рассмотрим : , , т.е. , . . . Таким образом, .

  1.  Метод фактор-базы и его модификации

Вторая простейшая модификация метода Ферма поставила новую проблему: как подобрать числа t и s, заведомо удовлетворяющие сравнению ? Метод фактор-базы решает эту проблему.

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

Пример. .

Выберем базу . Рассмотрим число :

,

т.е. число b можно выбрать в качестве t.

Другие подходящие числа:

,

.

Модификация метода 1. Пусть база . Рассмотрим h-мерное линейное векторное пространство над F2: каждому числу из набора  поставим в соответствие вектор . Если векторы  такие, что , то  можно представить в виде , где степени  – четные. Обозначим . Имеем:

,

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

.

Если это условие выполняется, то b считается подходящим и может быть выбрано в качестве t, а cв качестве s.

Пример. , .

,  

Таблица степеней для разложений :

.

.

Результат: .

Оценка трудоемкости метода фактор-базы составляет , где . В хороших алгоритмах .

Модификация метода 2. Основана на том, что если  – небольшое, то x с большей вероятностью раскладывается в произведение простых чисел. Используя это, в качестве  можно выбирать числа , , N или близкие к ним.

Пример. , .

,

,

,

Аналогично набираются остальные bi, представленные ниже в таблице:

bi

Степени элементов базы в разложении

42

1

0

0

1

0

0

1

43

0

2

0

1

0

0

0

61

0

0

2

0

1

0

0

74

1

0

0

0

0

1

0

85

1

0

0

0

1

0

1

86

0

4

0

1

0

0

0

, ,  ,

т.е. данное b не подходит. Рассмотрим другой вариант.

,  ,  ,

.

В итоге .

Модификация метода 3. В предыдущих модификациях числа из набора  выбирались в основном случайным образом. Данная модификация метода фактор-базы предназначена для поиска таких чисел.

Из теории чисел изветсно, что любое число x раскладывается в непрерывную дробь:

  

  

и т.д.

Такое разложение конечно тогда и только тогда, когда xрациональное число.

Если ввести обозначения , ; , , то дроби вида , где , ,  назыв. подходящими дробями разложения числа x в непрерывную дробь.

Утверждение 8.5 Если  – подходящая дробь, то .

Утверждение 8.6 Если  – подходящие дроби, то : .

Теперь рассмотрим применение этих результатов. Имеется набор чисел  таких, что  разлагается в произведение степеней элементов базы B. Разложим  в непрерывную дробь (скорей всего, она будет бесконечной). По утв. 8.6 имеем:

.

Теперь предположим, что  и будем искать :

,

откуда получаем оценку:

.

  1.  Алгоритм факторизации числа с помощью непрерывных дробей
  2.  Полагаем: , , , .
  3.  Вычисляем .
  4.  Полагаем для  , , .
  5.  Вычисляем (наименьший по абсолютной величине вычет).

Пример.

i

0

1

2

3

4

qi

95

3

1

26

2

i

0

1

2

3

4

bi

95

286

381

1119

2619

i

0

1

2

3

4

-48

139

-7

87

-27

Выбираем базу .

не раскладывается в выбранной базе

не раскладывается в выбранной базе

Рассмотрим сумму .

  1.  

18


 

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

19411. Генезис науки. Основные этапы развития науки 32 KB
  Генезис науки. Основные этапы развития науки. Относительно возникновения науки существуют пять точек зрения: 1Наука была всегда начиная с момента зарождения человеческого общества так как научная любознательность органично присуща человеку; 2Наука возникла в Дре...
19412. Техника. Этапы развития 28 KB
  Техника общее название различных преспособлениймеханизмов и устройствне существуемых в природе и созданных человеком. Техника это судьба человечества сопровождающая его с момента пробуждения сознания. Первоначально в эпоху каменного века техника была орудием уб...
19413. Технические достижения древних земледельческих цивилизаций 31 KB
  Технические достижения древних земледельческих цивилизаций Техника – это совокупность действий знающего человека направленных на господство над природой. Цель их – придать жизни человека такой облик который позволил бы ему снять с себя бремя нужды и обрести нужну
19414. Наука и техника в античном мире 29 KB
  Наука и техника в античном мире. До VII века до н. э. Греция была периферией ближневосточной цивилизации. Греки учились у Востока: они позаимствовали у финикийцев алфавит и конструкцию кораблей у египтян – искусство скульптуры и начала математических знаний. Греция была
19415. Наука и техника эпохи Возрождения 35.5 KB
  Наука и техника эпохи Возрождения. Эпоха Возрождения ─ особый период в европейской истории. С одной стороны это расцвет искусства возрождение античности гуманизм. Но с другой стороны рушились прежние ценности установки. Формировалась новая концепция человека ─ реш...
19416. Научная революция в Европе XVII столетия 31 KB
  Научная революция в Европе XVII столетия. XVII столетие – важнейший этап в развитие научного познания. С этого века начинается процесс утверждения науки в качестве доминирующей формы постижения бытия. В умах людей утверждается представление о познаваемости мир...
19417. Достижения научного и технического прогресса в советском государстве (период НЭПа и форсированной индустриализации) 46.5 KB
  Достижения научного и технического прогресса в советском государстве период НЭПа и форсированной индустриализации. Восстановление страны после гражданской войны преодоление социальноэкономического кризиса в целом к середине 20х гг. завершилось. Но перед советск
19418. Наука в годы Великой Отечественной войны. Роль техники во Второй Мировой войне 28 KB
  Наука в годы Великой Отечественной войны. Роль техники во Второй Мировой войне Важный вклад в победу над фашизмом внесли советские ученые: физики создавали теоретические и экспериментальные предпосылки для конструирования новых видов вооружения; математики разработ
19419. Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации 88 KB
  Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение передача и обработка информации. Общепринятого определения инфо