Center Binomial can "Self-Factor" RSA semiprimes.

Question

Given two odd primes $P$ and $Q$ s.t. $P < Q$, $PQ = N$, $P \neq 3$ and $Q \neq 5$ at same time... the center binomial $f(k)=\frac{(2k)!}{(k!)^{2}}$ can be used to factor $N$. This will not be fast nor efficient, but so far it appears to be guaranteed to work... consistent and repeatable. I have not found a contradiction to this statement.

Let $f(k)=\frac{(2k)!}{(k!)^{2}}$. (The Center Binomial Sequence)

Follow this simple algorithm:

1. Iterate the sequence $f(k)$ starting with $k=1$ and increment $k$ for each iteration.
2. For each iteration of $f(k)$, divide $f(k)$ by $N$.
3. When $N$ divides $f(k)$ s.t. the remainder is zero, STOP.
4. At this point $(2k-1)$ will always be equal to either $Q$ or equal to a multiple of $P$.
5. Since it will not be known if $(2k-1)$ equals $Q$ or equal to a multiple of $P$, then one must perform $gcd[(2k-1),N]$ to get $P$ or $Q$.
6. At this point $N$ is factored.

Ways to possibly speed up this algorithm

1. Iterate at $f(3k)$. When $N$ divides $f(3k)$ we are guaranteed a factor at $(6k-1)$ to be prime.

Questions:

1. Has anyone seen this method before?
2. If yes to question 1, is there a proof to show that when $N$ divides $f(k)$, then $(2k-1)$ will always equal $Q$ or a multiple of $P$?

Other Sequences that "Self-Factor" RSA Semiprimes

1. $f(k)=\frac{(2k-1)!}{(k!)(k-1)!}$. (The binomial sequence to the left & right of center). [1, 3, 10, 35, 126, ...]. This is half of the center binomial sequence.

If you're in doubt, please code the algorithm above to verify this claim.

Analyzing and Expanding the Division by N

$\frac{f(k)}{N} = \frac{(2k)!}{(k!)(k!)(P)(Q)}$

The Division of $f(k)$ by $N$ has two Cases:

1. Case A where $P$ and $Q$ are very close together, their difference is small.
2. Case B where $P$ and $Q$ are very far apart, their difference is large.

Case A: $\frac{(2k)(2k-1)(2k-2)<Q><P> ... (k+2)(k+1)(k!)}{(k!)(k!)<Q><P>}$ $=$ $\frac{(2k)(2k-1)(2k-2) ... (k+2)(k+1)}{(k!)}$

Notice that a $(k!)$ in the numerator and a $(k!)$ in the denominator will cancel out. Also notice that if $P$ and $Q$ are very close together, they'll both reside somewhere in here in the numerator:

$(2k)(2k-1)(2k-2) ... (k+2)(k+1)$

and they'll both cancel from the numerator and the denominator as shown from above and replicated here.

$\frac{f(k)}{N} = \frac{(2k)(2k-1)(2k-2)<Q><P> ... (k+2)(k+1)}{(k!)}$ (both $Q$ and $P$ are canceled out)

Case B: $\frac{(2k)(2k-1)(2k-2)<Q> ... (k+2)(k+1)(k!)}{(k!)(k!)<Q>(P)}$ $=$ $\frac{(2k)(2k-1)(2k-2) ... (k+2)(k+1)}{(k!)(P)}$

Notice that a $(k!)$ in the numerator and a $(k!)$ in the denominator will again cancel out. But notice this time if $P$ and $Q$ are very far apart, only $Q$ will cancel from the denominator and somewhere here in the numerator.

$(2k)(2k-1)(2k-2) ... (k+2)(k+1)$

$P$ remains in the denominator because $(k!)$ has been canceled where $P$ resided... leaving $P$ in the denominator as show from above and replicated here.

$\frac{f(k)}{N} = \frac{(2k)(2k-1)(2k-2)<Q> ... (k+2)(k+1)}{(k!)(P)}$(only $Q$ is canceled out)

CONCLUSION

I believe with some work, the algorithm can be improved with respect to speed and efficiency. Until then... this is slow and inefficient, but interesting and worth further investigation.

Answer 1

I haven't seen this method before, but it can be shown to always work by using Kummer's theorem. This states that, with your center binomial function, i.e.,

$$f(k) = \frac{(2k)!}{(k!)^2} = \binom{2k}{k}$$

the number of factors of a prime, i.e., $P$ or $Q$, of $f(k)$ is the number of carries, in the corresponding prime base $P$ or $Q$, when $k$ is added to itself. For $N$ to divide $f(k)$ requires there to be at least one factor of $P$ and $Q$. Since $Q \gt P$, this means the first set of values to consider are

$$\frac{Q + 1}{2} \le k \le Q - 1$$

where we have that $Q$ divides $f(k)$. If $N$ divides $f(k)$ for the smallest value, i.e., $k = \frac{Q + 1}{2} \;\to\; Q = 2k - 1$, then your first condition applies. Otherwise, we have

$$\frac{Q + 1}{2} = jP + r, \;\; j \ge 1, \;\; 0 \le r \le \frac{P - 1}{2}$$

Note the upper bound of $\frac{P - 1}{2}$ is because, if $\frac{P + 1}{2} \le r \le P - 1$, then $P$ would also divide $f(k)$ (which means $N$ does as well, but we are dealing with when it doesn't). Next, there's

$$Q + 1 = 2jP + 2r \;\;\to\;\; Q - 1 = 2jP + (2r - 2)$$

Consider if

$$\begin{equation}\begin{aligned} 2jP + (2r - 2) & \ge jP + \frac{P + 1}{2} \\ 4jP + (4r - 4) & \ge 2jP + P + 1 \\ (2j - 1)P + (4r - 5) & \ge 0 \end{aligned}\end{equation}$$

The above will always be true if $r \ge 1$, with it only possibly not applying if $r = 0$ and $j = 1$, where the resulting requirement of $P - 5 \ge 0 \;\to\; P \ge 5$ fails only for $P = 3$ and $Q = 5$. However, this is not applicable because of the $P \neq 3$ and $Q \neq 5$ requirement. Nonetheless, note that manual checking shows the first $k$ to work is $k = 8$, with $2k - 1 = 15$ being an integral multiple of $P$ (and, also $Q$), i.e., your second possibility.

Otherwise, when $k = jP + \frac{P + 1}{2}$ is reached, we have by Kummer's theorem that $P$ also divides $f(k)$. We then have

$$2k = 2\left(jP + \frac{P + 1}{2}\right) \;\;\to\;\; 2k - 1 = (2j + 1)P$$

i.e., your second possibility of $2k - 1$ being an integral multiple of $P$ occurs (also note $2k - 1 \gt Q$ and $2k - 1 \le 2Q - 3 \lt 2Q$, so it's not a multiple of $Q$).