Глава 7 для чого потрібні прості числа

Для чого потрібні прості числа

Пошук простих чисел - принаймні великих простих чисел - досить складне завдання, тому що ще нікому не вдалося знайти формулу або алгоритм, що дозволяє генерувати будь-які прості числа. Але може виникнути логічне запитання: «Для чого потрібно генерувати прості числа?»

На це питання можна дати дві відповіді. Перший з них має теоретичне значення. Спроби генерації простих чисел ведуть до появи нових цікавих інструментів для розрахунків, особливо для комп'ютерних обчислень. Крім того, наявність великого списку простих чисел дозволяє перевіряти теореми, які ще не доведені. Якщо хтось висуває гіпотезу щодо простих чисел, але виявляється, що одне з мільйонів чисел порушує її, то питання знімається. Це стимулює пошук простих чисел різних видів: простих чисел Мерсенна, чисел-близнюків і так далі. Іноді такий пошук перетворюється в змагання, в якому встановлюються світові рекорди і за перемоги присуджуються великі призи.

Прості числа в криптографії

Саме так працюють односторонні функції з потайним входом, які легко застосувати в одному напрямку, але практично неможливо - в зворотному.

Схема, що ілюструє алгоритм Діффі - Хеллмана. Є два абонента, Аліса і Боб, бажаючі спілкуватися потай. Вони відкрито домовляються про двох числах (просте число р і інше число g, що мають певні властивості). І Аліса, і Боб виконують деякі операції з цими числами і з ще одним цілим числом, яке вони тримають в секреті, а потім відкрито посилають один одному результати. Тепер і Аліса, і Боб виконують з отриманим результатом ще одну операцію і отримують один і той же відповідь, який буде для них секретним кодом. Потенційний шпигун, що перехопив результати, послані Алісою і Бобом, не може згенерувати секретний код, маючи лише цю інформацію.

Припустимо тепер, що замість банок з фарбою в магазині знаходяться прості числа. Візьмемо будь-які два, наприклад, 7 і 13, і перемножимо їх (аналогічно змішуванню фарби). В результаті ми отримаємо 7 х 13 = 91.

Тоді виникає питання: чи можна дізнатися, які прості числа були перемножити, щоб в результаті вийшло 91? Для відповіді на нього треба взяти список простих чисел і виконати кілька перевірок. Здавалося б, просте рішення, як і в разі визначення кольору фарб, якщо в магазині було всього близько десятка основних кольорів.

Але з простими числами все набагато складніше.

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

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