Searching for odd divisors of $n$ using the form $2x^2 + y^2 + z^2$ where $y^2+z^2 = p$ is prime

Question

Every odd integer $n$ is represented by the ternary quadratic form $n = 2x^2 + y^2 + z^2$.

By Fermat's Sum of Squares Theorem, primes of the form $p = 4k+1$ can be represented as $p = 4k+1 = a^2 +b^2$.

Suppose $n = (2a_1^2 + a_2^2 + a_3^2)(2b_1^2 + b_2^2 + b_3^2)$. WLOG take $2a_1^2 + a_2^2 + a_3^2 \le 2b_1^2 + b_2^2 + b_3^2$. The equality holds when $n$ is a square. Assume $n$ is not a square. Therefore, we have the inequality,

$$ 2a_1^2 + a_2^2 + a_3^2 < \sqrt{n} < 2b_1^2 + b_2^2 + b_3^2 < n $$

By taking $a_2^2 + a_3^2 = p = 4k+1$, we obtain the following algorithm for factoring $n$.

Algorithm Factor($n$)

Input: $n$: An odd positive integer that is not a square

Returns: $\begin{cases} 1 : \text{if $n$ is prime}, \\ a : \text{where $a|n$, if $n$ is composite} \end{cases} $

Begin

1. Let $\beta = \bigg\lfloor \sqrt{\frac{\sqrt{n}}{2}} \bigg\rfloor$

2. For $a_1 = 0,1, \cdots \beta$

   a. Let $\delta = 2a_1^2$

   b. Let $k_{\text{max}} = \frac{\sqrt{n} - \delta - 1}{4}$

   c. For $k = 1, 2, \cdots, k_{\text{max}}$

   1. Let $p = 4k + 1$

   2. Let $a = \delta + p$

   3. If $p$ is prime by Miller-Rabin test then

      a. If $a|n$ then

      1. return $a$ $\text{ ; Found $a$ as a factor of $n$}$

      c. End If

   4. End If

   d. Next

3. Next $a_1$

4. return $1$ $\text{ ; $n$ is prime}$

End

In step $2.c.3$, we do a Miller-Rabin primality test on $p$. This is not required and we can simply check $a|n$ even if $p$ is not prime. The algorithmic complexity remains unchanged.

Termination. The algorithm runs a finite number of times. It terminates in step $2.c.3.a.1$ or in step $4.$

Correctness. The algorithm is correct based on the following claims:

1. The outer loop in step $2$ ensures that we check each $\delta = 2a_1^2 \lt \sqrt{n}$.
2. The inner loop in step $2.c$ checks for all integers $p$ of the form $4k+1$ satisfying $\delta + p \lt \sqrt{n}$.
3. (Claim A): Since this represents all odd integers, the subset of primes $\lt \sqrt{n}$ are covered by this search.
4. Therefore, the algorithm finds the odd divisor of $n$ (which is also odd).
5. (Claim B): If we do not find an odd integer of the form $2a_1^2 + a_2^2 + a_3^2$ then $n$ has no divisors less than $\sqrt{n}$ which implies $n$ must be prime.

Time Complexity.

1. Excluding the Miller-Rabin test: If the Miller-Rabin test is not included, then the time complexity is:

$$ \begin{align} \overbrace{O\bigg(\frac{1}{\sqrt{2}}n^\frac{1}{4}\bigg)}^{\text{outer loop}} \times \overbrace{O\bigg(\frac{n^{\frac{1}{2}} - 1}{4}\bigg)}^{\text{inner loop}} \approx O\bigg(\frac{n^\frac{1}{4}}{\sqrt{2}} \cdot \big(\frac{n^{\frac{1}{2}} - 1}{4}\big) \bigg) \approx O\bigg(\frac{n^\frac{1}{4}}{\sqrt{2}} \cdot \frac{n^{\frac{1}{2}}}{4} \bigg) \approx O\bigg(\frac{n^\frac{3}{4}}{4\sqrt{2}}\bigg) \end{align} $$

2. Including the Miller-Rabin test: If the Miller-Rabin test is included, then the time complexity includes a factor $O(K \cdot (\log^3 n))$ i.e.,

$$O\bigg(K \cdot (\log^3 n) \cdot \frac{n^\frac{3}{4}}{4\sqrt{2}}\bigg)$$

where $K$ is the number of iterations in the Miller-Rabin test.

This is not better than trial division which is $O(\sqrt{n})$.

Question: Can we prove claims $A$ and $B$?