Can I decrease the factorization time with this formula ?

Godzilla · 2017-02-02, 06:22

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?

.

thyw · 2017-02-02, 10:09

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)

Godzilla · 2017-02-02, 12:31

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 ......

.

Godzilla · 2017-02-02, 12:43

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

CRGreathouse · 2017-02-02, 17:42

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?

Godzilla · 2017-02-02, 19:21

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 .

.

CRGreathouse · 2017-02-02, 19:35

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.

Godzilla · 2017-02-02, 19:55

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.

.

CRGreathouse · 2017-02-02, 20:18

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.

Godzilla · 2017-02-02, 20:30

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.

CRGreathouse · 2017-02-02, 21:50

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.

2017-02-02, 06:22	#1
Godzilla May 2016 2·3⁴ 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 83 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,15sqrt(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*

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

2017-02-02, 19:35	#7
CRGreathouse Aug 2006 3·1,993 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.