{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 }