論文の概要: On the History of the Square and Multiply Algorithm

• arxiv url: http://arxiv.org/abs/2606.00958v2
• Date: Sat, 06 Jun 2026 02:20:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:04.688244
• Title: On the History of the Square and Multiply Algorithm
• Title（参考訳）: 正方形アルゴリズムと乗算アルゴリズムの歴史について
• Authors: Nuh Aydin, Mohammad K. Azarian, Omid Khormali, Ghaya Mtimet,
• Abstract要約: 2乗乗算アルゴリズム(英: square-and-multiply algorithm)は、現代の暗号理論や計算数理論でよく用いられる高速指数法である。 本稿では,一次音源解析によるアルゴリズムの起源と形式化を批判的に検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The square-and-multiply algorithm, also known as binary exponentiation or repeated squaring, is a technique for fast exponentiation commonly used in modern cryptography and computational number theory. Despite its prominence, the historical origins of the algorithm are not known with certainty. This paper critically examines the origins and formalization of the algorithm through primary source analysis. We focus on Jamshid al-Kashi's fifteenth-century Miftah al-Hisab where the algorithm is articulated explicitly as a general method and claimed by al-Kashi as his own innovation. To contextualize this, we trace earlier instances of successive squaring in the works of al-Uqlidisi and al-Biruni, who applied these techniques for specific calculations, but did not formalize them into a general procedure. The earliest known work on this method of computation is found in Pingala's prosodic studies in ancient India (c. 200 BCE). Even though it was not fully developed as a general technique, Pingala's work seems to contain the conceptual foundation of the algorithm which is to employ the binary representation of a positive integer. By mapping this intellectual progression, the paper illustrates the historical background of an algorithm that is prominent in modern computation.
• Abstract（参考訳）: 2乗乗算アルゴリズム(英: square-and-multiply algorithm)は、現代の暗号理論や計算数理論でよく用いられる高速指数法である。 その名声にもかかわらず、アルゴリズムの歴史的起源は確証がない。 本稿では,一次音源解析によるアルゴリズムの起源と形式化を批判的に検討する。 我々はJamshid al-Kashiの15世紀のMiftah al-Hisabに焦点をあてる。 これを文脈化するために、これらの手法を特定の計算に応用したアル・ウクリディディ(英語版)とアル・ビルニ(英語版)の著作において、連続したスクアリングの初期の例を辿ったが、それらを一般的な手順に定式化しなかった。 この方法に関する最も初期の研究は、古代インド(紀元前200年頃)のピンガラの韻律研究で確認されている。 一般的な手法として完全には開発されなかったが、ピンガラの研究には正の整数のバイナリ表現を利用するアルゴリズムの概念的基礎が含まれているようである。 この知的進歩をマッピングすることにより、現代の計算において顕著なアルゴリズムの歴史的背景を示す。

関連論文リスト

• Randomized and quantum approximate matrix multiplication [0.718791111462057]
  長い行の文献ではランダム化アルゴリズムを考慮し、より速い時間で近似解を返す。 まず、Cohen-Lewis (99) によるランダムウォークに基づく古典的アルゴリズムの洗練された解析を行い、Sarl'os (06) と Drineas-Kannan-Mahoney (06) によるスケッチに基づく。 次に、他のすべての手法よりも高速な1つの古典的アルゴリズムを生成するコーエン=ルイスの改良を提案する。
  論文  参考訳（メタデータ） (2025-10-09T17:44:03Z)
• Basic interactive algorithms: Preview [0.0]
  現代のアルゴリズムの概念は1930年代から1950年代にかけて解明された。 公理化は、すべての基本アルゴリズムに振る舞いに等価な抽象状態機械が存在することを示すために用いられた。
  論文  参考訳（メタデータ） (2025-08-07T19:13:47Z)
• The Evolution of Cryptography through Number Theory [55.2480439325792]
  暗号は100年ほど前に始まり、その起源はメソポタミアやエジプトといった古代文明にまでさかのぼる。 本稿では、初期情報隠蔽技術とRSAのような現代的な暗号アルゴリズムとの関係について検討する。
  論文  参考訳（メタデータ） (2024-11-11T16:27:57Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  順序の場合、すなわち n>2 クラスの集合上で全順序が定義される場合について研究する。 本稿では,従来のアルゴリズムよりも優れた正規化OQアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-13T16:04:06Z)
• Basic Quantum Algorithms [0.0]
  量子コンピューティングは急速に進化しており、理論の基礎を再検討し、書き直し、更新せざるを得ない。 基本量子アルゴリズムは、初期の量子アルゴリズムを再考する。
  論文  参考訳（メタデータ） (2022-01-25T19:00:10Z)
• Deep Algorithm Unrolling for Biomedical Imaging [99.73317152134028]
  本章では,アルゴリズムのアンロールによるバイオメディカル応用とブレークスルーについて概説する。 我々はアルゴリズムのアンローリングの起源を辿り、反復アルゴリズムをディープネットワークにアンローリングする方法に関する包括的なチュートリアルを提供する。 オープンな課題を議論し、今後の研究方向性を提案することで、この章を締めくくります。
  論文  参考訳（メタデータ） (2021-08-15T01:06:26Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。