Yafu

[LaurV]

I am targeting the billion digit... why do you expect me to start with a c70?

Joking apart, this is not really "a start". I have already reported few hundreds factorizations (70-100 digits) to factordb in the last weeks since I started playing with yafu/msieve, and there is always a time to grow bigger, to see what the tools can do. If I wouldn't try the C185 then I would never find the problems, and I wouldn't know what to expect when the time would come to hunt that billion digit prime...

I used to play with numbers. I mean I graduated a prestigious math university, but number theory was never my strong point, and before joining GIMPS there was no interest in that. Everyone of us try to specialize on something.

Also, I played with P95 since the beginning and there was a time when I had over 40 computers in the project. Most of them were "abandoned" after the 12M prime came out. The fun remained, but the motivation (glory, maybe some money) disappeared. Or at least, there wasn't any more enough motivation to make me run around the building to maintain all the wheels turning. I just kept the stuff around me, which is somehow more accessible.

Factoring came again to my attention few weeks/months ago, related to some of my daily projects. That time I "discovered" factoring programs, tested few of them, had a long look into yafu's sources, did not understand anything... sky is blue, life goes on....

I already knew by heart the theory behind of mersenne and fermat numbers (mainly from GIMPS-related activities/web pages), but never put my nose too deep into factoring algorithms. There is always a start time for everything.

[schickel]

Originally Posted by LaurV

I am targeting the billion digit... why do you expect me to start with a c70?

Joking apart, this is not really "a start". I have already reported few hundreds factorizations (70-100 digits) to factordb in the last weeks since I started playing with yafu/msieve, and there is always a time to grow bigger, to see what the tools can do. If I wouldn't try the C185 then I would never find the problems, and I wouldn't know what to expect when the time would come to hunt that billion digit prime...

I just meant most of us start out with smaller jobs to get our feet wet before tackling something as big as your c185.

If something happens while you're doing a 3-4 day job and you have to start over, it hurts a whole lot less that if you're anticipating 1500 hrs and something happens 3/4 of the way through and you don't know how to recover.....just ask around here about stuff like that!

Anyway, I'm not trying to discourage you.....just be aware of the magnitude of the task you're taking on. Good luck!

PS. My biggest mistake was having a job finish, wiping the work directory clean, and starting a new job. When I went to proceed with the factors, I found out, OH NO, I forgot to copy the results off before the directory wipe. Luckily, there was a lot of intermediate stuff that got deleted so I was able to run a recovery tool and find the summary to get my factors.....

[yoyo]

Hello,

I run yafu factor(number). In the first step yafu runs rho, pp1, ecm until it starts with siqs. Siqs saves the progress in siqs.dat.
Than I restarted the computer and restarted yafu.
But now yafu starts from the beginning.
Can yafu be improved, if the siqs.dat exists for this number to continue the siqs part and not start from the beginning?
I think this is the case if I use siqs(number).
Here the complete log.

