Yafu

[cgy606]

Originally Posted by schickel

As noted, the estimate for the number of relations needed is usually off. For a number of this size you'll need in the vicinity of 10 million relations. Based on the post-processing attempts, you're nearly there.Keep an eye on the ratio of relations to ideals. You need more relations than ideals, and the larger the number the more extra you need.As you get closer, more relations will survive the reduction step, until they exceed the ideals that make it....

My laptop finished factoring 100!+3 . It was working on a c127 using nfs that I assumed from factorb was tested with ecm up to t35 (I formulated this based on the fact that many numbers in the sequence n!+3 around n=100 had primes in the range on 30-40 digits and still composite factors left. Thinking nothing special about 100!+3, I figured it was tested like the others). nfs after 46 hours spit out a p53 and a c74. I was annoyed that that meant my previous assumption was wrong and that it was only tested up to t30 (which is what I tested it too). It turns out that letting the program run another 332 curves at B1=1e6 spits out the 30 digit cofactor of the c74 in about 20 minutes on my laptop. If I would have searched up to t35, then nfs would have worked on a c98 instead of a c127 and only taken about 2 hours on my laptop. Oh well, at least I know that a c125-c130 takes a few days on my machine and the program works!! Any suggestions on a number to factor that is in that range?

[xilman]

Originally Posted by cgy606

My laptop finished factoring 100!+3 . It was working on a c127 using nfs that I assumed from factorb was tested with ecm up to t35 (I formulated this based on the fact that many numbers in the sequence n!+3 around n=100 had primes in the range on 30-40 digits and still composite factors left. Thinking nothing special about 100!+3, I figured it was tested like the others). nfs after 46 hours spit out a p53 and a c74. I was annoyed that that meant my previous assumption was wrong and that it was only tested up to t30 (which is what I tested it too). It turns out that letting the program run another 332 curves at B1=1e6 spits out the 30 digit cofactor of the c74 in about 20 minutes on my laptop. If I would have searched up to t35, then nfs would have worked on a c98 instead of a c127 and only taken about 2 hours on my laptop. Oh well, at least I know that a c125-c130 takes a few days on my machine and the program works!! Any suggestions on a number to factor that is in that range?

An ECM miss is always irritating but they happen. At least you found the factors.

[VolMike]

...Any suggestions on a number to factor that is in that range?

100!+14 :)

[VolMike]

Originally Posted by VolMike

100!+14 :)

It has been factored now.

[lorgix]

Originally Posted by cgy606

My laptop finished factoring 100!+3 . It was working on a c127 using nfs that I assumed from factorb was tested with ecm up to t35 (I formulated this based on the fact that many numbers in the sequence n!+3 around n=100 had primes in the range on 30-40 digits and still composite factors left. Thinking nothing special about 100!+3, I figured it was tested like the others). nfs after 46 hours spit out a p53 and a c74. I was annoyed that that meant my previous assumption was wrong and that it was only tested up to t30 (which is what I tested it too). It turns out that letting the program run another 332 curves at B1=1e6 spits out the 30 digit cofactor of the c74 in about 20 minutes on my laptop. If I would have searched up to t35, then nfs would have worked on a c98 instead of a c127 and only taken about 2 hours on my laptop. Oh well, at least I know that a c125-c130 takes a few days on my machine and the program works!! Any suggestions on a number to factor that is in that range?

There is no shortage of numbers to factor. Choose something that interests you.

(The c114 co-factor of 5179^41-1 has had 2t35, just as an example.)

I would suggest you use SIQS on the c74 if you find yourself in a similar situation in the future.

[wblipp]

Originally Posted by cgy606

Oh well, at least I know that a c125-c130 takes a few days on my machine and the program works!! Any suggestions on a number to factor that is in that range?

The Oddperfect Composites page was updated last week. I try to keep an assortment of numbers up to C159 available.

[bsquared]

Originally Posted by cgy606

Hi,

I am typing as above the following code:

ecm(number,904) -B1ecm 1000000

However, it runs ecm until the firsts factor is found then stops. Is there a way to tell it to run ecm until all curves are done regardless of how many factors it finds (in other words, keep running until it finishes that many curves). I looked at the docfile and then is a flag to tell ecm to find only one factor -one, hence if you do not include this flag it should factor until either the number of curves is done or the factorization is complete. Thank you,

-one is a flag used by factor(), which in general is the only function in yafu which strives to completely factor the input. The rest of the functions are happy with finding one factor. ecm() doesn't respond to the -one flag.

[lorgix]

I don't think doing three P+1 in a row is very efficient. I would suggest once, before each ECM-level.

[cgy606]

