mersenneforum.org > YAFU Yafu
 Register FAQ Search Today's Posts Mark Forums Read

2012-02-13, 08:18   #1123
cgy606

Feb 2012

3F16 Posts

Quote:
 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?

2012-02-13, 08:57   #1124
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·43·79 Posts

Quote:
 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.

2012-02-13, 09:23   #1125
VolMike

Jun 2007
Moscow,Russia

7×19 Posts

Quote:
 ...Any suggestions on a number to factor that is in that range?
100!+14 :)

Last fiddled with by VolMike on 2012-02-13 at 09:23

2012-02-13, 09:38   #1126
VolMike

Jun 2007
Moscow,Russia

7×19 Posts

Quote:
 Originally Posted by VolMike 100!+14 :)
It has been factored now.

2012-02-13, 10:11   #1127
lorgix

Sep 2010
Scandinavia

61510 Posts

Quote:
 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.

2012-02-13, 14:17   #1128
wblipp

"William"
May 2003
New Haven

22·32·5·13 Posts

Quote:
 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.

2012-02-13, 14:27   #1129
bsquared

"Ben"
Feb 2007

13×257 Posts

Quote:
 Originally Posted by cgy606 Hi, I am typing as above the following code: 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.

 2012-02-16, 20:53 #1130 lorgix     Sep 2010 Scandinavia 3×5×41 Posts factor() I don't think doing three P+1 in a row is very efficient. I would suggest once, before each ECM-level.
 2012-02-17, 14:42 #1131 cgy606   Feb 2012 32×7 Posts 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
2012-02-17, 20:23   #1132
swishzzz

Jan 2012

23·5 Posts

Quote:
 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: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 ...

Last fiddled with by swishzzz on 2012-02-17 at 20:27

2012-02-17, 20:41   #1133
bsquared

"Ben"
Feb 2007

1101000011012 Posts

Quote:
 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH YAFU 8 2018-03-14 17:22 bsquared YAFU 119 2015-11-05 16:24 storflyt32 YAFU 2 2015-06-29 05:19 bsquared YAFU 12 2012-11-08 04:12 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 20:02.

Mon Nov 23 20:02:34 UTC 2020 up 74 days, 17:13, 3 users, load averages: 2.89, 2.59, 2.50

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.