Прості числа. Що про них відомо сьогодні?

В попередній статті розповідалося про число Пі, зараз ми поговоримо про прості числа. Кожен знає, що прості числа - такі числа, які діляться тільки на одиницю і самих себе. Але чи так вони прості, як здаються, і чи актуальні сьогодні? Спробуємо розібратися.

Історія

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 ...

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

Мабуть, уже під час Ератосфена стало ясно, що якого-небудь чіткого критерію, чи є число простим, не існує - це можна перевірити лише експериментально. Існують різні способи для спрощення процесу (наприклад, очевидно, що число не повинно бути парним), але простий алгоритм перевірки не знайдений досі, і швидше за все знайдений не буде: щоб дізнатися, просте число чи ні, треба спробувати розділити його на все менші числа.

Чи підкоряються прості числа будь-яким законам? Так, і вони досить цікаві.

Так, наприклад, французький математик Мерсенн ще в 16 столітті виявив, що багато простих чисел має вигляд 2 ^ N - 1, ці числа названі числами Мерсенна. Ще незадовго до цього, в 1588 році, італійський математик Катальді виявив просте число 2 ^ 19 - 1 = 524 287 (за класифікацією Мерса воно називається M19). Сьогодні це число здається вельми коротким, проте навіть зараз з калькулятором перевірка його простоти зайняла б не один день, а для 16 століття це було дійсно величезною роботою.

На 200 років пізніше математик Ейлер знайшов інше просте число 2 ^ 31 - 1 = 2147483647. Знову ж таки, необхідний обсяг обчислень кожен може уявити сам. Він же висунув гіпотезу (названу пізніше «проблемою Ейлера», або «бінарної проблемою Гольдбаха»), суть якої проста: кожне парне число, більше двох, можна представити у вигляді суми двох простих чисел.

Наприклад, можна взяти 2 будь-яких парних числа: 123456 і 888 777 888.

За допомогою комп'ютера можна знайти їх суму у вигляді двох простих чисел: 123456 = 61813 + 61643 і 888 777 888 = 444 388 979 + 444388909. Цікаво тут те, що точне доказ цієї теореми не знайдено досі, хоча за допомогою комп'ютерів вона була перевірена до чисел з 18 нулями.

Існує й інша теорема математика П'єра Ферма, відкрита в 1640 році, яка говорить про те, що якщо просте число має вигляд 4 * k + 1, то воно може бути представлено у вигляді суми квадратів інших чисел. Так, наприклад, у нашому прикладі просте число 444388909 = 4 * 111 097 227 + 1. І дійсно, за допомогою комп'ютера можна знайти, що 444388909 = 19197 * 19197 + 8710 * 8710.

Теорема була доведена Ейлером лише через 100 років.

І нарешті Бернгардом Ріманом в 1859 році була висунута так звана «Гіпотеза Рімана» про кількість розподілу простих чисел, що не перевершують деяке число. Ця гіпотеза не доведена до сих пір, вона входить в список семи «проблем тисячоліття», за рішення кожної з яких Математичний інститут Клея в Кембриджі готовий виплатити нагороду в один мільйон доларів США.

Так що з простими числами не все так просто. Є й дивовижні факти. Наприклад, в 1883 р російський математик І.М. Первушин з Пермського повіту довів простоту числа 2 ^ 61 - 1 = +2305843009213693951. Навіть зараз побутові калькулятори не можуть працювати з настільки довгими числами, а на той час це була воістину гігантська робота, і як це було зроблено, що не дуже зрозуміло досі. Хоча дійсно існують люди, що володіють унікальними здібностями мозку - так наприклад, відомі аутисти, здатні знаходити в розумі (!) 8-значні прості числа. Як вони це роблять, незрозуміло.

Сучасність

Чи актуальні прості числа сьогодні? Ще й як! Прості числа є основою сучасної криптографії, так що більшість людей користуються ними щодня, навіть не замислюючись про це. Будь-який процес аутентифікації, наприклад, реєстрація телефону в мережі, банківські платежі та інше, вимагають криптографічних алгоритмів.

Суть ідеї тут вкрай проста і лежить в основі алгоритму RSA, запропонованого ще в 1975 році. Відправник і одержувач спільно вибирають так званий «закритий ключ», який зберігається в надійному місці. Цей ключ являє собою, як, напевно, читачі вже здогадалися, просте число. Друга частина - «відкритий ключ», теж просте число, формується відправником і передається у вигляді твору разом з повідомленням відкритим текстом, його можна опублікувати навіть в газеті. Суть алгоритму в тому, що не знаючи «закритої частини», отримати вихідний текст неможливо.

Наприклад, якщо взяти два простих числа 444388979 і 444388909, то «закритим ключем» буде 444388979, а відкрито будуть передано твір +197481533549433911 (444388979 * 444388909). Лише знаючи другу половинку, можна обчислити відсутнє число і розшифрувати їм текст.

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

Геніальність даної схеми в тому, що в самому алгоритмі немає нічого секретного - він відкритий і всі дані лежать на поверхні (і алгоритм, і таблиці великих простих чисел відомі). Сам шифр разом з відкритим ключем можна передавати як завгодно, в будь-якому відкритому вигляді. Але не знаючи секретної частини ключа, яку обрав відправник, зашифрований текст ми не отримаємо. Для прикладу можна сказати, що опис алгоритму RSA було надруковано в журналі в 1977 році, там же було наведено приклад шифру. Лише в 1993 році за допомогою розподілених обчислень на комп'ютерах 600 добровольців, був отриманий правильну відповідь.

Так що прості числа виявилися зовсім не настільки прості, і їх історія на цьому явно не закінчується.