Если нужно сгенерировать заведомо простое число, то посмотрите на применение методов, использующих разложение числа n-1 на простые множители (так называемые «n-1—методы»). В частности, это
тест Поклингтона. С помощью него достаточно легко строится метод построения последовательности простых чисел теоретически любой длины. ЕМНП некоторая модификация этого метода использовалась в старом отечественном ГОСТ'е на цифровую подпись.
