An Elementary Method For Fast Modular Exponentiation With Factored Modulus
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916389941411840 |
|---|---|
| author | Aggarwal, Anay Isaacs, Manu |
| author_facet | Aggarwal, Anay Isaacs, Manu |
| contents | We present a fast algorithm for modular exponentiation when the factorization of the modulus is known. Let $a,n,m$ be positive integers and suppose $m$ factors canonically as $\prod_{i=1}^k p_i^{e_i}$. Choose integer parameters $t_i\in [1, e_i]$ for $1\le i\le k$. Then we can compute the modular exponentiation $a^n\pmod{m}$ in $O(\max(e_i/t_i)+\sum_{i=1}^k t_i\log p_i)$ steps (i.e., modular operations). We go on to analyze this algorithm mathematically and programmatically, showing significant asymptotic improvement in specific cases. Specifically, for an infinite family of $m$ we achieve a complexity of $O(\sqrt{\log m})$ steps, much faster than the Repeated Squaring Algorithm, which has complexity $O(\log m)$. Additionally, we extend our algorithm to matrices and hence general linear recurrences. The complexity is similar; with the same setup we can exponentiate matrices in $GL_d(\mathbb{Z}/m\mathbb{Z})$ in less than $O(\max(e_i/t_i)+d^2\sum_{i=1}^k t_i\log p_i)$ steps. This improves Fiduccia's algorithm and the results of Bostan and Mori in the case of $\mathbb{Z}/m\mathbb{Z}$. We prove analogous results for $\mathbb{Z}/p^k\mathbb{Z}$ ring extensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10497 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Elementary Method For Fast Modular Exponentiation With Factored Modulus Aggarwal, Anay Isaacs, Manu Number Theory 11A15 G.4 We present a fast algorithm for modular exponentiation when the factorization of the modulus is known. Let $a,n,m$ be positive integers and suppose $m$ factors canonically as $\prod_{i=1}^k p_i^{e_i}$. Choose integer parameters $t_i\in [1, e_i]$ for $1\le i\le k$. Then we can compute the modular exponentiation $a^n\pmod{m}$ in $O(\max(e_i/t_i)+\sum_{i=1}^k t_i\log p_i)$ steps (i.e., modular operations). We go on to analyze this algorithm mathematically and programmatically, showing significant asymptotic improvement in specific cases. Specifically, for an infinite family of $m$ we achieve a complexity of $O(\sqrt{\log m})$ steps, much faster than the Repeated Squaring Algorithm, which has complexity $O(\log m)$. Additionally, we extend our algorithm to matrices and hence general linear recurrences. The complexity is similar; with the same setup we can exponentiate matrices in $GL_d(\mathbb{Z}/m\mathbb{Z})$ in less than $O(\max(e_i/t_i)+d^2\sum_{i=1}^k t_i\log p_i)$ steps. This improves Fiduccia's algorithm and the results of Bostan and Mori in the case of $\mathbb{Z}/m\mathbb{Z}$. We prove analogous results for $\mathbb{Z}/p^k\mathbb{Z}$ ring extensions. |
| title | An Elementary Method For Fast Modular Exponentiation With Factored Modulus |
| topic | Number Theory 11A15 G.4 |
| url | https://arxiv.org/abs/2401.10497 |