| Thomas Papanikolaou on Fri, 12 Jun 1998 11:05:22 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| New Factoring Method in PARI |
Dear All,
we are happy to announce our implementation of the Self-Initializing
Multipolynomial Quadratic Sieve (SIMPQS) in PARI. Before anything else
here are some timings on a P6-200
-----------------------------------------------------------------------------
N: 1000000000000000000390900000000000000000351 (43 decimals)
Factors: [100000000000000000039, 10000000000000000000009]
Total time for MPQS = 10.020000 seconds
-----------------------------------------------------------------------------
N: 100000000000000000039000000005700000000000000002223 (51 decimals)
Factors: [100000000000000000039, 1000000000000000000000000000057]
Total time for MPQS = 26.370000 seconds
-----------------------------------------------------------------------------
On an Ultra 1 we have also factored 75 decimals in about 5 hours of user time
(the real time is probably above than this because of the file operations
that have to be done).
The code is in principle a rewrite of the function existing in the LiDIA
package. We reorganized many parts and written other parts from the scratch.
However, because of this, the copyright of the code is more restrictive than
the one for PARI. You are allowed to use it only for non-commercial, educational
purposes. Commercial licenses are available from papanik@math.u-bordeaux.fr
1)
Xavier has already made a module for PARI, which is also sent to Karim.
This provides a combination of the currently available factoring methods
in PARI (Trial Division, ECM and MPQS) into a more generic factor function.
The combined function is faster than what existed in PARI for numbers having
more the 15 decimals. According to our tests it gains a factor of 7 over
the old version already at 29 decimals.
If you are also happy about these news, don't hesitate to send us donations!
We accept FF, $ or DM and wine bottles :-)
Best
Thomas Papanikolaou & Xavier Roblot
1) Remark from Thomas Papanikolaou:
The difference between the original package and the PARI module, is that
the original code is divided into many small files :-) whereas the module
is one BIG file :-) But anyway, this is the reason why we like PARI, isn't
it? :-)
PS Here some more information on timing (in French)
------------------------------------------------------------------------------
Temps necessaire pour factoriser N = p*q (temps moyen sur 100 nombres en ms).
Nbr chiffres de N E.C.M M.P.Q.S. Rapport
15 734 191 4
16 790 245 3
17 1210 213 6
18 1849 224 8
19 3008 253 12
20 3989 289 14
21 6904 326 21
22 8320 390 21
23 11314 448 25
24 13627 567 24
25 25810 700 37
26 27777 749 37
27 49153 906 54
28 58065 1115 52
29 105527 1324 80
------------------------------------------------------------------------------
Temps necessaire pour factoriser N = p*q*r (temps moyen sur 100 nombres en ms).
Nbr chiffres de N E.C.M M.P.Q.S. Rapport
15 130 158 1
16 108 159 1
17 327 146 2
18 281 157 2
19 350 147 2
20 526 149 4
21 625 189 3
22 554 189 3
23 1001 210 5
24 964 221 4
25 1136 219 5
26 1802 252 7
27 2434 297 8
28 2819 306 9
29 4613 376 12
------------------------------------------------------------------------------
Temps necessaire pour factoriser N aleatoire (temps moyen sur 1000 nombres en ms).
Nbr chiffres de N E.C.M E.C.M. + M.P.Q.S. Rapport
15 138 122 1
16 167 127 1
17 205 142 1
18 259 158 2
19 271 170 2
20 489 197 2
21 536 205 3
22 697 236 3
23 765 255 3
24 1179 302 4
25 1711 334 5
26 2261 394 6
27 2543 441 6
28 3284 507 6
29 4413 596 7
------------------------------------------------------------------------------