51418

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

Доклад

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

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

Русский

2014-02-11

386.5 KB

16 чел.

Раздел 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


 

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

51368. Исследование начальной остойчивости плавучей полупогружной буровой установки 155 KB
  Ознакомление студентов с особенностями остойчивости плавучих полупогружных буровых установок (ППБУ) и их поведения на взволнованной поверхности моря, изучение основных положений теории и расчета, а также ознакомление с методикой постановки эксперимента по определению параметров начальной остойчивости плавучих технических средств для освоения шельфа.
51369. Двухфазная СМО с отказами 95.5 KB
  Для упрощения расчёта представим данную СМО как совокупность 2ух одноканальных. Т.к. в данной системе очередь не бесконечной длинны, то все расчёты будут не очень точны. Но главная цель проведения данных расчётов – это сравнение их результатов с результатами имитационной модели (программой). Для оценки соответствия результатов такой точности будет достаточно.
51371. РАБОТА С ОДНОМЕРНЫМИ МАССИВАМИ В ЯЗЫКЕ C 487.8 KB
  Варианты для задания 1 Array1. Дано целое число N (>0). Сформировать и вывести целочисленный массив размера N, содержащий N первых положительных нечетных чисел:
51372. РАБОТА С МАТРИЦАМИ В ЯЗЫКЕ C 120.29 KB
  В соответствии со своим вариантом для задачи 1 составить: Алгоритм решения задачи, в котором предусмотреть использование следующих функций: 1) функция формирования матрицы, предусмотреть формирование матрицы с клавиатуры и с помощью генератора псевдослучайных чисел;