Go Back > Extra Stuff > Blogorrhea > carpetpool

Thread Tools
Old 2020-08-14, 04:08   #1
carpetpool's Avatar
Nov 2016

23·41 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

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
the learning curve SELROC Lounge 34 2019-07-31 21:33
Elliptic curve variants of Lucas-Lehmer Nick Computer Science & Computational Number Theory 0 2015-03-07 10:31
Lucky gmp-ecm curve... WraithX GMP-ECM 4 2009-01-12 16:29
Work Per ECM Curve wblipp GMP-ECM 8 2008-12-28 14:24
Why does it do only one curve? Andi47 GMP-ECM 6 2006-03-19 06:38

All times are UTC. The time now is 19:47.

Sat Dec 4 19:47:28 UTC 2021 up 134 days, 14:16, 1 user, load averages: 1.33, 1.04, 0.95

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.