New feature in my ECM applet - Page 2

alpertron · 2009-02-04, 23:05

I found that for many factorizations the linear algebra step is retried several times. After some investigation I found that the applet only gets 1 or 2 non-trivial dependencies for all factorizations, instead of a number near 32. The applet now shows the number of non-trivial dependencies found.

I will try to find the error in the Block Lanczos routine.

alpertron · 2009-02-08, 01:33

Yesterday I uploaded a new version which performs the factorization of 10^59+213 in 24 seconds (9 seconds for mprime) and the factorization of 10^71-1 in 4m22s (1m09s for mprime) in the Core 2 Duo 1.86 based PC.

I also fixed some errors in the Block Lanczos routine, so now it finds more non-trivial dependencies. I think there are more errors in the implementation because of the low number of non-trivial dependencies found. But now I have not seen more instances of matrix not solved.

10metreh · 2009-02-08, 07:57

Quote:

Originally Posted by alpertron

Yesterday I uploaded a new version which performs the factorization of 10^59+213 in 24 seconds (9 seconds for mprime) and the factorization of 10^71-1 in 4m22s (1m09s for mprime) in the Core 2 Duo 1.86 based PC.

I also fixed some errors in the Block Lanczos routine, so now it finds more non-trivial dependencies. I think there are more errors in the implementation because of the low number of non-trivial dependencies found. But now I have not seen more instances of matrix not solved.

Do you mean msieve rather than mprime?

henryzz · 2009-02-08, 09:20

Quote:

Originally Posted by alpertron

Yesterday I uploaded a new version which performs the factorization of 10^59+213 in 24 seconds (9 seconds for mprime) and the factorization of 10^71-1 in 4m22s (1m09s for mprime) in the Core 2 Duo 1.86 based PC.

I also fixed some errors in the Block Lanczos routine, so now it finds more non-trivial dependencies. I think there are more errors in the implementation because of the low number of non-trivial dependencies found. But now I have not seen more instances of matrix not solved.

those timings are slower than your previous timings

alpertron · 2009-02-08, 11:59

10metreh is right. It is msieve. The timing I wrote above includes both ECM & SIQS time, so you will need to compare it to the Total column in my previous post.

henryzz · 2009-02-08, 18:11

Quote:

Originally Posted by alpertron

10metreh is right. It is msieve. The timing I wrote above includes both ECM & SIQS time, so you will need to compare it to the Total column in my previous post.

impressive then
KUTGW

alpertron · 2009-03-06, 10:57

I was able to optimize the code related to the trial division stage on the SIQS algorithm and now the timings are better. I also added on the lower pane the timings for each step of the factorization: primality testing, ECM, SIQS. This was suggested to me by Jeff Gilchrist.

Code:

           Primality testing       ECM           SIQS            Total
10^59+213       0.0 sec          2.3 sec       18.8 sec          21 sec
10^71-1         0.0 sec         52.6 sec    3 min 2.4 sec     3 min 55 sec

Jeff Gilchrist · 2009-03-06, 18:26

Quote:

Originally Posted by alpertron

I was able to optimize the code related to the trial division stage on the SIQS algorithm and now the timings are better. I also added on the lower pane the timings for each step of the factorization: primality testing, ECM, SIQS. This was suggested to me by Jeff Gilchrist

Ooo thanks, that will be handy. You also fixed a bug or two in the code that caused some (rare?) SIQS factorizations to fail so good job on that too!

Jeff.

alpertron · 2009-03-14, 12:22

There were some people who contacted me saying that the SIQS algorithm did not work for large numbers (90-digit composites and larger). I found that the problem disappeared after adding the code for eliminating singletons.

For example the 90-digit cofactor of 10^99+279 took 2h54m in order to be factored in my new Core 2 Quad Q9300 2.5 GHz.

Jeff Gilchrist · 2009-03-17, 14:08

Here are some updated benchmarks with the new release of the Java applet.

Code:

Intel Core2 Q9550 @ 3.4GHz (Vista 64bit)

