How do we compute the CM discriminants without factoring?

In ECC, there is a parameter known as CM discriminants. Suppose that the trace of the curve is $t$ in $Z_p$. The amount of $s^2$ is the largest square dividing $t^2-4p$ then $\frac{t^2-4p}{s^2}$ is a square-free negative integer. The CM discriminant is $\frac{t^2-4p}{s^2}$ if $\frac{t^2-4p}{s^2} \mod 4 = 1$, otherwise as $4(\frac{t^2-4p}{s^2})$. How do we compute this parameter without factoring? Are there any algorithm for this? Can anybody write the program in Sage for computing D?

We want to find $D=-n/s^2$ for $s^2$ the largest square dividing known $n=4p-t^2>0$ (where $t$ is the trace and $n$ is the order of an Elliptic Curve with an equation in $\mathbb F_p$), for the same reason SafeCurves does: ascertain $-D\ge B$ for some bound $B$ (SafeCurves has $2^{-100}=B$ ). I had never attempted or researched that. This answer is a tentative wild guess.

There is no known method with heuristic time polynomial in the size of $n$ that pulls the square factors of $n$ with certainty (or even high confidence AFAIK), as desired; and I have no idea for one working for the kind of $n$ considered.

The best I have to propose is trying to factor $n$ using methods used for general integers, in particular Lenstra's ECM, different than those (PPMPQS or GNFS) that would be used for an RSA moduli of the size considered (in the order of $p$ at worse); and perform an early abort in the relatively rare case the full factorization is hard to obtain.

The (revised) method I propose goes:

1. Pull as many factors of $n$ as possible using trial division by small primes and optionally a little Pollard's rho.

2. At this point we have expressed $n$ as $n=u\prod{p_i}^{k_i}$ with distinct $p_i$, and each $k_i\ge1$. Improve that (e.g. by trial division of $u$ by each $p_i$) so that no $p_i$ divides $u$.

3. If $u$ is prime or $1$, then $D=-u\prod{p_i}^{k_i\bmod 2}$, we can test $-D\ge B$, stop.

4. If $u$ is a square (which is easily tested), then $D=-\prod p_i^{k_i\bmod 2}$, we can test $-D\ge B$, stop.

5. [optional] Try to pull out more factors of $u$ using a limited amount of Pollard's p-1, and Williams's p+1 (as e.g. in GMP-ECM); and if that succeeds improve the factorization and continue at (2.)

6. At this point, we know one of the following two things holds:

   • $u$ is the product of two distinct primes, none of which is one of our $p_i$;
   • $u$ is the product of three or more prime factors (that is, if $u=\prod{p_j}^{k_j}$ with $p_j$ prime then $\sum k_j\ge3$ ), therefore $u$ is divisible by a prime at most $\sqrt[3]u$.

   Now we use Lenstra's ECM as e.g. in GMP-ECM with hope to find a factor less than $\sqrt[3]u$, or less than the bound $B$. If that succeeds improve the factorization and continue at (2.)

7. If step (6.) did not uncover a factor, we have options:

   • Abandon our effort for this curve and try a new one with hope the check is easier;
   • Factor $u$ with PPMPQS or GNFS;
   • Output $D=-u\prod{p_i}^{k_i\bmod 2}$ which has only a low probability to be incorrect, bounded by the computable probability that the amount of Lenstra's ECM we did could not pull out a factor less than $\sqrt[3]u$
   • Affirm $-D\ge B$ which has only a low probability to be incorrect, bounded by the computable probability that the amount of Lenstra's ECM we did could not pull out a factor less than $B$