[QUOTE=Citrix;552271]To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small[/QUOTE]

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?

[QUOTE=retina;552272]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.[/QUOTE]

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.

[QUOTE=axn;552273]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?[/QUOTE]

N~ 100,000 bits +
m <1000

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

[QUOTE=Citrix;552271]To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small[/QUOTE]

[QUOTE=Citrix;552281]N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.[/QUOTE]
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.