Product–Congruence Games: A Unified Impartial-Game Framework for RSA ( ϕ ​ – ​ MuM \phi\text{--}\mathrm{MuM} ) and AES ( poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} )

Satyam Tyagi · 2025

Read Product–Congruence Games: A Unified Impartial-Game Framework for RSA ( ϕ ​ – ​ MuM \phi\text{--}\mathrm{MuM} ) and AES ( poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} ) by Satyam Tyagi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20087.txt.

Introduction

Satyam Tyagi builds a shared game frame that covers core steps inside two famous ciphers. His 2025 paper argues that RSA exponent work and AES box inversion rest on one play principle. The game tracks the product of heap values under modular or finite-field rules. That single tracked value unifies the algebra at the heart of both systems. Two companion games carry the proof of concept.

The first game compresses a chained RSA exponent task into a nim-like form, and its losing cases split by a classic remainder theorem. The second models field inversion as used in the AES box. There a single-hole trait makes game values multiply cleanly in a key region. Four broad theorems then set the frame's limits and rhythms. Tyagi stresses the parts are classical. The novelty is the shared lens that binds both ciphers.

Catalog record

CREATORSatyam Tyagi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20087

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Product–Congruence Games: A Unified Impartial-Game Framework for RSA ( ϕ ​ – ​ MuM \phi\text{--}\mathrm{MuM} ) and AES ( poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} ) Satyam Tyagi Abstract RSA exponent reduction and AES S-box inversion share a hidden commonality: both are governed by the same impartial combinatorial principle, which we call a Product–Congruence Game ( PCG \mathrm{PCG} ). A PCG \mathrm{PCG} tracks play via the modular (or finite-field) product of heap values, providing a single invariant that unifies the algebraic cores of these two ubiquitous symmetric and asymmetric cryptosystems. We instantiate this framework with two companion games. First, ϕ ​ – ​ MuM \phi\text{--}\mathrm{MuM} , where a left-associated “multi-secret” RSA exponent chain compresses via our Compression Theorem into the game of Multiplicative Modular Nim, PCG ⁡ ( k , { 1 } ) \mathrm{PCG}(k,\{1\}) , with k = ord N ⁡ ( g ) k=\operatorname{ord}_{N}(g) . The losing predicate of this game can then be factorized using the Chinese Remainder Theorem, mirroring RSA’s implementation. Second, poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} , our model for finite-field inversion in systems like AES. For poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} , we prove the single-hole property holds within its Threshold Region, which in turn implies that the Sprague-Grundy ( SG \operatorname{SG} ) values are multiplicative for disjunctive sums in that region. Beyond these concrete instances, we establish four structural theorems for general Product–Congruence Games PCG ⁡ ( m , R ) \mathrm{PCG}(m,R) : (i) single-heap repair above the modulus, (ii) ultimate period m m per coordinate, (iii) exact and asymptotic losing densities, and (iv) confinement of optimal play to a finite Indeterminacy Region . An operation-alignment collapse principle finally explains why some variants degenerate to a single aggregate while MuM, ϕ ​ – ​ MuM \phi\text{--}\mathrm{MuM} and poly – ​ MuM \textit{poly}\text{--}\mathrm{MuM} retain non-trivial structure. All ingredients (orders, CRT, finite fields) are classical; the novelty lies in this unified aggregation-compression viewpoint that embeds RSA and AES inside one impartial-game framework, together with the structural and collapse theorems for the resulting games. Keywords: Product–Congruence Game, Multiplicative Modular Nim, RSA, AES S-box, Threshold Region, Indeterminacy Region, Sprague–Grundy multiplicativity, operation alignment, aggregation–compression MSC Classification (2020): 91A46 (primary), 11A07, 94A60, 05A99 1 Introduction Our main contribution is to show that the algebraic cores of RSA (exponent reduction via Carmichael and the Chinese Remainder Theorem) and AES (finite-field inversion in \mathbb{F}_{2^{\!8}} ) can be analysed inside the same class of impartial combinatorial games . The key is a single multiplicative product-congruence invariant. A left-associated “multi-secret RSA exponent chain” compresses exactly to Multiplicative Modular Nim (MuM); its finite-field analogue, \textit{poly}\text{--}\mathrm{MuM} , models the AES S-box inversion. Impartial games often admit succinct aggregating invariants (Nim’s bitwise XOR ( Bouton 1901 ; Sprague and Grundy 1939 ) ). Our earlier work introduced MuM, replacing XOR by a modular product ( Tyagi 2025 ) . Here we show that the same multiplicative invariant explains both RSA’s exponent reduction and AES’s field inversion when they are cast as product-congruence games . From exponent chain to product congruence (Compression Theorem). Fix an RSA modulus N and g\in(\mathbb{Z}/N\mathbb{Z})^{\times} . A position \mathbf{h}=(h_{1},\dots,h_{n}) evaluates to E(\mathbf{h})=(((g^{h_{1}})^{h_{2}})^{h_{3}}\cdots)^{h_{n}}\pmod{N}, and is losing iff E(\mathbf{h})=g . Left-association gives E(\mathbf{h})=g^{H} with H=\prod_{i}h_{i} . If k=\operatorname{ord}_{N}(g) then E(\mathbf{h})\equiv g\;\Longleftrightarrow\;H\equiv 1\pmod{k}, so the chain game is isomorphic to \mathrm{PCG}(k,\{1\}) (MuM at modulus k ). With k=\prod p_{j}^{\alpha_{j}} the losing predicate CRT-factorizes, mirroring RSA implementations. A unified framework: Product-Congruence Games. The compressed form motivates product-congruence games \mathrm{PCG}(m,R) : positions are integer vectors, a move strictly decreases one heap, and a position is losing when \prod t_{i}\bmod m\in R . The chain game is \mathrm{PCG}(k,\{1\}) ; classical MuM is \mathrm{PCG}(m,\{1\}) . The finite-field instance \textit{poly}\text{--}\mathrm{MuM} plays the same game over \mathbb{F}_{2^{\!8}}^{\times} , matching the AES S-box inversion step. Structural localisation and the Indeterminacy Region. For every \mathrm{PCG}(m,R) we prove: (i) single-heap repair - if the residue is not in R and some heap \geq m , one move reaches R ; (ii) ultimate period m in each coordinate (numeric model); (iii) confinement of all residual strategy to the finite Indeterminacy Region I_{m}=[1,m-1]^{n} (field analogue: I_{q} with q-1 ). The proof uses an aggregation-compression normalisation: aggregate the invariant, compress to one canonical heap, then perform the single legal repair move. Collapse boundaries (operation alignment). If the local move operation aligns with the invariant (e.g. subtraction for a sum-mod game, or divisor moves for a product-mod game) the multi-heap game collapses outside the finite region to a trivial single aggregate. MuM and \textit{poly}\text{--}\mathrm{MuM} avoid collapse because their moves are additive while the invariant is multiplicative. Key Contributions 1. Unified RSA/AES game lens. RSA’s exponent reduction and the AES S-box inversion live in the same impartial-game class driven by a product-congruence invariant (MuM / \textit{poly}\text{--}\mathrm{MuM} ). 2. Compression Theorem. A multi-secret RSA exponent chain is isomorphic to \mathrm{PCG}(k,\{1\}) with k=\operatorname{ord}_{N}(g) ; the losing predicate factorizes via CRT. 3. Structural theorems for \mathrm{PCG}(m,R) . SG multiplicativity in the Threshold Region T_{\bullet} (numeric and field models) via the single-hole property; single-heap repair; ultimate period m per coordinate (numeric); exact/asymptotic losing densities; all residual complexity confined to the finite I_{\bullet} . 4. Collapse boundaries. An operation-alignment principle explains why aligned variants collapse while MuM and \textit{poly}\text{--}\mathrm{MuM} retain strategic depth. Related Work Orders, Carmichael’s \lambda , CRT ( Rivest et al. 1978 ; Carmichael 1912 ) , AES field inversion ( National Institute of Standards and Technology 2001 ) , and impartial game theory ( Sprague and Grundy 1939 ) are classical. Our earlier paper introduced MuM and \textit{poly}\text{--}\mathrm{MuM} ( Tyagi 2025 ) . Strategic game-theoretic models of cryptography do exist—see Katz’s survey on rational protocols ( Katz 2008 ) —but they analyse mixed-strategy equilibria for secure-multiparty computation and rely on probabilistic moves, rather than on the perfect-information impartial games used here. We are not aware of prior work that places RSA and AES under a single impartial-game invariant or proves the accompanying compression and collapse theorems. Organisation. • Section 2 proves the Compression Theorem. • Section 3 formalises \mathrm{PCG}(m,R) and its structure. • Section 4 gives collapse boundaries. • Section 5 develops the unified RSA ( \phi\text{--}\mathrm{MuM} ) / AES ( \textit{poly}\text{--}\mathrm{MuM} ) perspective. • Section 6 concludes with future directions. 2 The Exponent Chain Game and its Compression This section isolates the RSA lens (the “exponent-chain” game) and shows it compresses exactly to MuM at modulus k=\operatorname{ord}_{N}(g) . 2.1 Game definition Fix an RSA modulus N\geq 2 and g\in(\mathbb{Z}/N\mathbb{Z})^{\times} of order k=\operatorname{ord}_{N}(g) (so k\mid\lambda(N) ). The exponent-chain ( “ \phi\text{--}\mathrm{MuM} ” ) game is: Positions \mathbf{h}=(h_{1},\dots,h_{n})\in\mathbb{N}^{n} with each h_{i}\geq 1 . Evaluation E(\mathbf{h})=(((g^{h_{1}})^{h_{2}})^{h_{3}}\cdots)^{h_{n}}\pmod{N}. Losing predicate \mathbf{h} is losing iff E(\mathbf{h})\equiv g\pmod{N} . Moves Pick an index i with h_{i}>1 and replace h_{i} by some h_{i}^{\prime}<h_{i} . Once h_{i}\geq k we restrict the decrement to 1\leq h_{i}-h_{i}^{\prime}\leq k-1 to forbid residue-preserving “null moves.” Flattening. Because (g^{a})^{b}=g^{ab} we have E(\mathbf{h})\equiv g^{H(\mathbf{h})}\quad\text{with}\quad H(\mathbf{h}):=\prod_{i=1}^{n}h_{i}. 2.2 Compression and CRT factorisation Theorem 2.1 (Compression Theorem) . E(\mathbf{h})\equiv g\pmod{N} iff H(\mathbf{h})\equiv 1\pmod{k} . Proof. Flattening the exponent chain gives E(\mathbf{h})\equiv g^{H(\mathbf{h})}\pmod{N} . By the definition of multiplicative order k=\operatorname{ord}_{N}(g) , \displaystyle E(\mathbf{h})\equiv g\pmod{N} \displaystyle\iff g^{H(\mathbf{h})}\equiv g^{1}\pmod{N} \displaystyle\iff g^{H(\mathbf{h})-1}\equiv 1\pmod{N} \displaystyle\iff k\mid\bigl(H(\mathbf{h})-1\bigr) \displaystyle\iff H(\mathbf{h})\equiv 1\pmod{k}.\qed Corollary 2.2 (CRT factorisation) . If k=\prod_{j=1}^{r}p_{j}^{\alpha_{j}} , then \mathbf{h} is losing iff H(\mathbf{h})\equiv

Read the complete text