A code to describe the algorithm in Nielsen-Chuang exercise 5.17.

nielsen-chuang-exercise-5.17.py

import math as m

def pure_power(N):
    """checks if N is a pure power, i. e. N = a^b for some integers
    a >=1, b >= 2.
    returns (a, b) if a and b are found.
    returns (N, 1) if N is not a pure power.
    See ref.1.: https://en.wikipedia.org/wiki/
    Computational_complexity_of_mathematical_operations#Elementary_functions
    for the computational complexities for each element.
    """
    # N is given as an L bit integer.
    # In the actual implementation L is likely determined by the hardware archtechture or 
    # simply the size of the variables used.
    L = m.floor(m.log(N, 2))+1
    # special case: if N == 1, a == 1 and b is an arbitrary integer.
    # we return b == 2 for this case so that it matches with the condition
    # b >= 2.
    if N == 1:
        return 1, 2
    # The main loop iterates at most L times,
    # and each function in the loop runs in up to O(L^2) steps.
    # Thus the algorithm runs in O(L^3) steps total.
    for b in range(2, L):
        print("b = ", b)
        # y can be calculated in O(M(L)*L^(0.5)) by Taylor series expansion
        # (table in ref. 1.)
        # where M(L) stands for computational complexity for multiplication,
        # which can be e.g. O(L^1.465) by 3-way Toom-Cook algorithm listed in
        # ref. 1. Thus log is O(L^1.965) in this case.
        y = m.log(N, 2)
        # division also O(M(L)) = e.g. O(L^1.465) by Newton-Raphson algorithm
        # in ref. 1.
        x = y/b
        print("y, x = ", y, x)
        # the integer part of 2^x can be again calculated in O(L^1.965)
        # by Taylor series in ref. 1, assuming M(L) = O(L^1.465) and 2^x
        # is the same order as e^x.
        u1 = m.floor(m.pow(2, x))
        u2 = u1 + 1
        print("u1, u2 = ", u1, u2)
        if m.pow(u1, b) == N:
            return u1, b
        elif m.pow(u2, b) == N:
            return u2, b
    # last resort: no nontrivial solutions found.
    # N == N^1
    return N, 1


if __name__ == "__main__":
    N = 343
    assert(pure_power(343) == (7, 3))
    print("%d = %d ^ %d" % (N, *pure_power(N)))

    # ref. 1. Thus log is O(L^1.9465) in this case.
    # the integer part of 2^x can be again calculated in O(L^1.9465)

At the line 30 and 36, should the time complexity be O(L^1.965)?
Because m.log(N, 2) can be calculated by Taylor series in O(M(L)*L^(0.5)) and M(L) is O(L^1.465) here for example.

Thanks for letting me know, corrected :)
Obviously, my brain failed to handle floating-point addition there.

That's okay. I appreciate you wrote the code demonstrated the concept of solving exercise 5.17 🙏
(There is few article that talking about this question 😭)
BTW, according to the Peter Shor's paper, he recommended using Schonhage–Strassen algo. to calculate multiplication (when L is large).
Therefore, M(L) can be speed up to O(L * logL * loglogL).
(When L is small, one can just use elementary-school longhand multiplication instead.)