Understanding Prime Numbers

Slide1Prime Numbers Prime  Numbers By  Becky  James By  Becky  James

Slide2Prime Numbers Prime  Numbers Prime  numbers  are  numbers  which  have  no  factors  other  than  1  and  itself.  The  ancient Prime  numbers  are  numbers  which  have  no  factors  other  than  1  and  itself.  The  ancient Chinese  discovered  the  primes,  but  didn’t  really  do  anything  with  them.  It  was  only  in Chinese  discovered  the  primes,  but  didn’t  really  do  anything  with  them.  It  was  only  in the  Golden  Age  of  the  Greeks  that  the  mysteries  behind  prime  numbers  were the  Golden  Age  of  the  Greeks  that  the  mysteries  behind  prime  numbers  were investigated.  Euclid  in  his  Elements   offered  some  insight  into  prime  numbers: investigated.  Euclid  in  his  Elements   offered  some  insight  into  prime  numbers: If  you  look  at  the  prime  numbers  between  1and  20… If  you  look  at  the  prime  numbers  between  1and  20… 2,  3,  5,  7,  11,  13,  17,  19. 2,  3,  5,  7,  11,  13,  17,  19. There  are  8,  nearly  half  are  prime.  Between  20  and  40… There  are  8,  nearly  half  are  prime.  Between  20  and  40… 23,  29,  31,  37. 23,  29,  31,  37. There  are  4.  The  number  of  primes  is  reducing,  so  do  they  eventually  dwindle  out  to There  are  4.  The  number  of  primes  is  reducing,  so  do  they  eventually  dwindle  out  to nothing?  In  other  words,  are  there  an  infinite  number  of  prime  numbers? nothing?  In  other  words,  are  there  an  infinite  number  of  prime  numbers?

Slide3Euclid’s Proof Euclid’s  Proof Let’s  say  there  is  a  finite  amount  of  prime  numbers…  there  must  be  a Let’s  say  there  is  a  finite  amount  of  prime  numbers…  there  must  be  a largest  prime  number.  Call  that  number  P.  That  makes  our  series  of largest  prime  number.  Call  that  number  P.  That  makes  our  series  of prime  numbers  look  like  this: prime  numbers  look  like  this: 2,  3,  5,  7…….  P. 2,  3,  5,  7…….  P. If  we  multiply  all  of  those  numbers  together,  we  get…. If  we  multiply  all  of  those  numbers  together,  we  get…. 2  x  3  x  5  x  7  x…….  x  P  =  N 2  x  3  x  5  x  7  x…….  x  P  =  N

Slide4Euclid’s Proof Euclid’s  Proof N  is  the  product  of  all  the  primes. N  is  the  product  of  all  the  primes. If  we  now  consider  N  +  1… If  we  now  consider  N  +  1… which  numbers  are  factors? which  numbers  are  factors? None!  2  is  the  smallest  factor  of  N,  so  therefore  cannot  be  a  factor  of None!  2  is  the  smallest  factor  of  N,  so  therefore  cannot  be  a  factor  of N  +  1.  That  means  that  N  +  1  is  prime,  since  the  only  other  factor  can  be N  +  1.  That  means  that  N  +  1  is  prime,  since  the  only  other  factor  can  be 1.  This  means  there  is  an  infinite  number  of  prime  numbers. 1.  This  means  there  is  an  infinite  number  of  prime  numbers. The  largest  prime  number  to  have  been  calculated  has  9.1  million  digits! The  largest  prime  number  to  have  been  calculated  has  9.1  million  digits!

Slide5Finding Primes Finding  Primes Both  Fermat  and  Mersenne  have  offered  us  some  techniques  for  finding Both  Fermat  and  Mersenne  have  offered  us  some  techniques  for  finding the  prime  numbers.  Neither  always  bring  up  a  prime  number,  but  in  the the  prime  numbers.  Neither  always  bring  up  a  prime  number,  but  in  the case  of  Mersenne,  his  formula  leads  to  finding  perfect  numbers. case  of  Mersenne,  his  formula  leads  to  finding  perfect  numbers. Fermat’s  formula:  2 n   +  1 Fermat’s  formula:  2 n   +  1 Mersenne’s  formula:  2 n   –  1 Mersenne’s  formula:  2 n   –  1 We  don’t  know  whether  there  are  an  infinite  number  of  Mersenne  primes We  don’t  know  whether  there  are  an  infinite  number  of  Mersenne  primes or  whether  we  can  achieve  an  infinite  number  of  primes  from  Fermat’s or  whether  we  can  achieve  an  infinite  number  of  primes  from  Fermat’s Formula. Formula.

