Ask Your Question
-2

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

asked 2021-04-11 11:55:34 +0200

P_1_6 gravatar image

updated 2021-04-25 21:43:39 +0200

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.

Hopefully in your reply, I cordially greet you

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

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

Comments

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.

John Palmieri gravatar imageJohn Palmieri ( 2021-04-14 18:21:10 +0200 )edit

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

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

As John adviced you should perform (b).

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

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

P_1_6 gravatar imageP_1_6 ( 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.)

John Palmieri gravatar imageJohn Palmieri ( 2021-04-16 18:27:54 +0200 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2021-04-15 14:30:58 +0200

vdelecroix gravatar image

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.

edit flag offensive delete link more

Comments

@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

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

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

P_1_6 gravatar imageP_1_6 ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2021-04-16 02:35:03 +0200 )edit

Question Tools

1 follower

Stats

Asked: 2021-04-11 11:55:34 +0200

Seen: 482 times

Last updated: Apr 25