COUNTING FIXED DEGREE d ≥ 2 ADDITION CHAINS
Abstract
We denote the length of an addition chain with fixed degree $d\geq 2$ leading to $n$ by $l^d(n)$. We study the counting function $$F_d(m,r):=\#\{n\in[d^m,d^{m+1})~:~ l^d(n)\leq m+r\}$$establishing upper and lower bounds, which generalizes previous classical investigations of De Koninck, Doyon, and Verreault
Fields of Study & Subjects
Analytic Number Theory Research
Cryptography and Residue Arithmetic
Algebraic Geometry and Number Theory
Publication details
- Journal / source
- HAL
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Preprint