# What mathematical procedure does sagemath use to solve these types of systems? Is there a better process?

UPDATE: I tried to solve it in linear time i.e. the factorization of N happens in log N Italian language https://www.academia.edu/96992548/Fat...

I found a system (which varies its length as a function of (p + q-4) / 8) which generates all the numbers N = 8 * G + 3 = p * q so by inserting our number to factor in the underlying system instead of N we will have our p, factor of N.

System example up to x = (p + q-4) / 8 <= 3

var('x y p a A b B c z Z w W N v V')

eq0 = N -27 == 0

eq1 = (2*(3*x+1)-3*(a)+1)/24+3/2*x*(x+1) - A == 0
eq2 = A+b*(b-1)/2 - (2*x*(x+1)) == 0
eq3 = (2*(3*(A)+1)-3*(b)+1)/24+3/2*x*(x+1) - B == 0
eq4 = B+c*(c-1)/2 - (2*x*(x+1)) == 0
eq5 = (2*(3*(B)+1)-3*(c)+1)/24+3/2*x*(x+1) - (2*x*(x+1)) == 0
eq6 = a-(2*x+1) == 0

eq7 = (2*(3*(N-3)/8+1)-3*(z)+1)/24+3/2*x*(x+1) -((N-3)/8+Z) == 0
eq8 = (N-3)/8+z*(z-1)/2 - (2*x*(x+1)) == 0
eq9 = (2*(3*((N-3)/8+Z)+1)-3*(w)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W) == 0
eq10 = (N-3)/8+Z+w*(w-1)/2 - (2*x*(x+1)) == 0
eq11 = (2*(3*((N-3)/8+Z+W)+1)-3*(v)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V) == 0
eq12 = (N-3)/8+Z+W+v*(v-1)/2 - (2*x*(x+1)) == 0
eq13 = (N-3)/8+Z+W+V - (2*x*(x+1)) == 0

eq14 = (N-3)/8+y*(y-1)/2 - 2*x*(x+1) == 0
eq15 = 4*x+1-2*(y-1)-p == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15],x,y,p,a,A,b,B,c,z,Z,w,W,N,v,V)
sol = solutions
print(sol)


System example up to x = (p + q-4) / 8 <= 7

var('x y p a A b B c C d z Z w W N v V u U')

eq0 = N-59 == 0

eq1 = (2*(3*x+1)-3*(a)+1)/24+3/2*x*(x+1) - A == 0
eq2 = A+b*(b-1)/2 - (2*x*(x+1)) == 0
eq3 = (2*(3*(A)+1)-3*(b)+1)/24+3/2*x*(x+1) - B == 0
eq4 = B+c*(c-1)/2 - (2*x*(x+1)) == 0
eq5 = (2*(3*(B)+1)-3*(c)+1)/24+3/2*x*(x+1) - C == 0
eq6 = C+d*(d-1)/2 - (2*x*(x+1)) == 0
eq7 = (2*(3*(C)+1)-3*(d)+1)/24+3/2*x*(x+1) - (2*x*(x+1)) == 0
eq8 = a-(2*x+1) == 0

eq9 = (2*(3*(N-3)/8+1)-3*(z)+1)/24+3/2*x*(x+1) -((N-3)/8+Z) == 0
eq10 = (N-3)/8+z*(z-1)/2 - (2*x*(x+1)) == 0
eq11 = (2*(3*((N-3)/8+Z)+1)-3*(w)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W) == 0
eq12 = (N-3)/8+Z+w*(w-1)/2 - (2*x*(x+1)) == 0
eq13 = (2*(3*((N-3)/8+Z+W)+1)-3*(v)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V) == 0
eq14 = (N-3)/8+Z+W+v*(v-1)/2 - (2*x*(x+1)) == 0
eq15 = (2*(3*((N-3)/8+Z+W+V)+1)-3*(u)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V+U) == 0
eq16 = (N-3)/8+Z+W+V+u*(u-1)/2 - (2*x*(x+1)) == 0
eq17 = (N-3)/8+Z+W+V+U - (2*x*(x+1)) == 0

