search

TilmanNeumann / java-math-library

A Java math library focused on number theory and integer factorization in particular.
GNU General Public License v3.0
30 stars 7 forks source link

SIQS 2 times faster below 230 bits #22

Closed Pascal66 closed 5 years ago

Pascal66 commented 5 years ago

I dont know exactly the limit between 222 and 256 for now. Can you test it ? (Changing 3 lines in AParamGenerator01

Pascal66 commented 5 years ago

Before

0 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  - PSIQS(Cmult=0.32, Mmult=0.36, qCount=9, maxQRestExponent=0,174, noPowers, solver01_Gauss, 5 threads):
6 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  - Found factor 6896370919978056092984543633033 (103 bits) of N=5450273780896470537172691284382862523169832968962275136650623899499 in 21s, 812ms
6 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     multiplier k = 35, kN%8 = 1, primeBaseSize = 7337, pMax = 161731 (18 bits), sieveArraySize = 28416
6 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     polyGenerator: #a-parameters = 402, #processed polynomials = 102141
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     tDiv: tested 125161 congruence candidates and let 88021 (70.33%) pass
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     cc: found 7347 smooth congruences (4058 perfect, 3118 from 1-partials, 171 involving 2-partials) and 80485 partials (79461 1-partials, 1024 2-partials)
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     #solverRuns = 1, #tested null vectors = 141
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     Approximate phase timings: powerTest=4ms, initN=81ms, createThreads=223ms, initPoly=2861ms, sieve=10466ms, tdiv=2280ms, cc=1305ms, solver=5565ms
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> initPoly sub-timings: a-param=15ms, first b-param=7ms, filter prime base=34ms, first x-arrays=1435ms, next b-params=20ms, next x-arrays=1349ms
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> sieve sub-timings: init=212ms, sieve=8592ms, collect=1661ms
10 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> tdiv sub-timings: AQ=82ms, pass1=1511ms, pass2=312ms, primeTest=327ms, factor=46ms
34 [Thread-0] INFO de.tilman_neumann.jml.factor.base.UnsafeUtil  - All native memory has been released.

After

0 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  - PSIQS(Cmult=0.32, Mmult=0.36, qCount=9, maxQRestExponent=0,174, noPowers, solver01_Gauss, 5 threads):
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  - Found factor 1049 (11 bits) of N=5450273780896470537172691284382862523169832968962275136650623899499 in 6s, 877ms
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     multiplier k = 35, kN%8 = 1, primeBaseSize = 7337, pMax = 161731 (18 bits), sieveArraySize = 28416
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     polyGenerator: #a-parameters = 102, #processed polynomials = 25553
7 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     tDiv: tested 30946 congruence candidates and let 21510 (69.51%) pass
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     cc: found 1159 smooth congruences (976 perfect, 181 from 1-partials, 2 involving 2-partials) and 20285 partials (19994 1-partials, 291 2-partials)
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     #solverRuns = 0, #tested null vectors = 0
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     Approximate phase timings: powerTest=13ms, initN=214ms, createThreads=470ms, initPoly=854ms, sieve=4562ms, tdiv=768ms, cc=871ms, solver=1ms
8 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> initPoly sub-timings: a-param=7ms, first b-param=2ms, filter prime base=19ms, first x-arrays=399ms, next b-params=8ms, next x-arrays=418ms
9 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> sieve sub-timings: init=66ms, sieve=3768ms, collect=727ms
9 [main] INFO de.tilman_neumann.jml.factor.psiqs.PSIQSBase  -     -> tdiv sub-timings: AQ=70ms, pass1=456ms, pass2=87ms, primeTest=128ms, factor=26ms
28 [Thread-0] INFO de.tilman_neumann.jml.factor.base.UnsafeUtil  - All native memory has been released.
TilmanNeumann commented 5 years ago

As I understand, you tested a number with a very small factor. PSIQS.findSingleFactor() is supposed to be used for difficult numbers; if you use it for inputs with small factors, funny things may happen.

CombinedFactorAlgorithm.findSingleFactor() or PSIQS.factor() should behave in a better way.