I just got gmp-ecm 6.4 for my mac. I ran a couple hundred curves for a factor at b1=11M and I am pretty sure the program found a factor after 23 curves. However, the screen didn't display the factor. I know the program found a factor because the time required to perform step 1 and step 2 is displayed after each run and the time to perform decreases after step 23. However, the factor did not print out on the screen. Is the output save to some logfile like it is in yafu that I can access? Thanks

[swishzzz]

Originally Posted by schickel

As noted, the estimate for the number of relations needed is usually off. For a number of this size you'll need in the vicinity of 10 million relations. Based on the post-processing attempts, you're nearly there.Keep an eye on the ratio of relations to ideals. You need more relations than ideals, and the larger the number the more extra you need.As you get closer, more relations will survive the reduction step, until they exceed the ideals that make it....

Is it necessary to have more relations than ideals? Apparently this wasn't the case in the following example:

Thu Sep 22 16:38:37 2011 Msieve v. 1.49 (SVN unknown)
Thu Sep 22 16:38:37 2011 random seeds: cedff090 a39dc579
Thu Sep 22 16:38:37 2011 factoring 14154606037482006751216806823077551888056933202478369725975090478831148242241393450335291872156499420677923338442448578075087 (125 digits)
Thu Sep 22 16:38:38 2011 searching for 15-digit factors
Thu Sep 22 16:38:39 2011 commencing number field sieve (125-digit input)
Thu Sep 22 16:38:39 2011 R0: -1987868138274461522151738
Thu Sep 22 16:38:39 2011 R1: 13133513326051
Thu Sep 22 16:38:39 2011 A0: -26643052651255895262595920303185
Thu Sep 22 16:38:39 2011 A1: 425415258744318522554351623
Thu Sep 22 16:38:39 2011 A2: 462414780831949533207
Thu Sep 22 16:38:39 2011 A3: -5125318744148335
Thu Sep 22 16:38:39 2011 A4: -781978918
Thu Sep 22 16:38:39 2011 A5: 456
Thu Sep 22 16:38:39 2011 skew 841754.40, size 6.392e-012, alpha -6.968, combined = 1.675e-010 rroots = 5
Thu Sep 22 16:38:39 2011
Thu Sep 22 16:38:39 2011 commencing relation filtering
Thu Sep 22 16:38:39 2011 estimated available RAM is 2039.3 MB
Thu Sep 22 16:38:39 2011 commencing duplicate removal, pass 1
Thu Sep 22 16:39:30 2011 error -15 reading relation 4627292
Thu Sep 22 16:39:32 2011 error -15 reading relation 4759833
Thu Sep 22 16:40:10 2011 error -15 reading relation 8200643
Thu Sep 22 16:40:11 2011 error -15 reading relation 8279114
Thu Sep 22 16:40:44 2011 found 1275637 hash collisions in 11050845 relations
Thu Sep 22 16:41:44 2011 added 66 free relations
Thu Sep 22 16:41:44 2011 commencing duplicate removal, pass 2
Thu Sep 22 16:41:57 2011 found 1019547 duplicates and 10031364 unique relations
Thu Sep 22 16:41:57 2011 memory use: 49.3 MB
Thu Sep 22 16:41:57 2011 reading ideals above 5570560
Thu Sep 22 16:42:03 2011 commencing singleton removal, initial pass
Thu Sep 22 16:44:15 2011 memory use: 188.3 MB
Thu Sep 22 16:44:15 2011 reading all ideals from disk
Thu Sep 22 16:44:15 2011 memory use: 177.2 MB
Thu Sep 22 16:44:16 2011 commencing in-memory singleton removal
Thu Sep 22 16:44:18 2011 begin with 10031364 relations and 10239078 unique ideals
Thu Sep 22 16:44:30 2011 reduce to 3874419 relations and 3043595 ideals in 20 passes
Thu Sep 22 16:44:30 2011 max relations containing the same ideal: 18
Thu Sep 22 16:44:31 2011 reading ideals above 100000
Thu Sep 22 16:44:31 2011 commencing singleton removal, initial pass
Thu Sep 22 16:45:40 2011 memory use: 94.1 MB
Thu Sep 22 16:45:40 2011 reading all ideals from disk
Thu Sep 22 16:45:41 2011 memory use: 139.1 MB
Thu Sep 22 16:45:42 2011 keeping 3792920 ideals with weight <= 200, target excess is 22192
Thu Sep 22 16:45:43 2011 commencing in-memory singleton removal
Thu Sep 22 16:45:44 2011 begin with 3874485 relations and 3792920 unique ideals
Thu Sep 22 16:45:56 2011 reduce to 3866652 relations and 3784759 ideals in 11 passes
Thu Sep 22 16:45:56 2011 max relations containing the same ideal: 200
Thu Sep 22 16:46:01 2011 removing 352708 relations and 324633 ideals in 28075 cliques
Thu Sep 22 16:46:01 2011 commencing in-memory singleton removal
Thu Sep 22 16:46:02 2011 begin with 3513944 relations and 3784759 unique ideals
Thu Sep 22 16:46:15 2011 reduce to 3488541 relations and 3434448 ideals in 13 passes
Thu Sep 22 16:46:15 2011 max relations containing the same ideal: 191
Thu Sep 22 16:46:19 2011 removing 255181 relations and 227106 ideals in 28075 cliques
Thu Sep 22 16:46:20 2011 commencing in-memory singleton removal
Thu Sep 22 16:46:21 2011 begin with 3233360 relations and 3434448 unique ideals
Thu Sep 22 16:46:28 2011 reduce to 3218602 relations and 3192442 ideals in 8 passes
Thu Sep 22 16:46:28 2011 max relations containing the same ideal: 181
Thu Sep 22 16:46:33 2011 relations with 0 large ideals: 69
Thu Sep 22 16:46:33 2011 relations with 1 large ideals: 28
Thu Sep 22 16:46:33 2011 relations with 2 large ideals: 563
Thu Sep 22 16:46:33 2011 relations with 3 large ideals: 7672
Thu Sep 22 16:46:33 2011 relations with 4 large ideals: 57011
Thu Sep 22 16:46:33 2011 relations with 5 large ideals: 242357
Thu Sep 22 16:46:33 2011 relations with 6 large ideals: 621490
Thu Sep 22 16:46:33 2011 relations with 7+ large ideals: 2289412
Thu Sep 22 16:46:33 2011 commencing 2-way merge
Thu Sep 22 16:46:39 2011 reduce to 1831938 relation sets and 1805779 unique ideals
Thu Sep 22 16:46:39 2011 ignored 1 oversize relation sets
Thu Sep 22 16:46:39 2011 commencing full merge
Thu Sep 22 16:47:37 2011 memory use: 186.7 MB
Thu Sep 22 16:47:37 2011 found 921818 cycles, need 919979
Thu Sep 22 16:47:37 2011 weight of 919979 cycles is about 64687230 (70.31/cycle)
Thu Sep 22 16:47:37 2011 distribution of cycle lengths:
Thu Sep 22 16:47:37 2011 1 relations: 123737
Thu Sep 22 16:47:37 2011 2 relations: 112745
Thu Sep 22 16:47:37 2011 3 relations: 110493
Thu Sep 22 16:47:37 2011 4 relations: 96247
Thu Sep 22 16:47:37 2011 5 relations: 83290
Thu Sep 22 16:47:37 2011 6 relations: 69447
Thu Sep 22 16:47:37 2011 7 relations: 59341
Thu Sep 22 16:47:37 2011 8 relations: 49524
Thu Sep 22 16:47:37 2011 9 relations: 40208
Thu Sep 22 16:47:37 2011 10+ relations: 174947
Thu Sep 22 16:47:37 2011 heaviest cycle: 28 relations
Thu Sep 22 16:47:38 2011 commencing cycle optimization
Thu Sep 22 16:47:40 2011 start with 5454634 relations
Thu Sep 22 16:47:56 2011 pruned 101932 relations
Thu Sep 22 16:47:56 2011 memory use: 148.0 MB
Thu Sep 22 16:47:56 2011 distribution of cycle lengths:
Thu Sep 22 16:47:56 2011 1 relations: 123737
Thu Sep 22 16:47:56 2011 2 relations: 114910
Thu Sep 22 16:47:56 2011 3 relations: 113838
Thu Sep 22 16:47:56 2011 4 relations: 97698
Thu Sep 22 16:47:56 2011 5 relations: 84351
Thu Sep 22 16:47:56 2011 6 relations: 69873
Thu Sep 22 16:47:56 2011 7 relations: 59328
Thu Sep 22 16:47:56 2011 8 relations: 49141
Thu Sep 22 16:47:56 2011 9 relations: 39545
Thu Sep 22 16:47:56 2011 10+ relations: 167558
Thu Sep 22 16:47:56 2011 heaviest cycle: 27 relations
Thu Sep 22 16:48:02 2011 RelProcTime: 563
Thu Sep 22 16:48:02 2011 elapsed time 00:09:25
Thu Sep 22 16:48:02 2011 LatSieveTime: 5012.12
Thu Sep 22 16:48:02 2011 -> Running matrix solving step ...

[bsquared]

Originally Posted by swishzzz

Is it necessary to have more relations than ideals? Apparently this wasn't the case in the following example:

No, as you found it is not strictly necessary. But it is highly typical to find num relations > unique ideals before the filtering will succeed. It would be a better question for jasonp (or others) as to why...