Статьи

8.1.2. Тест Ферма

Наиболее развитые вероятностные алгоритмы проверки чисел на простоту основаны на теореме, обратной малой теореме Ферма. Напомним, что если G — мультипликативная группа порядка #G, то ввиду теоремы Лагранжа = 1 для любого элемента aG. Следовательно, если G = (Z/NZ)* — мультипликативная группа кольца вычетов по модулю N, т.е. группа порядка(), то для любого ее элемента а имеет место равенство

8.1.3. Тест Миллера - Рабина

Из-за существования чисел Кармайкла тест Ферма применяют крайне неохотно. Существует модификация теста Ферма, называемая тестом Миллера - Рабина, которая обходит проблему составных чисел, для которых не находится свидетеля. Это не означает, что легко найти свидетеля для каждого составного числа, это значит, что такой свидетель в принципе должен быть. Кроме того, тест Миллера-Рабина принимает составное число за простое с вероятностью 1/4 ,для любого случайного основания а. Поэтому многократное повторение теста позволяет уменьшить вероятность ошибки до любой наперед заданной величины. Приведем тест Миллера - Рабина на псевдокоде.

8.1.4. Доказательство простоты

До сих пор мы говорили только о свидетелях делимости чисел и интерпретировали наличие свидетелей как доказательство того, что тестируемое число является составным. Кроме того, у нас были методы, говорящие о том, что данное число правдоподобно простое, но стопроцентной уверенности в простоте чисел у нас не было (за исключением алгоритма пробного деления). Вероятностные ответы вполне приемлемы, поскольку вероятность того, что составное число выдержит тест Миллера - Рабина с двадцатью основаниями примерно равна, чего никогда не встречается на практике. Но с теоретической точки зрения (и может быть с практической, если Вы одержимы паранойей) этого может оказаться недостаточным. Точнее говоря, нам может потребоваться по-настоящему простое число, а не только правдоподобно простое.

8.2. Алгоритмы факторизации

Методы разложения на множители (или факторизации) можно разделить на средневековые методы, такие как

- пробное деление,

- (Р - 1)-метод,

- (Р + 1)-метод,

- р-метод Полларда;

и современные:

- метод непрерывных дробей (CFRAC),

- квадратичного решета,

8.2.1. Пробное деление

Пробное деление — это самый элементарный алгоритм факторизации. Для разложения числа N на множители поступают следующим образом:

for (p=1l; p<sqrt(N); р++) { е=0;

if ((N mod p)==0) then { while ((N mod p)==0)

{ e=e+l; N=N/p;

}

вывести (р,е);

} }

8.2.2. Гладкие числа

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

8.2.3. (Р — 1)-метод Полларда

Самое известное имя конца двадцатого века, связанное с алгоритмами факторизации, — это имя Джона Полларда. Практически все важные продвижения в факторизации были сделаны им, например,

- (Р — 1)-метод,

- р-метод,

- метод квадратичного решета в числовом поле.

В этом параграфе обсуждается (Р — 1)-метод, а в следующем мы рассмотрим метод квадратичного решета в числовом поле, оставив остальные методы в качестве упражнений.

8.2.4. Разность квадратов

Основной прием в алгоритмах факторизации, известный уже много веков, заключается в генерировании двух целых чисел х и у приблизительно той же величины, что и N, удовлетворяющих условию

(modN).

Применяя формулу сокращенного умножения, получим

8.3. Современные методы факторизации

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

- Выбирают границу гладкости В.

- Вычисляют базу простых чисел, не превосходящих В (или факторбазу F).

- Находят большое количество пар В-гладких чисел х и у, удовлетворяющих условию х — у (mod N). Такие пары называют соотношениями на факторбазе.

8.3.1. Комбинирование соотношений

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

8.4. Метод решета в числовом поле

Квадратичное решето в числовом поле — самый быстрый из известных алгоритмов разложения на множители. Основная его идея состоит в поиске целых чисел х и у, разность квадратов которых делится на N. Как уже было сказано, после этого можно надеяться, что НОД (х — y, N) — нетривиальный делитель числа N.

<< [Первая] < [Предыдущая] 1 2 3 4 5 6 7 8 [Следующая] > [Последняя] >>

Результаты 92 - 182 из 667

Линейная алгебра
Линейная алгебра – это направление в области математики, в основе которого лежит теория линейной структуры. Аксиоматическая обработка линейной структуры основана в вою очередь на понятиях линейного ...

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

Календарь
Календарь — это система организации дней в соответствии с социальной, религиозной, коммерческой или административной составляющими общественной жизнедеятельности. Такая система подразумевает опреде...