With the challenge of quantum computing ahead, an analysis of number and representation adequate to the task is needed. Some clarifications on the combinatorial nature of representation are presented here; this is related to the foundations of digital representations of integers, and is thus also of interest in clarifying what numbers are and how they are used in pure and applied mathematics. The author hopes this work will help mathematicians and computer scientists better understand the nature of the Generalized Knapsack Code, a lattice-based code which the author believes to be particularly promising, and the use of number in computing in general.
References
[1]
Hamlin, N. (2016) Recurrence Representations: An Exploration of Number, Representation, and Public-Key Cryptography. Lambert Academic Publishing, Saarbrücken. (Originally published as a dissertation in 2012)
[2]
Hamlin, N., Krishnamoorthy, B. and Webb, W. (2015) A Knapsack-Like Code Using Recurrence Sequence Representations. The Fibonacci Quarterly, 1, 24-33.
[3]
Shamir, A. (1984) A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. IEEE Transactions on Information Theory, 30, 699-704. https://doi.org/10.1109/TIT.1984.1056964
[4]
Merkle, R.C. and Hellman, M.E. (1978) Hiding Information and Signatures in Trap Door Knapsacks. IEEE Transactions on Information Theory, 24, 525-530. https://doi.org/10.1109/TIT.1978.1055927
[5]
Dedekind, R. and Beman, W., Trans. (1909) Essays on the Theory of Numbers. The Open Court Publishing Company, Chicago.
[6]
Bernstein, D., Buchmann, J. and Dahmen, E. (Eds.) (2009) Post-Quantum Cryptography. Springer, Heidelberg.
[7]
Hoffstein, J., Pipher, J. and Silverman, J.H. (2008) An Introduction to Mathematical Cryptography. Springer Science, New York.
[8]
Husserl, E. and Bernet, R. (Eds.), Willard, D. (Trans.) (2003) Philosophy of Arithmetic: Psychological and Logical investigations with Supplementary Texts from 1887-1901. Springer Science, Dordrecht.
[9]
Hamlin, N. and Webb, W.A. (2012) Representing Positive Integers as a Sum of Linear Recurrence Sequences. The Fibonacci Quarterly, 50, 99-105.
[10]
Arvind, V. and Schuler, R. (2003) The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems. International Symposium on Algorithms and Computation, 2906, 168-177.