eq18 = (N-3)/8+y*(y-1)/2 - 2*x*(x+1) == 0
eq19 = 4*x+1-2*(y-1)-p == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15,eq16,eq17,eq18,eq19],x,y,p,a,A,b,B,c,C,d,z,Z,w,W,N,v,V,u,U)
sol = solutions
print(sol)


System example up to x = (p + q-4) / 8 <= 15

var('x y p a A b B c C d D f z Z w W N v V u U t T')

eq0 = N - 123 == 0

eq1 = (2*(3*x+1)-3*(a)+1)/24+3/2*x*(x+1) - A == 0
eq2 = A+b*(b-1)/2 - (2*x*(x+1)) == 0
eq3 = (2*(3*(A)+1)-3*(b)+1)/24+3/2*x*(x+1) - B == 0
eq4 = B+c*(c-1)/2 - (2*x*(x+1)) == 0
eq5 = (2*(3*(B)+1)-3*(c)+1)/24+3/2*x*(x+1) - C == 0
eq6 = C+d*(d-1)/2 - (2*x*(x+1)) == 0
eq20 = (2*(3*(C)+1)-3*(d)+1)/24+3/2*x*(x+1) - D == 0
eq21 = D+f*(f-1)/2 - (2*x*(x+1)) == 0
eq7 = (2*(3*(D)+1)-3*(f)+1)/24+3/2*x*(x+1) - (2*x*(x+1)) == 0
eq8 = a-(2*x+1) == 0

eq9 = (2*(3*(N-3)/8+1)-3*(z)+1)/24+3/2*x*(x+1) -((N-3)/8+Z) == 0
eq10 = (N-3)/8+z*(z-1)/2 - (2*x*(x+1)) == 0
eq11 = (2*(3*((N-3)/8+Z)+1)-3*(w)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W) == 0
eq12 = (N-3)/8+Z+w*(w-1)/2 - (2*x*(x+1)) == 0
eq13 = (2*(3*((N-3)/8+Z+W)+1)-3*(v)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V) == 0
eq14 = (N-3)/8+Z+W+v*(v-1)/2 - (2*x*(x+1)) == 0
eq15 = (2*(3*((N-3)/8+Z+W+V)+1)-3*(u)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V+U) == 0
eq16 = (N-3)/8+Z+W+V+u*(u-1)/2 - (2*x*(x+1)) == 0
eq22 = (2*(3*((N-3)/8+Z+W+V+U)+1)-3*(t)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V+U+T) == 0
eq23 = (N-3)/8+Z+W+V+U+t*(t-1)/2 - (2*x*(x+1)) == 0
eq17 = (N-3)/8+Z+W+V+U+T - (2*x*(x+1)) == 0

eq18 = (N-3)/8+y*(y-1)/2 - 2*x*(x+1) == 0
eq19 = 4*x+1-2*(y-1)-p == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15,eq16,eq17,eq18,eq19,eq20,eq21,eq22,eq23],x,y,p,a,A,b,B,c,C,d,D,f,z,Z,w,W,N,v,V,u,U,t,T)
sol = solutions
print(sol)


What mathematical procedure does sagemath use to solve these types of systems?

Is there a better process?

edit retag close merge delete

Sort by ยป oldest newest most voted

Since your equations are polynomial, it may be worth to work with polynomial ideals instead of symbolic equations. Here is a translation of your first code into these settings:

R.<x,y,p,a,A,b,B,c,z,Z,w,W,N,v,V> = PolynomialRing(QQ)

eq0 = N -27

eq1 = (2*(3*x+1)-3*(a)+1)/24+3/2*x*(x+1) - A
eq2 = A+b*(b-1)/2 - (2*x*(x+1))
eq3 = (2*(3*(A)+1)-3*(b)+1)/24+3/2*x*(x+1) - B
eq4 = B+c*(c-1)/2 - (2*x*(x+1))
eq5 = (2*(3*(B)+1)-3*(c)+1)/24+3/2*x*(x+1) - (2*x*(x+1))
eq6 = a-(2*x+1)

