20141022, 07:47  #45 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
24231_{8} Posts 

20141022, 09:21  #46  
May 2012
2^{3} Posts 
Quote:
In order to compute a curve with a known jinvariant J, in most (as a matter of fact, in all) books, papers, or implementations, we can find something like this c = J/(J  1728) mod p a = (3c) mod p b = (2c) mod p and we get the curve C1 y**2 = x**3 + ax + b (mod p). It works but it is not the best way of doing. With any k such that 0 < k < p, the curve y**2 = x**3 + a k**2 x + b k**3 (mod p) has the same jinvariant than the curve C1. It is not difficult to show it, with this kind of curves, the jinvariant is equal to 1728 (4 a**3) / (4 a**3 + 27 b**2). So if we take k = J  1728, we immediately get a' = a * (J  1728)**2 = 3 J (J  1728) b' = b * (J  1728)**3 = 2 J (J  1728)**2 and then the curve C2 y**2 = x**3 + a'x + b' (mod p). C2 has the same jinvariant than C1 but we have no modular inverse to compute (computing a' and b' requires one square and one multiplication of big integers). Of course, C1 and C2 may have different cardinalities but since, here, most of the time we do not know (yet) whether the curve having the cardinality r*s is C1 or its twist, that we take C1 or C2... From now on, (a,b,p) is the curve C2. At this point we have a curve having J as jinvariant and p as modulus but not necessarily having the order r*s (the cardinality of (a,b,p) is either r*s or 2p+2r*s). Note that computing a curve and then computing a point is different from computing a curve and a point in *same* time. With the former, most of the time, we are compelled to compute a modular square root, with the latter we are not. We start with L = T**3 + a T + b (mod p) for the smallest T >= 0 such that L != 0. L being almost never a perfect square (otherwise (A,B,X,Y) = (a,b,T,sqrt(L)) would be ok), we have to transform the previous equality so that the lefthand side is a square whose root is known and so that we get a curve whose jinvariant is equal to the one of (a,b,p). Sometimes there are small miracles. Here, it is sufficient to multiply both sides by L**3 (mod p). (F. Morain was already using this trick 25 years ago. See "Elliptic Curves and Primality Proving", Β§8.6.3.) We get L**4 = T**3 L**3 + a T L**3 + b L**3, i.e., L**4 = (T L)**3 + a (T L) L**2 + b L**3. So, finally, we have (A,B,X,Y) = (a L**2, b L**3, T L, L**2). Now, if the order of (A,B,p) is not r*s, all we have to do is to increase T until the Jacobi symbol of the new L is the opposite of the previous one. Code:
// inputs: a,b,p,r,s (big integers) // return T (small integer) // (a,b,p) is a curve having J as jinvariant and p as modulus (p BPSWprime). // r*s is the wished order of the curve. r is a BPSWprime (much) bigger than s // (s is possibly composite). function GetT(a,b,p,r,s): small integer begin T = 1 js = 0 repeat repeat repeat repeat T = T + 1 L = (T**3 + a*T + b) mod p until L != 0 until (js == 0) or else (Jacobi(L,p) == js) X = T*L mod p Y = L*L mod p Z = 1 A = a*Y mod p //B = b*Y mod p // B is useless with most EC multiplication algorithms //B = B*L mod p (X,Y,Z) = (X,Y,Z)*s // on the curve (A,B,p) until (X,Y,Z) != IDENTITY (X,Y,Z) = (X,Y,Z)*r // on the curve (A,B,p) if (X,Y,Z) == IDENTITY return T if js != 0 return 1 // problem: r*s is not the order of (a,b,p) nor of its twist!? js = Jacobi(L,p) // so that the next curve has the order r*s until FALSE end I wish you good luck for your ECPP program but be ready to spend a lot of time. Last fiddled with by mjm on 20141022 at 09:26 

20141022, 14:33  #47  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Thank you very much! That's immensely helpful, and should let me efficiently make this type of certificates. I'm doing the standard way you mention at the beginning. It works well, but of course cannot be encoded in type 3 or 4, and makes larger certificates.
Let me reiterate that Primo is wonderful software and thank you for making it available. I use it myself. I know I'm very late to this, but I think this is useful software, it's open source, and I'm enjoying making it. Quote:


20141022, 18:43  #48 
I moo ablest echo power!
May 2013
1,741 Posts 

20150313, 17:56  #49 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13170_{8} Posts 
Trying to implement my own ecpp currently. I have a bug and can't find where. As such I am comparing my code with this program.
_ec_add_AB uses mpz_mod for the modulus while _ec_add_2A uses mpz_tdiv_r. Is there a particular reason for this? Have you found an online calculator that you can check the results of Elliptic Curve addition and multiplication? 
20150313, 18:21  #50  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001010_{2} Posts 
Quote:
Quote:


