home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15430 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  2.0 KB
  1. Xref: sparky sci.math:15430 sci.physics:19509
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!caen!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
  3. From: israel@unixg.ubc.ca (Robert B. Israel)
  4. Newsgroups: sci.math,sci.physics
  5. Subject: Re: RSA Encryption
  6. Date: 23 Nov 92 21:28:19 GMT
  7. Organization: The University of British Columbia
  8. Lines: 27
  9. Message-ID: <israel.722554099@unixg.ubc.ca>
  10. References: <avatarp.722363576@well.sf.ca.us> <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU> <1992Nov22.224208.12455@galois.mit.edu> <1992Nov23.014117.21496@CSD-NewsHost.Stanford.EDU>
  11. NNTP-Posting-Host: unixg.ubc.ca
  12. Keywords: cryptography, primes
  13.  
  14. In <1992Nov23.014117.21496@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU
  15.  (Vaughan R. Pratt) writes:
  16. > John's argument can strengthened as follows (found this even earlier,
  17. >around 1967 when I could still remember 4th year physics).  If the
  18. >distribution of states unfolds according to a linear operator U(t),
  19. >then the future of the universe can be predicted by raising the matrix
  20. >U(1) to any desired power by repeated squaring.  This enables one to
  21. >peek n steps into the nondeterministic future with only log n
  22. >squarings.
  23.  
  24. >My conclusion at the time was that this showed that the universe can't
  25. >be linear, or we could manufacture time paradoxes.  Now my feelings are
  26. >(i) U(1) is a big sucker, and (ii) should one be able to make out the
  27. >top quark just by staring at U(1)?
  28.  
  29. "Big sucker" is putting it mildly.   You want to predict the answer you'll
  30. get from a computer that will execute n steps and then halt?  Your Hilbert
  31. space will have to have at least one dimension for each possible state of
  32. the computer, in order to describe its behaviour.  If the computer is not
  33. going to go into an infinite loop, it needs at least n different states.
  34. So just one squaring of U(1), sparse or not, will require at least n steps.
  35. You can't win... 
  36. -- 
  37. Robert Israel                            israel@math.ubc.ca
  38. Department of Mathematics             or israel@unixg.ubc.ca
  39. University of British Columbia
  40. Vancouver, BC, Canada V6T 1Y4
  41.