I know that Hardy's work in number theory was used by Clifford Cocks in 1973 to develop the basis for public-key cryptography. What specifically was this work, and how is it used today in cryptography?
2
-
1$\begingroup$ The best thing to do is to read his famous book "introduction to number theory". You can find over the web some pdf, and I know there is a new edition some years ago. This is a reference for all those interested in theory of numbers. $\endgroup$– Robert NACIRISep 6, 2015 at 7:24
-
$\begingroup$ There is another connection with Hardy and crypto. Hardy believed (see, A Mathematician's apology) that number theory (and in general pure mathematics) should be practiced as an art, ignoring any possible application to our world. $\endgroup$– 111Sep 6, 2015 at 17:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I've been investigating and can't seem to find any reference to this. Could you say how you found this out?
Cocks's original paper makes reference to several results from number theory without attribution.
- An algorithm for determining if a number $M$ is prime with $\log M$ work, but which may fail to provide an answer (I think that this might be Pocklington's algorithm).
- A reference to the density of primes being roughly $1/\log M$, which is an observation of Gauss proven by Hadamard and de la Vallée Poussin
- The complexity of modular exponentiation being $(\log M)^k$ which is over 2000 years old (see Knuth vol. 2 for some history).
- An algorithm for factoring with complexity $N^{1/4}(\log N)^k$ (I think that this might be either Daniel Shanks's SQUFOF or CLASNO method).
G. H. Hardy made a large number of contributions to number theory, but none seem to be directly connected to any of the results used by Cocks.
$\begingroup$
$\endgroup$
I think there may not be any more to this than "despite what Hardy said regarding Number Theory has no applications...". A few links I dug up, none of which indicate any link to any concrete result by Hardy playing a role in this discovery.
- Part of the oration by Nigel Smart at the ceremony for honorary PhD for Cocks.
http://www.bristol.ac.uk/graduation/honorary-degrees/hondeg08/cocks.html
In 1940, the famous mathematician G.H. Hardy had remarked that Relativity and Number Theory were the truly great parts of mathematics as they had not been tainted by finding application. Hardy was soon proved wrong about relativity by the advent of the nuclear age, but in 1973 he was still correct about number theory. Clifford was about to alter that position for good by finding the most compelling application of Number Theory.
- Excerpt from Simon Singh's book which talks about this Alternative History of Public Key Crypto is below.
https://cryptome.org/ukpk-alt.htm
When Cocks did eventually realise what he had done, it struck him that his discovery might have disappointed G.H. Hardy, one of the great English mathematicians of the early part of the century. In his The Mathematician's Apology, written in 1940, Hardy had proudly stated: 'Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.' Real mathematics means pure mathematics, such as the number theory that was at the heart of Cocks's work. Cocks proved that Hardy was wrong. The intricacies of number theory could now be used to help generals plan their battles in complete secrecy. Because his work had implications for military communications, Cocks, like Ellis, was forbidden from telling anybody outside GCHQ about what he had done. Working at a top-secret government establishment meant that he could tell neither his parents nor his former colleagues at Cambridge University. The only person he could tell was his wife, Gill, since she was also employed at GCHQ.
- Ensuing discussion on uk-crypto mailing list:
https://cryptome.org/ukpk-true.htm
The main item of interest there is Ross Anderson claiming that the papers from GCHQ regarding Cocks' invention were "forged, not originals", since at that point even the existence of the GCHQ was denied.
- Comments by Diffie
