Khimik:

K>На каком этапе здесь математические операции — перемножение чисел и разложение чисел на простые множители?

Если про RSA, разложение на простые множители нужно только на этапе взлома.

На этапе генерации пары ключей выбираются два случайных простых числа. Проверка на простоту работает гораздо быстрее чем разложение на множители.