Efficient Lifting of Discrete Logarithms Modulo Prime Powers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913836309676032 |
|---|---|
| author | Viglietta, Giovanni Kachi, Yasuyuki |
| author_facet | Viglietta, Giovanni Kachi, Yasuyuki |
| contents | We present a deterministic algorithm that, given a prime $p$ and a solution $x \in \mathbb Z$ to the discrete logarithm problem $a^x \equiv b \pmod p$ with $p\nmid a$, efficiently lifts it to a solution modulo $p^k$, i.e., $a^x \equiv b \pmod {p^k}$, for any fixed $k \geq 1$.
The algorithm performs $k(\lceil \log_2 p\rceil +2)+O(\log p)$ multiplications modulo $p^k$ in the worst case, improving upon prior lifting methods by at least a factor of 8. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07434 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Lifting of Discrete Logarithms Modulo Prime Powers Viglietta, Giovanni Kachi, Yasuyuki Number Theory Discrete Mathematics We present a deterministic algorithm that, given a prime $p$ and a solution $x \in \mathbb Z$ to the discrete logarithm problem $a^x \equiv b \pmod p$ with $p\nmid a$, efficiently lifts it to a solution modulo $p^k$, i.e., $a^x \equiv b \pmod {p^k}$, for any fixed $k \geq 1$. The algorithm performs $k(\lceil \log_2 p\rceil +2)+O(\log p)$ multiplications modulo $p^k$ in the worst case, improving upon prior lifting methods by at least a factor of 8. |
| title | Efficient Lifting of Discrete Logarithms Modulo Prime Powers |
| topic | Number Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2505.07434 |