mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-02-02, 06:22   #1
Godzilla
 
Godzilla's Avatar
 
May 2016

7×23 Posts
Default Can I decrease the factorization time with this formula ?

Formula ( 3 Steps ) :

Note : \frac{1}{3}= 0.333

Step 1 :

prime number  * prime number  = product

2 * \sqrt{0,333 * product} = N1

Step 2 :

\sqrt{product} = N2

Step 3 :

N1 + N2 = N3

First Way \frac{product}{N3} * 3,5 = N4 It work always (for prime factors similar value or distant)

Second Way \frac{product}{N3} = N4 It work only for prime factors distant value


prime number < N4



Example First Way :


Step 1 :


101 * 211 = 21311


2 * \sqrt{0,333 * 21311} =168,...  N1

Step 2 :

\sqrt{21311} = 145,... N2

Step 3 :

168 + 145 = 313 N3

First Way \frac{21311}{313} * 3,5 = 238,.. N4 It work always (for prime factors similar value or distant)

Second Way \frac{21311}{313} = 68,.. N4 It work only for prime factors distant value


prime number < N4


211 < 238

--EDIT--


Can I decrease the factorization time with this formula for big numbers?



.

Last fiddled with by Godzilla on 2017-02-02 at 06:55
Godzilla is offline   Reply With Quote
Old 2017-02-02, 10:09   #2
thyw
 
Feb 2016
! North America

5×13 Posts
Default

What is the purpose of the "Second way" if the first one will "It work always (for prime factors similar value or distant)"?

And by looking at it and simplifying it, sqrt(product) < N3 < product. Always.
[ N3 = ( sqrt(3)+2 )/ sqrt(3) * sqrt(product) ] which is ~2,1547 *sqrt(product)

N4 = product / (~2,15*sqrt(product) )* 3,5 <- which is like (sqrt(product)/~2,15 ) * 3,5 =
sqrt prod * ~1,6 <- rough rounding

^- It might be wrong, and a mess, I'm little tired.
Also it's not scientific in any way.

Ok, so
product = 1852927
sqrt is 1361,222612213
N3 by using sqrt(3)s is 2933,027095
N4 by using ...*3,5 is 2211,109645
So what are the factors? (yafu: 0.0090 sec)

Last fiddled with by thyw on 2017-02-02 at 10:11
thyw is offline   Reply With Quote
Old 2017-02-02, 12:31   #3
Godzilla
 
Godzilla's Avatar
 
May 2016

101000012 Posts
Default

Quote:
Originally Posted by thyw View Post
What is the purpose of the "Second way" if the first one will "It work always (for prime factors similar value or distant)"?

And by looking at it and simplifying it, sqrt(product) < N3 < product. Always.
[ N3 = ( sqrt(3)+2 )/ sqrt(3) * sqrt(product) ] which is ~2,1547 *sqrt(product)

N4 = product / (~2,15*sqrt(product) )* 3,5 <- which is like (sqrt(product)/~2,15 ) * 3,5 =
sqrt prod * ~1,6 <- rough rounding

^- It might be wrong, and a mess, I'm little tired.
Also it's not scientific in any way.

Ok, so
product = 1852927
sqrt is 1361,222612213
N3 by using sqrt(3)s is 2933,027095
N4 by using ...*3,5 is 2211,109645
So what are the factors? (yafu: 0.0090 sec)
Ok , 1277 * 1471 = 1852927

2 * \sqrt{0,333* 1852927} = 1571,...N1

\sqrt{1852927} = 1361,...N2

1361 + 1571 =  2932  N3

First Way \frac{1852927}{2932} * 3.5 = 2211,...N4

Second Way \frac{1852927}{2932}  = 631,...N4


Now trying First Way and Second Way , but only First Way is correct 1471 <  2211 , than \frac{1852927}{2211} .....\frac{1852927}{2209} ...continue until \frac{1852927}{1471}

I think that for large numbers ( 300 digits ), could to be efficient ......


.
Godzilla is offline   Reply With Quote
Old 2017-02-02, 12:43   #4
Godzilla
 
Godzilla's Avatar
 
May 2016

7×23 Posts
Default

Quote:
Originally Posted by thyw View Post
What is the purpose of the "Second way" if the first one will "It work always (for prime factors similar value or distant)[B]"?

997 * 3 = 2991

First way = N4 by using ...*3,5 is 89

Second Way = N4 is 25
Godzilla is offline   Reply With Quote
Old 2017-02-02, 17:42   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133578 Posts
Default

Quote:
Originally Posted by Godzilla View Post
Can I decrease the factorization time with this formula for big numbers?
No, because you don't give any actionable suggestions/algorithms/etc. All you give are four numbers with no obvious connection to anything. But let's look at them anyway!

Let the product be N and its square root be S. Then

N1 = sqrt(3330)/50 * S = 1.154...S
N2 = S
N3 = (1 + sqrt(3330)/50)*S = 2.154...S
N4 = 35(3*sqrt(370) - 50)*S/166 = 1.62479...S

So basically you have four numbers, all of which are fixed algebraic multiples of the square root of the number you're trying to factor. How does this help?
CRGreathouse is offline   Reply With Quote
Old 2017-02-02, 19:21   #6
Godzilla
 
