Есть ли метод генерации большого простого числа с факторизацией p — 1?
Для изобретения велосипеда и обучения тому, как всё это работает, генерить большие числа не требуется.
Если уж очень хочется - то вот, ознакомьтесь. Ну и либо Решето Аткина, ну или того же Эратосфена.
Это первое. 
Второе: никогда, никогда, никогда, никогда, никогда не пытайтесь реализовать криптографические алгоритмы для любых целей, кроме образовательных. Никогда не используйте собственную реализацию для защиты хоть чего-либо важного. Я вас, конечно, не знаю, но докторской степени по математике и нескольких лет опыта в криптографии и криптоанализе у вас, скорее всего, нет.
Можно такой подход: Сгенерируйте два случайных простых числа длиной n/2 бит (Генерируйте случайное число, пока не получили простое). Потом перемножте их, прибавьте 1 и проверьте, что тоже результат простой.

Для этого надо уметь относительно быстро проверять что число простое. Можно использовать метод Миллера-Рабина. Он вероятностный, но увеличивая число итераций можно достичь произвольно маленькой вероятности ошибки.