mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-10-22, 07:47   #45
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

242318 Posts
Default

Quote:
Originally Posted by wombatman View Post
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.
xilman is offline   Reply With Quote
Old 2014-10-22, 09:21   #46
mjm
 
May 2012

23 Posts
Default

Quote:
Originally Posted by danaj View Post
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
mjm is offline   Reply With Quote
Old 2014-10-22, 14:33   #47
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by mjm View Post
...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.
danaj is offline   Reply With Quote
Old 2014-10-22, 18:43   #48
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

1,741 Posts
Default

Quote:
Originally Posted by xilman View Post
VirtualBox has worked well for me in the past.
Excellent.

Quote:
Originally Posted by danaj View Post
Thank you very much! That's immensely helpful, and should let me efficiently make this type of certificates.
Woohoo!
wombatman is offline   Reply With Quote
Old 2015-03-13, 17:56   #49
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131708 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2015-03-13, 18:21   #50
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
danaj is offline   Reply With Quote
Old 2015-03-14, 20:24   #51
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

23·719 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2015-03-20, 16:02   #52
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131708 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2018-01-31, 12:13   #53
mikeb
 
"Mike Bell"
Jan 2018

2 Posts
Default

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.
mikeb is offline   Reply With Quote
Old 2018-02-02, 19:51   #54
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90610 Posts
Default

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
danaj is offline   Reply With Quote
Old 2018-02-03, 07:36   #55
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11·211 Posts
Default

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.
ixfd64 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New ECPP record mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50
ECPP on Windows? CRGreathouse Software 10 2015-09-14 12:32
Can I just leave this here? (ECPP) trhabib Miscellaneous Math 6 2011-08-19 16:34
Looking for ECPP software nuggetprime Software 14 2010-03-07 17:09
new ECPP article 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.