mersenneforum.org Procedure for factorizing N into O (1) ...Not.
 Register FAQ Search Today's Posts Mark Forums Read

 2020-07-30, 08:22 #1 Alberico Lepore     May 2017 ITALY 1CD16 Posts Procedure for factorizing N into O (1) ...Not. Let N be an odd number to factorize such that N = p * q with (p + q-4) = 0 (mod 8) and (q-p + 2) = 0 (mod 4) then the derivative of sqrt[(2 + 3 x)^2 (2*((3*N-1)/8-1)/3+1 - x + x^2)]-sqrt[(-5 + 3 x)^2 (2*((3*N-1)/8-1)/3+1 - x + x^2)] that will be in the form 1/2*[(-36x^3+117x^2-Ax+B)/(sqrt((x^2-x+2*((3*N-1)/8-1)/3+1)*(-5+3x)^2))+(36x^3+9x^2+Cx+D)/((sqrt((x^2-x+2*((3*N-1)/8-1)/3+1)*(2+3x)^2)))] doing this system (4*b+2)^2-(2*a-1)^2=N, 1/2*[(-36*1^3+117*1^2-(A+36*(a-1))*1+B+60*(a-1))/(sqrt((a^2-a+47)*(-5+3*1)^2))+(36*1^3+9*1^2+(C+36*(a-1))*1+D+24*(a-1))/((sqrt((a^2-a+47)*(2+3*1)^2)))]=[3*(4*b+2)^2+3]/[4*b+2] that this is simplified (4*b+2)^2-(2*a-1)^2=N, [(-36*1^3+117*1^2-(A+36*(a-1))*1+B+60*(a-1))/(5-3*1)+(36*1^3+9*1^2+(C+36*(a-1))*1+D+24*(a-1))/(2+3*1)]=[3*(4*b+2)^2+3] are a and b p=4*b+2-(2*a-1) ed q=4*b+2+(2*a-1) Example (4*b+2)^2-(2*a-1)^2=N, [(-36*1^3+117*1^2-(A+36*(a-1))*1+B+60*(a-1))/(5-3*1)+(36*1^3+9*1^2+(C+36*(a-1))*1+D+24*(a-1))/(2+3*1)]=[3*(4*b+2)^2+3] , A=956 , B=1435 , C=830 , D=560 , N=187 -> a=2 ;b=3 ->p=11 ;q=17 If N = 4 * G + 1 multiply by 3 and it becomes 4 * H + 3 If N = 4 * H + 3 and the algorithm does not work, multiply by 5 What do you think?
 2020-07-30, 09:53 #2 Alberico Lepore     May 2017 ITALY 1110011012 Posts unfortunately it doesn't work. the correct formula is this (4*b+2)^2-(2*a-1)^2=N, [(-36*1^3+117*1^2-(A+36*a*(a-1)/2)*1+B+60*a*(a-1)/2)/(5-3*1)+(36*1^3+9*1^2+(C+36*a*(a-1)/2)*1+D+24*a*(a-1)/2)/(2+3*1)]=[3*(4*b+2)^2+3]
2020-07-30, 09:56   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts

Quote:
 Originally Posted by Alberico Lepore What do you think?
Show us how you factor something non-trivial.

2020-07-30, 10:03   #4
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

72·11·19 Posts

Quote:
 Originally Posted by Alberico Lepore What do you think?
I think you are wasting your time. However, it is your time to waste.

