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

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

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

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. Причиною цього є те, обчислювальна складність факторизації напівпростого числа утвореного добутком двох великих простих чисел є значно більшою, ніж обчислювальна складність множення цих чисел.

Посилання

• Напівпросте число [Архівовано 7 вересня 2019 у Wayback Machine.] на сайті MathWorld (англ.)
• Напівпросте число [Архівовано 11 лютого 2010 у Wayback Machine.] на сайті PlanetMath (англ.)