Godzilla's Avatar
 
May 2016

7·23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
No, because you don't give any actionable suggestions/algorithms/etc. All you give are four numbers with no obvious connection to anything. But let's look at them anyway!

Let the product be N and its square root be S. Then

N1 = sqrt(3330)/50 * S = 1.154...S
N2 = S
N3 = (1 + sqrt(3330)/50)*S = 2.154...S
N4 = 35(3*sqrt(370) - 50)*S/166 = 1.62479...S

So basically you have four numbers, all of which are fixed algebraic multiples of the square root of the number you're trying to factor. How does this help?
I think understand it ( but , I'm not sure ), ...for example (simple products)


2*2 = 4 and First Way N4 = 3,5 and Second Way N4 = 1 this is the minimum distance of the two prime factors for First Way ( 2 < 3,5 )


2*3 = 6 and First Way N4 = 5,25 and Second Way N4 = 1,5

2*5 = 10 and First Way N4 = 5,8 and Second Way N4 = 1,6

2*7 = 14 and First Way N4 = 7 and Second Way N4 = 2 this is the maximum distance of the two prime factors for First Way


2*11 = 4 and First Way N4 = 8,5 and Second Way N4 = 2,4 Now Second Way is correct


2*13 = 26 and First Way N4 = 9,1 and Second Way N4 = 2,6 Now Second way is correct


You say it does not work in proportion also for large numbers?

P.S.

Should be tried with a program .

.

Last fiddled with by Godzilla on 2017-02-02 at 19:22
Godzilla is offline   Reply With Quote
Old 2017-02-02, 19:35   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

587110 Posts
Default

Let's say I give you a number:

N = 67646988554084448110460372160440713890061829425106624449473216837898618103759093968747

Then I get (rounding down):

N1 = 9492406899940630172687271283182766199836725
N2 = 8224778936487256622736720394209992127637443
N3 = 17717185836427886795423991677392758327474168
N4 = 13363547807490383809719662986158762809329777

Knowing this, how do we factor the number N? Or what can be said about the factors of this number?

Note that N is not particularly large, and most of the people who post here could factor it without difficulty.
CRGreathouse is offline   Reply With Quote
Old 2017-02-02, 19:55   #8
Godzilla
 
Godzilla's Avatar
 
May 2016

7×23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Let's say I give you a number:

N = 67646988554084448110460372160440713890061829425106624449473216837898618103759093968747

Then I get (rounding down):

N1 = 9492406899940630172687271283182766199836725
N2 = 8224778936487256622736720394209992127637443
N3 = 17717185836427886795423991677392758327474168
N4 = 13363547807490383809719662986158762809329777

Knowing this, how do we factor the number N? Or what can be said about the factors of this number?

Note that N is not particularly large, and most of the people who post here could factor it without difficulty.



But , I begin by "(N4)" N4-2 , N4-4 , N4-6...(First Way and Second Way) and not by"(N)" N-2 , N-4 , N-6.....! And I bet it will be faster.




.
Godzilla is offline   Reply With Quote
Old 2017-02-02, 20:18   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·19·103 Posts
Default

Quote:
Originally Posted by Godzilla View Post
But , I begin by "(N4)" N4-2 , N4-4 , N4-6...(First Way and Second Way) and not by"(N)" N-2 , N-4 , N-6.....! And I bet it will be faster.
A 64-bit integer division takes 73 clocks, and a 286-bit division won't be faster than that. Assuming your clock speed is less than 100 GHz and you have no more than a million CPU cores it would take you more than 10^20 years to factor the number in this fashion. But it should only take a few minutes for SIQS.

Last fiddled with by CRGreathouse on 2017-02-02 at 20:18
CRGreathouse is offline   Reply With Quote
Old 2017-02-02, 20:30   #10
Godzilla
 
Godzilla's Avatar
 
May 2016

2418 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
A 64-bit integer division takes 73 clocks, and a 286-bit division won't be faster than that. Assuming your clock speed is less than 100 GHz and you have no more than a million CPU cores it would take you more than 10^20 years to factor the number in this fashion. But it should only take a few minutes for SIQS.


I was thinking in pencil, for example. I do not know how to work the clock.
Godzilla is offline   Reply With Quote
Old 2017-02-02, 21:50   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·19·103 Posts
Default

Quote:
Originally Posted by Godzilla View Post
I was thinking in pencil, for example. I do not know how to work the clock.
OK, let me rephrase. Your method, starting from N4 and working down through the odds, would take more than 10^40 divisions, and at one division per second would take 10^25 times the age of the universe to factor the number.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Quadratic time factorization" patent mickfrancis Factoring 5 2015-02-17 14:27
Decrease in activity? 10metreh Aliquot Sequences 8 2010-07-15 14:49
New LLT formula hoca Math 7 2007-03-05 17:41
results.txt - Prime95 didn't record time for factorization ixfd64 Software 1 2006-03-30 13:39
Does the LL test:s factorization save or waste CPU time? svempasnake Software 42 2002-10-24 19:27

All times are UTC. The time now is 11:38.

Sat Aug 15 11:38:51 UTC 2020 up 2 days, 8:14, 0 users, load averages: 1.27, 1.38, 1.54

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.