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

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

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

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 року найбільше відоме напівпросте число дорівнює (243112609 − 1)2, десятковий запис цього числа складається більш ніж з 25 мільйонів цифр. Воно є квадратом найбільшого відомого простого числа.

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

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

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

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

Посилання

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