2015/06/09 by Shizuo Kaji, Kaji, Shizuo, Toshiaki Maeno +5
Computer Science · Mathematics · #05E05 #11T06 (primary) #68R05 #94A60 #Coding theory and cryptography #Combinatorics (math.CO) #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT) #cs.CR #cs.IT #math.CO #math.IT #math.NT #msc:05E05 #msc:11T06 #msc:68R05 #msc:94A60
paper · pdf · doi:10.48550/arxiv.1506.02742
(v2) Improved results and new observations (v3) The authors are notified that our main theorem (Theorem 2) appears (by a different approach) in [C. Sturtivant, G. S. Frandsen: Theoretical Computer Science 112 (1993) 291-309]. The authors would like to keep this preprint online for reference purposes
openalex publication_date 2015/06/09 · arxiv created 2016/02/19 · arxiv updated 2016/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known that any n-variable function on a finite prime field of characteristic p can be expressed as a polynomial over the same field with at most pn monomials. However, it is not obvious to determine the polynomial for a given concrete function. In this paper, we study the concrete polynomial expressions of the carries in addition and multiplication of p-ary integers. For the case of addition, our result gives a new family of symmetric polynomials, which generalizes the known result for the binary case p = 2 where the carries are given by elementary symmetric polynomials. On the other hand, for the case of multiplication of n single-digit integers, we give a simple formula of the polynomial expression for the carry to the next digit using the Bernoulli numbers, and show that it has only (n+1)(p-1)/2 + 1 monomials, which is significantly fewer than the worst-case number pn of monomials for general functions. We also discuss applications of our results to cryptographic computation on encrypted data.