a recursive factoring algorithm?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 7:31 pm UTC

the quadratic mean of the quadratic mean and geometric mean of two odd numbers, is the arithmetic mean.

this suggests to me that it seems like some kind of recursive solution is possible. any ideas?
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 7:56 pm UTC

Why do you think there's a connection between this and factoring?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 8:03 pm UTC

the arithmetic mean^2 -N will give a perfect square. lets call it d.
thus (A-d)*(A+d) = N
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 8:12 pm UTC

phillip1882 wrote:
the arithmetic mean^2 -N will give a perfect square. lets call it d.
thus (A-d)*(A+d) = N

What is N in this case?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 8:14 pm UTC

the number you're trying to factor.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 8:19 pm UTC

Can you run through that equation with actual numbers? I don't see why the difference would be a perfect square.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 8:25 pm UTC

okay lets take 17 and 31.
17*31 = 527
(17+31)/2 = 24
24^2 -527 = 49
(24-7)*(24+7) = 17*31
i must confess i'm not sure how to prove this will always be the case,
but its worked with any two prime numbers i've thrown at it.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 8:32 pm UTC

phillip1882 wrote:the quadratic mean of the quadratic mean and geometric mean of two odd numbers, is the arithmetic mean.

This is true of any numbers, not just odd integers.

(x + y)/2 = sqrt((x + y)^2 / 4)
= sqrt((x^2 + 2xy + y^2) / 4)
= sqrt(((x^2+y^2)/2 + xy) / 2)
= sqrt((QM^2 + GM^2) / 2)

Where QM = sqrt((x^2+y^2)/2) is the quadratic mean and GM = sqrt(XY) is the geometric mean.

phillip1882 wrote:okay lets take 17 and 31.
17*31 = 527
(17+31)/2 = 24
24^2 -527 = 49
(24-7)*(24+7) = 17*31
i must confess i'm not sure how to prove this will always be the case,
but its worked with any two prime numbers i've thrown at it.

...you noticed that 17 and 31 are 24-7 and 24+7, right?

And you got 527 by multiplying a pair of numbers together in the first place, so if course it has those numbers as factors.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 8:39 pm UTC

hmm, i think you're not understanding my explanation.
17*31 = 527.
now lets assume we don't know 17 and 31 are factors of 527.
but we know the arithmetic mean of the two factors is 24.
then 24^2 -527 = 49.
then 24^2 -7^2 = 527
then (24-7)*(24+7) = 17*31
good luck have fun

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 8:47 pm UTC

as another example, lets take the number 7663.
if i square root the number, i get 88 approximately.
88^2 -7663 = 81
thus 88^2 -9^2 = 7663
thus (88 -9)*(88+9) = 7663.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 8:56 pm UTC

phillip1882 wrote:
now lets assume we don't know 17 and 31 are factors of 527.
but we know the arithmetic mean of the two factors is 24.

Why would we know that?

then 24^2 -527 = 49.
then 24^2 -7^2 = 527
then (24-7)*(24+7) = 17*31

I mean, yeah, but then what you've discovered is that if you can express your number as a difference of perfect squares then it's easy to calculate two of its factors. I'm not sure how that would lend itself to a useful algorithm because it's not any faster to check perfect squares than it is to check possible factors.

phillip1882 wrote:
as another example, lets take the number 7663.
if i square root the number, i get 88 approximately.
88^2 -7663 = 81
thus 88^2 -9^2 = 7663
thus (88 -9)*(88+9) = 7663.

Okay but that only works because you're starting with small factors fairly close together, rather than starting with the large unfactored number (or with factors farther apart, like 17 and 31; sqrt(527) is near 23, but 23^2 - 527 = 2, which isn't helpful).

7661 also has a square root of approximately 88.
88^2 - 7661 = 83, which isn't a perfect square. That doesn't tell you anything about 7661's factors, except that 88 isn't their arithmetic mean.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Mon May 13, 2019 10:07 pm UTC