SIQS (C85 = 1877138824359859508015524119652506869600959721781289179190693027302028679377371001561)
==================================================================================================
YAFU 1.07 64bit MSVC 32k     =  9m 30.405
YAFU 1.06 64bit MSVC         =  9m 40.275s
YAFU 1.07 64bit MSVC 64k     = 10m 32.239s
YAFU 1.07 32bit gcc-k8 32k   = 11m 29.671s
YAFU 1.07 32bit gcc 32k      = 11m 49.886s
YAFU 1.06 32bit gcc-k8       = 12m 19.639s
YAFU 1.07 32bit MSVC 32k     = 12m 34.496s
YAFU 1.06 32bit gcc          = 12m 37.120s
YAFU 1.07 32bit MSVC 64k     = 12m 38.842s
YAFU 1.07 32bit gcc-k8 64k   = 12m 48.736s
YAFU 1.07 32bit gcc 64k      = 12m 49.081s
YAFU 1.06 32bit MSVC         = 13m 09.457s
MSIEVE 1.40 32bit MSVC       = 14m 00.927s
YAFU 1.05 32bit MSVC         = 14m 07.829s
MSIEVE 1.40 32bit gcc        = 14m 59.053s
MSIEVE 1.39 32bit gcc        = 17m 13.576s
MSIEVE 1.39 64bit MSVC       = 19m 44.561s
MSIEVE 1.40 64bit MSVC       = 20m 03.693s
ALPERTRON 3/16/09 64bit Java = 35m 47.000s
ALPERTRON 3/16/09 32bit Java = 37m 52.900s
ALPERTRON 64bit Java         = 38m 54.000s
ALPERTRON 32bit Java         = 42m 54.000s


SIQS (C80 = 43756152090407155008788902702412144383525640641502974083054213255054353547943661)
=============================================================================================
YAFU 1.07 64bit MSVC 32k     =  3m 57.338s
YAFU 1.06 64bit MSVC         =  4m 02.683s
YAFU 1.07 64bit MSVC 64k     =  4m 20.777s
MSIEVE 1.40 32bit MSVC       =  4m 31.999s
YAFU 1.07 32bit gcc-k8 32k   =  4m 41.216s
YAFU 1.07 32bit gcc 32k      =  4m 49.585s
MSIEVE 1.40 32bit gcc        =  4m 56.035s
YAFU 1.06 32bit gcc-k8       =  4m 57.278s
YAFU 1.06 32bit gcc          =  5m 06.302s
YAFU 1.07 32bit MSVC 32k     =  5m 06.776s
YAFU 1.07 32bit MSVC 64k     =  5m 08.800s
YAFU 1.07 32bit gcc 64k      =  5m 11.860s
YAFU 1.07 32bit gcc-k8 64k   =  5m 12.650s
YAFU 1.06 32bit MSVC         =  5m 29.903s
YAFU 1.05 32bit MSVC         =  5m 32.054s
MSIEVE 1.39 32bit gcc        =  5m 32.956s
MSIEVE 1.39 64bit MSVC       =  6m 08.020s
MSIEVE 1.40 64bit MSVC       =  6m 11.059s
ALPERTRON 3/16/09 64bit Java = 16m 45.100s
ALPERTRON 3/16/09 32bit Java = 17m 21.600s
ALPERTRON 64bit Java         = 18m 54.000s
ALPERTRON 32bit Java       =   18m 55.000s


SIQS (C75 = 281396163585532137380297959872159569353696836686080935550459706878100362721)
========================================================================================
YAFU 1.07 64bit MSVC 32k     =  1m 35.525s
YAFU 1.06 64bit MSVC         =  1m 36.408s
YAFU 1.07 64bit MSVC 64k     =  1m 45.305s
MSIEVE 1.40 32bit MSVC       =  1m 45.507s
YAFU 1.07 32bit gcc-k8 32k   =  1m 51.000s
MSIEVE 1.39 32bit MSVC       =  1m 52.508s
MSIEVE 1.40 32bit gcc        =  1m 53.237s
YAFU 1.07 32bit gcc 32k      =  1m 55.265s
YAFU 1.06 32bit gcc-k8       =  2m 00.339s
YAFU 1.07 32bit MSVC 32k     =  2m 00.955s
YAFU 1.07 32bit MSVC 64k     =  2m 01.645s
MSIEVE 1.39 32bit gcc        =  2m 02.585s
YAFU 1.06 32bit gcc          =  2m 02.787s
YAFU 1.07 32bit gcc 64k      =  2m 04.011s
YAFU 1.07 32bit gcc-k8 64k   =  2m 04.610s
YAFU 1.06 32bit MSVC         =  2m 09.434s
YAFU 1.05 32bit MSVC         =  2m 13.849s
MSIEVE 1.40 64bit MSVC       =  2m 18.664s
MSIEVE 1.39 64bit MSVC       =  2m 20.431s
ALPERTRON 3/16/09 64bit Java =  4m 30.200s
ALPERTRON 3/16/09 32bit Java =  4m 42.200s
ALPERTRON 64bit Java         =  5m 08.000s
ALPERTRON 32bit Java         =  5m 08.000s


