I am stuck with a question with regards to finding an example of 10 digit safe prime number. I need the number for cryptography purposes. (for Diffie-Hellman key exchange)
I know that a safe prime is derived as such: safe prime = (p x 2) + 1
where safe prime is a prime number , and p is a prime number as well.
I have googled for quite awhile and haven't found any solution yet. Help is much appreciated. Thanks!
On
According to MathStudio's prime checker, $\ p=1,000,000,007\ $ is the smallest 10-digit prime, and $\ \frac{p-1}{2}=500,000,003\ $ is also prime, which would make $\ p\ $ the smallest 10-digit safe prime number.
On
For $10$ digits about one number in $\log(3\cdot 10^9) \approx 22$ is prime. If you limit yourself to numbers of the form $6k+1$ or $6k+5$ about one in $8$ is prime, so just start trying them. Note that if your first prime is of the form $6k+1$, doubling it and adding one makes a multiple of $3$, so your first prime should be of the form $6k+5$. The second will be of this form as well. It should only take about $64$ tries, on average, to find one.
For $10$ digits about one number in $\log(3\cdot 10^9) \approx 22$ is prime. If you limit yourself to numbers of the form $6k+1$ or $6k+5$ about one in $8$ is prime because you have avoided factors of $2$ and $3$, so just start trying them. Note that if your first prime is of the form $6k+1$, doubling it and adding one makes a multiple of $3$, so your first prime should be of the form $6k+5$. The second will be of this form as well. It should only take about $64$ tries, on average, to find one.