its generally faster than testing for divisibility by numbers because the arithmetic mean is generally "close" the the geometric mean.
for 7661
the square root is 88, the arithmetic mean is 105, 105 -88 = 17 where as testing for every prime to see if goes evenly in up to 88, is a greater number of possibilities.

for large numbers the difference between them gets more significant.
9877349, square root = 3142, arith mean (which you can get by testing values one at a time until you get a perfect square result), 3165.
3165^2 - 9877349 = 139876‬
(3165-374)*(3165+374) = 2791*3539
so i only had to test 23 possibilities rather than over 100, for trail division.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Mon May 13, 2019 10:13 pm UTC

The arithmetic mean of the factors of 2157647 is more than twice its square root.

You'd have to prove that it's generally faster, rather than just quoting some examples. And in any case if it averages to some constant fraction of trials it's not usefully better.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Tue May 14, 2019 12:58 am UTC

i don't have to prove its generally faster, i just have to prove that it will always factor numbers with 2 primes.
admittedly i not sure how to do that, but again if there's some recursive approach to getting the arithmetic mean, then that might break cryptography.
good luck have fun

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6537
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: a recursive factoring algorithm?

Postby Thesh » Tue May 14, 2019 1:33 am UTC

How are you planning on extending that to modular arithmetic?
Summum ius, summa iniuria.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 3:21 am UTC

phillip1882 wrote:if there's some recursive approach to getting the arithmetic mean, then that might break cryptography.

What kind of recursive approach? Where does recursion enter into it? So far all you've got is another method that requires guessing one-by-one that seems to be about as efficient (maybe give or take a constant) as just checking primes up to the square root.

If it's not significantly faster than existing factorization, it won't break cryptography or anything else.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 3351
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: a recursive factoring algorithm?

Postby Eebster the Great » Tue May 14, 2019 3:45 am UTC

Yeah, "recursion" doesn't mean "trial and error," it means "a process that calls itself as part of its algorithm until it reaches a base case." A recursive factorial function in python looks like this:

Code: Select all

def factorial(n):
   if n == 0:
      return 1
   else:
      return n * factorial(n-1)


So if I call factorial(2), it will return 2 * factorial(1), which is 2 * 1 * factorial(0), which is 2 * 1 * 1 = 2. This is as opposed to an iterative approach, like this:

Code: Select all

def factorial(n):
   a = 1
   for i in range(1,n+1):
      a = a * i
   return a


So if I call factorial(2), it will start with a = 1 and then multiply it by each number in [1,3) (the range function in python excludes the upper bound), computing 1 * 1 * 2 = 2.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 3:19 pm UTC

phillip1882 wrote:i don't have to prove its generally faster, i just have to prove that it will always factor numbers with 2 primes.

Just checking primes smaller than the square root will also always factor numbers. If your method isn't generally faster, then it's as slow or slower than basically the worst possible systematic way of factoring a number.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Tue May 14, 2019 8:21 pm UTC

we're veering quite away from my original intent.

my original question was: given that the quadratic mean of the quadratic and geometric mean is the arithmetic mean, is there some recursive way to repeatedly apply the quadratic mean until you get the desired result? i personally don't see how but thought maybe someone would have an idea.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 8:31 pm UTC

phillip1882 wrote:we're veering quite away from my original intent.

my original question was: given that the quadratic mean of the quadratic and geometric mean is the arithmetic mean, is there some recursive way to repeatedly apply the quadratic mean until you get the desired result? i personally don't see how but thought maybe someone would have an idea.

I still don't get the connection. Are you ever in a situation where you know the quadratic mean of a number's factors but not their arithmetic mean?

Are you asking whether there's some other number you can start with, instead of the QM of the factors, and then keep taking the quadratic mean to get closer and closer?

I don't imagine that would be a thing, since as I already showed the equivalence you noticed in the first post applies to any pair of numbers, not just integers or primes. If there is a convergence, I don't see any reason for it to be a rational number at all, let alone one with any particular relationship to the integer factors.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Tue May 14, 2019 8:36 pm UTC

