Напівпросте число

Напівпросте число (або біпросте число) — натуральне число, що дорівнює добутку двох простих чисел.

Послідовність напівпростих чисел починається так:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74 .

На лютий 2010 року найбільше відоме напівпросте число дорівнює (2^43112609 − 1)², десятковий запис цього числа складається більш ніж з 25 мільйонів цифр. Воно є квадратом найбільшого відомого простого числа.

Функція Ейлера напівпростих чисел рівна:

φ(p²) = (p − 1) p

φ(pq) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Застосування

Напівпрості числа використовуються в криптографії зокрема у криптосистемах з відкритим ключем таких, як RSA. Причиною цього є те, обчислювальна складність факторизації напівпростого числа утвореного добутком двох великих простих чисел є значно більшою, ніж обчислювальна складність множення цих чисел.

Посилання

Напівпросте число на сайті MathWorld (англ.)
Напівпросте число на сайті PlanetMath (англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.