Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji:
http://hdl.handle.net/11320/7843
Pełny rekord metadanych
Pole DC | Wartość | Język |
---|---|---|
dc.contributor.author | Okazaki, Hiroyuki | - |
dc.contributor.author | Nagao, Koh-ichi | - |
dc.contributor.author | Futa, Yuichi | - |
dc.date.accessioned | 2019-05-21T07:18:03Z | - |
dc.date.available | 2019-05-21T07:18:03Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Formalized Mathematics, Volume 27, Issue 1, Pages 87-91 | - |
dc.identifier.issn | 1426-2630 | - |
dc.identifier.uri | http://hdl.handle.net/11320/7843 | - |
dc.description.abstract | In this article we formalize in Mizar [1], [2] the maximum number of steps taken by some number theoretical algorithms, “right–to–left binary algorithm” for modular exponentiation and “Euclidean algorithm” [5]. For any natural numbers a, b, n, “right–to–left binary algorithm” can calculate the natural number, see (Def. 2), AlgoBPow(a, n, m) := ab mod n and for any integers a, b, “Euclidean algorithm” can calculate the non negative integer gcd(a, b). We have not formalized computational complexity of algorithms yet, though we had already formalize the “Euclidean algorithm” in [7].For “right-to-left binary algorithm”, we formalize the theorem, which says that the required number of the modular squares and modular products in this algorithms are ⌊1+log2 n⌋ and for “Euclidean algorithm”, we formalize the Lamé’s theorem [6], which says the required number of the divisions in this algorithm is at most 5 log10 min(|a|, |b|). Our aim is to support the implementation of number theoretic tools and evaluating computational complexities of algorithms to prove the security of cryptographic systems. | - |
dc.description.sponsorship | This study was supported in part by JSPS KAKENHI Grant Numbers JP17K00182 and JP15K00183. | - |
dc.language.iso | en | - |
dc.publisher | DeGruyter Open | - |
dc.subject | algorithms | - |
dc.subject | power residues | - |
dc.subject | Euclidean algorithm | - |
dc.title | Maximum Number of Steps Taken by Modular Exponentiation and Euclidean Algorithm | - |
dc.type | Article | - |
dc.identifier.doi | 10.2478/forma-2019-0009 | - |
dc.description.Affiliation | Hiroyuki Okazaki - Shinshu University, Nagano, Japan | - |
dc.description.Affiliation | Koh-ichi Nagao - Kanto Gakuin University, Kanagawa, Japan | - |
dc.description.Affiliation | Yuichi Futa - Tokyo University of Technology, Tokyo, Japan | - |
dc.description.references | Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007/978-3-319-20615-8_17. | - |
dc.description.references | Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, and Karol Pąk. The role of the Mizar Mathematical Library for interactive proof development in Mizar. Journal of Automated Reasoning, 61(1):9–32, 2018. doi:10.1007/s10817-017-9440-6. | - |
dc.description.references | Yoshinori Fujisawa, Yasushi Fuwa, and Hidetaka Shimizu. Euler’s Theorem and small Fermat’s Theorem. Formalized Mathematics, 7(1):123–126, 1998. | - |
dc.description.references | Magdalena Jastrzębska and Adam Grabowski. Some properties of Fibonacci numbers. Formalized Mathematics, 12(3):307–313, 2004. | - |
dc.description.references | Donald E. Knuth. Art of Computer Programming. Volume 2: Seminumerical Algorithms, 3rd Edition, Addison-Wesley Professional, 1997. | - |
dc.description.references | Gabriel Lamé. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Acad. Sci., 19:867–870, 1844. | - |
dc.description.references | Hiroyuki Okazaki, Yosiki Aoki, and Yasunari Shidama. Extended Euclidean algorithm and CRT algorithm. Formalized Mathematics, 20(2):175–179, 2012. doi:10.2478/v10037-012-0020-2. | - |
dc.description.references | Marco Riccardi. Pocklington’s theorem and Bertrand’s postulate. Formalized Mathematics, 14(2):47–52, 2006. doi:10.2478/v10037-006-0007-y. | - |
dc.identifier.eissn | 1898-9934 | - |
dc.description.volume | 27 | - |
dc.description.issue | 1 | - |
dc.description.firstpage | 87 | - |
dc.description.lastpage | 91 | - |
dc.identifier.citation2 | Formalized Mathematics | - |
Występuje w kolekcji(ach): | Formalized Mathematics, 2019, Volume 27, Issue 1 |
Pliki w tej pozycji:
Plik | Opis | Rozmiar | Format | |
---|---|---|---|---|
forma_2019_27_1_009.pdf | 273,63 kB | Adobe PDF | Otwórz |
Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL