How can I request the cooperation of sagemath mathematicians and programmers for a project? [closed]

My name is Alberico Lepore and I am an aspiring self-taught amateur and for about six years I have been looking for factorization in computationally acceptable times.

I have come to the point of verifying that resolving the type of systems listed below resolves the factorization.

All the variables I will mention are integers

Let N = p * q in the form 4 * G + 3 and p + q = 8 * x + 4 and q-p = 4 * y-2

then solving the system that I will show you we find p and q

How is the system composed?

If y is odd the first two lines

eq1 = 3*((p^2-4*p+N)/(8*p)+p)*((p^2-4*p+N)/(8*p)+p+1)/2-M == 0
eq2 = 3*((2*(3*((N-3)/8+p^2)+1)-3*(((-p^2+2*p+N)/(4*p)+2*p))+1)/24 + M)+1 - A1 == 0


If y is even the first two lines

eq1 = 3*((p^2-4*p+N)/(8*p)+p)*((p^2-4*p+N)/(8*p)+p+1)/2-M == 0
eq2 = 3*((2*(3*((N-3)/8+p^2)+1)-3*(1-((-p^2+2*p+N)/(4*p)+2*p))+1)/24 + M)+1 - A1 == 0


the other lines will be

3*((2* Aj - 3* aj + 1)/24 + M) + 1 - A(j+1) == 0
Aj + (3* aj *( aj - 1))/2 - 3*M-1-M == 0


where j goes from 1 to n-1 = IntegerPartOf (log_2 (y + 2 * p) -1)

the last two lines will be

3*((2* An + 3 + 1)/24 + M) + 1 - 3*M-1-M == 0
An + 3 - 3*M-1-M == 0


Example

Esempio N= 731

17*43 =731

(43-13+2)/4=7

7+2*17=41

var('N p M a1 a2 a3 a4 a5 A1 A2 A3 A4 A5')

eq0 = N-731 == 0

eq1 = 3*((p^2-4*p+N)/(8*p)+p)*((p^2-4*p+N)/(8*p)+p+1)/2-M == 0
eq2 = 3*((2*(3*((N-3)/8+p^2)+1)-3*(((-p^2+2*p+N)/(4*p)+2*p))+1)/24 + M)+1 - A1 == 0
eq3 = 3*((2* A1 - 3* a1 + 1)/24 + M) + 1 - A2 == 0
eq4 = A1 + (3* a1 *( a1 - 1))/2 - 3*M-1-M == 0
eq5 = 3*((2* A2 - 3* a2 + 1)/24 + M) + 1 - A3 == 0
eq6 = A2 + (3* a2 * ( a2 - 1))/2 - 3*M-1-M == 0
eq7 = 3*((2* A3 - 3* a3 + 1)/24 + M) + 1 - A4 == 0
eq8 = A3 + (3*a3*( a3 - 1))/2 - 3*M-1-M == 0
eq9 = 3*((2* A4 - 3* a4 + 1)/24 + M) + 1 - A5 == 0
eq10 = A4 + (3* a4 *( a4 - 1))/2 - 3*M-1-M == 0
eq11 = 3*((2* A5 - 3* a5 + 1)/24 + M) + 1 - 3*M-1-M == 0
eq12 = A5 + 3* a5 *( a5 -1)/2 - 3*M-1-M == 0
eq13 = a5 + 1 == 0

solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13],N,p,M,a1,a2,a3,a4,a5,A1,A2,A3,A4,A5)
sol = solutions
print(sol)


OUTPUT

(N, p, M, a1, a2, a3, a4, a5, A1, A2, A3, A4, A5)
[
[N == 731, p == 17, M == 900, a1 == 21, a2 == 11, a3 == -5, a4 == 3, a5 == -1, A1 == 2971, A2 == 3436, A3 == 3556, A4 == 3592, A5 == 3598],
[N == 731, p == (43/7), M == (34866/49), a1 == 21, a2 == 11, a3 == -5, a4 == 3, a5 == -1, A1 == (108643/49), A2 == (131428/49), A3 == (137308/49), A4 == (139072/49), A5 == (139366/49)]
]


Other information:

> if ((-p^2+2*p+N)/(4*p)+2*p)  is even
> and ((-p^2+2*p+N)/(4*p)+2*p)/2 is even
> then a1 =1-((-p^2+2*p+N)/(4*p)+2*p)/2
>
> if ((-p^2+2*p+N)/(4*p)+2*p)  is even
> and ((-p^2+2*p+N)/(4*p)+2*p)/2 id odd
> then a1 =((-p^2+2*p+N)/(4*p)+2*p)/2
>
> if ((-p^2+2*p+N)/(4*p)+2*p)  is odd
> and ((-p^2+2*p+N)/(4*p)+2*p+1)/2 is
> even then a1
> =1-((-p^2+2*p+N)/(4*p)+2*p+1)/2
>
> if ((-p^2+2*p+N)/(4*p)+2*p)  is odd
> and ((-p^2+2*p+N)/(4*p)+2*p+1)/2 id
> odd then a1
> =((-p^2+2*p+N)/(4*p)+2*p+1)/2
>
> in general then:
>
> if aj is negative and (-aj + 1)/2 is
> odd then a(j+1)=(-aj + 1)/2
>
> if aj is negative and (-aj + 1)/2 is
> even then a(j+1)=1-(-aj + 1)/2
>
> if aj is positive and (aj + 1)/2 is
> odd then a(j+1)=(aj + 1)/2
>
> if aj is positive and (aj + 1)/2 is
> even then a(j+1)=1-(aj + 1)/2
>
> other:
>
> if N=4*G+1 multiply N1=N * 3 ,N2=N*15
>
> if N=4*G+3 multiply N1=N * 1 ,N2=N*5
>
> N1 or N2 are in the form 4 * G + 3
> with p + q = 8 * x + 4 and q-p = 4 *
> y-2


I would like to have the cooperation of the mathematicians and programmers of sagemath to solve and implement the system solution ad hoc.

EDIT:

Method of solving the factorization system of P_1_6 Integer Factorization https://www.linkedin.com/feed/update/urn:li:activity:6792170426295447552/ (https://www.linkedin.com/feed/update/...)

edit retag reopen merge delete

Closed for the following reason not a real question by John Palmieri close date 2021-04-16 18:28:09.798263

I think this question should be closed. If you want to ask a question: (a) Do not keep changing it. Figure out what you want to ask before asking, don't use this site as a way to think through the problem yourself. (b) Ask a clear question. In this case: you're talking about factoring. What are you factoring? Integers, I'm guessing? Is there a variable representing the integer to be factored? What are $x$, $y$, and all of the other variables? Nothing here is defined nor explained with any clarity.

( 2021-04-14 18:21:10 +0200 )edit

@John Palmieri ok i won't edit anymore. Waiting for someone to answer

( 2021-04-14 18:34:56 +0200 )edit

As John adviced you should perform (b).

( 2021-04-14 20:38:57 +0200 )edit

@John Palmieri@vdelecroix I tried to explain in the best possible way

( 2021-04-15 12:20:12 +0200 )edit

If you can't explain what integer you're trying to factor, and if you can't explain what output you're looking for, then it's time to close the question. (In your answer below, for instance, if you're factoring 8979, then the output should include the factors 3, 41, 73, but those numbers are nowhere to be seen, nor have you explained above how to get them from the many other variables.)

( 2021-04-16 18:27:54 +0200 )edit

Sort by » oldest newest most voted

If you want to factor N=8979 then trial division is your best choice (here in a very naive version)

def factor_via_trial_division(N):
fac = []
i = 2
while i*i < N:
while N % i == 0:
fac.append(i)
N //= i
i += 1
return fac + [N]


You got

sage: %time factor_via_trial_division(8979)
CPU times: user 70 µs, sys: 3 µs, total: 73 µs
Wall time: 84.2 µs
[3, 41, 73]


Multivariate diophantine systems of degree > 1 are known to be complicated, see https://en.wikipedia.org/wiki/Hilbert.... In particular, it has been proven that there does not exist an algorithm that takes as input a diophantine system and outputs one of its solution if it exists. Because of this, it is hard to believe that building a complicated diophantine system will help in any way to factor.

more

@vdelecroix in my old computer i found a way in which to fix the system employs

CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 9.06 µs

now i am perfecting it after post it

( 2021-04-15 14:58:38 +0200 )edit

@vdelecroix I was wrong in calculating the execution time. Check it out now

( 2021-04-15 15:58:50 +0200 )edit

Sage also has its own factorization method. On my machine, %timeit 8979.factor() returns 3.13 µs ± 62.4 ns per loop, while %timeit factor_via_trial_division(8979) returns 9.96 µs ± 29.1 ns per loop.

( 2021-04-16 02:35:03 +0200 )edit