REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: `http://hdl.handle.net/11320/7843`
 Tytuł: Maximum Number of Steps Taken by Modular Exponentiation and Euclidean Algorithm Autorzy: Okazaki, HiroyukiNagao, Koh-ichiFuta, Yuichi Słowa kluczowe: algorithmspower residuesEuclidean algorithm Data wydania: 2019 Data dodania: 21-maj-2019 Wydawca: DeGruyter Open Źródło: Formalized Mathematics, Volume 27, Issue 1, Pages 87-91 Abstrakt: 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. Afiliacja: Hiroyuki Okazaki - Shinshu University, Nagano, JapanKoh-ichi Nagao - Kanto Gakuin University, Kanagawa, JapanYuichi Futa - Tokyo University of Technology, Tokyo, Japan Sponsorzy: This study was supported in part by JSPS KAKENHI Grant Numbers JP17K00182 and JP15K00183. URI: http://hdl.handle.net/11320/7843 DOI: 10.2478/forma-2019-0009 ISSN: 1426-2630 e-ISSN: 1898-9934 Typ Dokumentu: Article Występuje w kolekcji(ach): Formalized Mathematics, 2019, Volume 27, Issue 1

Pliki w tej pozycji:
Plik Opis RozmiarFormat