Два приклади: факторизація та НСД

Класичні комп'ютери, що існують сьогодні, неймовірно швидкі, і їхня швидкість, здається, невпинно зростає. З цієї причини дехто може вважати, що комп'ютери настільки потужні, що жодна обчислювальна задача не є для них недосяжною.

Це переконання хибне. Деякі обчислювальні задачі настільки складні, що, хоча для їх розв'язання й існують алгоритми, жоден комп'ютер на планеті Земля сьогодні не є достатньо швидким, щоб запустити ці алгоритми до завершення навіть на вхідних даних помірного розміру за час людського життя — або навіть за час існування самої Землі.

Для подальшого пояснення введемо задачу цілочислельної факторизації.

Цілочислельна факторизація

Вхідні дані: ціле число $N\geq 2$
Вихідні дані: розклад $N$ на прості множники

Під розкладом $N$ на прості множники розуміємо список простих дільників числа $N$ та степенів, до яких їх потрібно звести, щоб отримати $N$ при множенні. Наприклад, прості дільники числа $12$ — це $2$ і $3,$ і щоб отримати $12,$ потрібно взяти добуток $2$ у степені $2$ та $3$ у степені $1.$

12 = 2^2 \cdot 3

До упорядкування простих дільників включно, кожне натуральне число $N\geq 2$ має лише один розклад на прості множники — це твердження відоме як основна теорема арифметики.

Для подальшого пояснення цілочислельної факторизації та інших пов'язаних концепцій знадобиться кілька простих демонстрацій коду на Python. Нижче наведено необхідні імпорти.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

Функція factorint з пакета символьної математики SymPy для Python розв'язує задачу цілочислельної факторизації для будь-якого обраного вхідного $N$ . Наприклад, можна отримати розклад числа 12 на прості множники, що природно збігається з вищенаведеним.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Факторизація малих чисел на кшталт $12$ проста, але зі збільшенням числа $N$ задача ускладнюється. Наприклад, запуск factorint на значно більшому числі призводить до помітної затримки на типовому персональному комп'ютері.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Для ще більших значень $N$ задача стає практично нерозв'язною, принаймні наскільки нам відомо. Наприклад, RSA Factoring Challenge — конкурс з факторизації, організований RSA Laboratories з 1991 по 2007 рік, — пропонував грошовий приз $100 000 за факторизацію наступного числа, що містить 309 десяткових цифр (або 1024 біти у двійковому записі). Приз за це число так і не було отримано, а його прості дільники залишаються невідомими.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Не варто навіть намагатися запускати factorint на RSA1024 — він не завершиться за наших поколінь.

Найшвидший відомий алгоритм факторизації великих цілих чисел — метод решета числового поля. Наприклад, число RSA250 з конкурсу RSA, що містить 250 десяткових цифр (або 829 бітів у двійковому записі), було факторизовано цим методом у 2020 році. Обчислення потребувало тисяч людино-років роботи CPU, розподілених між десятками тисяч машин по всьому світу. Ось як можна оцінити ці зусилля, перевіривши розв'язок.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Безпека криптосистеми RSA з відкритим ключем ґрунтується на обчислювальній складності цілочислельної факторизації в тому сенсі, що ефективний алгоритм факторизації зламав би її.

Тепер розглянемо пов'язану, але принципово відмінну задачу — обчислення найбільшого спільного дільника (або НСД) двох цілих чисел.

Найбільший спільний дільник (НСД)

Вхідні дані: невід'ємні цілі числа $N$ та $M,$ принаймні одне з яких є додатним
Вихідні дані: найбільший спільний дільник чисел $N$ та $M$

Найбільший спільний дільник двох чисел — це найбільше ціле число, яке рівно ділить обидва.

Цю задачу легко вирішити за допомогою комп'ютера — її обчислювальна вартість приблизно така ж, як і множення двох вхідних чисел. Функція gcd з модуля math Python обчислює найбільший спільний дільник чисел, значно більших за RSA1024, за частку секунди. (Фактично RSA1024 є НСД двох чисел у цьому прикладі.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Це можливо завдяки дуже ефективним алгоритмам обчислення НСД, найвідомішим з яких є алгоритм Евкліда, відкритий понад 2 000 років тому.

Чи може існувати швидкий алгоритм цілочислельної факторизації, який ми просто ще не відкрили, що дозволить факторизувати великі числа на кшталт RSA1024 за частку секунди? Відповідь — так. Хоча можна було б очікувати, що ефективний алгоритм факторизації, такий само простий і елегантний, як алгоритм Евкліда для обчислення НСД, був би відкритий вже давно, нічого не виключає існування дуже швидкого класичного алгоритму цілочислельної факторизації — крім того, що ми досі не знайшли його. Може, він буде відкритий завтра — але не затримуй дихання. Покоління математиків і вчених-комп'ютерників шукали його, і факторизація чисел типу RSA1024 залишається поза нашими можливостями.