eq7 = (2*(3*(N-3)/8+1)-3*(z)+1)/24+3/2*x*(x+1) -((N-3)/8+Z)
eq8 = (N-3)/8+z*(z-1)/2 - (2*x*(x+1))
eq9 = (2*(3*((N-3)/8+Z)+1)-3*(w)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W)
eq10 = (N-3)/8+Z+w*(w-1)/2 - (2*x*(x+1))
eq11 = (2*(3*((N-3)/8+Z+W)+1)-3*(v)+1)/24+3/2*x*(x+1) -((N-3)/8+Z+W+V)
eq12 = (N-3)/8+Z+W+v*(v-1)/2 - (2*x*(x+1))
eq13 = (N-3)/8+Z+W+V - (2*x*(x+1))

eq14 = (N-3)/8+y*(y-1)/2 - 2*x*(x+1)
eq15 = 4*x+1-2*(y-1)-p

J = R.ideal([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15])
sol = J.variety()
print(sol)

more

@Max Alekseyev do you have any advice for me?

( 2022-04-16 17:55:35 +0200 )edit

( 2022-04-16 18:24:13 +0200 )edit

@Max Alekseyev One last favor, kindly. As you may have noticed, the system will have 12+4*[Integer_Part[log_2 (p+q-4)/8 ]] equations What is the computational complexity for solving the system as a function of Integer_Part[log_2 (p+q-4)/8 ] ?

( 2022-04-19 10:44:26 +0200 )edit
1

There is no direct dependency on the number of equations, but in general this problem is hard and some instances may be infeasible to solve in practice. Sometimes using a different monomial order, e.g. degrevlex, may speed up things. You may check this Wikipedia article for more details on the essence of the problem.

( 2022-04-19 18:51:11 +0200 )edit

@Max Alekseyev thank you

( 2022-04-19 19:43:03 +0200 )edit

I was able to cut the time on my computer in half

The first OUTPUT was

(x, y, p, a, A, b, B, c, C, d, D, f, z, Z, w, W, N, v, V, u, U, t, T)
7.9771857261657715
[
[x == -6, y == 10, p == -41, a == -11, A == 45, b == -5, B == 57, c == 3, C == 59, d == -1, D == 60, f == 1, z == -9, Z == 35, w == 5, W == 7, N == 123, v == 3, V == 2, u == -1, U == 1, t == 1, T == 0],
[x == -6, y == -9, p == -3, a == -11, A == 45, b == -5, B == 57, c == 3, C == 59, d == -1, D == 60, f == 1, z == -9, Z == 35, w == 5, W == 7, N == 123, v == 3, V == 2, u == -1, U == 1, t == 1, T == 0],
[x == 5, y == 10, p == 3, a == 11, A == 45, b == -5, B == 57, c == 3, C == 59, d == -1, D == 60, f == 1, z == -9, Z == 35, w == 5, W == 7, N == 123, v == 3, V == 2, u == -1, U == 1, t == 1, T == 0],
[x == 5, y == -9, p == 41, a == 11, A == 45, b == -5, B == 57, c == 3, C == 59, d == -1, D == 60, f == 1, z == -9, Z == 35, w == 5, W == 7, N == 123, v == 3, V == 2, u == -1, U == 1, t == 1, T == 0],
[x == -16, y == 31, p == -123, a == -31, A == 360, b == -15, B == 452, c == -7, C == 474, d == -3, D == 479, f == -1, z == 31, Z == 345, w == -15, W == 92, N == 123, v == -7, V == 22, u == -3, U == 5, t == -1, T == 1],
[x == -16, y == -30, p == -1, a == -31, A == 360, b == -15, B == 452, c == -7, C == 474, d == -3, D == 479, f == -1, z == 31, Z == 345, w == -15, W == 92, N == 123, v == -7, V == 22, u == -3, U == 5, t == -1, T == 1],
[x == 15, y == 31, p == 1, a == 31, A == 360, b == -15, B == 452, c == -7, C == 474, d == -3, D == 479, f == -1, z == 31, Z == 345, w == -15, W == 92, N == 123, v == -7, V == 22, u == -3, U == 5, t == -1, T == 1],
[x == 15, y == -30, p == 123, a == 31, A == 360, b == -15, B == 452, c == -7, C == 474, d == -3, D == 479, f == -1, z == 31, Z == 345, w == -15, W == 92, N == 123, v == -7, V == 22, u == -3, U == 5, t == -1, T == 1]
]


