Вы пробовали просто генерировать такие числа и проверять их? Я ожидаю, что это будет приемлемо быстро. Простая плотность уменьшается только как логарифм числа, поэтому я ожидаю, что вы попробуете несколько сотен чисел, пока не достигнете простого. ln(2^512) = 354 так что одно число из 350 будет простым.
Грубо говоря, теорема о простых числах гласит, что если выбрано случайное число около некоторого большого числа N, вероятность его простоты составляет около 1 / ln (N), где ln (N) обозначает натуральный логарифм N Например, около N = 10000, одно из девяти чисел является простым, тогда как около N = 1 000 000 000 только одно из каждых 21 чисел является простым. Другими словами, средний разрыв между простыми числами около N примерно равен ln (N)
(от http://en.wikipedia.org/wiki/Prime_number_theorem)
Вам просто нужно позаботиться о том, чтобы для ваших последних цифр существовал номер. Но я думаю, что это так же просто, как проверить, что последняя цифра не делится на 2 или 5 (т.е. это 1, 3, 7 или 9).
В соответствии с этими данными производительности вы можете выполнить около 2000 операций ModPow с 512-битными данными в секунду, и, поскольку простой простой тест проверяет 2^(p-1) mod p=1, что является одной операцией ModPow, вы должны генерировать несколько простых чисел с вашими свойствами в секунду.
Чтобы вы могли сделать (псевдокод):
BigInteger FindPrimeCandidate(int lastDigits)
{
BigInteger i=Random512BitInt;
int remainder = i % 100000;
int increment = lastDigits-remainder;
i += increment;
BigInteger test = BigInteger.ModPow(2, i - 1, i);
if(test == 1)
return i;
else
return null;
}
И проведите более обширные первичные проверки результата этой функции.