Number of seconds pari/gp's factorint function spends on other algorithms before trying MPQS for factoring numbers of various sizes (in bits). Most of that time is spent on the Elliptic Curve Method. Hardware and software info:
Intel(R) Core(TM)2 Duo CPU E8600 @ 3.33GHz
GP/PARI CALCULATOR Version 2.9.4 (released)
amd64 running linux (x86-64 kernel) 64-bit version
compiled: Jan 16 2018, gcc version 5.4.0 (Funtoo 5.4.0)
threading engine: single
for(n=95,151,p=precprime(2^n);q=precprime(p-1);T=gettime();factorint(p*q,9);print(2*n," ",(gettime()-T)/1e3))
| bits | seconds |
|---|---|
| 190 | 0.705 |
| 192 | 0.845 |
| 194 | 1.060 |
| 196 | 1.476 |
| 198 | 1.465 |
| 200 | 1.868 |
| 202 | 1.873 |
| 204 | 2.569 |
| 206 | 2.584 |
| 208 | 3.024 |
| 210 | 3.037 |
| 212 | 4.180 |
| 214 | 4.212 |
| 216 | 4.873 |
| 218 | 4.869 |
| 220 | 6.740 |
| 222 | 6.749 |
| 224 | 7.681 |
| 226 | 8.296 |
| 228 | 11.545 |
| 230 | 11.524 |
| 232 | 13.004 |
| 234 | 13.016 |
| 236 | 18.164 |
| 238 | 18.241 |
| 240 | 20.224 |
| 242 | 20.256 |
| 244 | 25.368 |
| 246 | 25.401 |
| 248 | 27.845 |
| 250 | 34.656 |
| 252 | 43.112 |
| 254 | 53.389 |
| 256 | 69.324 |
| 258 | 101.525 |
| 260 | 124.821 |
| 262 | 154.692 |
| 264 | 208.060 |
| 266 | 260.192 |
| 268 | 325.405 |
| 270 | 407.176 |
| 272 | 551.669 |
| 274 | 692.544 |
| 276 | 869.249 |
| 278 | 1094.428 |
| 280 | 1486.557 |
| 282 | 1875.436 |
| 284 | 2344.476 |
| 286 | 2948.697 |
| 288 | 3786.453 |
| 290 | 4642.560 |
| 292 | 5319.753 |
| 294 | 5968.460 |
| 296 | 6642.749 |
| 298 | 7310.425 |
| 300 | 8004.968 |
| 302 | 8700.257 |
One additional data point from a different computer and different software version: 299 bits (10^90-81), 5767.238 s.
No comments :
Post a Comment