no, but i hoped there was some way of approximating it by repeatedly applying the formula.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 8:40 pm UTC

phillip1882 wrote:no, but i hoped there was some way of approximating it by repeatedly applying the formula.

See my edit. The equivalence holds for any pair of numbers, so there's no reason to expect convergence to an integer.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
phillip1882
Posts: 131
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a recursive factoring algorithm?

Postby phillip1882 » Tue May 14, 2019 8:42 pm UTC

okay that's what i was asking.
good luck have fun

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 9:26 pm UTC

If a function converges, it converges to a fixed point.

That is, if you apply f to x again and again, and it converges to p, it must be true that f(p)=p.

The fact that the arithmetic mean doesn't show up on the left side of your equation (i.e. the "quadratic mean of the quadratic mean and the geometric mean" side) means it won't be a point of convergence in general.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 3351
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: a recursive factoring algorithm?

Postby Eebster the Great » Tue May 14, 2019 11:28 pm UTC

I just want to point out that I find that relation on obscure means kind of neat, even if it doesn't mean anything. I had never seen this before.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Tue May 14, 2019 11:46 pm UTC

phillip1882 wrote:
its generally faster than testing for divisibility by numbers because the arithmetic mean is generally "close" the the geometric mean.

Separate from the fact that there's no recursive way to get the arithmetic mean, is the fact that actually this is generally false, when you consider that primes get less and less dense.

For cryptographic purposes, the primes multiplied usually have the same number of bits, so range from S to 2S ("S" for "size").
For large S, primes are distributed relatively evenly between S and 2S.
The average difference between arithmetic mean and geometric mean of uniform random variables between S and 2S is more than 0.014S.
The number of primes below S is approximately S/ln(S).
This is smaller than 0.014S for all S greater than about 10^31 or 2^103.

Therefore, if S is larger than about 103 bits, which it should be (by a lot) for any self-respecting cryptographic purposes, it's actually going to be generally faster to "just" test divisibility by primes below the square root of the large number to be factored.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
PM 2Ring
Posts: 3688
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: a recursive factoring algorithm?

Postby PM 2Ring » Wed May 15, 2019 5:51 am UTC

FWIW, Fermat devised a factorization method that uses (a + b)(a - b) = a² - b². See https://en.wikipedia.org/wiki/Fermat%27 ... ion_method
In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.

User avatar
Eebster the Great
Posts: 3351
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: a recursive factoring algorithm?

Postby Eebster the Great » Wed May 15, 2019 7:38 am UTC

All of these methods have the same complexity up to a constant factor, right?

DavCrav
Posts: 248
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: a recursive factoring algorithm?

Postby DavCrav » Wed May 15, 2019 9:06 am UTC

PM 2Ring wrote:FWIW, Fermat devised a factorization method that uses (a + b)(a - b) = a² - b². See https://en.wikipedia.org/wiki/Fermat%27 ... ion_method
In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.


Indeed, it's called a Fermat attack (or at least I do) and it's why, when you choose p and q, you also make sure they are a long way apart, as well as big.

User avatar
Eebster the Great
Posts: 3351
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: a recursive factoring algorithm?

Postby Eebster the Great » Wed May 15, 2019 10:12 am UTC

I thought the Fermat attack was another name for Wiener's attack since it used Fermat's Little Theorem.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26665
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: a recursive factoring algorithm?

Postby gmalivuk » Wed May 15, 2019 12:46 pm UTC

Eebster the Great wrote:All of these methods have the same complexity up to a constant factor, right?

The wiki article says a combination of Fermat and trial division can factor N in O(N^(1/3)) time.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

DavCrav
Posts: 248
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: a recursive factoring algorithm?

Postby DavCrav » Thu May 16, 2019 10:05 am UTC

Eebster the Great wrote:I thought the Fermat attack was another name for Wiener's attack since it used Fermat's Little Theorem.


A quick Google search suggests it's not just me. For example, this page also calls it Fermat's attack. I couldn't possibly comment on where I heard it called that.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests