Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 256
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
193 · 127 · 109 · 107 · 61 · 13 · 7 C 212· 318−1 309 M 7.624 111181
151 · 31 · 7 C 215−1 114 M 7.600 1411
227 · 73 · 67 · 17 C 221· 32+1 180 M 7.447 20121
167 · 149 · 5 C 29· 35−1 132 M 7.799 8151
251 · 43 · 41 C 214· 33+24· 32+1 151 M 8.051 122311
241 · 229 · 19 C 220+24−1 157 M 7.850 18211
211 · 139 · 13 · 11 C 222−28−1 171 M 7.773 20211
233 · 191 · 173 · 157 C 227· 32+218· 3−1 230 M 7.623 252211
223 · 137 · 103 · 83 · 37 C 230· 32+211−1 251 M 7.567 282211
179 · 101 · 97 · 47 · 29 · 23 · 5 C 238−23−1 283 M 7.447 36211
181 · 131 · 89 · 59 · 11 C 224· 34+217· 34−28−1 241 M 7.940 213421
239 · 199 · 197 · 163 · 113 · 79 · 71 · 53 E 246· 36+242+214+33 421 M 7.584 4335121
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
5 · 35 M 72 M 7.027 67
28 M 40 M 5.000 8
Total 2748 M 7.574 2562241110111147

acpb = arithmetic cost per bit