SIQS (C65 = 34053408309992030649212497354061832056920539397279047809781589871)
==============================================================================
YAFU 1.07 64bit MSVC 32k     =  0m 12.040s
YAFU 1.06 64bit MSVC         =  0m 12.355s
YAFU 1.07 64bit MSVC 64k     =  0m 12.780s
YAFU 1.07 32bit gcc-k8 32k   =  0m 13.440s
YAFU 1.07 32bit gcc 32k      =  0m 13.965s
YAFU 1.07 32bit MSVC 32k     =  0m 14.125s
YAFU 1.07 32bit MSVC 64k     =  0m 14.165s
YAFU 1.07 32bit gcc-k8 64k   =  0m 15.020s
YAFU 1.07 32bit gcc 64k      =  0m 15.435s
YAFU 1.06 32bit gcc-k8       =  0m 15.568s
YAFU 1.06 32bit gcc          =  0m 15.631s
YAFU 1.06 32bit MSVC         =  0m 15.662s
YAFU 1.05 32bit MSVC         =  0m 16.817s
MSIEVE 1.39 64bit MSVC       =  0m 15.522s
MSIEVE 1.40 64bit MSVC       =  0m 15.978s
MSIEVE 1.39 32bit MSVC       =  0m 14.242s
MSIEVE 1.40 32bit MSVC       =  0m 14.423s
MSIEVE 1.39 32bit gcc        =  0m 15.023s
MSIEVE 1.40 32bit gcc        =  0m 15.244s
ALPERTRON 3/16/09 64bit Java =  0m 49.800s
ALPERTRON 64bit Java         =  0m 52.000s
ALPERTRON 3/16/09 32bit Java =  0m 54.100s
ALPERTRON 32bit Java         =  0m 56.000s

alpertron · 2009-03-17, 14:47

Thanks, Jeff.

2009-03-06, 10:57	#18
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	I was able to optimize the code related to the trial division stage on the SIQS algorithm and now the timings are better. I also added on the lower pane the timings for each step of the factorization: primality testing, ECM, SIQS. This was suggested to me by Jeff Gilchrist. Code: Primality testing ECM SIQS Total 10^59+213 0.0 sec 2.3 sec 18.8 sec 21 sec 10^71-1 0.0 sec 52.6 sec 3 min 2.4 sec 3 min 55 sec

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Java applet alternative	a1call	Programming	19	2019-11-08 22:31
New online applet for factorization	ET_	Lone Mersenne Hunters	69	2014-06-01 17:34
A strange applet:	3.14159	Miscellaneous Math	7	2010-06-01 01:29
Faster factorization applet	alpertron	Factoring	14	2006-01-01 04:00
Binomial Expansion Applet	jinydu	Lounge	2	2004-05-05 08:33

2009-02-04, 23:05	#12
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	I found that for many factorizations the linear algebra step is retried several times. After some investigation I found that the applet only gets 1 or 2 non-trivial dependencies for all factorizations, instead of a number near 32. The applet now shows the number of non-trivial dependencies found. I will try to find the error in the Block Lanczos routine.

2009-02-08, 01:33	#13
alpertron Aug 2002 Buenos Aires, Argentina 10111110011₂ Posts	Yesterday I uploaded a new version which performs the factorization of 10^59+213 in 24 seconds (9 seconds for mprime) and the factorization of 10^71-1 in 4m22s (1m09s for mprime) in the Core 2 Duo 1.86 based PC. I also fixed some errors in the Block Lanczos routine, so now it finds more non-trivial dependencies. I think there are more errors in the implementation because of the low number of non-trivial dependencies found. But now I have not seen more instances of matrix not solved.

2009-02-08, 11:59	#16
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	10metreh is right. It is msieve. The timing I wrote above includes both ECM & SIQS time, so you will need to compare it to the Total column in my previous post.

2009-03-14, 12:22	#20
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	There were some people who contacted me saying that the SIQS algorithm did not work for large numbers (90-digit composites and larger). I found that the problem disappeared after adding the code for eliminating singletons. For example the 90-digit cofactor of 10^99+279 took 2h54m in order to be factored in my new Core 2 Quad Q9300 2.5 GHz.

2009-03-17, 14:47	#22
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	Thanks, Jeff.