Sorry, this content is no longer available

Ask Your Question
1

What mathematical procedure does sagemath use to solve these types of systems? Is there a better process?
 
  
 
 
     
 
 
 
 
 
 
 
    
        
        asked 2 years ago  
 
 Periodic_1_6 gravatar image  
 
 
 
 
    
        
        updated 2 years ago  
 
 
 
 
 
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?
 
Preview: (hide)
 
 
 
 
          
 
add a comment
 
 
 
 
 
 2 Answers
    
 
 
                    Sort by »
                     oldest newest most voted 
 
 
 
 
 
  
 
 
 
 
3
 
 
  
 
 
 
 
 
 
 
 
    
        
        answered 2 years ago  
 
 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)
 
Preview: (hide)
 
 
 
 
         
        link
        
 
Comments
@Max Alekseyev do you have any advice for me?
Periodic_1_6 gravatar imagePeriodic_1_6 (
    
        2 years ago
    )
Take my answer as an advice.
Max Alekseyev gravatar imageMax Alekseyev (
    
        2 years ago
    )
@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 (
    
        2 years ago
    )
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 (
    
        2 years ago
    )
@Max Alekseyev thank you
Periodic_1_6 gravatar imagePeriodic_1_6 (
    
        2 years ago
    )
add a comment
 
 
 
 
   
 
 
 
 
1
 
 
  
 
 
 
 
 
 
 
 
    
        
        answered 2 years ago  
 
 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)
 
Preview: (hide)
 
 
 
 
         
        link
        
 
add a comment
 
 
 
 
 
 
 
 
 

    
        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
        
    
 
 
 subscribe to rss feed 
 
 
 
 
 
 
Stats
 

        Asked:  2 years ago  
 
 
        Seen: 698 times 
 

        Last updated: Feb 16 '23 
 
 
 
 
 
  
 
 
   
                
                Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

            
 
 about | faq | help  | privacy policy | terms of service 
 
 
                Powered by Askbot version 0.7.59