Slide6How Many  Primes? How  Many  Primes? Gauss  noticed,  as  Euclid  did,  that  the  prime  numbers  begin  to  dwindle Gauss  noticed,  as  Euclid  did,  that  the  prime  numbers  begin  to  dwindle out  as  we  get  higher  and  higher  up  the  number  ladder… out  as  we  get  higher  and  higher  up  the  number  ladder… After  lots  of  calculating  and  trial  and  error,  Gauss  showed  that: After  lots  of  calculating  and  trial  and  error,  Gauss  showed  that: Density  of  Primes  ≈  1/log  n Density  of  Primes  ≈  1/log  n (where  n  =  the  sample  of  numbers  in  which  the  primes  are  being  counted.) (where  n  =  the  sample  of  numbers  in  which  the  primes  are  being  counted.)

Slide7Uses of  Prime  Numbers Uses  of  Prime  Numbers There  are  a  number  of  uses  of  prime  numbers. There  are  a  number  of  uses  of  prime  numbers. Some  uses  have  been  invented  by  humans  for Some  uses  have  been  invented  by  humans  for various  reasons  and  some  are  so  engrained  in various  reasons  and  some  are  so  engrained  in nature  that  it  seems  prime  numbers  play  a  more nature  that  it  seems  prime  numbers  play  a  more fundamental  role  in  life  than  we  sometimes fundamental  role  in  life  than  we  sometimes realise… realise…

Slide8Music of  the  Primes Music  of  the  Primes Olivier  Messiaen,  a  famous  composer  found  a  great  use Olivier  Messiaen,  a  famous  composer  found  a  great  use for  prime  numbers  in  his  music: for  prime  numbers  in  his  music: Messiaen  used  both  a  17  and  29  sequence  in  his  piece  of  music Messiaen  used  both  a  17  and  29  sequence  in  his  piece  of  music Quartet  for  the  End  of  Time .  Both  motifs  start  at  the  same  time,  however, Quartet  for  the  End  of  Time .  Both  motifs  start  at  the  same  time,  however, since  they  are  both  prime  numbers,  the  same  sequence  of  notes  playing since  they  are  both  prime  numbers,  the  same  sequence  of  notes  playing together  from  each  sequence  wont  be  the  same  until  they  have  played together  from  each  sequence  wont  be  the  same  until  they  have  played through  17  x  29  times  each.  He  held  prime  numbers  very  close  to  his through  17  x  29  times  each.  He  held  prime  numbers  very  close  to  his heart  and  believed  they  gave  his  music  a  timelessness  quality. heart  and  believed  they  gave  his  music  a  timelessness  quality.

Slide9Primes In  Nature Primes  In  Nature Similarly,  the  cicada,  a  burrowing  insect Similarly,  the  cicada,  a  burrowing  insect owes  its  survival  to  prime  numbers  and  their owes  its  survival  to  prime  numbers  and  their properties.  The  cicada  lives  underground  for  17 properties.  The  cicada  lives  underground  for  17 years,  making  no  sound  or  showing  any  signs  for years,  making  no  sound  or  showing  any  signs  for this  amount  of  time.  After  17  years,  all  of  the  insects this  amount  of  time.  After  17  years,  all  of  the  insects appear  in  the  forest  for  just  six  weeks  to  mate  before appear  in  the  forest  for  just  six  weeks  to  mate  before dying  out. dying  out.

