Talk:Euler's factorization method
This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
June 2015
editI 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)
Another Euler Factorisation method mentioned in Dickson's History of Numbers
editEuler 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"[1]:
- Euler[2] noted that imply
- , ,
- so that , 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 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 [3] on this type of factorization and claims it is .
Another source that extends Euler's work to is at url [4]. — Preceding unsigned comment added by Endo999 (talk • contribs) 01:55, 2 April 2020 (UTC)
References
- ^ "History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p362, Chelsea Publishing 1952 read online
- ^ Nova acta Academiae scientiarum imperialis petropolitanae., 14, 1797-8 (1778).3 p 11. Comm Arith,2, 220-242, for Opera posthuma, I, 1862, 159
- ^ "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
- ^ "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.