View Single Post
Old 2020-08-14, 04:08   #1
carpetpool's Avatar
Nov 2016

2·163 Posts
Post 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

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.
carpetpool is offline   Reply With Quote