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