Ask Your Question

Revision history [back]

If you want to factor N=8979 then trial division is your best choice (here in a very naive version)

def factor_via_trial_division(N):
    fac = []
    i = 2
    while i*i < N:
       while N % i == 0:
           N //= i
       i += 1
    return fac + [N]

You got

sage: %time factor_via_trial_division(8979)                                                                                                                                                    
CPU times: user 70 µs, sys: 3 µs, total: 73 µs
Wall time: 84.2 µs
[3, 41, 73]

Multivariate diophantine systems of degree > 1 are known to be complicated, see In particular, it has been proven that there does not exist an algorithm that takes as input a diophantine system and outputs one of its solution if it exists. Because of this, it is hard to believe that building a complicated diophantine system will help in any way to factor.