2
$\begingroup$

If a composite integer resembles a prime too closely, it must pass algorithmic tests designed to find primes and in addition avoid nontrivial factorization.

Given an integer $p$, assume it is prime and run some testing algorithms for primality. If $p$ fails verification then declare $p$ composite and stop.

Which composites $p$ pass the following probabilistic primality test?:

  1. Pick random integers $a,b$ and count the points modulo $p$ on the elliptic curve $E : y^2=x^3+ax+b$. Let the number of points be $o$. For point counting use Schoof's algorithm.

  2. Verify $o$ is a multiple of the order by finding a point $P$ on $E$ and check if $oP=0$. For finding $P$, chose deterministic algorithm for square roots, say the implementation in sagemath 7.0.

  3. Pick a random integer $X$ and compute $d=\psi_o(X) \mod p$ where $\psi_n$ is the $n$-th division polynomial. Verify $\gcd(d,p) \mod p \in \{0,1\}$. This step might find a nontrivial factor, since counting points modulo composites is probabilistically equivalent to factoring.

The running time of this algorithm is polynomial in $\log{p}$ if $p$ is prime. I believe explicit bounds for the running time are known for prime $p$.

Similar algorithm is via computing square roots modulo $p$. Square roots modulo composite are probabilistically equivalent to factoring, so just try to factor $p$ with square roots and if you fail to compute the square root of known square then $p$ is composite.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ A websearch will turn up something called "elliptic pseudoprime" but I don't think it's quite what you have here. $\endgroup$ – Gerry Myerson Oct 2 '17 at 12:07
  • 1
    $\begingroup$ I highly doubt that the points on $E$ over $\mathbb{Z}/p\mathbb{Z}$ can be counted in time polynomial in $\log p$ if $p$ is not prime and you do not know the factorization of $p$. In particular, counting points on $y^{2} = x^{3} + 1$ mod $pq$ where $p$ and $q$ are both primes congruent to $2 \pmod{3}$ is equivalent to factoring $pq$. $\endgroup$ – Jeremy Rouse Oct 2 '17 at 13:10
  • $\begingroup$ @JeremyRouse I meant it is polynomial for prime $p$. If it is not polynomial or the result is wrong then $p$ is composite. $\endgroup$ – joro Oct 2 '17 at 13:24
  • 2
    $\begingroup$ This will be sensitive to exactly how you compute the number of points in step 1 then. $\endgroup$ – Watson Ladd Oct 2 '17 at 17:06
  • 2
    $\begingroup$ If you use Schoof in step 1 and attempt to find the trace of Frobenius in the $\ell$-torsion $E[\ell]$, you need to see if $(x^p,y^p)$ behaves like Frobenius in $E[\ell]$, which amounts to a Frobenius pseudoprime test in the field generated by $E[\ell]$. $\endgroup$ – Felipe Voloch Oct 2 '17 at 20:15
5
$\begingroup$

Turning my comment into an answer, as I recently learned that my hunch can be justified.

Schoof's algorithm computes, for each small $\ell$ and a point $(x,y) \in E[\ell]$, the element $a_{\ell} \in \mathbb{Z}/\ell$ such that $(x^{p^2},y^{p^2})+p(x,y) = a_{\ell}(x^p,y^p)$ (in the group law on $E$) and recovers the trace of Frobenius by applying the Chinese remainder theorem to the $a_{\ell}$.

We can try to do that when $p$ is not prime and it may fail in many ways. One way it can fail is that $(x^p,y^p)$ is not in $E[\ell]$ (or even in $E$). We can start by checking this, which is a polynomial time computation in the range of $\ell$ of interest. And, if $p$ is not a prime power, [1] proves that indeed there is an $\ell$ in the range of interest where this failure will happen, showing that $p$ is not prime.

[1] Couveignes, Jean-Marc; Ezome, Tony; Lercier, Reynald, https://arxiv.org/abs/0810.2853

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Wouldn't this give possibly inefficient factoring algorithm? $\endgroup$ – joro May 21 '18 at 8:05
  • $\begingroup$ @joro I don't think so. $\endgroup$ – Felipe Voloch May 21 '18 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.