Прості числа та їх генератори

ніж 2000-річною історією, основа сучасних систем криптографії. Багато питань, пов'язаних з

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

Греції також встановили нескінченність множини простих чисел і розуміли факт

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

з'явилися в результаті рахунку,називаються  натуральними.  Натуральних
чисел нескінченно багато. Найбільше

натуральне число назвати в принципі неможливо, оскільки нескінченність ряду таких чисел розуміє обов'язкову наявність числа, більшого будь-якого названого на 1. За цих умов правий край ряду натуральних чисел прийнято позначати символом нескінченності (значок ∞).

до класу простих чисел, або до класу складених чисел; відповідно,

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

n може бути представлено у вигляді добутку простих чисел і

притому єдиним чином. Тобто




7 - просте число; ділиться без залишку тільки на 7 і 1
11 - просте число; ділиться без залишку тільки на 11 і 1 
6 - складене число; ділиться без залишку на 6, 3, 2 і 1
9 - складене число; ділиться без залишку на 9, 3 і 1
15 - складене число; ділиться без залишку на 15, 5, 3 і 1

Одиниця умовно вважається простим числом, хоча вона не є ні

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

Двійка - випадок, коли в клас простих чисел потрапило парне число. Взагалі ж серед простих чисел більше немає жодного парного числа, оскільки інші парні числа більші 2 і діляться на 2.

нескінченна множина в тому сенсі, що прості числа продовжують з'являтися

на всьому проміжку ряду натуральних чисел, а не перериваються в натуральному ряду чисел. 
Це випливає з основної теореми арифметики. 
Якщо б поява простих чисел після деякого числа в натуральному ряду припинилася, в ряду чисел виявилися б порожні проміжки, які вже неможливо представити добутком наявних простих чисел.
Приклад. Нехай після 3 прості числа перестають з'являтися. Нам доступно лише три простих числа: 1, 2 і 3. Їхніми добутками можна представити якісь числа в числовому ряду. Легко представити число
4 = 2*2.  Але як бути з числом 5?  З'являється “пустота".

чисел, ми змушені визнати в нашому припущенні на числі 4

закінчення ряду натуральних чисел, тому що такий ряд повинен складатися з простих і складених чисел. Але з прийнятих нами обмежень число 5 не можна визнати простим (прості числа закінчилися на 3) і в той же час це число не потрапляє в клас складених чисел. А значить після числа 4 маємо вже не ряд натуральних чисел.

чисел, ми змушені визнати нескінченність ряду натуральних чисел, оскільки кожне

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