Power number

[axn]

Originally Posted by Citrix

To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small

That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?

[axn]

Originally Posted by retina

Okay. But it still doesn't meet the criterion 99%.

log(6¹⁰⁰)/log(7×6¹⁰⁰+11) = 98.92...%

Indeed for any integer N I can't see how you ever get 99%. The only way would be something like e×e⁹⁹+0 = 99%. So k=e, b=e, n=99, c=0. And other multiples of those values.

Ah! You're thinking 99% as an exact number, whereas I'm pretty sure OP intended to give the general flavor of the structure of the number. Meaning, b^n part is the dominant term.

[Citrix]

Originally Posted by axn

That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?

N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.

[axn]

Originally Posted by Citrix

To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small

Originally Posted by Citrix

N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.

Let's take m=1000 so we have the largest search space.

When N is about 1e5 bits, the first n that satisfies m*n > b is n_min~=4500, and b_max ~=4.5 million

When N is about 1e6 bits, it is n_min ~= 39600 and b_max ~=39.6 million.

For the above numbers, it should be feasible to brute force all prime b's < b_max. Basic outline of the algorithm would be to do c = N % (b^k), (prime b from 2 to b_max) where b^k is about 256 bits (>> our target c with is < 64 bits).
If |c| < 2^64, we may have a potential solution, so trial factor N-c upto b_max and see if we get a complete factorization.