mersenneforum.org Eliptic curve J-variants
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-14, 04:08   #1
carpetpool

"Sam"
Nov 2016

2·3·53 Posts
Eliptic curve J-variants

I am interesting in understanding the theoretical aspect of the ECPP test, and how everything works.

Looking at this ECPP example so far I understand:

4*N = u^2 + D*v^2, with Jacobi(-D,N)=1

and tested with different D's until N+1-u has some large probable prime factor q. Then the test is repeated with q and so on until q is small. Makes sense so far, but the concept basic arithmetic, no group theory yet.

I am not sure how the curve used in the test is constructed from the above representation of 4*N:

E: y^2 = x^3 + a*x + b

nor how the cardinality of |E(FN)| = N+u-1

(E over the finite field of N elements)

In the Wikipedia example:

N = 167;
4*N = 25^2 + 43*(1)^2;

so u=25 and the cardinality of the constructed E is N-u+1 = 143.

From wikipedia

Quote:
 In order to construct the curve, we make use of complex multiplication. In our case we compute the J-invariant: j = -960^3 ...

I am completely lost at this point. For the J-invariant (wiki page) j(r) there are only special cases, and formulas involving the discriminant of the cubic polynomial involved in the elliptic curve. I find that also linked on the wikipedia page:

j(i) = 12^3
j( (i*sqrt(163)+1)/2 ) = -640320^3

both of which are functions of the roots of quadratic polynomials. So probably is the case with the ECPP example that

j( (i*sqrt(43)+1)/2 ) = -960^3 ?

Is so, how is this derived... is there are simple formula to compute j(r) for any quadratic integer r as it is used in the ECPP test? There must be some way to understand this without knowing too much CM theory. Can anyone explain this to me? Thanks.

 Similar Threads Thread Thread Starter Forum Replies Last Post SELROC Lounge 34 2019-07-31 21:33 Nick Computer Science & Computational Number Theory 0 2015-03-07 10:31 WraithX GMP-ECM 4 2009-01-12 16:29 wblipp GMP-ECM 8 2008-12-28 14:24 Andi47 GMP-ECM 6 2006-03-19 06:38

All times are UTC. The time now is 16:13.

Thu Nov 26 16:13:18 UTC 2020 up 77 days, 13:24, 4 users, load averages: 1.53, 1.63, 1.54