AN AUTHENTICATION METHOD BASED ON A DIOPHANTINE MODEL OF THE COIN BAG PROBLEM
Krzysztof NIEMIEC
(Poland)
https://orcid.org/0009-0008-8101-2789
Grzegorz BOCEWICZ
grzegorz.bocewicz@tu.koszalin.plKoszalin Univeristy of Technology (Poland)
https://orcid.org/0000-0002-5181-2872
Abstract
The article presents the so-called coin bag problem, which is modeled by linear Diophantine equations. The problem in question involves assessing the contents of a set of coins based on its weight. Since this type of problem is undecidable, a special variant of the problem was proposed for which effective problem-solving algorithms can be developed. In this paper, an original heuristic is presented (an algorithm based on problem decomposition) which allows to solve the coin bag problem in fewer steps compared to a brute force algorithm. The proposed approach was verified in a series of computational experiments. Additionally, an authentication scheme making use of the approach was proposed as an example of potential practical use.
Keywords:
Diophantine equations coin bag problem, decomposition algorithm, branch-and-bound method, authenticationReferences
Azrour, M., Mabrouki, J., Guezzaz, A., & Farhaoui, Y. (2021). New enhanced authentication protocol for Internet of Things. Big Data Mining and Analytics, 4(1), 1–9. https://doi.org/10.26599/BDMA.2020.9020010
DOI: https://doi.org/10.26599/BDMA.2020.9020010
Google Scholar
Barbeau, A. (2003). Pell’s equation. New York: Springer.
DOI: https://doi.org/10.1007/b97610
Google Scholar
Brody, J., & Verbin, E. (2010). The Coin Problem and Pseudorandomness for Branching Programs. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 30–39. https://doi.org/10.1109/FOCS.2010.10
DOI: https://doi.org/10.1109/FOCS.2010.10
Google Scholar
Clausen, M., & Fortenbacher, A. (1989). Efficient solution of linear diophantine equations. Journal of Symbolic Computation, 8(1–2), 201–216. https://doi.org/10.1016/S0747-7171(89)80025-2
DOI: https://doi.org/10.1016/S0747-7171(89)80025-2
Google Scholar
Darmon, H., Diamond, F., & Taylor, R. (1995). Fermat’s last theorem. Current developments in mathematics.
DOI: https://doi.org/10.4310/CDM.1995.v1995.n1.a1
Google Scholar
Gilbert, W. J., & Pathria, A. (1990). Linear Diophantine Equation. Manuscript.
Google Scholar
Haakegaard, R., & Lang, J. (2015). The Elliptic Curve Diffie-Hellman (ECDH).
Google Scholar
Jonsson, F., & Tornkvist, M. (2017). RSA authentication in Internet of Things: Technical limitations and industry expectations. Dissertation.
Google Scholar
Kane, D. M. (2006). An elementary derivation of the asymptotics of partition functions. The Ramanujan Journal, 11(1), 49–66. https://doi.org/10.1007/s11139-006-5307-x
DOI: https://doi.org/10.1007/s11139-006-5307-x
Google Scholar
Karimi, E., Kazemi, F., Heidarzadeh, A., & Sprintson, A. (2018). A Simple and Efficient Strategy for the Coin Weighing Problem with a Spring Scale. 2018 IEEE International Symposium on Information Theory (ISIT), 1730–1734. https://doi.org/10.1109/ISIT.2018.8437774
DOI: https://doi.org/10.1109/ISIT.2018.8437774
Google Scholar
Matiyasevich, Y. (1993). Hilbert’s 10th Problem. MIT press.
Google Scholar
Mordell, L. J. (1969). Diophantine Equations. Academic Press.
Google Scholar
Mumtaz, M., Akram, J., & Ping, L. (2019). An RSA Based Authentication System for Smart IoT Environment. 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), 758–765. https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00112
DOI: https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00112
Google Scholar
Picciotto, H. (1987). Math McPuzzle. 85(52).
DOI: https://doi.org/10.1163/22116117-90001475
Google Scholar
Pólya, G. (1956). On Picture-Writing. The American Mathematical Monthly, 63(10), 689–697. https://doi.org/10.1080/00029890.1956.11988895
DOI: https://doi.org/10.1080/00029890.1956.11988895
Google Scholar
Schell, E. D. (1945). Weighed and found wanting. 52(42).
DOI: https://doi.org/10.2307/2304840
Google Scholar
Stark, H. (1973). Effective estimates of solutions of some diophantine equations. 24(3), 251–259.
DOI: https://doi.org/10.4064/aa-24-3-251-259
Google Scholar
Tripathi, A. (1978). On a linear Diophantine problem of Frobenius. Journal Für Die Reine Und Angewandte Mathematik (Crelles Journal), 1978(301), 171–178. https://doi.org/10.1515/crll.1978.301.171
DOI: https://doi.org/10.1515/crll.1978.301.171
Google Scholar
Wiles, A. (1995). Modular elliptic curves and Fermat’s last theorem. Annals of mathematics.
DOI: https://doi.org/10.1007/978-3-0348-9078-6_18
Google Scholar
Wright, J. W. (1975). The Change-Making Problem. Journal of the ACM, 22(1), 125–128. https://doi.org/10.1145/321864.321874
DOI: https://doi.org/10.1145/321864.321874
Google Scholar
Authors
Grzegorz BOCEWICZgrzegorz.bocewicz@tu.koszalin.pl
Koszalin Univeristy of Technology Poland
https://orcid.org/0000-0002-5181-2872
Statistics
Abstract views: 191PDF downloads: 60
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.
Most read articles by the same author(s)
- Grzegorz BOCEWICZ, Robert WÓJCIK, Paweł SITEK, Zbigniew BANASZAK, TOWARDS DIGITAL TWIN-DRIVEN PERFORMANCE EVALUATION METHODOLOGY OF FMS , Applied Computer Science: Vol. 18 No. 3 (2022)
- Grzegorz RADZKI, Amila THIBBOTUWAWA, Grzegorz BOCEWICZ, UAVS FLIGHT ROUTES OPTIMIZATION IN CHANGING WEATHER CONDITIONS – CONSTRAINT PROGRAMMING APPROACH , Applied Computer Science: Vol. 15 No. 3 (2019)
- Janani DEWMINI, W Madushan FERNANDO, Izabela Iwa NIELSEN, Grzegorz BOCEWICZ, Amila THIBBOTUWAWA, Zbigniew BANASZAK, IDENTIFYING THE POTENTIAL OF UNMANNED AERIAL VEHICLE ROUTING FOR BLOOD DISTRIBUTION IN EMERGENCY REQUESTS , Applied Computer Science: Vol. 19 No. 4 (2023)
Similar Articles
- Esraa Alaa MAHAREEK, Doaa Rizk FATHY, Eman Karm ELSAYED, Nahed ELDESOUKY, Kamal Abdelraouf ELDAHSHAN, VIOLENCE PREDICTION IN SURVEILLANCE VIDEOS , Applied Computer Science: Vol. 20 No. 3 (2024)
- Łukasz SEMKŁO, Łukasz GIERZ, NUMERICAL AND EXPERIMENTAL ANALYSIS OF A CENTRIFUGAL PUMP WITH DIFFERENT ROTOR GEOMETRIES , Applied Computer Science: Vol. 18 No. 4 (2022)
- Peeraya THAPATSUWAN, Warattapop THAPATSUWAN, Chaichana KULWORATIT, ENHANCEMENT OF ARTIFICIAL IMMUNE SYSTEMS FOR THE TRAVELING SALESMAN PROBLEM THROUGH HYBRIDIZATION WITH NEIGHBORHOOD IMPROVEMENT AND PARAMETER FINE-TUNING , Applied Computer Science: Vol. 20 No. 4 (2024)
- Stanisław SKULIMOWSKI, Jerzy MONTUSIEWICZ, Marcin BADUROWICZ, ENHANCING THE EFFICIENCY OF THE LEVENSHTEIN DISTANCE BASED HEURISTIC METHOD OF ARRANGING 2D APICTORIAL ELEMENTS FOR INDUSTRIAL APPLICATIONS , Applied Computer Science: Vol. 19 No. 4 (2023)
- Anna CZARNECKA, Łukasz SOBASZEK, Antoni ŚWIĆ, 2D IMAGE-BASED INDUSTRIAL ROBOT END EFFECTOR TRAJECTORY CONTROL ALGORITHM , Applied Computer Science: Vol. 14 No. 1 (2018)
- Mantas Vaitonis, Konstantinas Korovkinas, THE POTENTIAL FOR REAL-TIME TESTING OF HIGH FREQUENCY TRADING STRATEGIES THROUGH A DEVELOPED TOOL DURING VOLATILE MARKET CONDITIONS , Applied Computer Science: Vol. 19 No. 2 (2023)
- Kuba ROSŁANIEC, ANALYSIS OF THE EFFECT OF PROJECTILE IMPACT ANGLE ON THE PUNCTURE OF A STEEL PLATE USING THE FINITE ELEMENT METHOD IN ABAQUS SOFTWARE , Applied Computer Science: Vol. 18 No. 1 (2022)
- Mohammed A. Hussein, Ekhlas H. Karam, Rokaia S. Habeeb, CANCER GROWTH TREATMENT USING IMMUNE LINEAR QUADRATIC REGULATOR BASED ON CROW SEARCH OPTIMIZATION ALGORITHM , Applied Computer Science: Vol. 17 No. 2 (2021)
- Sri INDRA MAIYANTI, Anita DESIANI, Syafrina LAMIN, P PUSPITAHATI, Muhammad ARHAMI, Nuni GOFAR, Destika CAHYANA, ROTATION-GAMMA CORRECTION AUGMENTATION ON CNN-DENSE BLOCK FOR SOIL IMAGE CLASSIFICATION , Applied Computer Science: Vol. 19 No. 3 (2023)
- Waldemar SUSZYŃSKI, Małgorzata CHARYTANOWICZ, Wojciech ROSA, Leopold KOCZAN, Rafał STĘGIERSKI, DETECTION OF FILLERS IN THE SPEECH BY PEOPLE WHO STUTTER , Applied Computer Science: Vol. 17 No. 4 (2021)
<< < 1 2 3 4 5 6 7 8 9 10 > >>
You may also start an advanced similarity search for this article.