While now it is OUTPUT

OUTPUT

(N, x, y, p, B, c, C, d, D, e, E, f, F, g, G, h, H, m, L, n)
4.016726016998291
[
[N == 123, x == 15, y == 31, p == 1, B == 452, c == -7, C == 474, d == -3, D == 479, E == 360, e == 31, f == -15, F == 452, g == -7, G == 474, h == -3, H == 480, m == -1, L == 479, n == -1],
[N == 123, x == 15, y == 31, p == 1, B == 452, c == -7, C == 474, d == -3, D == 479, E == 360, e == -30, f == -15, F == 452, g == -7, G == 474, h == -3, H == 480, m == -1, L == 479, n == -1],
[N == 123, x == 5, y == -9, p == 41, B == 57, c == 3, C == 59, d == -1, D == 60, E == 50, e == 10, f == 5, F == 57, g == 3, G == 59, h == -1, H == 60, m == 1, L == 60, n == 1],
[N == 123, x == 5, y == -9, p == 41, B == 57, c == 3, C == 59, d == -1, D == 60, E == 50, e == -9, f == 5, F == 57, g == 3, G == 59, h == -1, H == 60, m == 1, L == 60, n == 1]
]


this is the modified system

import time
Start_Time = time.time()
var('N x y p B c C d D e E f F g G h H m L n')

eq0 = N - 123 == 0

eq1 = (2*(3*(3/2*x*(x+1))+1)-3*(-x)+1)/24+(3/4*(H)) - B == 0
eq2 = B+c*(c-1)/2 - (H) == 0
eq3 = (2*(3*(B)+1)-3*(c)+1)/24+(3/4*(H)) - C == 0
eq4 = C+d*(d-1)/2 - (H) == 0
eq5 = (2*(3*(C)+1)-3*(d)+1)/24+(3/4*(H)) - D == 0
eq19 = D+n*(n-1)/2 - (H) == 0
eq20 = (2*(3*(D)+1)-3*(n)+1)/24+(3/4*(H)) - H == 0

eq6 = (N-3)/8+e*(e-1)/2 - (H) == 0
eq7 = (2*(3*((N-3)/8)+1)-3*(y)+1)/24+(3/4*(H)) - E == 0
eq8 = E+f*(f-1)/2 - (H) == 0
eq9 = (2*(3*(E)+1)-3*(f)+1)/24+(3/4*(H)) - F == 0
eq10 = F+g*(g-1)/2 - (H) == 0
eq11 = (2*(3*(F)+1)-3*(g)+1)/24+(3/4*(H)) - G == 0
eq12 = G+h*(h-1)/2 - (H) == 0
eq13 = (2*(3*(G)+1)-3*(h)+1)/24+(3/4*(H)) - L == 0
eq14 = L+m*(m-1)/2 - (H) == 0
eq17 = (2*(3*(L)+1)-3*(m)+1)/24+(3/4*(H)) - H == 0
eq18 = H - ((N-3)/8+y*(y-1)/2) == 0

eq15 = (N-3)/8+y*(y-1)/2 - 2*x*(x+1) == 0
eq16 = 4*x+1-2*(y-1)-p == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15,eq16,eq17,eq18,eq19,eq20],N,x,y,p,B,c,C,d,D,E,e,f,F,g,G,h,H,m,L,n)
sol = solutions
Execution_Time = time.time() - Start_Time
print (Execution_Time)
print(sol)

more