Означення простого числа
Криптографія використовує дуже великі прості числа. На жаль, використання стандартних засобів мов програмування надає можливість працювати лише з такими цілими числами, значення яких не виходять за межі довгого цілого типу LongInt, для якого найбільше домустиме значення становить 2147483647. При цьому найбільше ціле число рівне 2147302891(просте), що далеко не задовольняє потреби криптографії. Саме тому дуже важливо розробляти швидкодіючі алгоритми обробки простих чисел.
Означення. Натуральне число р>1 називається простим, якщо воно не має інших натуральних дільників, крім 1 і р. Простим числом буде найменший, відмінний від 1 дільник цілого а, а>1.
Теорія чисел визначає прості числа наступним чином:
всі натуральні числа, крім 1, мають, щонайменше, двох дільників – одиницю та самого себе;
ті з них, що не мають ніяких інших дільників, називаються простими; наприклад, декілька перших простих чисел 2, 3, 5, 7, 11, 13, 17, 19;
ті числа, які мають ще й інших дільників, називаються складеними; наприклад, 12 – складене число (його дільники 1, 2, 3, 4, 6, 12);
число 1 розглядають окремо, не відносячи ні до простих, ні до складених, оскільки одиниця не має всіх властивостей, справедливих для всіх інших простих чисел.
Означення. Натуральні числа a і b, для яких НСД(a,b)=1, називаються взаємно простими.
Закономірності в розподілі простих чисел на даний час ще не знайдено.
Теорема. Існує нескінченно багато простих чисел.
Теорема. Будь-яке ціле число більше від одиниці розкладається на добуток простих множників. Цей розклад єдиний з точністю до порядку слідування множників.
-
Yandex.RTB R-A-252273-3