09/05/11 04:00:22 v1.28.4 @ STM11647, 
09/05/11 04:00:22 v1.28.4 @ STM11647, ****************************
09/05/11 04:00:22 v1.28.4 @ STM11647, Starting factorization of 41285311719805955987870990403314964284156777185282115706759112499904162203091021318556917829
09/05/11 04:00:22 v1.28.4 @ STM11647, ****************************
09/05/11 04:00:22 v1.28.4 @ STM11647, rho: x^2 + 1, starting 1000 iterations on C92
09/05/11 04:00:22 v1.28.4 @ STM11647, rho: x^2 + 3, starting 1000 iterations on C92
09/05/11 04:00:22 v1.28.4 @ STM11647, rho: x^2 + 2, starting 1000 iterations on C92
09/05/11 04:00:22 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 04:00:22 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 04:00:22 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 04:00:23 v1.28.4 @ STM11647, pm1: starting B1 = 100K, B2 = gmp-ecm default on C92
09/05/11 04:00:24 v1.28.4 @ STM11647, Finished 25 curves using Lenstra ECM method on C92 input, B1 = 2K, B2 = gmp-ecm default
09/05/11 04:00:50 v1.28.4 @ STM11647, Finished 90 curves using Lenstra ECM method on C92 input, B1 = 11K, B2 = gmp-ecm default
09/05/11 04:04:38 v1.28.4 @ STM11647, Finished 200 curves using Lenstra ECM method on C92 input, B1 = 50K, B2 = gmp-ecm default
09/05/11 04:04:38 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 04:04:44 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 04:04:49 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 04:04:54 v1.28.4 @ STM11647, pm1: starting B1 = 2500K, B2 = gmp-ecm default on C92
09/05/11 04:16:11 v1.28.4 @ STM11647, Finished 139 curves using Lenstra ECM method on C92 input, B1 = 250K, B2 = gmp-ecm default
09/05/11 04:16:12 v1.28.4 @ STM11647, pp1: starting B1 = 5M, B2 = gmp-ecm default on C92
09/05/11 04:16:31 v1.28.4 @ STM11647, pp1: starting B1 = 5M, B2 = gmp-ecm default on C92
09/05/11 04:16:50 v1.28.4 @ STM11647, pm1: starting B1 = 10M, B2 = gmp-ecm default on C92
09/05/11 04:18:20 v1.28.4 @ STM11647, Finished 1 curves using Lenstra ECM method on C92 input, B1 = 1M, B2 = gmp-ecm default
09/05/11 04:21:12 v1.28.4 @ STM11647, Finished 1 curves using Lenstra ECM method on C92 input, B1 = 10M, B2 = gmp-ecm default
09/05/11 04:21:13 v1.28.4 @ STM11647, starting SIQS on c92: 41285311719805955987870990403314964284156777185282115706759112499904162203091021318556917829
09/05/11 04:21:13 v1.28.4 @ STM11647, random seeds: 1771520841, 3295213941
09/05/11 07:20:05 v1.28.4 @ STM11647, 
09/05/11 07:20:05 v1.28.4 @ STM11647, ****************************
09/05/11 07:20:05 v1.28.4 @ STM11647, Starting factorization of 41285311719805955987870990403314964284156777185282115706759112499904162203091021318556917829
09/05/11 07:20:05 v1.28.4 @ STM11647, ****************************
09/05/11 07:20:05 v1.28.4 @ STM11647, rho: x^2 + 1, starting 1000 iterations on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, rho: x^2 + 3, starting 1000 iterations on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, rho: x^2 + 2, starting 1000 iterations on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, pp1: starting B1 = 20K, B2 = gmp-ecm default on C92
09/05/11 07:20:05 v1.28.4 @ STM11647, pm1: starting B1 = 100K, B2 = gmp-ecm default on C92
09/05/11 07:20:07 v1.28.4 @ STM11647, Finished 25 curves using Lenstra ECM method on C92 input, B1 = 2K, B2 = gmp-ecm default
09/05/11 07:20:29 v1.28.4 @ STM11647, Finished 90 curves using Lenstra ECM method on C92 input, B1 = 11K, B2 = gmp-ecm default
09/05/11 07:24:00 v1.28.4 @ STM11647, Finished 200 curves using Lenstra ECM method on C92 input, B1 = 50K, B2 = gmp-ecm default
09/05/11 07:24:00 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 07:24:05 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 07:24:09 v1.28.4 @ STM11647, pp1: starting B1 = 1250K, B2 = gmp-ecm default on C92
09/05/11 07:24:14 v1.28.4 @ STM11647, pm1: starting B1 = 2500K, B2 = gmp-ecm default on C92
09/05/11 07:33:59 v1.28.4 @ STM11647, Finished 138 curves using Lenstra ECM method on C92 input, B1 = 250K, B2 = gmp-ecm default
09/05/11 07:33:59 v1.28.4 @ STM11647, pp1: starting B1 = 5M, B2 = gmp-ecm default on C92
09/05/11 07:34:15 v1.28.4 @ STM11647, pp1: starting B1 = 5M, B2 = gmp-ecm default on C92
09/05/11 07:34:31 v1.28.4 @ STM11647, pp1: starting B1 = 5M, B2 = gmp-ecm default on C92
09/05/11 07:34:47 v1.28.4 @ STM11647, pm1: starting B1 = 10M, B2 = gmp-ecm default on C92
09/05/11 07:36:27 v1.28.4 @ STM11647, Finished 2 curves using Lenstra ECM method on C92 input, B1 = 1M, B2 = gmp-ecm default
09/05/11 07:38:54 v1.28.4 @ STM11647, Finished 1 curves using Lenstra ECM method on C92 input, B1 = 10M, B2 = gmp-ecm default
09/05/11 07:38:54 v1.28.4 @ STM11647, starting SIQS on c92: 41285311719805955987870990403314964284156777185282115706759112499904162203091021318556917829
09/05/11 07:38:54 v1.28.4 @ STM11647, random seeds: 1855866611, 2252645047

