Quote:
Originally Posted by Citrix
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
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.