Is there a way in sagemath assisted by mathematics to find only and exclusively the first valid solution without calculating the other solutions? [closed]

asked 2021-08-11 11:17:15 +0100

Periodic_1_6 gravatar image

updated 2021-08-11 11:23:08 +0100

Hi, I'm an aspiring amateur, I have found a way to bring the factorization of a number N into O ((log_2 (N)) ^ 2) in a system of this type:

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

eq0 = N-4899 == 0

eq1 = (-2 + sqrt(N + (1 - 2*y)^2))/4-A == 0
eq2 = 4*A+1-2*(y-1)-a == 0
eq3 = 8*(A-1)*a-(N-36)-(a-6)^2  == 0
eq4 = ((a-7)-2*(B-1))*((a-5)-2*(B-1))+1-(b-6)^2  == 0
eq5 = ((b-7)-2*(C-1))*((b-5)-2*(C-1))+1-(c-6)^2  == 0
eq6 = ((c-7)-2*(D-1))*((c-5)-2*(D-1))+1-(d-6)^2  == 0
eq7 = 8*(B-1)*a-(a-6)^2+36-(16*B*(B+1)+3) == 0
eq8 = 8*(C-1)*b-(b-6)^2+36-(16*C*(C+1)+3) == 0
eq9 = 8*(D-1)*c-(c-6)^2+36-(16*D*(D+1)+3) == 0
eq10= d-13 == 0

eq11= 8*(A-1)*(4*A+1)-(16*A*(A+1)+3-36)-(w-6)^2 == 0
eq12= ((w-7)-2*(V-1))*((w-5)-2*(V-1))+1-(v-6)^2  == 0
eq13= ((v-7)-2*(Z-1))*((v-5)-2*(Z-1))+1-(z-6)^2  == 0
eq14= ((z-7)-2*(U-1))*((z-5)-2*(U-1))+1-(u-6)^2  == 0
eq15= 8*(V-1)*w-(w-6)^2+36-(16*V*(V+1)+3) == 0
eq16= 8*(Z-1)*v-(v-6)^2+36-(16*Z*(Z+1)+3) == 0
eq17= 8*(U-1)*z-(z-6)^2+36-(16*U*(U+1)+3) == 0
eq18 = u-13 == 0

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

As can be seen from the outputs, a factorizes N, and every solution is good.

[
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21]
]

What I would like to ask is there a way in sagemath assisted by mathematics to find only and exclusively the first valid solution without calculating the other solutions?

edit retag flag offensive reopen merge delete

Closed for the following reason the question is answered, right answer was accepted by Periodic_1_6
close date 2021-08-14 11:00:51.176759

Comments

If you do not know what solvedoes, you also won't know the time complexity of your algorithm...

FabianG gravatar imageFabianG ( 2021-08-12 01:30:48 +0100 )edit
1

Strictly speaking, there is no "first" solution (in general, there is no "natural" ordering of the roots of a given system of equations). What you seem to want is to avoid the bother of computing all solutions, since any of them is sufficient for your needs.

It happens that, notwithstanding the case of "obvious" solution(s), most of the work needed to obtain one solution is also needed to obtain the other solutions. Let $t$ the time necessary to get the $n$ solutions to a given system ; the time necessary to get one solution among $n$ is therefore not $\frac{t}{n}$ but much closer to $t$...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-08-12 10:51:58 +0100 )edit

@Emmanuel Charpentier@FabianG thanks, i get it. forgive my ignorance. What is the computational complexity as a function of the number of unknown variables in this type of system?

Periodic_1_6 gravatar imagePeriodic_1_6 ( 2021-08-12 11:43:17 +0100 )edit

Please reopen

Periodic_1_6 gravatar imagePeriodic_1_6 ( 2022-06-17 18:08:07 +0100 )edit