Is perfect_power() too slow?

[mhostetter]

Some inputs to perfect_power() take a very long time to return. Is this expected? Is there an inefficiency in the algorithm?

In [2]: import galois

In [3]: %time galois.perfect_power(2**300)
CPU times: user 102 µs, sys: 129 µs, total: 231 µs
Wall time: 233 µs
Out[3]: (2, 300)

In [4]: %time galois.perfect_power(2**500)
CPU times: user 195 µs, sys: 247 µs, total: 442 µs
Wall time: 446 µs
Out[4]: (2, 500)

In [5]: %time galois.perfect_power(2**471)
CPU times: user 3.03 s, sys: 0 ns, total: 3.03 s
Wall time: 3.03 s
Out[5]: (2, 471)

In [6]: %time galois.perfect_power(2**571)
# Takes forever....

[mhostetter]

This is particularly slow for a prime to a prime power.

[mhostetter]

After #454, this runs as follows. There may still be an underlying bug in the perfect_power() algorithm, however.

In [1]: import galois

In [2]: %time galois.perfect_power(2**471)
CPU times: user 7 µs, sys: 14 µs, total: 21 µs
Wall time: 23.8 µs
Out[2]: (2, 471)

In [3]: %time galois.perfect_power(2**571)
CPU times: user 25 µs, sys: 0 ns, total: 25 µs
Wall time: 26.5 µs
Out[3]: (2, 571)