1 Primality and Factoring + Binary Representation) 1. Use the prime number theor

Question

1 Primality and Factoring + Binary Representation) 1. Use the prime number theorem to estimate the probability that a randomly selected 2. Recall a conversion from binary to decimal and estimate the probability that a randomly 3. Let p(t) be a probability that a randomly selected t-bit string is a (binary representation 4. An algorithm for choosing a random prime of binary length t (i.e. whose binary rep- integer with 100 decimal digits is a prime number selected 1000-bit string is a (binary representation of a) prime number. of a) prime number. Give a formula which estimates p(t) as a function of t. resentation has t bits) performs the following loop: It picks a random t-bit a, runs a primality testing subprocedure on r, and returns r (and breaks the loop) if the primality subprocedure says "yes", and repeats the loop otherwise How many times do you expect this loop to execute until it finds a t-bit prime number?

Explanation / Answer

1)

pi (x) - number of prime number less than x

pi(N) = N/log(N)

probability = pi(N) /N = 1/ (log(N))

here N = 10^100

hence

probability = 1/log(10^100) = 1/ 230.2 = 0.00434294

Please rate

You are allowed to ask one question at time

Please post next questions at time

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.