Home‎ > ‎GC1P8QN‎ > ‎

Factorizing with msieve.exe

Here'a a quite good factorization tool msieve.exe. The following instructions are for a DOS shell user. Window&rodent entusiastics sure know how to do it in a more modern way.

Usage

1) Execute msieve.exe (The name can also be "msieve142.exe" or something similar.)  with the number as argument.

2) A file msieve.log will be created in the same directory you did execute the msieve.exe. This log file will contain the solved prime factors of the given number.


Example 1:

c:\tmp>msieve 35

c:\tmp>type msieve.log
Sun Jun 07 11:14:03 2009
Sun Jun 07 11:14:03 2009
Sun Jun 07 11:14:03 2009  Msieve v. 1.41
Sun Jun 07 11:14:03 2009  random seeds: 6b621e54 f478feee
Sun Jun 07 11:14:03 2009  factoring 35 (2 digits)
Sun Jun 07 11:14:03 2009  p1 factor: 5
Sun Jun 07 11:14:03 2009  p1 factor: 7
Sun Jun 07 11:14:03 2009  elapsed time 00:00:00
c:\tmp>

Thus the prime factors of 35 are 5 and 7. In other words 35 = 5 x 7

Example 2 (This is the performance test example):

c:\tmp>msieve 5382000000735683358022919837657883000000078236999000000000000063

c:\tmp>type msieve.log
Sun Jun 07 11:46:55 2009
Sun Jun 07 11:46:55 2009
Sun Jun 07 11:46:55 2009  Msieve v. 1.41
Sun Jun 07 11:46:55 2009  random seeds: 70e08de8 ba685f00
Sun Jun 07 11:46:55 2009  factoring 53820000007356833580229198376578830000000782
36999000000000000063 (64 digits)
Sun Jun 07 11:46:55 2009  searching for 15-digit factors
Sun Jun 07 11:46:57 2009  commencing quadratic sieve (64-digit input)
Sun Jun 07 11:46:57 2009  using multiplier of 3
Sun Jun 07 11:46:57 2009  using 32kb Intel Core sieve core
Sun Jun 07 11:46:57 2009  sieve interval: 12 blocks of size 32768
Sun Jun 07 11:46:57 2009  processing polynomials in batches of 17
Sun Jun 07 11:46:57 2009  using a sieve bound of 114001 (5400 primes)
Sun Jun 07 11:46:57 2009  using large prime bound of 5700050 (22 bits)
Sun Jun 07 11:46:57 2009  using trial factoring cutoff of 22 bits
Sun Jun 07 11:46:57 2009  polynomial 'A' values have 8 factors
Sun Jun 07 11:47:21 2009  6053 relations (2763 full + 3290 combined from 26081 partial), need 5496
Sun Jun 07 11:47:21 2009  begin with 28844 relations
Sun Jun 07 11:47:21 2009  reduce to 8877 relations in 2 passes
Sun Jun 07 11:47:21 2009  attempting to read 8877 relations
Sun Jun 07 11:47:21 2009  recovered 8877 relations
Sun Jun 07 11:47:21 2009  recovered 6828 polynomials
Sun Jun 07 11:47:21 2009  attempting to build 6053 cycles
Sun Jun 07 11:47:21 2009  found 6053 cycles in 1 passes
Sun Jun 07 11:47:21 2009  distribution of cycle lengths:
Sun Jun 07 11:47:21 2009     length 1 : 2763
Sun Jun 07 11:47:21 2009     length 2 : 3290
Sun Jun 07 11:47:21 2009  largest cycle: 2 relations
Sun Jun 07 11:47:21 2009  matrix is 5400 x 6053 (0.7 MB) with weight 165072 (27.27/col)
Sun Jun 07 11:47:21 2009  sparse part has weight 165072 (27.27/col)
Sun Jun 07 11:47:21 2009  filtering completed in 4 passes
Sun Jun 07 11:47:21 2009  matrix is 4999 x 5063 (0.6 MB) with weight 131741 (26.02/col)
Sun Jun 07 11:47:21 2009  sparse part has weight 131741 (26.02/col)
Sun Jun 07 11:47:21 2009  commencing Lanczos iteration
Sun Jun 07 11:47:21 2009  memory use: 0.8 MB
Sun Jun 07 11:47:22 2009  lanczos halted after 81 iterations (dim = 4997)
Sun Jun 07 11:47:22 2009  recovered 64 nontrivial dependencies
Sun Jun 07 11:47:22 2009  prp32 factor: 69000000003314259000000000000007
Sun Jun 07 11:47:22 2009  prp32 factor: 78000000006915524000000000000009
Sun Jun 07 11:47:22 2009  elapsed time 00:00:27
c:\tmp>

The prime factors of 5382000000735683358022919837657883000000078236999000000000000063 are thus 69000000003314259000000000000007 and 78000000006915524000000000000009.
In other words 5382000000735683358022919837657883000000078236999000000000000063 = 69000000003314259000000000000007 x 78000000006915524000000000000009.
(By the way, ASCII code for E is 69 and ASCII code for N is 78.)
The elapsed time, 27 seconds, is a result of a desktop PC with Intel 2 GHz CPU running some other applications at the same time.


You can give the argument also by creating a file worktodo.ini containing one line
N=<n>
where <n> is the number to be factorized. For example
N=35
or
N=5382000000735683358022919837657883000000078236999000000000000063
or the ultimate
N=53830765614815296147077056056897689769993289313646389390585730478414476891677078524821470774994245604550003267

[Edited 2009-09-28. New link to msieve142.exe]
Comments