Difficulty in the calculation of accuracy in an RP-algorithm

Esha

3/8/24, 2:17 PM

I am studying about RP-algorithm from the book Algebraic Aspects of Cryptography by Neal Koblitz.

The following example is given in the beginning which is the Probabilistic Primality Test.

I understand the scheme of the algorithm but I am facing difficulty in understanding and deducing the probability that given the number $N$ passes the Fermat Strong Primality Test k-times, $N$ is actually prime. How are they getting the number $1-4^{-k}$ ?

I tried several times to calculate this but I think I need some guidance in doing this.

Any help will be highly appreciated.

1 + 1

probability

poncho

4/7/24, 8:26 PM

Is your question "why is the probability of a composite number successfully passing a single iteration $< 4^{-1}$"? Or, is it rather "I understand that for a single iteration, but why is the probability for $k$ iterations $< 4^{-k}$? Why are the probabilities independent?"

Score:1

Crypto

swineone

3/8/24, 5:58 PM

If a candidate passes the Miller-Rabin test for one choice of $a$, say $a_0$, then according to the theorem at the start of page 46, its probability of being composite is $\leq 25\% = 1/4$.

If it passes the test for a second choice of $a$, say $a_1$, then by the same theorem, it has a further $\leq 25\% = 1/4$ probability of being composite. Combining the two results, one arrives at a $\leq 1/4 \times 1/4 = 1/4^2$ probability.

In general, for $k$ choices of $a$, the probability is brought down to $\leq 1/4^k = 4^{-k}$. Given that an integer is either composite or prime, then if its probability of being composite is $\leq 4^{-k}$, then the probability of being prime is $> 1 - 4^{-k}$.

+ 2

Esha

3/9/24, 2:07 AM

Then why can't I calculate the probability of it being prime in the same way as greater than equal to $(3/4)^k$ ? Why do I have to do it the opposite way?

swineone

3/9/24, 3:30 AM

This is a basic high-school algebra question. Have you tried picking any $k > 1$ and seeing whether the results match?

Elon Musk

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

EN: Difficulty in the calculation of accuracy in an RP-algorithm

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.