Score:0

Crypto

The number of odd integers we have to test until to find one that is a prime for any arbitrary RSA modulus size

Mohammadsadeq Borjiyan

4/5/23, 11:30 PM

Popular RSA modulus sizes are $1024$, $2048$, $3072$ and $4092$ bit. How many random odd integers do we have to test on average until we expect to find one that is a prime? I know roughly every $\ln p$ integers has a prime. For a $1024$ bit $p$, $\ln p = 710$. On average, need to test about $710/2=355$ odd numbers before finding a prime. Is it true and can we extract the formula $(\ln p)/2$ for any arbitrary RSA modulus size?

144

0 + 0

rsa

prime-numbers

kelalaka

4/5/23, 11:35 PM

See the question : [Prime number theorem - RSA](https://crypto.stackexchange.com/q/11106/18298)

Mohammadsadeq Borjiyan

4/5/23, 11:47 PM

Thanks. Yes, I know the formula of the prime numbers less than x you mentioned. Now is my conclusion true?

poncho

4/6/23, 4:42 AM

To let the complexity of actual implementations get in the way, we often use sieving to eliminate multiples of small primes (e.g. all small primes less than 10,000); this reduces the expected number of values we need to subject to fuller tests considerably; however it also complicates the simple application of the prime number theorem...

gnasher729

4/6/23, 4:54 AM

Kekalaka you need the natural logarithm.

Score:-1

Crypto

gnasher729

4/6/23, 4:42 AM

For n-bit RSA, you need to find two primes whose product is an n-bit number, that is around n/2 bits each. Actually one a bit smaller and one a bit larger, because you don’t want the primes too close together.

About one in ln M numbers around M is prime; that’s the natural logarithm. ln (2) is close to 0.7. If M = 2^(n/2), then ln M ≈ 0.35n. You are checking only odd integers which are twice as likely to be prime, with probability 2 / 0.35n. Testing 0.175n odd integers finds a prime. You need two, so about 0.35n.

But note that many of those have small divisors and can be identified very quickly; for example by using a sieve removing numbers with factors < 1000 or 10,000. To accept a prime, you will run the Miller-Rabin test 50 or 100 times, while for 3/4 of the non-primes you run it once, for 3/4 of the rest you run it twice etc. The point is that testing a non-prime for primality is usually quite fast. Testing the two actual primes takes long time. The number of composites that you test for primality doesn’t matter much.

PS I just realised that everyone is overestimating by a factor 2. Say I decided I want a prime near some odd K, so I test K, K+2, K+4 etc until I run into a prime. Let p be the largest prime less than K, and q the first prime >= K. The number of off numbers to test is not the gap q-p, divided by 2 (because we are only testing odd numbers) but half that, because K can be anywhere in that gap.

PPS I just realised there is something wrong with that argument…

0 + 0

j.p.

4/6/23, 7:41 AM

What do you mean with "while for 3/4 of the non-primes you run it once, for 3/4 of the rest you run it twice etc."? It sounds like that you assume that a non-prime passes a Miller-Rabin test with probability 1/4, which is much too high. Unless someone (maybe evil constructing a special number) gave the prime candidate to you, you can be quite confident that a 1000-bit random number passing a Miller-Rabin test is prime. The reason for repeating the MR-tests is to convince an evaluator that the probability for not being prime is *provably* less than - let's say - $2^{-80}$.

poncho

4/6/23, 6:32 PM

This answer also assumes you'll use Miller-Rabin for your primality test; that is not necessarily true. For example, if you're using the Shawe-Taylor algorithm (which starts with a large prime factor of $p-1$), you only need one iteration if you hit a prime. In my experience, the task of building up the increasingly large prime values (to be the large factor of $p-1$ for the next larger prime) is faster than repeated Miller-Rabin.

tylo

4/7/23, 2:58 AM

Half of this answer addresses a question, which was not asked in the question at all.

gnasher729

4/8/23, 7:45 AM

The probability of 3/4 that a composite number fails one Rabin-Miller pass is easy to prove. So at least 3/4 of the numbers you test for primality fail with one pass, 3/4 of the remaining quarter fail in the second pass etc. Only when you test an actual prime do you need many passes. The number of candidates you test is therefore not very relevant; you spend most of the work on the one value that is a prime.

Score:-2

Crypto

tylo

4/6/23, 4:20 AM

No, you're wrong, because

I know roughly every ln p integers has a prime.

is a rough estimate, which is actually wrong.

The estimation of the prime counting function $\Pi(p)=p /ln(p)$ estimates the total primes between 0 and $p$. So for a number with x bits, you need to look at $\Pi(2^{x}) - \Pi(2^{x-1})$ and compare it to the total number of candidates, which are $2^{x-2}$, when you only consider odd numbers.

You are not far off, and the difference is small for large numbers, but the formula isn't that simple.

0 + 0

gnasher729

4/6/23, 4:46 AM

“Roughly”. He’s roughly right. And your exponents are off by one, And the prime counting function doesn’t estimate.

tylo

4/6/23, 12:38 PM

@gnasher729 That's roughly as right as saying $\Pi=3$. You're right about the exponents bring off by one, I have changed that.

Daniel S

4/6/23, 4:11 PM

A more accurate estimate for the prime counting function is $\pi(x)\sim\int_2^x\frac{dt}{\log t}$ which heuristically equates to Gauss’s observation that primes around $t$ have density around $1/\log t$. In other words the estimate in the question is more accurate than $(2^x/(\log 2^x)-2^{x-1}/(\log 2^{x-1}))/2^{x-2}$.

tylo

4/7/23, 3:05 AM

The density at a certain point is not the same as the density over a large interval. And that was the main point here.

Daniel S

4/7/23, 2:27 PM

According to sagemath $\mathrm{li}(2^{1024})-\mathrm{li}(2^{1023})\approx 1.2669e305$, whereas $2^{1023}/1024\log(2)\approx 1.2663e305$ and $2^{1024}/1024\log(2)-2^{1023}/1023\log(2)\approx 1.2651e305$. Note that the error in the $\mathrm{li}(x)$ estimate is (assuming RH) going to be $O(x^{1/2+\epsilon})$ and so less than, say, 1e200. The estimate in the question is more accurate.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: The number of odd integers we have to test until to find one that is a prime for any arbitrary RSA modulus size

TH: จำนวนเต็มคี่ที่เราต้องทดสอบจนกว่าจะพบจำนวนที่เป็นจำนวนเฉพาะสำหรับขนาดโมดูลัส RSA ตามอำเภอใจ

RO: Numărul de numere întregi impare până la care trebuie să testăm pentru a găsi unul care este prim pentru orice dimensiune arbitrară a modulului RSA

RU: Количество нечетных целых чисел, которые мы должны проверить, пока не найдем то, которое является простым для любого произвольного размера модуля RSA.

VI: Số lượng số nguyên lẻ mà chúng ta phải kiểm tra cho đến khi tìm được một số nguyên tố cho bất kỳ kích thước mô đun RSA tùy ý nào

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.