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+1u 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(F
_{N}) = N+u1
(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 Nu+1 = 143.
From wikipedia
Quote:
In order to construct the curve, we make use of complex multiplication. In our case we compute the Jinvariant:
j = 960^3 ...

I am completely lost at this point. For the Jinvariant (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.