У Шнайера этот вопрос хорошо освящен (стр 296 «Прикладной криптографии» — pdf легкой найти). Генерируете случайное p. Сначала проверяете p на четность (по младшему биту). Затем проверяете остаток от деления на 3,5,7,… — первые простые числа кроме 2, меньше 2000. Затем прогоняете 5 тестов Рабина-Миллера (google) для 5 разных случайных чисел a. Если прошел все 5 — можно считать число простым. В целях эффективности можно генерировать небольшие a.
Еще, возможно, вас заинтересует статья об эллиптических кривых —
http://eax.me/elliptic-curves-crypto/. Криптография на ЭК не менее безопасна, чем RSA, но существенно проще в реализации и более эффективна благодаря тому, что ключи длиной 256 бит так же надежны, как RSA ключи длиной 4096 бит.