Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20087 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908469186002944 |
|---|---|
| author | Tyagi, Satyam |
| author_facet | Tyagi, Satyam |
| contents | 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). A Product-Congruence Game 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, in which a left-associated "multi-secret" RSA exponent chain compresses into the game of Multiplicative Modular Nim, PCG($k,\{1\}$), where $k = ord_N(g)$. The losing predicate then factorizes via the Chinese remainder theorem, mirroring RSA's structure. Second, poly-MuM, our model for finite-field inversion such as the AES S-box. For poly-MuM we prove the single-hole property inside its threshold region, implying that the Sprague-Grundy values are multiplicative under disjunctive sums in that region. Beyond these instances, we establish four structural theorems for a general Product-Congruence Game PCG($m,R$): (i) single-heap repair above the modulus, (ii) ultimate period $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 explains why some variants degenerate to a single aggregate while MuM, $ϕ$-MuM and poly-MuM retain rich local structure. All ingredients (multiplicative orders, the Chinese remainder theorem, finite fields) are classical; the contribution is the unified aggregation-compression viewpoint that embeds both RSA and AES inside one impartial-game framework, together with the structural and collapse theorems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20087 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Product-Congruence Games: A Unified Impartial-Game Framework for RSA ($ϕ$-MuM) and AES (poly-MuM) Tyagi, Satyam Discrete Mathematics Cryptography and Security Information Theory 91A46 (primary), 11A07, 94A60, 05A99 G.2.1; E.3 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). A Product-Congruence Game 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, in which a left-associated "multi-secret" RSA exponent chain compresses into the game of Multiplicative Modular Nim, PCG($k,\{1\}$), where $k = ord_N(g)$. The losing predicate then factorizes via the Chinese remainder theorem, mirroring RSA's structure. Second, poly-MuM, our model for finite-field inversion such as the AES S-box. For poly-MuM we prove the single-hole property inside its threshold region, implying that the Sprague-Grundy values are multiplicative under disjunctive sums in that region. Beyond these instances, we establish four structural theorems for a general Product-Congruence Game PCG($m,R$): (i) single-heap repair above the modulus, (ii) ultimate period $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 explains why some variants degenerate to a single aggregate while MuM, $ϕ$-MuM and poly-MuM retain rich local structure. All ingredients (multiplicative orders, the Chinese remainder theorem, finite fields) are classical; the contribution is the unified aggregation-compression viewpoint that embeds both RSA and AES inside one impartial-game framework, together with the structural and collapse theorems. |
| title | Product-Congruence Games: A Unified Impartial-Game Framework for RSA ($ϕ$-MuM) and AES (poly-MuM) |
| topic | Discrete Mathematics Cryptography and Security Information Theory 91A46 (primary), 11A07, 94A60, 05A99 G.2.1; E.3 |
| url | https://arxiv.org/abs/2507.20087 |