mersenneforum.org Can I decrease the factorization time with this formula ?
 Register FAQ Search Today's Posts Mark Forums Read

 2017-02-02, 06:22 #1 Godzilla     May 2016 7×23 Posts 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
 2017-02-02, 10:09 #2 thyw   Feb 2016 ! North America 5×13 Posts 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
2017-02-02, 12:31   #3
Godzilla

May 2016

101000012 Posts

Quote:
 Originally Posted by thyw 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 ......

.

2017-02-02, 12:43   #4
Godzilla

May 2016

7×23 Posts

Quote:
 Originally Posted by thyw 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

2017-02-02, 17:42   #5
CRGreathouse

Aug 2006

133578 Posts

Quote:
 Originally Posted by Godzilla 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?

2017-02-02, 19:21   #6
Godzilla

May 2016

7·23 Posts

Quote:
 Originally Posted by CRGreathouse 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

 2017-02-02, 19:35 #7 CRGreathouse     Aug 2006 587110 Posts 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.
2017-02-02, 19:55   #8
Godzilla

May 2016

7×23 Posts

Quote:
 Originally Posted by CRGreathouse 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.

.

2017-02-02, 20:18   #9
CRGreathouse

Aug 2006

3·19·103 Posts

Quote:
 Originally Posted by Godzilla 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

2017-02-02, 20:30   #10
Godzilla

May 2016

2418 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2017-02-02, 21:50   #11
CRGreathouse

Aug 2006

3·19·103 Posts

Quote:
 Originally Posted by Godzilla 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 5 2015-02-17 14:27 10metreh Aliquot Sequences 8 2010-07-15 14:49 hoca Math 7 2007-03-05 17:41 ixfd64 Software 1 2006-03-30 13:39 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