Slide10Primes In  Nature Primes  In  Nature This  survival  technique,  whilst  the  noise  drives  local  residents This  survival  technique,  whilst  the  noise  drives  local  residents to  evacuate  the  area  for  the  six  weeks  due  to  the  noise,  has to  evacuate  the  area  for  the  six  weeks  due  to  the  noise,  has come  about  due  to  a  predator  that  would  appear  in  the  forest come  about  due  to  a  predator  that  would  appear  in  the  forest at  regular  intervals.  The  cicada  could  avoid  confrontation  with at  regular  intervals.  The  cicada  could  avoid  confrontation  with the  predator  more  often  by  only  appearing  every  17  years  as the  predator  more  often  by  only  appearing  every  17  years  as the  number  is  prime.  As  with  Messiaen’s  music,  it  would  be  a the  number  is  prime.  As  with  Messiaen’s  music,  it  would  be  a long  time  before  the  predator  and  the  cicada  would  meet long  time  before  the  predator  and  the  cicada  would  meet again. again.

Slide11Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking Prime  numbers  assist  us  more  in  today’s  society  than Prime  numbers  assist  us  more  in  today’s  society  than some  people  realise.  Internet  banking,  shopping  and some  people  realise.  Internet  banking,  shopping  and general  interaction  would  not  be  secure  if  it  wasn’t  for general  interaction  would  not  be  secure  if  it  wasn’t  for these  interesting  numbers.  A  particular  feature  of these  interesting  numbers.  A  particular  feature  of prime  factors  comes  in  very  useful  in  keeping  details prime  factors  comes  in  very  useful  in  keeping  details private… private…

Slide12Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking Codes  used  to  be  kept  entirely  private.  The Codes  used  to  be  kept  entirely  private.  The encoded  message,  the  key  to  decoding  the encoded  message,  the  key  to  decoding  the message…  everything  was  confidential.  However, message…  everything  was  confidential.  However, today  there  exist  a  technique  that  allows  encoded today  there  exist  a  technique  that  allows  encoded messages  and  even  the  method  to  unlocking  the messages  and  even  the  method  to  unlocking  the message  to  be  publicly  announced. message  to  be  publicly  announced.

Slide13Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking To  encode  a  message… To  encode  a  message… If  we  want  to  send  the  message  “HELLO”  we  simply  convert  it  into  a If  we  want  to  send  the  message  “HELLO”  we  simply  convert  it  into  a string  of  numbers: string  of  numbers: 0805121216 0805121216 (A=01,  B=02…  etc.) (A=01,  B=02…  etc.) We  can  then  raise  that  number  to  a  publicly  announced  power,  divide  it We  can  then  raise  that  number  to  a  publicly  announced  power,  divide  it by  another  number  which  has  again  been  publicly  announced  and  we by  another  number  which  has  again  been  publicly  announced  and  we will  be  left  with  a  remainder.  This  is  our  encoded  message… will  be  left  with  a  remainder.  This  is  our  encoded  message…

Slide14Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking To  decode  this  message… To  decode  this  message… The  person  who  received  the  coded  string  of  numbers The  person  who  received  the  coded  string  of  numbers would  raise  that  number  to  another  power  which would  raise  that  number  to  another  power  which would  only  be  known  to  them.  They  then  divide  it would  only  be  known  to  them.  They  then  divide  it again  by  the  number  publicly  announced  earlier  and again  by  the  number  publicly  announced  earlier  and the  remainder  from  that  would  be  the  string  of the  remainder  from  that  would  be  the  string  of numbers  that  break  down  to  say  “HELLO”! numbers  that  break  down  to  say  “HELLO”!

Slide15Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking For  Example… For  Example… Let  our  message  be  “E”.  “E”  is  converted  to  05,  and  is  then Let  our  message  be  “E”.  “E”  is  converted  to  05,  and  is  then raised  to  the  7 th   power  (this  is  important  and  will  be  explained raised  to  the  7 th   power  (this  is  important  and  will  be  explained later).  Our  number  is  now  78,125.  We  divide  that  number  by later).  Our  number  is  now  78,125.  We  divide  that  number  by 33  (again  will  be  explained  later)  to  give  2367  with  a 33  (again  will  be  explained  later)  to  give  2367  with  a remainder  of  14. remainder  of  14. 14  is  our  encoded  message. 14  is  our  encoded  message.

