Generate large prime number with specified last digits

Question

Was wondering how is it possible to generate 512 bit (155 decimal digits) prime number, last five decimal digits of which are specified/fixed (eg. ***28071) ??

The principles of generating simple primes without any specifications are quite understandable, but my case goes further.

Any hints for, at least, where should I start?

Java or C# is preferable.

Thanks!

Answer 1

I guess the only way would be to first generate a random number of 150 decimal digits, then append the 28071 behind it by doing number = randomnumber * 100000 + 28071 then just brute force it out with something like

while (!IsPrime(number))
    number += 100000;

Of course this could take awhile to compute ;-)

Answer 2

Did you try just generating such numbers and checking them? I would expect that to be acceptably fast. The prime density decreases only as the logarithm of the number, so I'd expect you to try a few hundred numbers until you hit a prime. ln(2^512) = 354 so about one number in 350 will be prime.

Roughly speaking, the prime number theorem states that if a random number nearby some large number N is selected, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. For example, near N = 10,000, about one in nine numbers is prime, whereas near N = 1,000,000,000, only one in every 21 numbers is prime. In other words, the average gap between prime numbers near N is roughly ln(N)

(from http://en.wikipedia.org/wiki/Prime_number_theorem)

You just need to take care that a number exists for your final digits. But I think that's as easy as checking that the last digit isn't divisible by 2 or 5 (i.e. it is 1, 3, 7 or 9).

According to this performance data you can do about 2000 ModPow operations on 512 bit data per second, and since a simple prime-test is checking 2^(p-1) mod p=1 which is one ModPow operation, you should be able to generate several primes with your properties per second.

So you could do (pseudocode):

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;
}

And do more extensive prime checks on the result of that function.

Answer 3

As @Doggot said, but start from least possible 150 digit number which ends with 28071, means 100000....0028071, now add it up with 100000 each time and for testing primarily use miller rabin like the code I provided here, It needs some customization. If the return value is true, check it for exact primarily.