Ask Your Question
1

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 gravatar image

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

2 Answers

Sort by ยป oldest newest most voted
3

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

Max Alekseyev gravatar image

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 more

Comments

@Max Alekseyev do you have any advice for me?

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

Take my answer as an advice.

Max Alekseyev gravatar imageMax 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 gravatar imagePeriodic_1_6 ( 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.

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

@Max Alekseyev thank you

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

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

Periodic_1_6 gravatar image

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)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

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

Seen: 184 times

Last updated: May 11