yaox023
yaox023's blog

yaox023's blog

Fermat's Factorization Method

Fermat's Factorization Method

yaox023's photo
yaox023
·Aug 29, 2022·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

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));
 
Share this