fi:od:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 57 "\n if i > 100 then print(cat(n,` is probably prime `)) fi:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 31 "\n if i > 100 then \+ n else 0 fi:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 5 "\nend:" } {MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 30 "p rimetester(1122334455667789);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 17 "primetester(131);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 286 "" 0 "" {TEXT 296 14 "Finding primes" }{TEXT 296 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 119 "Now that we can te st if a number is prime, we can try to find a prime by testing numbers in order until we find a prime" }{TEXT 292 0 "" }}}{EXCHG {PARA 281 " > " 0 "" {MPLTEXT 1 291 20 "findprime := proc(n)" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 30 "\n local temp, temp2, a, b, c:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n temp := rand(n)():" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 40 "\n print(\"The random number is \", temp):" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n a := 0: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n c:= 0:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 19 "\n while a = 0 do: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 28 "\n b := primetester(temp):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n temp := temp +1:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 14 " \n c := c+1:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 28 "\n if b < > 0 then a := 1: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n fi:od:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 70 "\n print(`After `,c-1,` uns uccessful tries, the prime number is `, b):" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 5 "\n b:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 5 "\nen d:" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 105 "Le t us use this procedure to find an 8 digit prime. We use the Maple co mmand isprime to test our answer." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 16 "findprime(10^8);" }{MPLTEXT 1 291 0 " " }{MPLTEXT 1 291 12 "\nisprime(%);" }{MPLTEXT 1 291 0 "" }}}{SECT 0 {PARA 287 "" 0 "" {TEXT 297 9 "Exercise:" }{TEXT 297 0 "" }}{EXCHG {PARA 282 "" 0 "" {TEXT 292 35 "3) Find two primes with 7 digits." } {TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 0 "" }}}} {EXCHG {PARA 282 "" 0 "" {TEXT 292 160 "As the size of the prime we ar e looking at grows, the number of tries needed also grows. Thus we wa nt to modify the findprime so that it only gives the answer." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 23 "primetester2 := proc(n)" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 17 "\n local i, tem p:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n for i from 2 to 100 d o" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 32 "\n temp := Power(i,n-1) mod n:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 22 "\n if temp <> 1 t hen" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 13 "\n break:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n fi:od:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 57 "\n if i > 100 then print(cat(n,` is probably prime`)) fi:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 31 "\n if i > 100 then n else 0 fi:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 5 "\nend:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 22 "\nfindprime2 := proc(n)" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 30 "\n local temp, temp2, a, b, c :" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n temp := rand(n)():" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 40 "\n print(\"The random number \+ is \", temp):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n a := 0: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n c:= 0:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 19 "\n while a = 0 do: " }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 29 "\n b := primetester2(temp):" }{MPLTEXT 1 291 0 " " }{MPLTEXT 1 291 21 "\n temp := temp +1:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 14 "\n c := c+1:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 28 "\n if b <> 0 then a := 1: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n fi:od:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 70 "\n prin t(`After `,c-1,` unsuccessful tries, the prime number is `, b):" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 5 "\n b:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 5 "\nend:" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 281 "> \+ " 0 "" {MPLTEXT 1 291 18 "findprime2(10^20);" }{MPLTEXT 1 291 0 "" }}} {SECT 1 {PARA 288 "" 0 "" {TEXT 298 9 "Exercise:" }{TEXT 298 0 "" }} {EXCHG {PARA 282 "" 0 "" {TEXT 292 50 "4) Find primes with 10, 20, 30, 40, and 50 digits." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 0 "" }}}}}{SECT 1 {PARA 283 "" 0 "" {TEXT 293 25 "Oops \+ - Carmichael numbers" }{TEXT 293 0 "" }}{EXCHG {PARA 282 "" 0 "" {TEXT 292 72 "Let us try our test on 3828001 = 101*151*251 which is cl early not prime." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 56 "primetester(3828001): isprime(3828001);ifactor(3828 001);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 396 "The number 3828001 was specially chosen so that the order of the mult iplicative group divides n-1 even though n is not prime. Such numbers are called Carmichael numbers. We would still spot the that n is not prime if we tested a number that is not relatively prime to n. Unfor tunately, n was chosen so that its smallest prime factor is 101. Thus we need to use the more sensitive Miller test." }{TEXT 292 0 "" }}} {EXCHG {PARA 289 "" 0 "" {TEXT 299 35 "The Miller-Rabin Test of primal ity." }{TEXT 299 0 "" }}}{EXCHG {PARA 290 "" 0 "" {TEXT 300 122 "We al so want to see what happens with the more sophisticated test, the Mill er-Rabin test. For that test we factor n-1 as " }{XPPEDIT 18 0 "k*2^t " "6#*&%\"kG\"\"\")\"\"#%\"tGF%" }{TEXT 300 206 " for some odd number \+ k. We then look at a raised to the powers k, 2*k, 2^2*k, ..., 2^t*k = n-1. If n is prime, then a^(n-1) = 1 mod n. Additionally, if a^(2j) = 1 mod n, then a^j mod n is either 1 or -1." }{TEXT 300 0 "" }} {PARA 290 "" 0 "" {TEXT 300 51 "We illustrate this test with n=77. We notice that " }{XPPEDIT 18 0 "76 = 2^2*19" "6#/\"#w*&\"\"#F&\"#>\"\" \"" }{TEXT 300 66 ". Thus we want to look at raising a to the powers \+ 19, 38, and 76." }{TEXT 300 0 "" }}{PARA 282 "" 0 "" {TEXT 292 290 "Fo r the Miller-Rabin test with a to fail to show n is composite,we need \+ the last power to be 1. We also need for the previous power, if it ex ists, to be 1 or -1. Recall that 76 = -1 mod 77. Equivalently, the t est fails if the 19th power is 1, or if either the 19th, or 38th power s is -1." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 19 "gammas := map(i -> " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 72 " \n [i, Power(i,19) mod 77, Power(i,38) mod 77, Power(i,76) mod 7 7]," }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n alphas);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 156 "Thus, \+ the test shows 77 is not a prime unless we choose a to be 1 or -1. In effect the test shows that n is composite if we choose any a between \+ 2 and n-2." }{TEXT 292 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 313 "To do the Miller-Rabin test we first need to express n-1 as an odd nu mber times a power of 2. We do that with the procedure oddfactor. Th e procedure WitnessTest below performs the Miller-Rabin test and look \+ for numbers from 2 to 100 (or n-2 if it is lower) that fails to witnes s to the fact that n is composite." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 22 "WitnessTest := proc(n)" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 50 "\n local n1, witnesslist, witnesslist2, \+ liarlist, " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 33 "\n liarlist2, \+ inconlist, i, k, " }{MPLTEXT 1 291 20 "numliar, numwitness," } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 5 "\n " }{MPLTEXT 1 291 13 "num incon, m, " }{MPLTEXT 1 291 32 "testlist, testlength, a, p1,top:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 23 "\n top := min(n-1,101):" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 13 "\n n1 := n-1:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n k := n1:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 44 "\n while ((k mod 2) = 0) do k := k/2 end do:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 28 "\n# find the odd factor of n1" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n witnesslist := []:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 18 "\n liarlist := []:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n inconlist" }{MPLTEXT 1 291 7 " := []:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 39 "\n# First w e check if a^k = 1 mod n. " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 54 " \n# We break the numbers 2 to 100 into three groups, " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 41 "\n# those that witness n is composite, " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 66 "\n# those that are not \+ yet witnesses, but may be with more work," }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 65 "\n# and those that fail to witness that n is com posite (liars)." }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 29 "\n for i fr om 2 to (top-1) do" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n p1 \+ := " }{MPLTEXT 1 291 17 "Power(i,k) mod n:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 45 "\n if ((p1 = 1) or (p1 = n1)) then liarlist" } {MPLTEXT 1 291 8 " := [op(" }{MPLTEXT 1 291 8 "liarlist" }{MPLTEXT 1 291 6 "), i]:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n else " } {MPLTEXT 1 291 9 "inconlist" }{MPLTEXT 1 291 8 " := [op(" }{MPLTEXT 1 291 9 "inconlist" }{MPLTEXT 1 291 6 "), i]:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 12 "\n end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n end do:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 40 "\n numl iar := linalg[vectdim](liarlist):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 42 "\n numincon := linalg[vectdim](inconlist):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 39 "\n# Print the results up to this stage" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 62 "\n print(cat(\"Testing a^\",k ,\" shows a is not a witness for \", " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 13 "\n numliar," }{MPLTEXT 1 291 13 "\" numbers\"));" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 19 "\n print(liarlist);" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 53 "\n print(cat(\"The test is in conclusive so far for \", " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 27 " \n numincon,\" numbers\"));" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 20 "\n print(inconlist);" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n m := 2*k:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 60 "\n# The next s tep check to see if a^m = -1 when m = k*2^i." }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 20 "\n while (m < n1) do" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 17 "\n testlist := " }{MPLTEXT 1 291 9 "inconlist" } {MPLTEXT 1 291 2 ": " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 45 "\n t estlength := linalg[vectdim](testlist);" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 21 "\n liarlist2 := []:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 24 "\n witnesslist2 := []:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 21 "\n inconlist := []:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 34 "\n for i from 1 to testlength do" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 24 "\n a := testlist[i]:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 31 "\n p1 := Power(a, m) mod n:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n if (p1 = n1) then " } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 16 "\n liar" }{MPLTEXT 1 291 28 "list2 := [op(liarlist2), a]:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 25 "\n elif (p1 = 1) then" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 19 "\n witness" }{MPLTEXT 1 291 31 "list2 := \+ [op(witnesslist2), a]:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n \+ else " }{MPLTEXT 1 291 32 "inconlist := [op(inconlist), a]:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 14 "\n end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n end do:" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 43 "\n numliar := linalg[vectdim](liarlist2):" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 49 "\n numwitness := linalg[vec tdim](witnesslist2):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 60 "\n p rint(cat(\"Testing a^\",m,\" shows a is a witness for \", " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 19 "\n numwitness, " }{MPLTEXT 1 291 24 "\" additional numbers\"));" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n print(witnesslist2);" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 64 "\n print(cat(\"Testing a^\",m,\" shows a is not a witness for \+ \", " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 16 "\n numliar, " } {MPLTEXT 1 291 24 "\" additional numbers\"));" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 22 "\n print(liarlist2);" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 47 "\n liarlist := [op(liarlist), op(liarlist2)]:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 56 "\n witnesslist := [op(witne sslist), op(witnesslist2)]:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 14 " \n m := m*2:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n end do:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 44 "\n numwitness := linalg[vec tdim](inconlist):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 62 "\n print( cat(\"We have \", numwitness, \" additional witnesses \"," }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 47 "\n \"not already ruled out before m \+ = \", n1));" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 20 "\n print(inconl ist);" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 40 "\n numliar := linalg[ vectdim](liarlist):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 58 "\n prin t(cat(\"The test fails for \", numliar,\" numbers\"));" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n print(sort(liarlist));" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\nend proc:" }{MPLTEXT 1 291 0 "" }}} {EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 21 "WitnessTest(3828001);" } {MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 186 "Theoretic arguments say tha t 3 of 4 numbers will witness that n is composite. Note that in our t est case only 19 of the numbers from 2 through 100 fail to witness tha t n is not prime. " }{TEXT 292 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 259 "Compare the results to a few other Carmichael numbers. \+ With two Carmichael numbers we note that the first primality test fai ls to identify them as composite numbers, then note that the Miller te st does identify them as composites, then we factor the numbers." } {TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 63 "primet ester(6733693): WitnessTest(6733693): ifactor(6733693);" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 65 "\nprimetester(34657141): WitnessTest(34 657141): ifactor(34657141);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 118 "In these two cases respectively 86% and 82% of \+ the numbers from 2 to 100 are witnesses that the numbers are not prime ." }{TEXT 292 0 "" }}}{SECT 0 {PARA 291 "" 0 "" {TEXT 301 8 "Exercise" }{TEXT 301 0 "" }}{EXCHG {PARA 282 "" 0 "" {TEXT 292 201 "5) Pick 3 \+ random 50 digit numbers. Test if each to see if it is prime and if it is composite, note the percentage of choices of a from 2 to 100 that \+ will show they are composite with the Miller test." }{TEXT 292 0 "" }} }{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 0 "" }}}}{EXCHG {PARA 282 " " 0 "" {TEXT 292 330 "It is worth noting that we have yet to find a co mposite n that we can't show to be composite by testing the number 2. \+ Such a number would be called a strong probable-prime base 2. It has been shown in the literature that letting the base range over the pri mes less than 20 will correctly identify all composites less than 10^1 5." }{TEXT 292 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 132 "We can \+ clean up the code and give a better prime finding routine. In particu lar we eliminate the printing of the unsuccessful tries" }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 23 "primetester4 := pr oc(n)" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 30 "\n local a, temp, tem p2, k, m:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 14 "\n temp2 := n:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n k:= n-1:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 41 "\n while (k mod 2 = 0) do k:= k/2 end do:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n for a from 2 to 100 do" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n m := k:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 30 "\n temp := Power(a,k) mod n:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 49 "\n if ((temp = 1) or (temp \+ = n-1)) then break:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n e lse " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 25 "\n while (m < n-1) do" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 18 "\n m := 2*m:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 37 "\n temp := Power(temp,2 ) mod n:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 36 "\n if (temp \+ = n-1) then break:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 52 "\n \+ elif (temp = 1) then temp2 := 0: break: " }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 16 "\n end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 14 "\n end do:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 61 "\n if ((m = n-1) and (temp <> 1)) then temp2 := 0 end if:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 12 "\n end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 38 "\n if (temp2 = 0) then break end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n end do:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n temp2;" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\nend proc:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 22 "\nfindpr ime4 := proc(n)" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 23 "\n local te mp, a, b, c:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 21 "\n temp := ran d(n)():" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 37 "\n temp := temp + ( 1 - irem(temp,2)):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 40 "\n print (`the random number is `, temp):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 11 "\n a := 0: " }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 9 "\n c:= \+ 0:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 19 "\n while a = 0 do: " } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 31 "\n b := primetester4(temp ):" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 23 "\n temp := temp +2:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 16 "\n c := c+1:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 37 "\n if b <> 0 then a := 1: end if:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\n end do:" } {MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 70 "\n print(`After `,c-1,` unsuc cessful tries, the prime number is `, b):" }{MPLTEXT 1 291 0 "" } {MPLTEXT 1 291 5 "\n b:" }{MPLTEXT 1 291 0 "" }{MPLTEXT 1 291 10 "\ne nd proc:" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 31 "findprime4(10^100); isprime(%);" }{MPLTEXT 1 291 0 "" }}} {SECT 1 {PARA 292 "" 0 "" {TEXT 302 9 "Exercise:" }{TEXT 302 0 "" }} {EXCHG {PARA 282 "" 0 "" {TEXT 292 69 "6) Use the findprime4 procedur e to find 60, 70, and 80 digit primes." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 0 "" }}}}}{SECT 1 {PARA 283 "" 0 "" {TEXT 293 32 "Maple's method of finding primes" }{TEXT 293 0 "" }} {EXCHG {PARA 282 "" 0 "" {TEXT 292 74 "It is worthwhile seeing how Map le finds primes with the nextprime command." }{TEXT 292 0 "" }}} {EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 25 "nextprime(rand(10^10)()) ;" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 55 "We c an look at the code used with the showstat command." }{TEXT 292 0 "" } }}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 20 "showstat(nextprime);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 184 "This i s essentially the same algorithm we used. From the starting point, ch eck odd numbers going up until a prime is found. We then want to see \+ how Maple checks if a number is prime." }{TEXT 292 0 "" }}}{EXCHG {PARA 281 "> " 0 "" {MPLTEXT 1 291 18 "showstat(isprime);" }{MPLTEXT 1 291 0 "" }}}{EXCHG {PARA 282 "" 0 "" {TEXT 292 487 "The isprime rout ine first check if the test candidate n is in the list of primes below 100. If not it checks to see if any of those primes divide n by comp uting the gcd of n and the product of primes less than 100, thus testi ng if n is a prime less than (101)^2. If not, it computes the gcd of \+ n and the product of primes less than 1000 to test for primes less tha n (1009)^2. Failing to find that n has any small factors, Maple then \+ turns to techniques beyond the scope of this class " }{TEXT 292 0 "" } }}{EXCHG {PARA 293 "> " 0 "" {MPLTEXT 1 303 0 "" }}}}{PARA 294 "" 0 "" {TEXT 204 0 "" }}{PARA 295 "" 0 "" {TEXT 275 0 "" }}{PARA 296 "" 0 "" {TEXT 253 0 "" }}{PARA 297 "" 0 "" {TEXT 304 0 "" }}{PARA 298 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 15 10 1804 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }ղ纤,ȹؽҶ]9E;DD?;=40-53(%.1),'&'861,)-0**221./,+15.0464;34CH᳝ȸ÷̸\D;mY쮔ޱФŲ̴ݩYۦS,7.772/230.()*24*(14,/*)*(E72-*.1++332/0-,27649;:>87;Bⷥķʺи뭬ҧȵѼɽW/;2;;636784-*)23($-0(+&%&;2-(%),&&..-*+('-1*,445?6;;F²ս¯ƣS9E;DD?絝{ǨŧWP;:KJDŽٰ⤇Ц̪ݬɺ]٢F/6+280/4410)(*01+',3--**-(G3/*',0)',5/,/.'-927<47D;::8鿯ܐݻ“sy͠ݴ始ӫҭߨJ1:/6<437896.+)02)#(/))&'*<.*%"'+$"'0*'*)")2&-5.3D:;45˼^ïߵ۹F3247ຸɲӹēȃ礣̲Пܲ޲Ϊѹ׸L2:07<437896-+)02)#(/))&&)26-2ϧٕ߽_ж³ാߺI;0-*01'%)0**''+;3/*&,/(&,5.+.-'-6+07047,3>C؛w^k{R_OWyULfϿн|hGJ?8D9@E=<@@>;0-*01'%)0**''+;10+%-1*(,5/,/.(.6*070155EDJ٭Ǥ`\2j1PKaBYUXnѾn:KB5>Gعơƨmδ827-39104321*02+(-4-.+*-'F40+(-1+).60-0/).916<56:9H;Cຓ٫ӹ}ª{s}mƫ׸ձռ¸Ժũ:6;07<5479:8/,)03*$)0)*'')BB@<1.*01(%*1*+((+:9.,/21'(.-,+)+$*820563;21,7م:Es{z彤v}|`dbWzѤ7,4)45//.53-''&1.*%(0.(#'2$J5,(+0.##-/-,*,%*;84:;8@8865~囱Ş}\կoynoԧҽ/˩˵١ٵٵ߯A29.9:54461,&J1/& $,*$#.@0'#&+)((&%$%$31/451820/7ɻͲśo^ۿҹ̩ðȘ0:>3>?:98<:4-)&1-&"%-+% $->>1)(./',0.-,*,%*600343;224=^OubRBud1 eckPri3-CheckPrimeTest.mwinfoblob0x 5-FatoriazationExamples.mwsinfoblob0ś9-BirthdayAttackDiscreteLog.mwinfoblob0  @ @ @ @ E DSDB ` @ @ @'*)!'3,,.2.6/.;Hknilko~xqyqkl~ezwKVNA0>??<3+,,8>815>==A5358;7,FA<:;>@@?@8>C@EJG?IR/9:;JCu|mr_i~vhnsxv+;A5<>;7:994.(-34,!%.+)##)!?93-*1+(*).-.-&+$7..142:31+C7Paj\XwE8'JpLYvڭxwtxohc\ey~wgN^ǸĿ)1/5+/40-.160*$)/.,%(1.,&&*0N60*'.(%'(1/'-%8//253;43/:YX[Z{py⼺PKVT^RZ]XR_V[N[\_fde`\dml_[Hb]]_]Y[^^X[_XTPNLFQ__ZL;Iʺ*39.2730224/)#(..)!$-*(""( ?1+%")# "$*)!'2**-0.6/,*:Swy]\WttҚh/+43A?GJ@:E7:1CCBB=<40BLOFG8KFGKJFIJMIMPJE?@?;APLG>-A'9@59>:7:894.(-34,!%.+)##)!>82*'.)&&(0/-.-,'711382:32?Gז6-3(06202560*&)1.*)(/.,&&+*P5/'$+&##&0.,-,+&722493;436A͐QNZ_QPRY[`W_Va_jdcdfmja]ZQgKFYRW^`^]WWZZSJjMc%;ݙ516+3953564/)%(0.)%$+*(""(D0*"&!!)*&)%$"2--/4.6/-3@pm0g3>B32=CAG=B:D?E@?ACJE>EC;V@BSIFMIFHAIQOGBF]4;7=2:@<:=:94.*-54,%%,+)##)D72+$-)')(21-/2*+4-+162:31?Hm`aj|ookakz}}wwlyɕP̟cp[l}zdlYrEԮ5,0%.611354.+)&1/()(-/,&&,$S4/(!*&$&%.-)+.''3/,273;432>žɱFKQZfhbaWJM[WaabddieTOLR`B™^cLU`]Z^Ya\Ŀ+UAᱨÑ503(1944762-*(%0.&%$)+(""(I/*#%!! *($')"".*'-2.6/./>{þ(:BJWULKC7:DBMH@HHPO?>;C Prime Test Effectiveness\251Mike May, S.J,2004maymk@slu.eduIn class we looked at a the Fermat test as a quick method for checking if a number is composite. If a^(n-1) is not congruent to 1 mod n, then a is a Fermat witness that n is not prime. This worksheet looks at how effective that test is with numbers f various sizes. We will see that for numbers of the size we are interested in checking the Fermat test with a single alpha is incredibly efficient. The first step is to create a modification of the rand function that returns random odd integers greater than 1.oddRand := proc(magN) local m: m := rand(3..10^magN)(): m := m + 1 - (m mod 2): end proc:n := oddRand(80);NiM+SSJuRzYiIltwUDFCaT8uUTAkUXZZbigqPShlJWVOY1ZoRHV1cHRJalYuRiRwNTZLIjNwJz4=
<Text-field layout="Heading 1" style="Heading 1">Testing many witnesses for a single number n</Text-field>The next step is to create a function that will take a pair (n,m) and tell us that either n is prime, or will test the first n integers starting with 2 and see if they are witnesses that n is composite. It will tell us the number of these integers that fail to be witnesses.witnessTest := proc(n,m) local badWitness, i: badWitness := 0: if (isprime(n)) then print(n, " is prime"): else for i from 2 to (m+1) do if ((Power(i, n-1) mod n) = 1) then print(i, " fails to withness ", n, " is composite."): badWitness := badWitness + 1: end if: end do: end if: print(badWitness, " of the first ", m, " candidates failed to witness."): end proc:witnessTest(n,20);NiYiIiFRL35vZn50aGV+Zmlyc3R+NiIiIz9RP35jYW5kaWRhdGVzfmZhaWxlZH50b353aXRuZXNzLkYlPutting the two procedures together lets us test random odd integers of a specified size.n := oddRand(4); witnessTest(n,200);NiM+SSJuRzYiIiUkcCY=NiQiJSRwJlEqfmlzfnByaW1lNiI=NiYiIiFRL35vZn50aGV+Zmlyc3R+NiIiJCsjUT9+Y2FuZGlkYXRlc35mYWlsZWR+dG9+d2l0bmVzcy5GJQ==It is interesting to try this several times with the degree of n set at 3, 4, and 5. My experience from simply repeating the code above many times is that by the time the degree of n is 6, we expect most composite n will have no Fermat liars in the first 200 numbers. If the order of n is small we can also try letting m = n-3, tating 2 through n-2 as cadidates..n := oddRand(5); witnessTest(n,n-3);NiM+SSJuRzYiIiZONCQ=NiYiJDEpUTR+ZmFpbHN+dG9+d2l0aG5lc3N+NiIiJk40JFEvfmlzfmNvbXBvc2l0ZS5GJQ==NiYiJSJRJlE0fmZhaWxzfnRvfndpdGhuZXNzfjYiIiZONCRRL35pc35jb21wb3NpdGUuRiU=NiYiJSc9J1E0fmZhaWxzfnRvfndpdGhuZXNzfjYiIiZONCRRL35pc35jb21wb3NpdGUuRiU=NiYiJlxaI1E0fmZhaWxzfnRvfndpdGhuZXNzfjYiIiZONCRRL35pc35jb21wb3NpdGUuRiU=NiYiJmFiI1E0fmZhaWxzfnRvfndpdGhuZXNzfjYiIiZONCRRL35pc35jb21wb3NpdGUuRiU=NiYiJkgsJFE0fmZhaWxzfnRvfndpdGhuZXNzfjYiIiZONCRRL35pc35jb21wb3NpdGUuRiU=NiYiIidRL35vZn50aGV+Zmlyc3R+NiIiJks0JFE/fmNhbmRpZGF0ZXN+ZmFpbGVkfnRvfndpdG5lc3MuRiU=
<Text-field layout="Heading 1" style="Heading 1">Testing primeness with many n and many witnesss</Text-field>The next step is to have a procedure that would try numRand random odd numbers of order sizeRand, and tell us how many are prime, and how which of the first numCand candidates fail to witness to each composite.CandidateTester := proc(numRand, sizeRand, numCand) local falseWitness, numberPrimes, nCount, i, test, n: falseWitness := 0: numberPrimes := 0: for nCount from 1 to numRand do n := rand(2..10^sizeRand)(): n:= n + 1 + (n mod 2): if (isprime(n)) then numberPrimes := numberPrimes + 1: else for i from 2 to numCand + 1 do test := (Power(i, n-1) mod n): if ((Power(i, n-1) mod n) = 1) then print (i, "is fails to witness for the composite ", n): falseWitness := falseWitness + 1: end if; end do: end if: end do: print(numberPrimes, " primes found"); print(falseWitness, " cases where a number failed to witness to a composite"): end proc:We can use this to look at what happens with 1000 random numbers chosen at various sizes with 10 candidates tested at each n. Thus we are trying 10,000 tests at each sizefor i from 4 to 15 do CandidateTester(1000,i,10); print("After testing 1000 numbers about the size of 10^",i): end do:NiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJHJA==NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJHJA==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVZtNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVZtNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJXJ1NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUxsNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUxsNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUxsNiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUAkKQ==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUAkKQ==NiUiIihRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUAkKQ==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUAkKQ==NiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTRDNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJDYmNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJDYmNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxFNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxFNiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTZjNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJThSNiUiIihRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJEQkNiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxtNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVQ6NiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVQ6NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVQ6NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVQ6NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiIyYpNiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJvJQ==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJvJQ==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJvJQ==NiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJXJ1NiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSxGNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJThkNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJDAjNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSZ5Ig==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTw5NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJXI/NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUokKg==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTAnKg==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTJyNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTJyNiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUJUNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUJUNiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSJlIg==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJVgqKg==NiUiIihRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUQ9NiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIihRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJWxDNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJThkNiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJChwNiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUJUNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUJUNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiI04=NiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSwlKQ==NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSwlKQ==NiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJSwlKQ==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTAnKg==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJV5wNiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJCR6NiQiJGQjUS5+cHJpbWVzfmZvdW5kNiI=NiQiIycpUVd+Y2FzZXN+d2hlcmV+YX5udW1iZXJ+ZmFpbGVkfnRvfndpdG5lc3N+dG9+YX5jb21wb3NpdGU2Ig==NiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiIlNiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUg8NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJlQ5JQ==NiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUBYNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJkxyJg==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJTAnKg==NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJUokKg==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJnBBIw==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJXI/NiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJiRHWw==NiQiJCI9US5+cHJpbWVzfmZvdW5kNiI=NiQiIzxRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiImNiUiIzVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJywhKioqNiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ2RRaQ==NiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ0pfNg==NiUiIiZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJyJcQyo=NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJlA2Ig==NiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIidRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ1xoPA==NiUiIiNRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ2w5Nw==NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ2w5Nw==NiUiIilRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ2w5Nw==NiUiIiRRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ0ooUSc=NiUiIiVRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ0ooUSc=NiUiIipRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJ0ooUSc=NiUiIzZRR2lzfmZhaWxzfnRvfndpdG5lc3N+Zm9yfnRoZX5jb21wb3NpdGV+NiIiJyJbJz4=NiQiJGMiUS5+cHJpbWVzfmZvdW5kNiI=NiQiIz1RV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiInNiQiJEUiUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiIoNiQiJC0iUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiIpNiQiJCwiUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiIqNiQiJDEiUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM1NiQiIykpUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM2NiQiIyQpUS5+cHJpbWVzfmZvdW5kNiI=NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM3NiQiI3RRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM4NiQiI3VRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM5NiQiI2xRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+MTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiM6As the size of the candiate numbers rises from 10^4 to 10^15, the number of primes found in 1000 tries fell from something around 250 to somewhere around 65 primes. The number of Fermat liars with 10,000 tests fell from from about 80 when n n is about 10^4, to 20 when n=6 to no cases when n is larger than 8.By the time randSize is at least 10, potential candidates fail to witness in less than 1 in 100,000 cases.
<Text-field layout="Heading 1" style="Heading 1">Checking efficiency of using a single Fermat witness</Text-field>For 80 digits numbers we can test how often testing with 2 fails to find when n is prime. To make the computer not look like it is frozen, we will pring out results after every 5000 tests.for i from 1 to 20 do CandidateTester(5000,80,1); print("After testing 5000 numbers about the size of 10^",80): end do:NiQiI3VRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI15RLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2VRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI1lRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2FRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI25RLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI15RLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI1tRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2hRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI1tRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI19RLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2RRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2JRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2RRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2RRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2JRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2VRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2BRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI2VRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==NiQiI1tRLn5wcmltZXN+Zm91bmQ2Ig==NiQiIiFRV35jYXNlc353aGVyZX5hfm51bWJlcn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiRRUUFmdGVyfnRlc3Rpbmd+NTAwMH5udW1iZXJzfmFib3V0fnRoZX5zaXplfm9mfjEwXjYiIiMhKQ==Checking 100,000 odd numers of size 80 found about 1000 primes and no cases where checking with the Fermat test did not correctly identify composite numebers.We would like to look generalize the investigation above and look at how often we fail to spot a composite number by simply trying the Fermat test with a = 2. For this procedure we eliminate the random number and instead ask for a starting point and a number of odd numbers to check.twoCandidateTester := proc(startNumber, numCand) local falseWitness, numberPrimes, nCount, test, temp: falseWitness := 0: numberPrimes := 0: test := startNumber + 1 - (startNumber mod 2): print(test, numCand): for nCount from 1 to numCand do if (isprime(test)) then numberPrimes := numberPrimes + 1: else temp := (Power(2, test-1) mod test): if (temp = 1) then: print ("2 fails to witness for the composite ", test): falseWitness := falseWitness + 1: end if; end if: test := test + 2: end do: print(numberPrimes, " primes found"); print(falseWitness, " cases where 2 failed to witness to a composite"): end proc:twoCandidateTester(10^6, 10^5);NiQiKCwrKyIiJysrNQ==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoYFkrIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoLG8sIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoQCo9NQ==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoQEotIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoXlktIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIocE8uIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoJik0MCI=NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoLkQwIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoSEgwIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoaFAwIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoYFMxIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoQEkyIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoLEMzIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoNEczIg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoWkQ0Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoPE00Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoXFY1Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoJnkxNg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoaCU0Ng==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoQCJHNg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoZEU4Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoIkdSNg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoVDY5Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoZF85Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIockE6Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoKm9kNg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoOCZvNg==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoQEs+Ig==NiRRRjJ+ZmFpbHN+dG9+d2l0bmVzc35mb3J+dGhlfmNvbXBvc2l0ZX42IiIoXFk+Ig==NiQiJlNXIlEufnByaW1lc35mb3VuZDYiNiQiI0hRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=We can speed things up by only printing out the number of instances.twoCandidateTester2 := proc(startNumber, numCand) local falseWitness, numberPrimes, nCount, test, temp: falseWitness := 0: numberPrimes := 0: test := startNumber + 1 - (startNumber mod 2): print("Starting with ",test, " and checking ", numCand, " odd numbers"): for nCount from 1 to numCand do if (isprime(test)) then numberPrimes := numberPrimes + 1: else temp := (Power(2, test-1) mod test): if (temp = 1) then: falseWitness := falseWitness + 1: end if; end if: test := test + 2: end do: print(numberPrimes, " primes found"); print(falseWitness, " cases where 2 failed to witness to a composite"): end proc:twoCandidateTester2(10^5, 10^5);NidRL1N0YXJ0aW5nfndpdGh+NiIiJywrNVEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJjBrIlEufnByaW1lc35mb3VuZDYiNiQiI2dRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=
We want to see how effective the more sensitive test is with the cases that the first test missed. The next procedure checks Miller-Rabin for 2 on the cases the first test failed on.twoCandidateTester3 := proc(startNumber, numCand) local falseWitness1, falseWitness2, numberPrimes, nCount, test, temp, exp2, tExp, test1, eCount: falseWitness1 := 0: falseWitness2 := 0: numberPrimes := 0: test := startNumber + 1 - (startNumber mod 2): print("Starting with ",test, " and checking ", numCand, " odd numbers"): for nCount from 1 to numCand do if (isprime(test)) then numberPrimes := numberPrimes + 1: else temp := (Power(2, test-1) mod test): if (temp = 1) then: falseWitness1 := falseWitness1 + 1: exp2 := test-1: while (temp =1) do exp2 := exp2/2: temp := (Power(2, exp2) mod test): test1 := ((temp +1) mod test): if (test1 = 0) then falseWitness2 := falseWitness2 + 1: print("2 failed to witness for the Miller-Rabin test for ",test): elif (test1 > 2) then print("2 is a witness for Miller-Rabin for ", test): print("2^",exp2,"=",temp," and 2^",2*exp2,"= 1"); end if: if ((exp2 mod 2) = 1) then temp := 0 end if: end do: end if; end if: test := test + 2: end do: print(numberPrimes, " primes found"); print(falseWitness1, " cases where 2 failed to witness to a composite"): print(falseWitness2, " cases where 2 failed to Witness Miller-Rabin"): end proc:twoCandidateTester3(10^4, 10^4);NidRL1N0YXJ0aW5nfndpdGh+NiIiJiwrIlEvfmFuZH5jaGVja2luZ35GJCImKysiUS1+b2Rkfm51bWJlcnNGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZoLSI=NilRIzJeNiIiJWxEUSI9RiQiJSYpPlEofmFuZH4yXkYkIiVJXlEkPX4xRiQ=NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYmZTU=NilRIzJeNiIiJVlFUSI9RiQiJiVINVEofmFuZH4yXkYkIiUjSCZRJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYwOCI=NilRIzJeNiIiJV9jUSI9RiQiJlQxIlEofmFuZH4yXkYkIiYvOCJRJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYsRyI=NilRIzJeNiIiJCsiUSI9RiQiJWdBUSh+YW5kfjJeRiQiJCsjUSQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZUUCI=NilRIzJeNiIiJXFvUSI9RiQiJVZqUSh+YW5kfjJeRiQiJlNQIlEkPX4xRiQ=NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZaUCI=NilRIzJeNiIiJXRvUSI9RiQiJUAkKlEofmFuZH4yXkYkIiZZUCJRJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYiKVIiNilRIzJeNiIiJSEqcFEiPUYkIiVDNVEofmFuZH4yXkYkIiYhKVIiUSQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYiXDk=NilRIzJeNiIiJVhzUSI9RiQiJlsvIlEofmFuZH4yXkYkIiYhXDlRJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiY0ZCI=NilRIzJeNiIiJUZSUSI9RiQiJVs/USh+YW5kfjJeRiQiJWF5USQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYwbiI=NilRIzJeNiIiJSkzI1EiPUYkIiUnUiZRKH5hbmR+Ml5GJCIld1RRJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYwKD0=NilRIzJeNiIiJVFCUSI9RiQiJiVRO1EofmFuZH4yXkYkIiV3WVEkPX4xRiQ=NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZAKD0=NilRIzJeNiIiJWckKlEiPUYkIiZNJD1RKH5hbmR+Ml5GJCImPyg9USQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZeKj4=NilRIzJeNiIiJXYqKlEiPUYkIiVpa1EofmFuZH4yXkYkIiZdKj5RJD1+MUYkNiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiYsSSM=NilRIzJeNiIiJis6IlEiPUYkIiZKTiJRKH5hbmR+Ml5GJCImK0kjUSQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZ4TCM=NilRIzJeNiIiJilvNlEiPUYkIiYyZiJRKH5hbmR+Ml5GJCImd0wjUSQ9fjFGJA==NiRRRTJ+aXN+YX53aXRuZXNzfmZvcn5NaWxsZXItUmFiaW5+Zm9yfjYiIiZoZCM=NilRIzJeNiIiJTU7USI9RiQiJiRbRFEofmFuZH4yXkYkIiU/S1EkPX4xRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJlQkSA==NiQiJTs/US5+cHJpbWVzfmZvdW5kNiI=NiQiIz1RUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiJRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiThe last procedure simply gives summary resultstwoCandidateTester4 := proc(startNumber, numCand) local falseWitness1, falseWitness2, numberPrimes, nCount, test, temp, exp2, tExp, test1, eCount: falseWitness1 := 0: falseWitness2 := 0: numberPrimes := 0: test := startNumber + 1 - (startNumber mod 2): print("Starting with ",test, " and checking ", numCand, " odd numbers"): for nCount from 1 to numCand do if (isprime(test)) then numberPrimes := numberPrimes + 1: else temp := (Power(2, test-1) mod test): if (temp = 1) then: falseWitness1 := falseWitness1 + 1: exp2 := test-1: while (temp =1) do exp2 := exp2/2: temp := (Power(2, exp2) mod test): test1 := ((temp +1) mod test): if (test1 = 0) then falseWitness2 := falseWitness2 + 1: print("2 failed to witness for the Miller-Rabin test for ",test): end if: if ((exp2 mod 2) = 1) then temp := 0 end if: end do: end if; end if: test := test + 2: end do: print(numberPrimes, " primes found"); print(falseWitness1, " cases where 2 failed to witness to a composite"): print(falseWitness2, " cases where 2 failed to Witness Miller-Rabin"): end proc:twoCandidateTester4(10^4, 10^5);NidRL1N0YXJ0aW5nfndpdGh+NiIiJiwrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJlQkSA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJlQiXA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJiJHbA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJmxZKA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJiJlISk=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJipbJik=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJmQkKSk=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJ2BZNQ==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJ2gwOA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJyQ0Jz4=NiQiJnl2IlEufnByaW1lc35mb3VuZDYiNiQiIygpUVB+Y2FzZXN+d2hlcmV+Mn5mYWlsZWR+dG9+d2l0bmVzc350b35hfmNvbXBvc2l0ZTYiNiQiIzVRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYitwoCandidateTester4(10^5, 10^5);NidRL1N0YXJ0aW5nfndpdGh+NiIiJywrNVEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJ2BZNQ==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJ2gwOA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJyQ0Jz4=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJzxJQg==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJyxFRA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJ1RLRA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiJywxRw==NiQiJjBrIlEufnByaW1lc35mb3VuZDYiNiQiI2dRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIihRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYitwoCandidateTester4(10^6, 10^5);NidRL1N0YXJ0aW5nfndpdGh+NiIiKCwrKyJRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKGBZKyI=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKCxvLCI=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKEBKLSI=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKFxZPiI=NiQiJlNXIlEufnByaW1lc35mb3VuZDYiNiQiI0hRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiVRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYitwoCandidateTester4(10^7, 10^5);NidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrKzVRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiQiJiJSN1EufnByaW1lc35mb3VuZDYiNiQiIilRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYifor i from 1 to 10 do twoCandidateTester4(10^7+i*2*10^5, 10^5); end do:NidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrPzVRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKXBQSzU=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKVRpUTU=NiQiJjdDIlEufnByaW1lc35mb3VuZDYiNiQiIzZRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiNRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrUzVRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiQiJjhDIlEufnByaW1lc35mb3VuZDYiNiQiIihRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrZzVRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKTBmbDU=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKWBPdzU=NiQiJmZCIlEufnByaW1lc35mb3VuZDYiNiQiIilRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiNRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrITMiUS9+YW5kfmNoZWNraW5nfkYkIicrKzVRLX5vZGR+bnVtYmVyc0YkNiQiJmpCIlEufnByaW1lc35mb3VuZDYiNiQiIilRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrKzZRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKWY5MzY=NiQiJmNCIlEufnByaW1lc35mb3VuZDYiNiQiIidRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiJRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrPzZRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKSxiTDY=NiQiJmVBIlEufnByaW1lc35mb3VuZDYiNiQiIiZRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiJRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrUzZRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKSYpUVo2NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKTI4YTY=NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiKSRIJmU2NiQiJkNCIlEufnByaW1lc35mb3VuZDYiNiQiIiZRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiRRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrZzZRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiQiJj1CIlEufnByaW1lc35mb3VuZDYiNiQiIiVRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrIT0iUS9+YW5kfmNoZWNraW5nfkYkIicrKzVRLX5vZGR+bnVtYmVyc0YkNiQiJihHN1EufnByaW1lc35mb3VuZDYiNiQiIiRRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiKSwrKzdRL35hbmR+Y2hlY2tpbmd+RiQiJysrNVEtfm9kZH5udW1iZXJzRiQ=NiQiJkRBIlEufnByaW1lc35mb3VuZDYiNiQiIiRRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYifor i from 0 to 10 do twoCandidateTester4(10^10+i*2*10^5, 10^5); end do:NidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrKysrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJW8nKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrPysrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiLEA4SysrIg==NiQiJXEnKVEufnByaW1lc35mb3VuZDYiNiQiIiJRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiJRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrUysrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiRRUzJ+ZmFpbGVkfnRvfndpdG5lc3N+Zm9yfnRoZX5NaWxsZXItUmFiaW5+dGVzdH5mb3J+NiIiLFwyUysrIg==NiQiJSJvKVEufnByaW1lc35mb3VuZDYiNiQiIiNRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiJRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrZysrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJXknKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrITMrNVEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJUkoKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrKywrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJU8nKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrPywrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJTAnKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrUywrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJUgoKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrZywrIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJUQoKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrIT0rNVEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJSZwKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrKy0rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJUgnKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYifor i from 11 to 30 do twoCandidateTester4(10^10+i*2*10^5, 10^5); end do:NidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrPy0rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJWonKVEufnByaW1lc35mb3VuZDYiNiQiIiJRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrUy0rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJXYoKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrZy0rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJU0nKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrIUcrNVEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJWQnKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrKy4rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJVgnKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrPy4rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJWwoKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYiNidRL1N0YXJ0aW5nfndpdGh+NiIiLCwrUy4rIlEvfmFuZH5jaGVja2luZ35GJCInKys1US1+b2Rkfm51bWJlcnNGJA==NiQiJSRwKVEufnByaW1lc35mb3VuZDYiNiQiIiFRUH5jYXNlc353aGVyZX4yfmZhaWxlZH50b353aXRuZXNzfnRvfmF+Y29tcG9zaXRlNiI=NiQiIiFRTn5jYXNlc353aGVyZX4yfmZhaWxlZH50b35XaXRuZXNzfk1pbGxlci1SYWJpbjYi