HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Other publications

On the Number of Carries Occuring in an Addition $\mod 2^k-1$

Abstract : In this paper we study the number of carries occurring while performing an addition modulo $2^k-1$. For a fixed modular integer $t$, it is natural to expect the number of carries occurring when adding a random modular integer $a$ to be roughly the Hamming weight of $t$. Here we are interested in the number of modular integers in $\Zk$ producing strictly more than this number of carries when added to a fixed modular integer $t \in \Zk$. In particular it is conjectured that less than half of them do so. An equivalent conjecture was proposed by Tu and Deng in a different context~\cite{DCC:TD}. Although quite innocent, this conjecture has resisted different attempts of proof~\cite{DBLP:conf/seta/FloriRCM10, cryptoeprint:2010:170, cusick_combinatorial_2011, Carlet:Private} and only a few cases have been proved so far. The most manageable cases involve modular integers $t$ whose bits equal to $\textttup{0}$ are sparse. In this paper we continue to investigate the properties of $\Ptk$, the fraction of modular integers $a$ to enumerate, for $t$ in this class of integers. Doing so we prove that $\Ptk$ has a polynomial expression and describe a closed form of this expression. This is of particular interest for computing the function giving $\Ptk$ and studying it analytically. Finally we bring to light additional properties of $\Ptk$ in an asymptotic setting and give closed forms for its asymptotic values.
Document type :
Other publications
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00642291
Contributor : Jean-Pierre Flori Connect in order to contact the contributor
Submitted on : Thursday, November 17, 2011 - 5:17:37 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Friday, November 16, 2012 - 11:21:37 AM

File

245.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00642291, version 1

Collections

Citation

Jean-Pierre Flori, Hugues Randriambololona. On the Number of Carries Occuring in an Addition $\mod 2^k-1$. 2011. ⟨hal-00642291⟩

Share

Metrics

Record views

122

Files downloads

55