## a recursive factoring algorithm?

**Moderators:** gmalivuk, Moderators General, Prelates

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### a recursive factoring algorithm?

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?

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

good luck have fun

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

Why do you think there's a connection between this and factoring?

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

the arithmetic mean^2 -N will give a perfect square. lets call it d.

thus (A-d)*(A+d) = N

thus (A-d)*(A+d) = N

good luck have fun

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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?

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

Can you run through that equation with actual numbers? I don't see why the difference would be a perfect square.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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

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

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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

### Re: a recursive factoring algorithm?

How are you planning on extending that to modular arithmetic?

Summum ius, summa iniuria.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- Eebster the Great
**Posts:**3357**Joined:**Mon Nov 10, 2008 12:58 am UTC**Location:**Cleveland, Ohio

### Re: a recursive factoring algorithm?

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:

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:

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.

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.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: a recursive factoring algorithm?

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

good luck have fun

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

- phillip1882
**Posts:**132**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

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.

- Eebster the Great
**Posts:**3357**Joined:**Mon Nov 10, 2008 12:58 am UTC**Location:**Cleveland, Ohio

### Re: a recursive factoring algorithm?

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.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

### Re: a recursive factoring algorithm?

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.

- Eebster the Great
**Posts:**3357**Joined:**Mon Nov 10, 2008 12:58 am UTC**Location:**Cleveland, Ohio

### Re: a recursive factoring algorithm?

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

### Re: a recursive factoring algorithm?

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

- Eebster the Great
**Posts:**3357**Joined:**Mon Nov 10, 2008 12:58 am UTC**Location:**Cleveland, Ohio

### Re: a recursive factoring algorithm?

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

- gmalivuk
- GNU Terry Pratchett
**Posts:**26676**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: a recursive factoring algorithm?

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.

### Re: a recursive factoring algorithm?

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.

### Who is online

Users browsing this forum: No registered users and 16 guests