A new Binary Number Code and a Multiplier, based on 3 as semi-primitive root of 1 mod 2^k

2001/05/03 by N. F. Benschop, Nico F. Benschop, Benschop, N. F.
Computer Science · Engineering · Mathematics · #11A07 #11A63 #Advanced Wireless Communication Techniques #Coding theory and cryptography #FOS: Mathematics #General Mathematics (math.GM) #graph theory and CDMA systems #math.GM #msc:11A07 #msc:11A63

paper · pdf · doi:10.48550/arxiv.math/0105029

3 pages. Patent US-5923888 (13-july-1999). See also http://home.iae.nl/users/benschop/pat3star.dvi and and http://164.195.100.11/netahtml/srchnum.htm (type nr: 5923888)

arxiv created 2001/05/03 · openalex publication_date 2001/05/03 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The powers of 3 generate half of the odd residues mod 2^k (k>2), and a sign change yields the other half. In other words: 3 is a semi-primitive root of 1 mod 2^k (k>2). Hence each k-bit residue is n = +/- 3ⁱ.2^j mod 2^k, with unique non-neg exponent pair: i<2^k-2 and j

Related

• Semi-primitive roots and the discrete logarithm module 2^k
• Fast Integer Multiplication using Modular Arithmetic
• Memory Efficient Arithmetic
• An Improved Integer Modular Multiplicative Inverse (modulo 2^w)
• Secure Montgomery Multiplication and Repeated Squares for Modular Exponentiation