mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2020-07-30, 08:22   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1CD16 Posts
Default 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?
Alberico Lepore is offline   Reply With Quote
Old 2020-07-30, 09:53   #2
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1110011012 Posts
Default

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]
Alberico Lepore is offline   Reply With Quote
Old 2020-07-30, 09:56   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
What do you think?
Show us how you factor something non-trivial.
retina is online now   Reply With Quote
Old 2020-07-30, 10:03   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

72·11·19 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
xilman is offline   Reply With Quote
Old 2020-07-31, 08:30   #5
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

7158 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2020-07-31, 09:12   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
retina is online now   Reply With Quote
Old 2020-07-31, 16:52   #7
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

461 Posts
Default

Quote:
Originally Posted by retina View Post
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?
Alberico Lepore is offline   Reply With Quote
Old 2020-07-31, 17:22   #8
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

206178 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
Uncwilly is online now   Reply With Quote
Old 2020-07-31, 17:35   #9
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

46110 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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)?
Alberico Lepore is offline   Reply With Quote
Old 2020-07-31, 17:58   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

72×11×19 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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
xilman is offline   Reply With Quote
Old 2020-07-31, 18:04   #11
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

461 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Factorizing" function jnml Miscellaneous Math 8 2017-11-01 18:31
Factorizing with MSIEVE, GGNFS & Factmsieve.py Romuald Msieve 24 2015-11-09 20:16
"factoring" vs "factorizing" ixfd64 Factoring 4 2012-10-16 04:07
Suggestion to P-1 procedure jocelynl Software 3 2004-11-28 12:41
Improvements possible for assignment procedure and double checking???? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.