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

asked 2022-04-15 11:54:10 +0200

Periodic_1_6
65 ●1 ●5 ●14

updated 2023-02-16 10:29:36 +0200

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 flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2022-04-16 05:01:23 +0200

Max Alekseyev

5748 ●5 ●37 ●123

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)

edit flag offensive delete link

Comments

@Max Alekseyev do you have any advice for me?

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

Take my answer as an advice.

Max Alekseyev ( 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 ] ?

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

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.

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

@Max Alekseyev thank you

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

add a comment

answered 2022-05-11 08:27:53 +0200

Periodic_1_6
65 ●1 ●5 ●14

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)