We got argument and strong experimental support that integers of the form $n=p q^2$ can be factored using elliptic curves easier than general integers
Q1 Is this known?
Added This is known since at least 2002: Factoring N = p q^2 with the Elliptic Curve Method
Q3 Can the method be improved for general integers?
Assume $E$ is elliptic curve modulo $n$ with known point $P$ of the order of $P$ over $\mathbb{F}_p$ is $\rho = S U$ where $S$ is $B_1$ smooth. We can find the factor $p$ working over the curve modulo $n$ in time $O(B_1 + \sqrt{U})$ and constant memory. It is an open problem if this can be generalized to arbitrary $n$.
Stage 1:
This is the first stage of the elliptic curve factoring algorithm.
Set $Q=P$ and for primes $r$, $r \le B_1$ let $Q=r^{\log_r{n}} Q$.
If we reach the point at infinity modulo $p$ we are done and the algorithm stops with factor $p$.
Stage 2: This is based on the birthday paradox and Pollard's rho algorithm for discrete logarithms in groups.
Let $\mathrm{kronecker}(a,n)$ denote the kronecker symbol and for a point $a$ on an elliptic curve $X(a)$ denote the $X$ coordinate of $a$.
For points $a,b$ on $E$ define the function $f(a,g)$:
If $\mathrm{kronecker}(X(a),n)=1,f(a,g)=2 a + 5 g$, else $f(a,g)=3 a + g$.
For $Q$ from stage 1, set $a=Q,b=Q,g=Q$.
For $n$ from $1$ to $B_2$ set $a=f(a,g),b=f(b,g),b=f(b,g)$.
If $\gcd(X(a)-X(b),n) \bmod n>1$ return the factor.
Stage 2 finds multiple of $U Q$ in time $B_2$ while $U \sim B_2^2$.
Since the kronecker symbol is multiplicative, we have $\mathrm{kronecker}(a,n)=\mathrm{kronecker}(a,p)$ for $a$ coprime to $n$.
Iterates of $f^k(a,g)$ are deterministic random walk modulo $p$, so $f^N(a,g)=f^{2N}(a,g)$ happens for $N = O(\sqrt{U}) \sim B_2$.