20150314, 20:24  #51 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}·719 Posts 
It seems that my elliptic curve multiplication is correct based on that link.
I seem to be missing something. I will step through the calculations showing the steps I am following. N=618970019642690137449562111 D=3 By the modified CornacchiaSmith algorithm 4N=u^2+abs(D)*v^2, u=48215832688019 and v=7097266064519. I take m=N+1+u = 618970019642738353282250131 m = 7*1609*1951*491539*57306024217633 57306024217633 > (n^1/4 + 1)^2 so q = 57306024217633 and k = 10801133529907 Next I select g: Jacobi(3,N)=1 N=1 (mod 3) and 3^((N1)/3)!=1 (mod N) so g=3 Since D=3 the possible (a,b) = (0,(g)^k) for k=0 to 5 I will start with a=0 and b=N1=618970019642690137449562110 The random x=237820880 satisfied Jacobi((x * x * x + a * x + b) % n,n)!=1 I calculated y = 581851259021954244271885071 P = (237820880,581851259021954244271885071) I then calculated U=kP = (512592549065013519526686029, 543465707103223282087870785) U != O. V=qU = (288909358890031734582251919, 423839432278858021463751209) At this point V should equal O according to C&P 7.6.3. However, it doesn't. I have tried all the possible (a,b) and selected multiple random x and I never get V=O. I can't see what I am doing wrong. Have I missed a step? 
20150320, 16:02  #52 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13170_{8} Posts 
I have found my bug. I have forgotten to modulo n when checking if y1+y2=0 in my curve addition.
Now to make it recursive and add more discriminants. 
20180131, 12:13  #53 
"Mike Bell"
Jan 2018
2 Posts 
Thanks danaj for making available a decent open source ECPP implementation!
I've been working on adding multithreading support, an early version based on the ecppdj1.04 code drop is available here: https://github.com/MichaelBell/ecppdj The approach I've taken is to run multiple curves in parallel during stage 1, and run proofs in parallel during stage 2. The certicificate ends up being written out of order, but the validation check doesn't mind this. Still to do:  Add in a decent task scheduler instead of a quick roll my own solution  Consider refactoring ecpp_down so it's not recursive, as that would fit better with a multithreading approach  Make the number of threads configurable (currently it's hardcoded in ecpp.cpp. 
20180202, 19:51  #54 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
906_{10} Posts 
Wow, that's great!
The standalone ecpp is generated from https://github.com/danaj/MathPrimeUtilGMP by running xt/createstandalone.sh. I recently added the ability to use Ramanujan class polynomials (from Konstantinou and Kontogeorgis 2006) which is a big space savings. Unfortunately I lack a method to generate the polynomials so it is a rather small win at the moment since I can only use the published results. For task scheduling, I've really thought there are some major changes that would help when we have to backtrack. Also it would be nice to generally refactor some of the code. Stage 2 parallelization is mostly straightforward I think, unless one wants to do it eagerly while stage 1 is still running. As you say, the certificate is out of order, but the verifier does the required proof for each step and then adds the "N is prime if Q is prime" relation to a table. The final step makes sure the table contains a complete chain from N down to a 64bit Q. It would also be a relatively simple matter to sort them after the fact. I didn't get to see the talk, but I would like to point out Jared Asuncion's slides here: http://guissmo.com/files/lfantseminar/ecpplong.pdf He added ECPP to Pari/GP last year, and it looks like he's made fantastic progress. I suspect the results for my code would be better with a bigger polynomial set, but that's impractical beyond some point. Pari/GP has some great code to generate them which makes that problem so much easier. But he's also doing some very clever math to solve some things I don't. Last fiddled with by danaj on 20180202 at 19:52 
20180203, 07:36  #55 
Bemusing Prompter
"Danny"
Dec 2002
California
11·211 Posts 
It's nice to see that ECPPDJ is still being developed. I hope it will eventually replace Primo as the de facto standard of ECPP software.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New ECPP record  mjm  Computer Science & Computational Number Theory  33  20200213 14:50 
ECPP on Windows?  CRGreathouse  Software  10  20150914 12:32 
Can I just leave this here? (ECPP)  trhabib  Miscellaneous Math  6  20110819 16:34 
Looking for ECPP software  nuggetprime  Software  14  20100307 17:09 
new ECPP article  R. Gerbicz  GMPECM  2  20060913 16:24 