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

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 x, runs a primality testing subprocedure on r, and returns x (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)

Let (x) be the prime-counting function that gives the number of primes less than or equal to x, for any real number x.

(N) ~ N/log(N),

here N = 10^100

hence required probability

=(N) / N = 1/ (log(N)) = 1 / log(10^100) = 1 / (100 * 2.306 ) = 1/230.6 = 0.0043365

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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