Talk:Euler's factorization method

I have my own variation on the theme, which I shall demonstrate using the same numbers as in the worked example:

1000009 = 1000^2 + 3^2 = 972^2 + 235^2.

Pair off the squared numbers, odd with odd and even with even: {1000,972} and {235,3}.

Take one pair and put their half-sum and half-difference along the diagonal of a 2x2 square:

986 ===

=== 14

Fill in the remaining spaces with the half-sum and half-difference from the other pair:

986 119

116 14

Now calculate the ratios reading across and down:

986/119 = 116/14 = 58/7

986/116 = 119/14 = 17/2

986 119 17

116 14 2

58 7

And the factors are:

58^2 + 7^2 = 3413

17^2 + 2^2 = 293

86.4.253.180 (talk) 00:17, 12 June 2013 (UTC)

86.4.253.180 (talk) 00:21, 12 June 2013 (UTC)

86.4.253.180 (talk) 00:24, 12 June 2013 (UTC)

"which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test." This sentence doesn't make sense. Typo maybe? — Preceding unsigned comment added by 50.46.174.233 (talk) 03:25, 7 December 2013 (UTC)

:Why doesn't this make any sense? Pieater3.14159265 (talk) 03:10, 30 July 2015 (UTC)

Euler Can Factor From Two Equations Of a^2+D*y^2, not just from x^2+y^2

Euler seems to have another factoring method, mentioned in p362 of vol 1 of Dickson's "History of Numbers"

"History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p362, Chelsea Publishing 1952

[https://archive.org/stream/historyoftheoryo01dick#page/362/mode/2up read online]

:

:EulerNova acta Academiae scientiarum imperialis petropolitanae., 14, 1797-8 (1778).3 p 11. Comm Arith,2, 220-242, for $\backslash lambda=2$ Opera posthuma, I, 1862, 159 noted that $N=a^\{2\}+\backslash lambda*b^\{2\}=x^\{2\}+\backslash lambda*y^\{2\}$ imply

:$N=(1/4)*(\backslash lambda*m^\{2\}+n^\{2\})*(\backslash lambda*p^\{2\}+q^\{2\})$, $a\backslash pm\; x=\backslash lambda*m*p,\; n*q$, $y\backslash pm\; b=m*q,\; n*p$

:so that $\backslash lambda*p^\{2\}+q^\{2\}$, or its half or quarter, is a factor of N.

Can someone verify whether this is true or not. And whether this math should get into the article.

It seems that finding one $a^\{2\}+\backslash lambda*b^\{2\}=P*Q$ is easy but finding two with the same lambda is difficult.

The following equation shows this to work:

Solve[
a^2 + 5 b^2 == 8467 39343 && a > 0 && b > 0, {a, b}, Integers]
{{a -> 16541, b -> 3450}, {a -> 17776, b -> 1851}}
aa =
Solve[16541 - 17776 == 5 m p && 3450 + 1851 == m q &&
3450 - 1851 == n p, {m, n, p, q}, Integers]
{{m -> -19, n -> 123, p -> 13, q -> -279}, {m -> 19,
n -> -123, p -> -13, q -> 279}}
now one of the factors is seen, 39343
(1/2) (5 p^2 + q^2) /. aa
{39343, 39343}

This example shows the factoring algorithm works on 3 mod 4 semiprimes, and is thus more general

than the more well known Euler factoring algorithm.

James McKee has a paper

"Turning Euler's Factoring Method into a factoring algorithm" by James McKee. Bulletin. London

Math Society 28(1996)351-355 url=https://pdfs.semanticscholar.org/6d7d/9e973cc9d228e7b62e77917dc53ec053d98a.pdf

on this type of factorization and claims it is $\backslash Omega(\backslash sqrt[3]\{N\})$.

Another source that extends Euler's $x^\{2\}+D*y^\{2\}==p*q$ work to $F*x^\{2\}+D*y^\{2\}==p*q$

is at url "The Completion of Euler's factoring formula", Blecksmith, Brillhart, Decaro url=https://projecteuclid.org/euclid.rmjm/1375361973, Rocky Mountain J. Math.

Volume 43, Number 3 (2013), 755-762.. — Preceding unsigned comment added by Endo999 (talk • contribs) 01:55, 2 April 2020 (UTC)

{{talkref}}