Fermat Factorisation
Used when p and q are numericaly close
Last updated
Was this helpful?
Used when p and q are numericaly close
Last updated
Was this helpful?
If and are numerically close, we can use .
During Fermat Factorisation, we hope to find and such that
Because that then means we can factorise the left-hand expression into
As thus we get the two factors of as and .
The reason we use this when and $q$ are numerically close is because the closer they are to each other the closer they are to . If we say rounded up to the nearest number, we can calculate (as rearranged from before) until is a whole number, after which we've solved the equation.
An example of this attack can be found in , which may make it a bit clearer.