I have already wasted far too much of my time on this one.

 2020-07-31, 08:30 #5 Alberico Lepore     May 2017 ITALY 7158 Posts English Hi retina and xilman I found an algorithm that factorizes N=[4*b+2]^2-(2*a-1) in O(1) which only works if a<[sqrt[32*b+9]+1]/2 Now I'll explain it Code: M=((N*3-1)/8-1)/3 Let's rewrite this (4*b+2)^2-(2*a-1)^2=N so (-36*1^3+117*1^2-((M+3)*36+20+36*(a-1)*a/2)*1+(M*60+55)+60*(a-1)*a/2)/2-4=24*b*(b+1) If we put a = 2 we notice that solve (-36*1^3+117*1^2-((M+3)*36+20+36*(2-1)*2/2)*1+(M*60+55)+60*(2-1)*2/2)/2-4>24*(b-1)*(b-1+1) , (4*b+2)^2-(2*a-1)^2=((M*3+1)*8+1)/3 b>1/8*(a^2-a-2) -> a<[sqrt[32*b+9]+1]/2 Example N=667=(4*b+2)^2-(2*a-1)^2=[(4*b+2)-(2*a-1)]*[(4*b+2)+(2*a-1)] M=((667*3-1)/8-1)/3=83 solve (-36*1^3+117*1^2-((83+3)*36+20+36*(2-1)*2/2)*1+(83*60+55)+60*(2-1)*2/2)/2-4>24*(b-1)*(b-1+1) b<7 -> b=6 This is in O (1) assigning to a value of 2 if we know that q and p are of the same order, for example 100 digits we can assign a value of 98 digits so as to be less than true a Italian Ciao retina e xilman ho trovato un algoritmo che fattorizza N=[4*b+2]^2-(2*a-1) in O(1) che funziona solo se a<[sqrt[32*b+9]+1]/2 Ora te lo spiego M=((N*3-1)/8-1)/3 Riscriviamo questa (4*b+2)^2-(2*a-1)^2=N così (-36*1^3+117*1^2-((M+3)*36+20+36*(a-1)*a/2)*1+(M*60+55)+60*(a-1)*a/2)/2-4=24*b*(b+1) Se mettiamo a=2 notiamo che solve (-36*1^3+117*1^2-((M+3)*36+20+36*(2-1)*2/2)*1+(M*60+55)+60*(2-1)*2/2)/2-4>24*(b-1)*(b-1+1) , (4*b+2)^2-(2*a-1)^2=((M*3+1)*8+1)/3 b>1/8*(a^2-a-2) -> a<[sqrt[32*b+9]+1]/2 Esempio N=667=(4*b+2)^2-(2*a-1)^2=[(4*b+2)-(2*a-1)]*[(4*b+2)+(2*a-1)] M=((667*3-1)/8-1)/3=83 solve (-36*1^3+117*1^2-((83+3)*36+20+36*(2-1)*2/2)*1+(83*60+55)+60*(2-1)*2/2)/2-4>24*(b-1)*(b-1+1) b<7 -> b=6 Questo è in O(1) assegnando ad a valore 2 se conosciamo che q e p sono dello stesso ordine ad esempio 100 cifre possiamo assegnare ad a un valore di 98 cifre in modo da essere minori del vero a
2020-07-31, 09:12   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts

Quote:
 Originally Posted by Alberico Lepore if we know that q and p are of the same order, for example 100 digits we can assign a value of 98 digits
So show us that. Show us how you factor a 200 digit number.

2020-07-31, 16:52   #7
Alberico Lepore

May 2017
ITALY

461 Posts

Quote:
 Originally Posted by retina So show us that. Show us how you factor a 200 digit number.
I'm not programmer

If it works in O (1) for a <[sqrt [32 * b + 9] +1] / 2
then it works in O (log) for any a

do you agree?

2020-07-31, 17:22   #8
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

206178 Posts

Quote:
 Originally Posted by Alberico Lepore I'm not programmer
If you work in math nowadays you need to learn some programming. Also, if you work in Astronomy. And also in a number of other fields it can be needed.

Go learn Java or Python or some other language. Once you have one of your procedures coded up, try running it on a 200 digit number.

2020-07-31, 17:35   #9
Alberico Lepore

May 2017
ITALY

46110 Posts

Quote:
 Originally Posted by Uncwilly If you work in math nowadays you need to learn some programming. Also, if you work in Astronomy. And also in a number of other fields it can be needed. Go learn Java or Python or some other language. Once you have one of your procedures coded up, try running it on a 200 digit number.
I give you my word that I will learn.
could you give me a little help:
does it work in O (1)?

2020-07-31, 17:58   #10
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

72×11×19 Posts

Quote:
 Originally Posted by Alberico Lepore I give you my word that I will learn. could you give me a little help: does it work in O (1)?
No.

Your turn. Go learn some programming and some computer science and we will then take our turn.

Last fiddled with by xilman on 2020-07-31 at 18:14

2020-07-31, 18:04   #11
Alberico Lepore

May 2017
ITALY

461 Posts

Quote:
 Originally Posted by xilman No. If you knew anything at all about asymptotic analysis, you would know that it takes time O(log N) just to read the input. Your turn. Go learn some programming and some computer science and we will then take our turn.
for O(1) I mean the number of cycles in programming.

 Similar Threads Thread Thread Starter Forum Replies Last Post jnml Miscellaneous Math 8 2017-11-01 18:31 Romuald Msieve 24 2015-11-09 20:16 ixfd64 Factoring 4 2012-10-16 04:07 jocelynl Software 3 2004-11-28 12:41 Erasmus PrimeNet 10 2004-02-19 12:09

All times are UTC. The time now is 14:27.

Fri Sep 18 14:27:23 UTC 2020 up 8 days, 11:38, 1 user, load averages: 1.32, 1.35, 1.41