Thread: Power number
View Single Post
Old 2020-08-02, 16:47   #15
axn's Avatar
Jun 2003

24·307 Posts

Originally Posted by Citrix View Post
To refine the question I am looking for

with m small
Originally Posted by Citrix View Post
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.
axn is online now   Reply With Quote