ポラード・ロー素因数分解アルゴリズム

prime-factrize.js

'use strict';

const xor64 = function (y) {
	y = y >>> 0;
	y = y ^ (y << 13);
	y = y ^ (y >> 7);
	y = y ^ (y << 17);
	return y >>> 0;
};

const GCD = function(m, n) {
	while (n != 0) {
		[m, n] = [n, m % n];
	}
	return m;
}

const factorize = function (n) {
	const f = function (seed) {
		return xor64(seed) % n;
	}
	let x = 2;
	let y = 2;
	let d = 1;
	while (d == 1) {
		x = f(x);
		y = f(f(y));
		d = GCD(Math.abs(x - y), n);
	}
	if (d == n) {
		return false;
	}
	return d;
};