mersenneforum.org Power number
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-02, 06:38   #12
axn

Jun 2003

10011001000112 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb 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?

2020-08-02, 06:40   #13
axn

Jun 2003

3×23×71 Posts

Quote:
 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.

2020-08-02, 07:25   #14
Citrix

Jun 2003

1,579 Posts

Quote:
 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.

2020-08-02, 16:47   #15
axn

Jun 2003

132316 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb with m small
Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 Teams 10 2019-10-15 17:36 CRGreathouse Hardware 9 2016-02-06 18:46 JohnFullspeed Miscellaneous Math 45 2011-07-10 20:13 bitblit Math 8 2009-04-24 02:48 Unregistered Information & Answers 7 2008-08-30 14:36

All times are UTC. The time now is 20:03.

Sat Apr 10 20:03:10 UTC 2021 up 2 days, 14:44, 1 user, load averages: 1.80, 1.55, 1.47