[James Heinrich]

I'm using yafu on Windows (Win7x64) to run through about 33 million known Mersenne factors to verify that they are prime. I don't want factor.log or session.log, but I can't figure out how to suppress their creation?

[bsquared]

Originally Posted by James Heinrich

I'm using yafu on Windows (Win7x64) to run through about 33 million known Mersenne factors to verify that they are prime. I don't want factor.log or session.log, but I can't figure out how to suppress their creation?

How are you currently doing it? If you have all of these numbers in a file called "input.dat", you could do something like this:

yafu-32k-x64.exe "isprime(@)" -batchfile input.dat > output.dat

which will run isprime on all of them and output all of the results to the file output.dat. This will only write to session.log once, and never to factor.log.

To answer your question directly, just continue to do what you're doing with the addition of

-logfile NUL -session NUL

which will suppress all factorization and session logging.

[bsquared]

Originally Posted by yoyo

Hello,

I run yafu factor(number). In the first step yafu runs rho, pp1, ecm until it starts with siqs. Siqs saves the progress in siqs.dat.
Than I restarted the computer and restarted yafu.
But now yafu starts from the beginning.
Can yafu be improved, if the siqs.dat exists for this number to continue the siqs part and not start from the beginning?
I think this is the case if I use siqs(number).

Yeah, that sounds like a good idea. And yes, if you restart with siqs(number) it will restart where it left off in the siqs routine.

[wblipp]

Here's a surprise (at least to me) - two 11 digit composites that pass YAFU's PRP test. I had thought a stronger PRP test would be used.

74845656211 = 173707 x 430873
10678346407 = 96697 x 110431

=== Starting work on batchfile expression ===
factor((628681^13-1)/(628681-1))
=============================================
factoring 3812103772180083589451043543655202013959359239617616178947611044963453
using pretesting plan: normal

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 1, starting 1000 iterations on C69 
rho: x^2 + 3, starting 1000 iterations on C69 
rho: x^2 + 3, starting 1000 iterations on C64 
rho: x^2 + 3, starting 1000 iterations on C53 
rho: x^2 + 3, starting 1000 iterations on C46 
rho: x^2 + 2, starting 1000 iterations on C46 
pp1: starting B1 = 20K, B2 = gmp-ecm default on C46
pp1: starting B1 = 20K, B2 = gmp-ecm default on C46
pp1: starting B1 = 20K, B2 = gmp-ecm default on C46

starting SIQS on c46: 1397929092484133938574316365114490153057244253

==== sieving in progress (1 thread):    1120 relations needed ====
====           Press ctrl-c to abort and save state           ====
143 rels found: 115 full + 28 from 938 partial, (2592.00 rels/sec)
289 rels found: 218 full + 71 from 1615 partial, (3170.59 rels/sec)
487 rels found: 325 full + 162 from 2383 partial, (3610.67 rels/sec)
746 rels found: 426 full + 320 from 3190 partial, (4060.07 rels/sec)
1005 rels found: 530 full + 475 from 4006 partial, (4332.90 rels/sec)

SIQS elapsed time = 1.2656 seconds.
b = 1
Total factoring time = 1.6250 seconds


***factors found***

P2 = 13
PRP5 = 40847
PRP11 = 74845656211
PRP8 = 68613481
PRP21 = 855215960592089766203
PRP25 = 1634591912335579887169351

ans = 1

=== Starting work on batchfile expression ===
factor((1007935272731^3-1)/(1007935272731-1))
=============================================
factoring 1015933514016323287471093
using pretesting plan: normal

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 1, starting 1000 iterations on C22 
rho: x^2 + 3, starting 1000 iterations on C22 
rho: x^2 + 3, starting 1000 iterations on C18 
Total factoring time = 0.0156 seconds


