{VERSION 5 0 "IBM INTEL LINUX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "This worksheet concerns distributions of primes. First we lo ok for a particular type of prime that Sopie Germain studied, and whic h " }}{PARA 0 "" 0 "" {TEXT -1 134 "are called Sophie Germain primes. \+ They are primes p such that 2p+1 is also prime. I will call a prime \+ q \"good\" if (q-1)/2 is prime. " }}{PARA 0 "" 0 "" {TEXT -1 143 "It t urns out that these primes are good for cryptographic systems. We'll als look at slight variations of \"good\" and at the distribution of " }}{PARA 0 "" 0 "" {TEXT -1 31 "good and \"pretty-good \" primes." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "There a re also exercises at the end of this worksheet for studying primes in arithmetic progressions." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 105 "In addition to the study of primes in this worksh eet, there is a second objective, to write procedures. " }}{PARA 0 " " 0 "" {TEXT -1 116 "The exercises guide you in writing simple procedu res and building more complex ones from the simple building blocks." } }{PARA 0 "" 0 "" {TEXT -1 89 "Good programming practice is to keep fun ctions and procedures short, simple, and clear. " }}{PARA 0 "" 0 "" {TEXT -1 83 "Test what you write thoroughly before building something \+ more complex on top of it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 45 "Some procedures for testing for good p rimes." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 198 "In this section I will \+ present a few simple procedures. They are written for clarity, not f or typing efficiency. I am sure that you could write a more compact v ersion of each of the procedures. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 248 "In the RSA cryptosystem, it is useful t o have a prime number p such that (p-1)/2 has large prime factors. Fo r example if (p-1)/2 is itself prime that would be ideal. Let us writ e a simple test for a prime to see if it satisfies this condition. \+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 141 "goodprime := proc(p)\n local pp, bool;\n\npp := (p-1)/2;\nif isprime(pp) \n then bool := tr ue;\n else bool := false;\nfi;\nRETURN(bool);\nend proc;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "There are a few things to notice in this simple example. " }}{PARA 0 "" 0 "" {TEXT -1 87 "1) The if statement must be terminated with either \"en d if\" or its abbreviation \"fi\"." }}{PARA 0 "" 0 "" {TEXT -1 105 "2) The else statement is optional. You can also have a sequence of el se if statements, written \"elif\"." }}{PARA 0 "" 0 "" {TEXT -1 118 "3 ) If you hold down the key when typing you don't get a new cursor and the annoying warning message." }}{PARA 0 "" 0 "" {TEXT -1 89 "4) I like to explicitly say what the procedure should re turn, using RETURN() as shown. " }}{PARA 0 "" 0 "" {TEXT -1 65 "I'm n ot completely clear on the rules if RETURN is not specified." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "Now let 's make a list of all good primes between m and n." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 187 "goodprimelist := proc(m,n)\nlocal i, plist ;\n\nplist := [];\nfor i from m to n do\n if (isprime(i) and goodpri me(i))\n then plist := [op(plist), i];\n fi;\nod;\nRETURN(plis t);\nend proc;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 191 "Notes: 1) W e closed both the if and the do statements. 2) The indentation is \+ my choice for legibility. 3) I had to initialize plist . 4) Extendi ng a list is done via the op() command." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "goodprimelist(100,1000 );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Now let's count how many go od primes there are less than 2^(i+1) and " }}{PARA 0 "" 0 "" {TEXT -1 141 "graph the result. This indicate tell how easy it is to find such primes, and thus the feasibility of finding them for an RSA cryp tosystem." }}{PARA 0 "" 0 "" {TEXT -1 125 "For comparison, the Prine N umber Theorem says that the number of primes less than 2^i is approxim ately ((2^i / i * log(2) )." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 281 "numgoodprimes := \+ proc(pow)\nlocal i, tot_cnt, new_cnt, countlist;\n\ncountlist := [];\n tot_cnt := 0;\nfor i from 2 to pow do\n new_cnt := nops(goodprimelis t(2^i, 2^(i+1)));\n tot_cnt := tot_cnt + new_cnt;\n countlist := [ op(countlist), [i,tot_cnt]];\nod;\nRETURN(countlist);\nend proc;\n" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "datalist := numgoodprimes(1 5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 234 "Now go back to the numgoo dprimes function and change it so that it prints out the number of goo dprimes in each range 2^i .... 2^(i+1), so that we can keep track of h ow long it takes to do range (it should increase exponentially). Use " }}{PARA 0 "" 0 "" {TEXT -1 17 "print(\"i is \" i);" }}{PARA 0 "" 0 " " {TEXT -1 92 "print( \"the number of goodprimes in the range\" (2^i, 2^(i+1)) );\nprint( \"is \" (new_+cnt));" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(plots);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 290 "Now we will plot the datalist wit h the number of good primes and compare it to what we might expect acc ording to the prime number theorem. There number of primes less than \+ t is roughly t/ln(t). We might expect that t and (t-1)/2 would bo th be prime for t/ (ln(t)*ln(t/2)) values of t." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 37 "plot1 := plot(datalist, color = red);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "plot2 := plot(2^t/(log(2^t)* log(2^(t-1))), t=2..15, color = blue):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "display(plot1,plot2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 33 "Some aids for w riting procedures" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Here are a \+ few Maple commands that may be of use." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 194 "Setting printlevel to 10 will force \+ Maple to print out intermediate data computed within a given procedure . Setting it to 20 will also printout data in procedures called by th e given procedure." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "printlevel := 1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "goodprimelist(10,50);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 17 "printlevel := 20;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "goodprimelist(10,50);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Another interesting thing is to look at the Maple code fo r some of the functions that you use." }}{PARA 0 "" 0 "" {TEXT -1 75 " The rather cryptic command sequence is to set verboseproc =2 and use p rint." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "printlevel := 1; \+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verboseproc=3 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(isprime);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(ifactor);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "Finally the function showtime() allows will tell you how long a fu nction takes to perform." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "showtime();" }}}{EXCHG {PARA 0 "O1 := " 0 "" {MPLTEXT 1 0 22 "isprime ((2^(2^11)+1));" }}}{EXCHG {PARA 0 "O2 := " 0 "" {MPLTEXT 1 0 4 "off; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 3 " " 0 "" {TEXT -1 22 "Exercises: Good Primes" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 172 "1) Write a new version of goodprime, pretty_good_prime, which uses the criteria that p is a good prime if (p-1) has a prime f actor exceeding p/(log_2(p)). Use ifactors()." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172 "2) Examine the asymptoti cs of good primes: Write a procedure that will test what proportion of primes in the range 2^i....2^(i+1) are good, as i varies. Graph the result." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 178 "3) Write a new function that looks for really good primes. Those p such that (p-1)/2 is also a good prime. I suppose you could also \+ define a function pretty_really_good_primes" }}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 44 "Exercises: Primes in artihmetic progress ion" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "1) For b = 1 and -1 and fo r n an a (large) integer, find the number of primes less than n of th e form 6k+b for k an integer.\n " }}{PARA 0 "" 0 "" {TEXT -1 234 "2 ) Write a procedure Num_primes(a, b, n) that will output the number o f primes of the from ak+b that are less than n.\n\n3) Write a procedu re Proportions(a,n) that outputs a table containing for each positive \+ b< a with b coprime to a " }}{PARA 0 "" 0 "" {TEXT -1 57 "the proporti on of primes less than n of the form ak+b. " }}}}}{MARK "8" 0 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }