We'd like to factorize a semiprime \$N\$. The goal of this challenge is to find two small integers \$u\$ and \$v\$ such that \$uvN\$ can be trivially factorized with Fermat's method, thus allowing to easily deduct the factors of \$N\$.
The task
Given a semiprime \$N\$ and a positive integer \$k\$, we define \$x\$ and \$y\$ as:
$$x=\lceil\sqrt{kN}\rceil$$ $$y=x^2-kN$$
Step #1 - Find \$k\$
You first need to find the smallest possible value of \$k\$ such that \$y\$ is a square number (aka perfect square).
This allows to factorize \$kN\$ with a single iteration of Fermat's factorization method. More concretely, this immediately leads to:
$$kN=(x+\sqrt{y})\times(x-\sqrt{y})$$
(Update: this sequence is now published as A316780)
Step #2 - Factorize \$k\$
You then have to find the two positive integers \$u\$ and \$v\$ such that:
$$uv=k$$ $$cu=x+\sqrt{y}$$ $$dv=x-\sqrt{y}$$
where \$c\$ and \$d\$ are the prime factors of \$N\$.
Summary
Your task is to write a program or function that takes \$N\$ as input and prints or outputs \$u\$ and \$v\$ in any order and any reasonable format.
Example
Let's consider \$N = 199163\$
Step #1
The smallest possible value of \$k\$ is \$40\$, which gives:
$$x = \lceil(\sqrt{40 \times 199163})\rceil = 2823$$ $$y = 2823^2 - 40 \times 199163 = 7969329 - 7966520 = 2809 = 53^2$$ $$kN = (2823 + 53) \times (2823 - 53)$$ $$kN = 2876 \times 2770$$
Step #2
The correct factorization of \$k\$ is \$k = 4 \times 10\$, because:
$$kN = 2876 \times 2770$$ $$kN = (719 \times 4) \times (277 \times 10)$$ $$N = 719 \times 277$$
So, the correct answer would be either \$[ 4, 10 ]\$ or \$[ 10, 4 ]\$.
Rules
- It is not required to strictly apply the two steps described above. You're free to use any other method, as long as it finds the correct values of \$u\$ and \$v\$.
- You must support all values of \$uvN\$ up to the native maximum size of an unsigned integer in your language.
- The input is guaranteed to be a semiprime.
- This is code-golf, so the shortest answer in bytes wins.
- Standard loopholes are forbidden.
Test cases
N | k | Output
-----------+------+------------
143 | 1 | [ 1, 1 ]
2519 | 19 | [ 1, 19 ]
199163 | 40 | [ 4, 10 ]
660713 | 1 | [ 1, 1 ]
4690243 | 45 | [ 9, 5 ]
11755703 | 80 | [ 40, 2 ]
35021027 | 287 | [ 7, 41 ]
75450611 | 429 | [ 143, 3 ]
806373439 | 176 | [ 8, 22 ]
1355814601 | 561 | [ 17, 33 ]
3626291857 | 77 | [ 7, 11 ]
6149223463 | 255 | [ 17, 15 ]
6330897721 | 3256 | [ 74, 44 ]
Example implementation
In the snippet below, the \$f\$ function is an ungolfed implementation which takes \$N\$ as input and returns \$u\$ and \$v\$.
For illustrative purposes only, the snippet also includes the \$g\$ function which takes \$N\$, \$u\$ and \$v\$ as input and computes the factors of \$N\$ in \$O(1)\$.
f = N => {
for(k = 1;; k++) {
x = Math.ceil(Math.sqrt(k * N));
y = x * x - k * N;
ySqrt = Math.round(Math.sqrt(y));
if(ySqrt * ySqrt == y) {
p = x + ySqrt;
for(u = 1;; u++) {
if(!(p % u) && !(N % (p / u))) {
v = k / u;
return [ u, v ];
}
}
}
}
}
g = (N, u, v) => {
x = Math.ceil(Math.sqrt(u * v * N));
y = x * x - u * v * N;
ySqrt = Math.round(Math.sqrt(y));
p = x + ySqrt;
q = x - ySqrt;
return [ p / u, q / v ];
}
[
143, 2519, 199163, 660713, 4690243, 11755703,
35021027, 75450611, 806373439, 1355814601,
3626291857, 6149223463, 6330897721
]
.map(N => {
[u, v] = f(N);
[c, d] = g(N, u, v);
console.log(
'N = ' + N + ', ' +
'u = ' + u + ', ' +
'v = ' + v + ', ' +
'N = ' + c + ' * ' + d
);
});
Nwill in fact be a semiprime? \$\endgroup\$