***factors found***

P1 = 7
P2 = 19
PRP5 = 39679
PRP11 = 10678346407
PRP8 = 18028057

ans = 1

[bsquared]

Originally Posted by wblipp

Here's a surprise (at least to me) - an 11 digit composite that passes YAFU's PRP test. I had thought a stronger PRP test would be used.

74845656211 = 173707 x 430873

=== Starting work on batchfile expression ===
factor((628681^13-1)/(628681-1))
=============================================
factoring 3812103772180083589451043543655202013959359239617616178947611044963453
 
 ...
 
***factors found***
 
P2 = 13
PRP5 = 40847
PRP11 = 74845656211
PRP8 = 68613481
PRP21 = 855215960592089766203
PRP25 = 1634591912335579887169351
 
ans = 1

PS S:\buhrow\yafu\build.vc10\Win32\Release> .\yafu-32k-Win32.exe "isprime(74845656211)"
 
not prime
ans = 0

PS S:\buhrow\yafu-neworg\build.vc10\Win32\Release> .\yafu-32k-Win32.exe "isprime(10678346407)"

not prime
ans = 0

??

Can you look into factor.log and see what routine found that (pseudo)prime? Maybe factors are not being checked fully somewhere.

I use trial division by primes < 100 followed by 20 rounds of rabin-miller (with bases taken from primes less than 100) for the PRP check.

[wblipp]

Originally Posted by bsquared

Can you look into factor.log and see what routine found that (pseudo)prime? Maybe factors are not being checked fully somewhere.

Here is what I found in factor.log:

09/05/11 17:20:15 v1.28.4 @ HESTIA, ****************************
09/05/11 17:20:15 v1.28.4 @ HESTIA, Starting factorization of 3812103772180083589451043543655202013959359239617616178947611044963453
09/05/11 17:20:15 v1.28.4 @ HESTIA, ****************************
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 1, starting 1000 iterations on C69
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C69
09/05/11 17:20:15 v1.28.4 @ HESTIA, prp5 = 40847
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C64
09/05/11 17:20:15 v1.28.4 @ HESTIA, prp11 = 74845656211
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C53
09/05/11 17:20:15 v1.28.4 @ HESTIA, prp8 = 68613481
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C46
09/05/11 17:20:15 v1.28.4 @ HESTIA, rho: x^2 + 2, starting 1000 iterations on C46
09/05/11 17:20:15 v1.28.4 @ HESTIA, pp1: starting B1 = 20K, B2 = gmp-ecm default on C46
09/05/11 17:20:15 v1.28.4 @ HESTIA, pp1: starting B1 = 20K, B2 = gmp-ecm default on C46
09/05/11 17:20:15 v1.28.4 @ HESTIA, pp1: starting B1 = 20K, B2 = gmp-ecm default on C46


09/05/11 12:17:10 v1.28.4 @ HESTIA, ****************************
09/05/11 12:17:10 v1.28.4 @ HESTIA, Starting factorization of 1015933514016323287471093
09/05/11 12:17:10 v1.28.4 @ HESTIA, ****************************
09/05/11 12:17:10 v1.28.4 @ HESTIA, rho: x^2 + 1, starting 1000 iterations on C22
09/05/11 12:17:10 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C22
09/05/11 12:17:10 v1.28.4 @ HESTIA, prp5 = 39679
09/05/11 12:17:10 v1.28.4 @ HESTIA, rho: x^2 + 3, starting 1000 iterations on C18
09/05/11 12:17:10 v1.28.4 @ HESTIA, prp11 = 10678346407
09/05/11 12:17:10 v1.28.4 @ HESTIA, prp8 = 18028057
09/05/11 12:17:10 v1.28.4 @ HESTIA, Total factoring time = 0.0156 seconds

[bsquared]

Originally Posted by wblipp

Here is what I found in factor.log:

Thanks. Looks like I broke this in version 1.28.4 when I ported rho to GMP - the factor isn't initialized correctly and that causes the PRP check to be skipped.

I'll get a new version out soon with this (and several other things) fixed.

[yoyo]

Can I get a static linked version for Linux in the next release?
I'm sending yafu automatic to registered Boinc user and most of them do not have libgmp.so installed.

thanks,
yoyo