 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)

 axn 2020-08-02 06:38

[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?

 axn 2020-08-02 06:40

[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.

 Citrix 2020-08-02 07:25

[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.

 axn 2020-08-02 16:47

[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.

All times are UTC. The time now is 23:37.