Slide16Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking Now,  to  decode… Now,  to  decode… We  raise  14  to  the  3 rd   power  to  give  2744.  We  divide We  raise  14  to  the  3 rd   power  to  give  2744.  We  divide that  number  by  33  which  gives  83  with  a  remainder  of that  number  by  33  which  gives  83  with  a  remainder  of 5… 5… 5  is  our  decoded  message  and  converts  to  “E”,  the 5  is  our  decoded  message  and  converts  to  “E”,  the original  message. original  message.

Slide17Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking 33  is  the  key  in  this  code  breaking  scenario.  There  is  a 33  is  the  key  in  this  code  breaking  scenario.  There  is  a mathematical  occurrence  deep  within  this  number mathematical  occurrence  deep  within  this  number concerning  its  prime  factors,  3  and  11. concerning  its  prime  factors,  3  and  11. If  we  multiply  the  numbers  that  are  one  less  than  the If  we  multiply  the  numbers  that  are  one  less  than  the factors  and  add  one  we  get  another  number.  So; factors  and  add  one  we  get  another  number.  So; (3-1)  x  (11-1)  +  1  =  21 (3-1)  x  (11-1)  +  1  =  21

Slide18Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking We  can  then  split  the  resulting  number  (21)  into  its We  can  then  split  the  resulting  number  (21)  into  its prime  factors,  3  and  7. prime  factors,  3  and  7. Notice  that  these  are  the  powers  used  to  code  and Notice  that  these  are  the  powers  used  to  code  and decode  the  message.  This  procedure  caries  through decode  the  message.  This  procedure  caries  through with  all  numbers,  no  matter  how  big  they  are.  This  is with  all  numbers,  no  matter  how  big  they  are.  This  is precisely  why  the  coding  works. precisely  why  the  coding  works.

Slide19Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking Now,  splitting  33  into  its  prime  factors  isn’t  really that  difficult.  However,  imagine  you  were  given: Now,  splitting  33  into  its  prime  factors  isn’t  really that  difficult.  However,  imagine  you  were  given: 34457638482334756487658734623864765476789475684365847568 34457638482334756487658734623864765476789475684365847568 36823764864352364238428734682736387642836482364357364329 36823764864352364238428734682736387642836482364357364329 84729037464364863483648774554768757645365078655445376545 84729037464364863483648774554768757645365078655445376545 43584385734587395790475934723984798574356765932740293874 43584385734587395790475934723984798574356765932740293874 9479487683746293479238794563475623846902374902347… 9479487683746293479238794563475623846902374902347…

Slide20Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking Splitting  that  number,  with  hundreds  of  digits,  into  two prime  factors  would  take  even  the  fastest  computer in  the  world  more  time  to  crack  it  than  the  Universe has  existed. Splitting  that  number,  with  hundreds  of  digits,  into  two prime  factors  would  take  even  the  fastest  computer in  the  world  more  time  to  crack  it  than  the  Universe has  existed. Unless  by  a  fluke  the  prime  factors  are  found,  it Unless  by  a  fluke  the  prime  factors  are  found,  it simply  takes  far  too  much  time  to  decode  the simply  takes  far  too  much  time  to  decode  the messages. messages.

Slide21Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking The  numbers  used  as  coding  and  decoding  powers  depend The  numbers  used  as  coding  and  decoding  powers  depend entirely  on  the  technology  available  at  the  time  and  the entirely  on  the  technology  available  at  the  time  and  the amount  of  time  it  would  take  a  computer  to  factor  a  number. amount  of  time  it  would  take  a  computer  to  factor  a  number. Since  the  messages  tend  to  be  a  lot  longer  than  “E”  or Since  the  messages  tend  to  be  a  lot  longer  than  “E”  or “HELLO”  the  process  becomes  longer  and  more  complicated, “HELLO”  the  process  becomes  longer  and  more  complicated, which  unfortunately  the  finite  nature  of  technology  can which  unfortunately  the  finite  nature  of  technology  can sometimes  struggle  to  cope  with. sometimes  struggle  to  cope  with.

Slide22Prime Numbers  In  Code  Breaking Prime  Numbers  In  Code  Breaking However,  since  no-ones  knows  of  a  way  of quickly  factorising  a  number  into  prime  factors the  process  is  quite  safe  for  now! However,  since  no-ones  knows  of  a  way  of quickly  factorising  a  number  into  prime  factors the  process  is  quite  safe  for  now!