Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 105
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
73 · 71 · 61 · 17 · 5 C 212· 38−1 189 M 7.658 11181
97 · 43 · 37 · 31 · 13 · 7 · 5 C 212· 312−1 237 M 7.640 111121
89 · 53 · 29 · 23 C 220· 3+29−1 169 M 7.829 182111
101 · 83 · 79 · 19 E 222· 3−25+3 185 M 7.844 202111
103 · 67 · 59 · 11 E 211· 37+24−35 180 M 8.147 926111
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
32 M 22 M 6.940 22
32 M 22 M 6.940 22
7 M 22 M 7.837 22
47 M 46 M 8.281 26
41 M 46 M 8.586 26
26 M 30 M 5.000 6
Total 1144 M 7.677 6982723411618

acpb = arithmetic cost per bit