{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 14 " Prime Numbers" }}}
{EXCHG {PARA 19 "" 0 "" {TEXT -1 58 "Mike O'Sullivan\nSan Diego State \+
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 distributions o
f primes. First we look for a particular type of prime that \nSopie G
ermain studied, which is called a Sophie Germain prime. This is a pri
mes 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 cry
ptographic systems. We'll look at slight variations of \"good\" and
at the distribution of " }}{PARA 0 "" 0 "" {TEXT -1 31 "good and \"pr
etty-good \" primes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 101 "There are 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 worksheet, there is a second objective, to write pr
ocedures. " }}{PARA 0 "" 0 "" {TEXT -1 117 "The exercises guide you i
n writing simple procedures and building more complex ones from \nthe \+
simple building blocks." }}{PARA 0 "" 0 "" {TEXT -1 90 " Good programm
ing practice is to keep functions and procedures short, simple, and cl
ear. " }}{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 1 {PARA 3 "" 0 "" {TEXT -1 45 "Some procedur
es 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 p
rime 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 that wou
ld 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)\nlocal pp, bo
ol;\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 t
hings to notice in this simple example. " }}{PARA 0 "" 0 "" {TEXT -1
87 "1) The if statement must be terminated with either \"end if\" or
its abbreviation \"fi\"." }}{PARA 0 "" 0 "" {TEXT -1 105 "2) The els
e statement is optional. You can also have a sequence of else if sta
tements, written \"elif\"." }}{PARA 0 "" 0 "" {TEXT -1 118 "3) If you
hold down the key when typing you don't get a new cu
rsor and the annoying warning message." }}{PARA 0 "" 0 "" {TEXT -1 89
"4) I like to explicitly say what the procedure should return, using \+
RETURN() as shown. " }}{PARA 0 "" 0 "" {TEXT -1 65 "I'm not completel
y 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 goodprime(i))\n \+
then plist := [op(plist), i];\n fi;\nod;\nRETURN(plist);\nend p
roc;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 192 "Notes: 1) We closed b
oth the if and the do statements. 2) The indentation is my choice \+
for legibility. \n3) I had to initialize plist . 4) Extending a lis
t 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 good pri
mes 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 pr
imes, and thus the feasibility of " }}{PARA 0 "" 0 "" {TEXT -1 37 "fin
ding them for an RSA cryptosystem." }}{PARA 0 "" 0 "" {TEXT -1 125 "Fo
r comparison, the Prine Number Theorem says that the number 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_cn
t, countlist;\n\ncountlist := [];\ntot_cnt := 0;\nfor i from 3 to pow \+
do\n new_cnt := nops(goodprimelist(2^(i-1), 2^i));\n tot_cnt := to
t_cnt + new_cnt;\n countlist := [op(countlist), [i,tot_cnt]];\nod;\n
RETURN(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 change it \+
so that it prints the number of goodprimes in \neach range, 2^(i-1) .
... 2^i, while executing the procedure. This will show how long it ta
kes to process\neach range (it should increase exponentially). Use"
}}{PARA 0 "" 0 "" {TEXT -1 17 "print(\"i is \" i);" }}{PARA 0 "" 0 ""
{TEXT -1 91 "print( \"the number of goodprimes in the range\" (2^(i-1
), 2^i );\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 "" }}}}{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 tha
t 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 i
ntermediate data computed within a given procedure. Setting it to 20 \+
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 "p
rintlevel := 20;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "goodpri
melist(10,50);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Another interes
ting thing is to look at the Maple code for some of the functions that
you use." }}{PARA 0 "" 0 "" {TEXT -1 75 "The rather cryptic command s
equence is to set verboseproc =2 and use print." }}}{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 "pr
int(isprime);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(ifac
tor);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "Finally the function sho
wtime() allows will tell you how long a function 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 "Exercises: Good Primes" }
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 172 "1) Write a new version of goodp
rime, pretty_good_prime, which uses the criteria that p is a good prim
e 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) E
xamine the asymptotics of good primes: Write a procedure that will tes
t 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 supp
ose 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 1 {PARA 3 "" 0 "" {TEXT -1 44 "Exercises: Primes in
artihmetic progression" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "1) For
b = 1 and -1 and for n an a (large) integer, find the number of prim
es less than n of the 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 of primes of the from ak+b that are less than n.\n
\n3) Write a procedure Proportions(a,n) that outputs a table containi
ng 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 "0 0 0" 13 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 0 1 2 33 1 1 }