Efficient Lifting of Discrete Logarithms Modulo Prime Powers
Giovanni Viglietta, Yasuyuki Kachi · 2025
Read Efficient Lifting of Discrete Logarithms Modulo Prime Powers by Giovanni Viglietta, Yasuyuki Kachi (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-2505-07434.txt.
Introduction
Giovanni Viglietta and Yasuyuki Kachi present a faster method for a classic problem in number theory, in a 2025 paper. The discrete logarithm problem asks for the power that turns one number into another under modular arithmetic. Solving it for a prime modulus is one task; lifting that answer to higher powers of the prime is another. Their algorithm takes an answer modulo a prime and raises it to any fixed prime power.
The method is exact and always gives the same result, with no guessing involved. It needs far fewer multiplications than earlier lifting methods, improving on them by at least a factor of eight. The gain matters for cryptography, where discrete logarithms underpin many security schemes and attacks alike.
Catalog record
| CREATOR | Giovanni Viglietta, Yasuyuki Kachi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07434
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Lifting of Discrete Logarithms Modulo Prime Powers Giovanni Viglietta, Yasuyuki Kachi Abstract We present a deterministic algorithm that, given a prime p p and a solution x ∈ ℤ x\in\mathbb{Z} to the discrete logarithm problem a x ≡ b ( mod p ) a^{x}\equiv b\pmod{p} with p ∤ a p\nmid a , efficiently lifts it to a solution modulo p k p^{k} , i.e., a x ≡ b ( mod p k ) a^{x}\equiv b\pmod{p^{k}} , for any fixed k ≥ 1 k\geq 1 . The algorithm performs k ( ⌈ log 2 p ⌉ + 2 ) + O ( log p ) k(\lceil\log_{2}p\rceil+2)+O(\log p) multiplications modulo p k p^{k} in the worst case, improving upon prior lifting methods by at least a factor of 8. 1 Introduction Summary. In 1984, Bach [ 3 ] gave an efficient deterministic algorithm for lifting a discrete logarithm modulo a prime p to a higher prime-power modulus p^{k} . In this paper, we improve on Bach’s result by providing a more efficient algorithm for the same task. In Section 2 we describe the algorithm itself, while in Section 3 we prove its correctness, and in Section 4 we analyze its performance and compare it to Bach’s algorithm’s. Section 5 contains some concluding remarks. Significance. Our result has applications in computational number theory, where arithmetic modulo p^{k} arises naturally in algorithms involving p -adic methods, local fields, and root-lifting techniques such as Hensel’s lemma. Many standard discrete logarithm algorithms, such as index calculus and its variants [ 1 ] , are designed for finite fields and do not extend naturally to the ring \mathbb{Z}_{p^{k}} . While generic methods like baby-step giant-step [ 11 ] or Pollard’s rho [ 10 ] can still be applied, they do not leverage any known solution modulo p and are slower than methods that exploit the structure of \mathbb{Z}_{p^{k}} . On the other hand, general-purpose algorithms such as Pohlig–Hellman [ 9 ] rely on factoring the multiplicative group order \varphi(p^{k})=p^{k-1}(p-1) , which is impractical when p is large and p-1 is difficult to factor. Our contribution is also relevant in certain cryptographic settings, including fault and side-channel attack models [ 4 , 5 , 7 ] , where computations modulo p^{k} are used to track error propagation through arithmetic operations. It further applies to lattice-based cryptographic constructions such as NTRU and Ring-LWE [ 2 , 6 , 8 ] , where modular arithmetic over rings modulo a prime power plays a central role in both algorithm design and implementation. Notation. We adopt standard number-theoretic notation and terminology. \mathbb{Z} indicates the set of all integers; \mathbb{Z}^{+} denotes the positive integers, and \mathbb{N} the non-negative integers. If b\in\mathbb{Z} is an integer multiple of a\in\mathbb{Z} , we write a\mid b ; otherwise, we write a\nmid b . The congruence a\equiv b\pmod{m} means that m\mid a-b . For a prime p\in\mathbb{N} , \nu_{p}(a) indicates the p -adic valuation of a , i.e., the maximum r\in\mathbb{N} such that p^{r}\mid a ; by convention, \nu_{p}(0)=+\infty . If a and m have no common prime divisor, they are said to be relatively prime . If this is the case, then \ord_{m}(a) denotes the multiplicative order of a modulo m , that is, the smallest positive integer r such that a^{r}\equiv 1\pmod{m} . We will often make use of Fermat’s Little Theorem : If p is a prime and p\nmid a , then a^{p-1}\equiv 1\pmod{p} . Equivalently, \ord_{p}(a)\mid p-1 . We adopt the convention that 0^{0}=1 . 2 The Algorithm Language. Our algorithm is presented in Listing 1 . Python 3.0 was chosen because its syntax is close to pseudocode and it natively supports arithmetic on arbitrarily large integers. 0 0 0 We remark that, in Python 3.0, the operator a//b returns \lfloor a/b\rfloor , the operator a%b returns the remainder after dividing a by b (it is always non-negative if b>0 ), pow(a,n) computes a^{n} , and pow(a,n,m) computes a^{n} modulo m . That said, the algorithm can be straightforwardly implemented in any language that supports multiprecision integer arithmetic, such as Java (via the BigInteger class), C++ (using libraries such as GMP or NTL), or Mathematica. Listing 1: Python 3.0 implementation of our algorithm. It assumes that k\in\mathbb{N} , p is a prime, p\nmid a , and a^{z}\equiv b\pmod{p} . It returns x\in\mathbb{N} such that a^{x}\equiv b\pmod{p^{k}} , or None if no such x exists. ⬇ 1 def discrete_log_lift ( a , z , b , p , k ): 2 m = pow ( p , k ) 3 z = z % ( p - 1) 4 a = a % m 5 b = b % m 6 c = pow ( a , z , m ) 7 y = 0 8 if p == 2: 9 u = 2 10 e = pow ( a , 2, m ) 11 else : 12 u = 1 13 e = pow ( a , p - 1, m ) 14 h = e - 1 15 r = 0 16 while h % p == 0 and r < k : 17 h = h // p 18 r = r + 1 19 v = pow ( p , r ) 20 if ( b - c ) % v != 0: 21 if p > 2 or ( b - a ) % v != 0: 22 return None 23 c = a 24 y = 1 25 g = pow ( h * b , p - 2, p ) 26 while b != c : 27 d = ( g * (( b - c ) // v )) % p 28 y = y + d * u 29 if r + r >= k : 30 f = (1 + ( e - 1) * d ) % m 31 e = (1 + ( e - 1) * p ) % m 32 else : 33 f = pow ( e , d , m ) 34 e = ( f * pow ( e , p - d , m )) % m 35 c = ( c * f ) % m 36 u = u * p 37 v = v * p 38 r = r + 1 39 return ( p - 1) * y + z Overview. The algorithm assumes that a^{z}\equiv b\pmod{p} and returns x such that a^{x}\equiv b\pmod{p^{k}} (or reports that no such x exists), provided that p\nmid a . 1 1 1 The case p\mid a is of little interest, as the minimum solution x can easily be found without knowledge of z , either via an exhaustive search, since necessarily 0\leq x\leq k , or by solving the linear equation \nu_{p}(a)x=\nu_{p}(b) , after ruling out some trivial cases. The details are left to the reader. The final solution x is expressed in the form x=(p-1)y+z (Line 39), where z is given, and y is computed incrementally, one digit in base p at a time. Specifically, the algorithm computes a sequence (y_{j})_{j\geq 0} such that y_{j}<p^{j} , that is, y_{j} has j digits in base p . In particular, y_{0}=0