mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   carpetpool (https://www.mersenneforum.org/forumdisplay.php?f=145)
-   -   Eliptic curve J-variants (https://www.mersenneforum.org/showthread.php?t=25833)

carpetpool 2020-08-14 04:08

Eliptic curve J-variants
 
I am interesting in understanding the theoretical aspect of the ECPP test, and how everything works.



Looking at [URL="https://en.wikipedia.org/wiki/Elliptic_curve_primality#Example_of_Atkin%E2%80%93Morain_ECPP"]this[/URL] 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(F[SUB]N[/SUB])| = 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 [URL="https://en.wikipedia.org/wiki/J-invariant"]J-invariant:[/URL]


j = -960^3 ...

[/QUOTE]


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 [URL="https://en.wikipedia.org/wiki/Complex_multiplication"]CM theory[/URL]. Can anyone explain this to me? Thanks.


All times are UTC. The time now is 05:49.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.