Fermat's Factorization Method

·

Let's see the leetcode problem Sum of Square Numbers first.

The first solution often goes by brute force way. Let's write it first.

``````function judgeSquareSum(c: number): boolean {
for (let x = 0; x*x <= c; x++) {
for (let y = 0; y*y <= c; y++) {
if (x*x + y*y === c) {
return true;
}
}
}
return false;
};
``````

How to speed up this process? Well, instead of increasing `x` and `y` by 1 in each loop, we can think of it reversely. So we need to calculate `x^2 + y^2 = c`, then we can convert it into `Math.sqrt(c - y^2)`. Then we can increment `y` by one, then calculate if the result can be sqrtted.

``````// x^2 + y^2 = c
// x = Math.sqrt(c - y^2)
function judgeSquareSum(c: number): boolean {
for (let y = 0; y * y <= c; y++) {
const x = Math.sqrt(c - y * y);
if (x === Math.floor(x)) return true;
}
return false;
};
``````

OK, now we solved this problem.

This problem is actually very similar to the part of the calculation of Fermat's factorization method. Fermat's factorization method is used to calculate factorization of a number. So given a number `n`, we need to find `a` and `b` with `n = a * b`.

Follow below process, we can convert `n = a * b` into other formats:

``````n = a * b
n = ((a+b)/2)^2 - ((a-b)/2)^2

x = (a+b)/2
y = (a-b)/2

n = x^2 - y^2
n = (x-y) * (x+y)
``````

So we can follow the solution of above problem to calculate `x` and `y` in `n = x^2 - y^2`. Then we can calculate `a` and `b` by `n = (x-y) * (x+y`.

OK, let see the code.

``````// n = x^2 - y^2
// y = sqrt(x^2 - n)
function factor(n: number): [number, number] {
if (n % 2 == 0) return [2, n / 2];

let x = 0;
while (true) {
const yy = x * x - n;
if (yy >= 0) {
const y = Math.sqrt(yy);
if (y === Math.floor(y)) {
return [x - y, x + y];
}
}
x++;
}
}

console.log(factor(9));
``````