{VERSION 6 0 "IBM INTEL LINUX" "6.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 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 } {PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 22 "Distribution of Primes" } }}{EXCHG {PARA 19 "" 0 "" {TEXT -1 58 "Mike O'Sullivan\nSan Diego Stat e University\nSeptember, 2004" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 408 "This worksheet concerns distribu tions of primes. First we look for a particular type of prime that \n Sopie Germain studied, which is called a Sophie Germain prime. This i s a primes p such that 2p+1 \nis also prime. I will call a prime q \" good\" if (q-1)/2 is prime. It turns out that these primes are good \+ for cryptographic systems. We'll look at slight variations of \"goo d\" and at the distribution of " }}{PARA 0 "" 0 "" {TEXT -1 31 "good a nd \"pretty-good \" primes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "There are also exercises at the end of this wo rksheet 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 worksheet, there is a second objective, to wri te procedures. " }}{PARA 0 "" 0 "" {TEXT -1 117 "The exercises guide \+ you in writing simple procedures and building more complex ones from \+ \nthe simple building blocks." }}{PARA 0 "" 0 "" {TEXT -1 90 " Good pr ogramming practice is to keep functions and procedures short, simple, \+ and clear. " }}{PARA 0 "" 0 "" {TEXT -1 83 "Test what you write thoro ughly before building something more complex on top of it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 45 "Some pr ocedures for testing for good primes." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "In this section I will present a few simple procedures. They \+ are written for clarity, not for typing " }}{PARA 0 "" 0 "" {TEXT -1 95 "efficiency. I am sure that you could write a more compact version of each of the procedures. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 97 "In the RSA cryptosystem, it is useful to \+ have a prime number p such that (p-1)/2 has large prime " }}{PARA 0 " " 0 "" {TEXT -1 98 "factors. For example if (p-1)/2 is itself prime t hat would be ideal. Let us write a simple test " }}{PARA 0 "" 0 "" {TEXT -1 53 "for a prime to see if it satisfies this condition. " }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 141 "goodprime := proc(p)\nloca l pp, bool;\n\npp := (p-1)/2;\nif isprime(pp) \n then bool := true; \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 192 "Notes: 1) W e closed both the if and the do statements. 2) The indentation is \+ my choice for legibility. \n3) I had to initialize plist . 4) Exten ding a list is done via the op() command." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "goodprimelist(100,10 00);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Now let's count how many \+ good primes there are less than 2^(i+1) and " }}{PARA 0 "" 0 "" {TEXT -1 103 "graph the result. This indicates whether it is easy to find such primes, and thus the feasibility of " }}{PARA 0 "" 0 "" {TEXT -1 37 "finding them for an RSA cryptosystem." }}{PARA 0 "" 0 "" {TEXT -1 125 "For comparison, the Prine Number Theorem says that the n umber of primes less than 2^i is \napproximately ((2^i / i * ln(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 := [];\ntot_cnt := 0;\nfor i from 2 \+ to pow do\n new_cnt := nops(goodprimelist(2^i, 2^(i+1)));\n tot_cn t := 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(15);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 262 "Now go back to the numgoodprimes function and chang e it so that it prints the number of goodprimes in \neach range, 2^i \+ .... 2^(i+1), while executing the procedure. This will show how long \+ it takes to process\neach 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 datali st with the number of good primes and compare it to what we might expe ct according 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 wo uld both 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/(lo g(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 "" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 33 "Some aids for writing 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 2 0 will also printout data in procedures called by the 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 "" }}}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 22 "Exerc ises: Good Primes" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 172 "1) Write a \+ new version of goodprime, pretty_good_prime, which uses the criteria t hat p is a good prime if (p-1) has a prime factor exceeding p/(log_2(p )). Use ifactors()." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 172 "2) Examine the asymptotics of good primes: Write a pro cedure 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_real ly_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 "Exe rcises: Primes in artihmetic progression" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "1) For b = 1 and -1 and for n an a (large) integer, fin d the number of primes less than n of the form 6k+b for k an integer. \n " }}{PARA 0 "" 0 "" {TEXT -1 234 "2) Write a procedure Num_prim es(a, b, n) that will output the number of primes of the from ak+b tha t are less than n.\n\n3) Write a procedure Proportions(a,n) that outp uts a table containing for each positive b< a with b coprime to a " }} {PARA 0 "" 0 "" {TEXT -1 57 "the proportion of primes less than n of \+ the form ak+b. " }}}}}{MARK "6 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }