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

22×5×239 Posts
Default

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

k<m*n
c<m*n
n*m>b
with m small
Quote:
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