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


 

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

29374. Фазы трансляции программ 32.5 KB
  На вход лексического анализатора подаётся последовательность символов входного языка. ЛА выделяет в этой последовательности простейшие конструкции языка которые называют лексическими единицами лексемами. Генератор каждому символу действия поступающему на его вход ставит в соответствие одну или несколько команд выходного языка. В качестве выходного языка могут быть использованы команды устройства команды ассемблера либо операторы какоголибо другого языка.
29375. Основные функции сканера 34 KB
  Лексический анализ программ – один из основных этапов фаз трансляции программ – выделение в исходной программе элементарных единиц языка таких как идентификаторы константы ключевые слова символы операций разделители и др. Лексический анализ завершается преобразованием выделенных единиц языка в некоторую унифицированную форму обычно числовую.Часть транслятора которая выполняет лексический анализ называется сканером лексический анализатор. Лексический анализатор сканер должен распознать идентификаторы константы ключевые слова...
29376. Принципы работы сканера 95.5 KB
  Синтаксис целых констант представляется: целое ::=цифра знак цифра целое цифра знак ::= Для представления грамматики состояния целых констант диаграмма имеет вид:Вершины соответствуют состояниям автомата и определяются нетерминальными символами. Построим диаграмму состояний для автомата который распознает лексемы трех типов: целые константы десятичные константы идентификаторы идентр ::=буква идентр буква идентр цифра десятичная константа: дес.число цифра смеше число цифра смеше число ::= целое целое ::=цифра знак цифра целое цифра...
29377. Нисходящий грамматический разбор с возвратами 83 KB
  Суть данного метода можно представить в виде следующей последовательности шагов выполнение которых повторяется в процессе чтения входной цепи символов. Если активная вершина помечена а T то сравнить его с очередным символом входной цепочки. Сравниваемые символы совпали тогда сделать активной вершиной дерева лист правее а и перейти к следующим символам входной цепочки. Символы не совпали то выполним возврат к предыдущему уровню дерева разбора и соответствующему символу входной цепочки.
29378. Грамматический разбор методом операторного предшествования 68.5 KB
  Метод операторного предшествованияДанный метод относится к классу восходящих методов синтаксического анализа.Дерево разбора:Идея метода: входная цепочка символов просматривается слева направо пока не будет найдено подвыражение имеющее более высокий уровень предшествования чем соседние операторы. Для реализации метода необходимо установить отношение предшествования между всеми парами операторов грамматики.
29379. Основные функции и построение семантического анализатора программ 43 KB
  При работе семантических программ широко используется набор данных с организацией в виде стека. Операнды переписываются в выходную строку а операторы заносятся в стек. В зависимости от приоритета операторов при записи в стек оператор может вытолкнуть из стека другой оператор который последовательно записывается в выходную строку. Работа со стеком организуется так:1.
29380. Семантическое дерево как форма представления программ в языковых процессорах САПР 38 KB
  Семантическое дерево 2 польская запись 3 список тетрад. Семантическое дерево СД – модифицированное дерево грамматического разбора из которого исключили вершины соответствующие нетерминальным символам.Пример: E→ET TT→TM MM→E a b cabcДерево разбора:При построении СД скобки не требуются т.
29381. Польская запись как форма представления программ в языковых процессорах САПР 24 KB
  операнды следуют в том же порядке что и в исходной записи.Пример: 1 ab – инфиксная форма записи; ab – польская запись постфиксная.2 abc – инфиксная форма записи abc – польская запись.Формально построение польской записи описывается следующим грамматическим правилом: операнд ::= константа идентификатор операнд операнд оператор оператор ::= – Если должны быть учтены операторы с одним операндом то грамматическое правило должно быть расширено с учётом введения таких операторов добавляется бинарный и унарный оператор.
29382. Качества полноценного навыка чтения и пути их формирования 44 KB
  Качества полноценного навыка чтения и пути их формирования Овладение учащимися полноценным навыком чтения является важнейшим условием успешного обучения в школе по всем предметам. Навык чтения – это автоматизированное умение по озвучиванию печатного текста предполагающее осознание идеи воспринимаемого произведения и выработку собственного отношения к читаемому. В методике наряду с термином навык чтения употребляется термин техника чтения. Техника чтения обозначает все три компонента процесса чтения: восприятие произнесение понимание.