TABLE OF CONTENTS We call strong prime an odd prime n such that 
is prime as well. Prove that we can (heuristically) generate -bit strong primes within a time complexity of O( ? 5).
Hint: Make the heuristic assumption that m and 2 m + 1 behave like independent random odd numbers when m is a random odd number.
Assume we have a table S of n Boolean elements. We consider the five following algorithms.
<b class="bold">Algorithm A<i class="emphasis">:</i></b> <i class="emphasis">1: </i><b class="bold">for</b> <i class="emphasis">i </i>= 1 <i class="emphasis">to n </i><b class="bold">do</b> <i class="emphasis">2: S</i>[<i class="emphasis">i </i>] <span class="unicode">?</span> true <i class="emphasis">3: </i><b class="bold">end for</b> <i class="emphasis">4: S</i>[1] <span class="unicode">?</span> false <i class="emphasis">5: </i><b class="bold">for</b> <i class="emphasis">i </i>= 2 to <i class="emphasis">n </i><b class="bold">do</b> <i class="emphasis">6: </i><b class="bold">if</b> <i class="emphasis">S</i>[<i class="emphasis">i </i>] <b class="bold">then</b> <i class="emphasis">7: </i><b class="bold">for</b> <i class="emphasis">j </i>= 2<i class="emphasis">i </i>to <i class="emphasis">n </i>by step of <i class="emphasis">i </i><b class="bold">do</b> <i class="emphasis">8: S</i>[ <i class="emphasis">j </i>] <span class="unicode">?</span> false <i class="emphasis">9: </i><b class="bold">end for</b><i class="emphasis">10: </i><b class="bold">end if</b><i class="emphasis">11: </i><b class="bold">end for</b><i class="emphasis">12: </i><b class="bold">for</b> <i class="emphasis">i </i>= 1 to <i class="emphasis">n </i><b class="bold">do</b><i class="emphasis">13: </i><b class="bold">if</b> <i class="emphasis">S</i>[<i class="emphasis">i </i>] <b class="bold">then</b><i class="emphasis">14:...
