Факторизация целых чисел

Факторизация целых чисел

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

В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей.

Содержание

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

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

L_{N}(\alpha,\;c):=O(\exp((c+o(1))(\log N)^{\alpha}(\log\log N)^{1-\alpha})),

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

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

Экспоненциальные алгоритмы

Субэкспоненциальные алгоритмы

Решето числового поля

В настоящее время самыми эффективными алгоритмами факторизации являются вариации решета числового поля:

Применение в криптографии

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

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Факторизация целых чисел" в других словарях:

  • Факторизация — Эта статья  о математической концепции. Другие значения термина в заглавии статьи см. на Фактор. Иллюстрация полинома x2 + …   Википедия

  • Рекорды факторизации целых чисел — Факторизация простого числа это процесс определения простых чисел, являющихся делителями данного числа. Числа общего вида Первой очень большой распределенной факторизацией была факторизация RSA 129. Это число было разложено между сентябрем 1993… …   Википедия

  • Общий метод решета числового поля — (англ. general number field sieve, GNFS) метод факторизации натуральных чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой[1] Метод… …   Википедия

  • Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом (англ. Daniel Shanks).[1] в 1975 году, как развитие метода факторизации Ферма. Для 32 разрядных компьютерах алгоритмы, основанные на… …   Википедия

  • Простое число — Простое число  это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… …   Википедия

  • Алгоритм Блюма — Алгоритм Блюм  Блюма  Шуба (англ. Algorithm Blum Blum Shub, BBS)  это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). BBS выглядит так: где является… …   Википедия

  • Алгоритм Блюма — Блюма — Шуба — Алгоритм Блюма  Блюма  Шуба (англ. Algorithm Blum Blum Shub, BBS)  это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). BBS выглядит так: где M = pq является… …   Википедия

  • Блюм-Блюм-Шуб — Алгоритм Блюма  Блюма  Шуба (англ. Algorithm Blum Blum Shub, BBS)  это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). BBS выглядит так: где M = pq является произведением… …   Википедия

  • Нерешённые проблемы информатики — В этой статье приводится список нерешённых проблем информатики. В информатике проблема считается нерешенной, если эксперт в этой области считает проблему нерешенной, либо если несколько экспертов расходятся во мнениях по поводу её решения.… …   Википедия

  • IEEE P1363 — IEEE P1363  проект Института инженеров по электротехнике и электронике (англ. Institute of Electrical and Electronics Engineers, IEEE) по стандартизации криптосистем с открытым ключом. Целью проекта было объединение опыта разработчиков… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»