Register FAQ Search Today's Posts Mark Forums Read  2014-10-22, 07:47   #45
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

242318 Posts Quote:
 Originally Posted by wombatman This is true. Maybe I'll set one up--it'd be good to learn about them. Do you have a recommendation for virtualization software? I've heard VirtualBox thrown around a good bit?
VirtualBox has worked well for me in the past.   2014-10-22, 09:21   #46
mjm

May 2012

23 Posts Quote:
 Originally Posted by danaj The problem I have generating certificates in Primo format is that Primo assumes the curves/points are of a specific form. ECPP (the algorithm) doesn't require them to be that type, but that is what Primo uses and encodes. My way of generating the curves/points follows the method described in most papers, which don't make values of that form, hence cannot be represented in his format.
In all that follows, we are in the context of ECPP, using the so-called complex multiplication to find the order of a curve, and the j-invariants J are different from 0 and from 1728.

In order to compute a curve with a known j-invariant 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 j-invariant than the curve C1. It is not difficult to show it, with this kind of curves, the j-invariant 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 j-invariant 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 j-invariant and p as modulus but not necessarily having the order r*s (the cardinality of (a,b,p) is either r*s or 2p+2-r*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 left-hand side is a square whose root is known and so that we get a curve whose j-invariant 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 j-invariant and p as modulus (p BPSW-prime).
// r*s is the wished order of the curve. r is a BPSW-prime (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
This way of doing was the best I found (13 years ago) in order to get smaller certificates for Primo while not increasing the running times of verifications (the running time of the re-computation of (A,B,X,Y) from (J,T) is insignificant -- no modular inverse, no modular square root -- compared to the running time of the EC multiplications).

I wish you good luck for your ECPP program but be ready to spend a lot of time.

Last fiddled with by mjm on 2014-10-22 at 09:26   2014-10-22, 14:33   #47
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts Quote:
 Originally Posted by mjm ...lots of great stuff...
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:
 This way of doing was the best I found (13 years ago) in order to get smaller certificates for Primo while not increasing the running times of verifications (the running time of the re-computation of (A,B,X,Y) from (J,T) is insignificant -- no modular inverse, no modular square root -- compared to the running time of the EC multiplications).
Indeed, constructing (A,B,X,Y) from (J,T) is easy and negligible in time.   2014-10-22, 18:43   #48
wombatman
I moo ablest echo power!

May 2013

1,741 Posts Quote:
 Originally Posted by xilman VirtualBox has worked well for me in the past.
Excellent.

Quote:
 Originally Posted by danaj Thank you very much! That's immensely helpful, and should let me efficiently make this type of certificates.
Woohoo!    2015-03-13, 17:56 #49 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 131708 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?   2015-03-13, 18:21   #50
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts Quote:
 Originally Posted by henryzz 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?
No. Typically I use mpz_tdiv_r because it gives better performance.

Quote:
 Have you found an online calculator that you can check the results of Elliptic Curve addition and multiplication?
That's a nice idea -- no I haven't. A simple google search shows this one but I haven't used it or checked that it would even handle this case. Perhaps hack something up using GMP-ECM? One problematic thing would be the representation -- there are a lot of different forms.   2015-03-14, 20:24 #51 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 23·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 Cornacchia-Smith 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^((N-1)/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=N-1=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?   2015-03-20, 16:02 #52 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 131708 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.   2018-01-31, 12:13 #53 mikeb   "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 ecpp-dj-1.04 code drop is available here: https://github.com/MichaelBell/ecpp-dj 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.   2018-02-02, 19:51 #54 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 90610 Posts Wow, that's great! The standalone ecpp is generated from https://github.com/danaj/Math-Prime-Util-GMP by running xt/create-standalone.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 64-bit 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 2018-02-02 at 19:52   2018-02-03, 07:36 #55 ixfd64 Bemusing Prompter   "Danny" Dec 2002 California 11·211 Posts It's nice to see that ECPP-DJ is still being developed. I hope it will eventually replace Primo as the de facto standard of ECPP software.    Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50 CRGreathouse Software 10 2015-09-14 12:32 trhabib Miscellaneous Math 6 2011-08-19 16:34 nuggetprime Software 14 2010-03-07 17:09 R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 02:04.

Wed Dec 2 02:04:12 UTC 2020 up 82 days, 23:15, 1 user, load averages: 1.28, 1.33, 1.43