EECM: ECM using Edwards curves

Performance of EECM-MPFQ

• bits: an integer b in {15,16,...,63}. EECM-MPFQ was run with a sample set of b-bit primes, i.e., primes between 2^(b-1) and 2^b.
• B_1, d_1, e, #{i}/#{j}: the parameters used for the EECM-MPFQ run.
• samples: the size of the sample set.
• Pr: the success probability, within the sample set, of the curve x^2+y^2=1-(24167/25)x^2y^2 with base point (5/23,-1/7) and torsion group Z/12Z.
• mults: the number of modular multiplications used for both stage 1 and stage 2. This is a worst-case number; primes found before the end of stage 2 will actually use fewer modular multiplications.
• ratio: mults / Pr; i.e., the number of modular multiplications per prime found.
• power: log(ratio)/sqrt(2*log(2^b)*log(log(2^b))).
• savings: the fraction of modular multiplications saved within the sample set by primes found before the end of stage 2.
• cycles: the number of cycles used for both stage 1 and stage 2 on a 3.2GHz AMD Phenom II X4 (100f42) for n between 192 bits and 256 bits, divided by Pr; i.e., the number of cycles per prime found.

Here is the table:

	Parameters				Effectiveness
bits	B_1	d_1	e	#{i}/#{j}	samples	Pr	mults	ratio	power	savings	cycles
15	16	60	1	1	1612	65.4467%	475	725.8	0.9440	6.0743%	398383
16	16	60	1	1	3030	50.5941%	475	938.8	0.9369	3.7812%	519846
17	27	60	1	1	5709	54.6856%	632	1155.7	0.9250	4.4719%	542882
18	27	90	1	1	10749	53.7073%	816	1519.3	0.9231	4.2088%	655581
19	37	90	1	1	20390	50.4708%	946	1874.4	0.9145	4.0127%	753288
20	37	90	1	1	38635	40.2329%	946	2351.3	0.9092	2.7869%	940225
21	37	90	1	1	73586	30.9787%	946	3053.7	0.9088	1.8815%	1229364
22	47	120	1	1	140336	33.0086%	1292	3914.1	0.9075	2.1786%	1413109
23	64	120	1	1	268216	30.3744%	1491	4908.7	0.9045	1.9515%	1682287
24	81	210	1	1	513708	36.7985%	2276	6185.0	0.9026	2.5365%	1971371
25	97	210	1	1	985818	31.7403%	2427	7646.4	0.8994	2.1164%	2390659
26	97	210	1	1	1048576	25.4204%	2427	9547.5	0.8976	1.5147%	2973591
27	131	210	1	1	1048576	24.4857%	2904	11860.0	0.8959	1.4755%	3528747
28	131	210	1	1	1048576	19.7381%	2904	14712.7	0.8944	1.0864%	4371407
29	149	210	1	1	1048576	16.5716%	3065	18495.5	0.8945	0.8797%	5363333
30	149	210	1	1	1048576	13.1368%	3065	23331.5	0.8953	0.6386%	6769323
31	263	210	1	2	1048576	18.4570%	5376	29127.1	0.8953	1.0937%	7834148
32	263	210	1	2	1048576	15.0913%	5376	35623.1	0.8938	0.8394%	9615434
33	263	210	1	2	1048576	12.1644%	5376	44194.5	0.8939	0.6248%	11915678
34	343	330	1	1	1048576	12.3212%	6787	55084.0	0.8945	0.6643%	14534927
35	389	420	1	1	1048576	12.3528%	8384	67871.0	0.8944	0.6747%	17488151
36	433	420	1	1	1048576	10.6944%	8892	83146.3	0.8941	0.5658%	21345174
37	521	420	1	1	1048576	9.7486%	9909	101644.8	0.8937	0.4983%	25652386
38	521	420	1	1	1048576	7.9452%	9909	124717.5	0.8939	0.3825%	31436961
39	587	420	1	1	1048576	6.8847%	10621	154270.3	0.8948	0.3185%	38319718
40	587	420	1	1	1048576	5.6551%	10621	187812.8	0.8946	0.2510%	47190133
41	937	630	1	1	1048576	7.8935%	18236	231026.5	0.8954	0.4196%	56113371
42	1031	630	1	1	1048576	6.9196%	19386	280161.7	0.8953	0.3544%	67437743
43	1031	630	1	1	1048576	5.7678%	19386	336106.1	0.8945	0.2840%	81087478
44	1031	630	1	1	1048576	4.6908%	19386	413273.7	0.8957	0.2201%	99684763
45	1151	630	1	1	1048576	4.1508%	20833	501906.6	0.8960	0.1901%	121979006
46	1319	630	1	1	1048576	3.7610%	22884	608454.3	0.8964	0.1619%	144341609
47	1709	840	1	1	1048576	4.3684%	32129	735486.6	0.8966	0.2170%	175028834
48	1889	840	1	1	1048576	3.8442%	34195	889529.8	0.8970	0.1785%	211435752
49	2221	840	1	1	1048576	3.5111%	37877	1078765.6	0.8977	0.1548%	251473421
50	2521	840	2	1	1048576	3.3565%	42981	1280546.8	0.8971	0.1686%	296542182
51	2521	840	2	1	1048576	2.7771%	42981	1547693.9	0.8977	0.1338%	360247031
52	2953	1050	1	1	1048576	2.8251%	52231	1848839.5	0.8977	0.1323%	437110078
53	3259	1050	2	1	1048576	2.5904%	57638	2225087.4	0.8982	0.1344%	512873213
54	3461	1050	2	1	1048576	2.2459%	59834	2664140.0	0.8985	0.1094%	611793212
55	4177	1260	2	1	1048576	2.3957%	75773	3162841.8	0.8983	0.1207%	725716426
56	4591	1260	2	1	1048576	2.1110%	80365	3807039.1	0.8991	0.1064%	871954529
57	5179	1260	2	1	1048576	1.9176%	87113	4542925.4	0.8994	0.0928%	1042971842
58	6037	1470	2	1	1048576	1.9300%	105181	5449931.9	0.9000	0.0931%	1240276698
59	6619	1470	2	1	1048576	1.7487%	112026	6406401.3	0.8996	0.0808%	1464353027
60	7039	1470	2	1	1048576	1.5140%	117156	7738391.8	0.9008	0.0675%	1770959606
61	7039	1470	2	1	1048576	1.2843%	117156	9122073.9	0.9006	0.0566%	2068996731
62	10099	2310	2	1	1048576	1.7102%	184177	10769173.1	0.9006	0.0874%	2465038140
63	10427	2310	2	1	1048576	1.4974%	187902	12548852.1	0.9000	0.0751%	2882767693

Version