Alex Rivera | Logout

Generate large prime number with specified last digits

Asked 2010-12-04T17:32:07.313
11

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!

c# java algorithm primes
Edit
Report

1 Answer

2

Let ABCDE be the five digits number in base ten, which you are considering. Based on Dirichlet's theorem on arithmetic progressions, if ABCDE and 100000 are coprime, then there are infinitely many primes of the form 100000*k+ABCDE. Since you are looking for prime numbers, neither 2 nor 5 would divide ABCDE anyway, thus ABCDE and 100000 are coprime. So there are infinitely many primes of the form you are considering.

answered 2010-12-04T22:01:48.183

Your Answer