How to determine if $n = 53467$ is prime or not using Elliptic curves?

Question

I want to use Elliptic curves modulo $n$ to find out if $n$ is prime or not.

Now, I know that $n = 53467 = 127\times 421$, but how do I find this out using Elliptic curves?

I tried factorization using Lenstra factorization, but how to choose an efficient Elliptic curve to get the factors fast?

Answer 1

Here is a computer search adapted to...

https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

(There is not too much chance to provide an answer without letting the computer search for the answer.)

We pretend that $n=53467$ is a prime, and use a random elliptic curve of the shape $y^2 = x^3+ax$, a random point $P$ on it, and perform some operations with $P$...

n = 53467
R = Integers(n)
a = R.random_element()
E = EllipticCurve(R, [a, 0])
print(f'Using the random element a={a} in the ring (field?) R=ZZ/{n}')

for x0 in [1..n]:
    y0_2 = R(x0)^3 + a*R(x0)
    if y0_2.is_square():
        P = E.point( (R(x0), sqrt(y0_2)) )
    break

print(f'Using the random point P = {P.xy()} on\nE = {E}\n')

import traceback
for k in [1..n]:
    try:
        Q = k*P
    except Exception:
        traceback.print_exc()
        print(f'An error appeared for k={k}. Please analyze the reason above.')
        break

The above gave me this time...

Using the random element a=41275 in the ring (field?) R=ZZ/53467
Using the random point P = (1, 2097) on
E = Elliptic Curve defined by y^2 = x^3 + 41275*x over Ring of integers modulo 53467

Then there is a final error message, showing something went wrong...

An error appeared for k=14. Please analyze the reason above.

And looking inside the looong traceback message, we explicitly can extract this reason:

    raise ZeroDivisionError(f"inverse of Mod({x}, {n}) does not exist")
ZeroDivisionError: inverse of Mod(13472, 53467) does not exist

We have an idea why this fails and ask for...

sage: gcd(13472, 53467)
421

Answer 2

pari/gp code:

ecm()=
{
 n= 53467;
 a= random(n)+1;
 E= ellinit([a, 0], n);
 for(x=1, n,
  X= Mod(x,n);
  if(issquare(X^3+a*X),
   for(y=1, n,
    Y= Mod(y,n);
    if(X^3+a*X==Y^2,
     P= [x,y];
     break(2)
    )
   )
  )
 );
 for(k=1, n,
  iferr(
   ellmul(E, P, k), Err,
   print("E = ["a", "0"] by modulo "n);
   print("P = "P);
   print("k = "k);
   print("inverse error k*P: "Err);
   print("factor of "n" is "gcd(lift(component(Err, 2)), n)"\n");
   return()
  )
 )
};

Examples output:

? \r ecm.gp
? ecm()
E = [41853, 0] by modulo 53467
P = [1, 1440]
k = 14
inverse error k*P: error("impossible inverse in Fp_inv: Mod(421, 53467).")
factor of 53467 is 421

? ecm()
E = [6631, 0] by modulo 53467
P = [6, 1817]
k = 28
inverse error k*P: error("impossible inverse in Fp_inv: Mod(421, 53467).")
factor of 53467 is 421

? ecm()
E = [1381, 0] by modulo 53467
P = [6, 19259]
k = 64
inverse error k*P: error("impossible inverse in Fp_inv: Mod(127, 53467).")
factor of 53467 is 127

? ecm()
E = [15203, 0] by modulo 53467
P = [6, 4434]
k = 30
inverse error k*P: error("impossible inverse in Fp_inv: Mod(421, 53467).")
factor of 53467 is 421

? ecm()
E = [12638, 0] by modulo 53467
P = [5, 12587]
k = 32
inverse error k*P: error("impossible inverse in Fp_inv: Mod(127, 53467).")
factor of 53467 is 127

? ecm()
E = [17202, 0] by modulo 53467
P = [6, 24050]
k = 30
inverse error k*P: error("impossible inverse in Fp_inv: Mod(421, 53467).")
factor of 53467 is 421

? ecm()
E = [34955, 0] by modulo 53467
P = [3, 864]
k = 7
inverse error k*P: error("impossible inverse in Fp_inv: Mod(421, 53467).")
factor of 53467 is 421