God almighty, APG says bitcoin currently uses half the world's computing cycles??? And it isn't even very popular at present??!!?! What a nightmare. What an utterly colossal epic fail for humanity. That's worse than the "gold standard" was. See papers underlying "digicash" digital money by David Chaum et al for something actually comparatively sensible, though his company digicash ended up failed. [I do not think you can replace the PKC inside with some lattice based "post quantum" PKC, it is not that simple, sorry.] If you can figure out how to produce quantum-immune digital money with properties like Chaum had, that I think would be an excellent accomplishment. I used to think quantum computers would never happen, but they are worrying... On 7/14/14, math-fun-request@mailman.xmission.com <math-fun-request@mailman.xmission.com> wrote:
Send math-fun mailing list submissions to math-fun@mailman.xmission.com
To subscribe or unsubscribe via the World Wide Web, visit https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun or, via email, send a message with subject or body 'help' to math-fun-request@mailman.xmission.com
You can reach the person managing the list at math-fun-owner@mailman.xmission.com
When replying, please edit your Subject line so it is more specific than "Re: Contents of math-fun digest..."
Today's Topics:
1. Re: "period" 6 (Dan Asimov) 2. Post-quantum proof-of-work system? (Warren D Smith) 3. Shanks' 707 digits (James Propp) 4. Re: Shanks' 707 digits (Hans Havermann) 5. Warren Smith versus Bitcoin (was Re: Post-quantum proof-of-work system?) (Adam P. Goucher) 6. Mildly surprising: The 2-sphere of radius 2 (Bill Gosper) 7. Re: Mildly surprising: The 2-sphere of radius 2 (Tom Rokicki)
----------------------------------------------------------------------
Message: 1 Date: Sun, 13 Jul 2014 22:46:27 -0700 From: Dan Asimov <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] "period" 6 Message-ID: <8536A091-E207-47F1-8975-ACEC97915CAE@earthlink.net> Content-Type: text/plain; charset=utf-8
This has to be due to the Pisotudinousness of GoldenRatio, and the +-1 slope of Sin at multiples of Pi.
--Dan
On Jul 13, 2014, at 10:33 PM, Bill Gosper <billgosper@gmail.com> wrote:
On Sun, Jul 13, 2014 at 8:57 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[360]:= Table[GoldenRatio^n*Sin[?*GoldenRatio^n] // N[N[#, 99]] &, {n, 69, 105}]
Out[360]= {3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159} --rwg
Whereas In[362]:=Table[ (Sqrt[2] + Sqrt[3])^n*Sin[?*(Sqrt[2] + Sqrt[3])^n]/? // N[N[#, 99]] &, {n, 69, 105}]
Out[362]= {6.81476*10^33, -1., 6.77788*10^34, -1., -4.89061*10^35, -1., -2.09519*10^36, -1., -4.56286*10^37, -1., -4.59961*10^38, -1., -3.15805*10^39, -1., 5.68896*10^40, -1., 2.91069*10^41, -1., -2.724*10^42, -1., -4.32617*10^43, -1., -4.06476*10^44, -1., 4.21738*10^44, -1., 6.08704*10^46, -1., 5.32596*10^47, -1., 1.94754*10^48, -1., 5.52776*10^49, -1., -5.72711*10^50, -1., -5.86847*10^51} --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Message: 2 Date: Mon, 14 Jul 2014 09:53:21 -0400 From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Post-quantum proof-of-work system? Message-ID: <CAAJP7Y04wnTcOFiTQyo61wxZC=caXWLJjprunkW4-t_JtQn3sw@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
If you were not worried about having exponentially large memory for a classical computer I suppose to be fair we should allow this for a quantum computer too.
In that case, you could have the quantum computer seek 2^(n*C) words, at least two of which agree about the first n bits of their hash. This has probability of occurrence that is of order 2^(-max(1-2*C, 0)*n) if random words are tried.
Now there are versions of Grover search algorithm, which run in expected #steps proportional to about squareroot(1/p) where p=probability of occurrence. If time for a step is here 2^(n*C), then total time is of order 2^( (C + max(1-2*C,0)) * n ) which is optimized by choosing C=1/3, which causes the quantum runtime to be of order 2^( n*2/3 ).
So... no. The quantum computer here is faster than the classical algorithm, so Adam Goucher's proposal only partially worked.
While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind. Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever). Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken.
These still will be busted by quantum computers though (which bust the PKC schemes that were used).
------------------------------
Message: 3 Date: Mon, 14 Jul 2014 10:27:46 -0400 From: James Propp <jamespropp@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Shanks' 707 digits Message-ID: <CA+G9J-ea4sNTtaE42OS9Y6qOjMUawx9GOQt8BvV-OrYt-CuKuQ@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
Does anyone know what precise error (or errors) William Shanks made?
(see http://en.m.wikipedia.org/wiki/William_Shanks)
E.g., if you take the difference between Shanks' 707-digit approximation to pi and the 707-digit truncation of pi, do you get the initial digits of some rational number?
Jim Propp
------------------------------
Message: 4 Date: Mon, 14 Jul 2014 11:39:11 -0400 From: Hans Havermann <gladhobo@teksavvy.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Shanks' 707 digits Message-ID: <DEB3E289-2825-4101-9EDC-783C887976FC@teksavvy.com> Content-Type: text/plain; charset=us-ascii
http://www.engert.us/erwin/miscellaneous/William%20Shanks%20707%20digits.pdf
I believe the "707 digits" refers to decimal places. The first 527 (excluding typos) were correct. I think your difference is 696972233400402414486921529175050301808106570457226115312565026347185368614269829439388229424273703513612402766518096376765306056957758635728165741884423700490282252529162636899/10^706.
On Jul 14, 2014, at 10:27 AM, James Propp <jamespropp@gmail.com> wrote:
Does anyone know what precise error (or errors) William Shanks made?
E.g., if you take the difference between Shanks' 707-digit approximation to pi and the 707-digit truncation of pi, do you get the initial digits of some rational number?
------------------------------
Message: 5 Date: Mon, 14 Jul 2014 19:22:35 +0200 From: "Adam P. Goucher" <apgoucher@gmx.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Warren Smith versus Bitcoin (was Re: Post-quantum proof-of-work system?) Message-ID: <trinity-8cfeb0c9-5cca-47a7-b056-2322f5ef4d06-1405358555663@3capp-mailcom-bs05>
Content-Type: text/plain; charset=UTF-8
Warren Smith wrote:
While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind.
?!
Have you read the original paper? It's quite a beautiful system.
Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever).
It already uses about half of the world's computing power, apparently. Of course, one can replace the proof-of-work system with something different (and useful), such as how PrimeCoin resulted in vast quantities of Cunningham chains being discovered.
Basically, the proof-of-work can be anything that's in NP but not in P. And ideally we don't want quantum computers to be vastly better than classical computers, although it doesn't matter too much when quantum computers go mainstream (since then the `honest nodes' will again have more processing power than `attacker nodes').
Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken.
How do you prevent double-spending without either a proof-of-work-driven blockchain (a la Bitcoin) or a centralised server (in which case the owners can cheat)?
These still will be busted by quantum computers though (which bust the PKC schemes that were used).
It's fairly easy to replace every instance of `elliptic curve DSA' with `lattice-based cryptography' to make a public-key cryptosystem resistant to quantum computers.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Message: 6 Date: Mon, 14 Jul 2014 10:59:11 -0700 From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Mildly surprising: The 2-sphere of radius 2 Message-ID: <CAA-4O0FJ=2ud3APigxd-y+zO-KYNMzP9aUNZS=KLTwKWrv3BCA@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
(at the origin) bisects the unit 2-sphere at (1,1,1): Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, {0, 2}, {0, 2}}] gosper.org/2spheres.png --rwg
------------------------------
Message: 7 Date: Mon, 14 Jul 2014 11:06:23 -0700 From: Tom Rokicki <rokicki@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Mildly surprising: The 2-sphere of radius 2 Message-ID: <CAGia-=UJ2DgmaUk3vn26Y__3ae5G764Qh+YNNRMEiBbGBApnmg@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
Nice!
On Mon, Jul 14, 2014 at 10:59 AM, Bill Gosper <billgosper@gmail.com> wrote:
(at the origin) bisects the unit 2-sphere at (1,1,1): Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, {0, 2}, {0, 2}}] gosper.org/2spheres.png --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
------------------------------
Subject: Digest Footer
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
End of math-fun Digest, Vol 137, Issue 20 *****************************************
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)