2021/08/27 by Laura Monroe, Monroe, Laura
Computer Science · Mathematics · #11A63 #11B83 #68R01 #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11A63 #msc:11B83 #msc:68R01 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.12417
21 pages, 3 figures. Portions of this previously appeared as arXiv:2103.05810 which was split for publication
arxiv created 2021/08/27 · openalex publication_date 2021/08/27 · arxiv updated 2021/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The binary signed-digit representation of integers is used for efficient computation in various settings. The Stern polynomial is a polynomial extension of the well-studied Stern diatomic sequence, and has itself has been investigated in some depth. In this paper, we show previously unknown connections between BSD representations and the Stern polynomial. We derive a weight-distribution theorem for i-bit BSD representations of an integer n in terms of the coefficients and degrees of the terms of the Stern polynomial of 2i-n. We then show new recursions on Stern polynomials, and from these and the weight-distribution theorem obtain similar BSD recursions and a fast O(n) algorithm that calculates the number and number of 0s of the optimal BSD representations of all of the integers of NAF-bitlength log(n) at once, which then may be compared.