Fermat's factorization method: Difference between revisions

Revision as of 16:11, 8 October 2022

Revision as of 16:15, 8 October 2022

Line 151:

==Other improvements==

The fundamental ideas of Fermat's factorization method are the basis of the [[quadratic sieve]] and [[general number field sieve]], the best-known algorithms for factoring large [[semiprimes]], which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of <math>a^2 - n</math>, it finds a subset of elements of this sequence whose ''product'' is a square, and it does this in a highly efficient manner. The end result is the same: a difference of square mod ''n'' that, if nontrivial, can be used to factor ''n''.

==Factorization with rectangles==

The method can be modified to use rectangles instead of squares, by adding a constant c: <math>(a+c) \times a - (b+c) \times b = (a-b) \times (a+b+c)</math>

==Factorization with cubes==

<math>a^3 - b^3 = (a-b) \times ((a+b) \times a+ b \times b)</math> {{citation needed

==Factorization with cuboids==

<math>(a+c) \times a^2 - (b+c) \times b^2 = (a-b) \times ((a+b+c) \times a + (b+c) \times b)</math>

==See also==