mersenneforum.org All square roots failed
 Register FAQ Search Today's Posts Mark Forums Read

2016-12-04, 16:47   #1
chris2be8

Sep 2009

22×487 Posts
All square roots failed

Hello,

I've just had a run where all 36 relations failed. It's one with no irreducible primes, so not very unlikely. See the attached log.

Is there any way to complete this run? Would adding a few more relations and re-running filtering etc be likely to work?

Chris
Attached Files
 ggnfs.log (77.5 KB, 215 views)

 2016-12-04, 18:37 #2 kurtb   "Beschorner Kurt" Jul 2016 Germany 1316 Posts I guess: 380M - 420 M unique relations are necessary Kurt
 2016-12-04, 18:52 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 217408 Posts Welcome to the forum, Kurt!
2016-12-05, 05:48   #4
jyb

Aug 2005
Seattle, WA

3×13×41 Posts

Quote:
 Originally Posted by chris2be8 Hello, I've just had a run where all 36 relations failed. It's one with no irreducible primes, so not very unlikely. See the attached log. Is there any way to complete this run? Would adding a few more relations and re-running filtering etc be likely to work? Chris
Noticing that this was a very small job, I just decided to try to replicate your results. In my case I actually started post-processing with fewer unique relations (2998338), and I did get a whole lot of "Newton iteration failed to converge" (as well as a few GCDs of 1 or N), but on the 14th dependency it actually succeeded. And it was a nice split, too. (See FactorDB.)

So if you care about this particular number, then hey, problem solved. But I suspect you really want to know what can be done in general in this situation, especially if it happens for larger numbers. And the answer is I'm afraid I don't really know. I think your suggestion is probably the one I'd try; that is, do some more sieving and try again. I think that maybe just having a different set of relations to work with is enough to make the filtering/LA produce different dependencies, and that's what's needed. But jasonp will obviously have some actual insight into this, so hopefully he'll weigh in.

 2016-12-11, 16:58 #5 chris2be8     Sep 2009 22·487 Posts @jasonp: Any comments? I've still got the dat file etc if you want them to help you investigate. Chris
 2016-12-12, 11:34 #6 jasonp Tribal Bullet     Oct 2004 22×883 Posts There's a lot I don't understand about what happens when you can't find a prime p for which an NFS polynomial mod p is not irreducible. References don't talk much about this case at all and my reading of the probability they state for the Newton iteration succeeding is much lower than what we actually see from these jobs. So unfortunately I can't offer additional insight here.
 2017-02-05, 16:39 #7 chris2be8     Sep 2009 22·487 Posts I've had another interesting occurrence in the square root stage: Code: Sat Feb 4 22:36:14 2017 Msieve v. 1.52 (SVN 956) Sat Feb 4 22:36:14 2017 random seeds: fb0b9f07 1d17cad7 Sat Feb 4 22:36:14 2017 factoring 2958866433961714724519604433633559712837901381475268861194367370217958852861572851176084153382731169515631 (106 digits) Sat Feb 4 22:36:15 2017 searching for 15-digit factors Sat Feb 4 22:36:15 2017 commencing number field sieve (106-digit input) Sat Feb 4 22:36:15 2017 R0: -11695209869184195626129127843 Sat Feb 4 22:36:15 2017 R1: 1 Sat Feb 4 22:36:15 2017 A0: 9 Sat Feb 4 22:36:15 2017 A1: 0 Sat Feb 4 22:36:15 2017 A2: 2811 Sat Feb 4 22:36:15 2017 A3: 0 Sat Feb 4 22:36:15 2017 A4: 877969 Sat Feb 4 22:36:15 2017 skew 0.06, size 5.334e-13, alpha -0.020, combined = 2.911e-08 rroots = 0 Sat Feb 4 22:36:15 2017 Sat Feb 4 22:36:15 2017 commencing square root phase Sat Feb 4 22:36:15 2017 reading relations for dependency 1 Sat Feb 4 22:36:15 2017 read 53921 cycles Sat Feb 4 22:36:15 2017 cycles contain 181062 unique relations Sat Feb 4 22:36:18 2017 read 181062 relations Sat Feb 4 22:36:18 2017 multiplying 181062 relations Sat Feb 4 22:36:23 2017 multiply complete, coefficients have about 6.59 million bits Sat Feb 4 22:36:23 2017 warning: no irreducible prime found, switching to small primes Sat Feb 4 22:37:43 2017 initial square root is modulo 101 Sat Feb 4 22:37:52 2017 Newton iteration failed to converge Sat Feb 4 22:37:52 2017 algebraic square root failed Sat Feb 4 22:37:52 2017 reading relations for dependency 2 Sat Feb 4 22:37:52 2017 read 53902 cycles Sat Feb 4 22:37:53 2017 cycles contain 181374 unique relations Sat Feb 4 22:37:55 2017 read 181374 relations Sat Feb 4 22:37:55 2017 multiplying 181374 relations Sat Feb 4 22:38:00 2017 multiply complete, coefficients have about 6.60 million bits Sat Feb 4 22:38:00 2017 warning: no irreducible prime found, switching to small primes Sat Feb 4 22:38:00 2017 initial square root is modulo 53 Sat Feb 4 22:38:17 2017 sqrtTime: 122 Sat Feb 4 22:38:17 2017 prp35 factor: 50883663903647478965541548004353149 Sat Feb 4 22:38:17 2017 prp71 factor: 58149634027230793762697993489469471494185135901250052026412114869424219 Sat Feb 4 22:38:17 2017 elapsed time 00:02:03 I don't think I've seen a square root other than 53 when msieve switches to small primes ( except when it takes hours searching for a small prime, and then it used 59). It was the delay of nearly a minute before it said it was using 101 that drew my attention to this run. I don't have the relations any more, my script deleted them since it successfully factored the number. Chris
 2017-02-06, 03:34 #8 jasonp Tribal Bullet     Oct 2004 22×883 Posts When the square root switches to small primes p for the algebraic polynomial of degree d, it uses brute force looking through all p^d polynomials with coefficients modulo p trying to find one that satisfies the algebraic square root equation modulo p. When d is 4 this is only a few polynomials so it's feasible to look through several values of p quickly; it's when the degree is 6 or even 8 that searching takes a long time. I guess it's possible to be really unlucky and deal with an algebraic polynomial that has unusually few suitable small p such that you need to go through a lot of trials to find a good answer. The search terminates with p = 150 so the entire dependency is aborted if we get that far, but otherwise if there's no complaining about the Newton iteration failing then the algebraic square root did work with p=101
 2020-10-13, 20:22 #9 pinhodecarlos     "Carlos Pinho" Oct 2011 Milton Keynes, UK 12B216 Posts For 3p2_1446M going for dependency 13, already a factor found, just wondering if it is quicker to just run some ECM on the c125. Code: Tue Oct 13 14:46:26 2020 commencing square root phase Tue Oct 13 14:46:26 2020 handling dependencies 1 to 64 Tue Oct 13 14:46:26 2020 reading relations for dependency 1 Tue Oct 13 14:46:30 2020 read 5763923 cycles Tue Oct 13 14:46:42 2020 cycles contain 18295140 unique relations Tue Oct 13 14:53:57 2020 read 18295140 relations Tue Oct 13 14:55:26 2020 multiplying 18295140 relations Tue Oct 13 15:02:52 2020 multiply complete, coefficients have about 543.55 million bits Tue Oct 13 15:02:55 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 15:02:56 2020 initial square root is modulo 53 Tue Oct 13 15:17:01 2020 Newton iteration failed to converge Tue Oct 13 15:17:01 2020 algebraic square root failed Tue Oct 13 15:17:01 2020 reading relations for dependency 2 Tue Oct 13 15:17:03 2020 read 5767231 cycles Tue Oct 13 15:17:15 2020 cycles contain 18298230 unique relations Tue Oct 13 15:24:32 2020 read 18298230 relations Tue Oct 13 15:26:01 2020 multiplying 18298230 relations Tue Oct 13 15:33:28 2020 multiply complete, coefficients have about 543.63 million bits Tue Oct 13 15:33:31 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 15:33:32 2020 initial square root is modulo 53 Tue Oct 13 15:47:36 2020 Newton iteration failed to converge Tue Oct 13 15:47:36 2020 algebraic square root failed Tue Oct 13 15:47:36 2020 reading relations for dependency 3 Tue Oct 13 15:47:38 2020 read 5764729 cycles Tue Oct 13 15:47:50 2020 cycles contain 18303422 unique relations Tue Oct 13 15:55:09 2020 read 18303422 relations Tue Oct 13 15:56:39 2020 multiplying 18303422 relations Tue Oct 13 16:04:07 2020 multiply complete, coefficients have about 543.80 million bits Tue Oct 13 16:04:10 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 16:04:10 2020 initial square root is modulo 53 Tue Oct 13 16:18:16 2020 found factor: 4092548937881641137005120020566114770332136530455541914336089917 Tue Oct 13 16:18:16 2020 reading relations for dependency 4 Tue Oct 13 16:18:18 2020 read 5762709 cycles Tue Oct 13 16:18:30 2020 cycles contain 18291758 unique relations Tue Oct 13 16:25:41 2020 read 18291758 relations Tue Oct 13 16:27:10 2020 multiplying 18291758 relations Tue Oct 13 16:34:36 2020 multiply complete, coefficients have about 543.45 million bits Tue Oct 13 16:34:39 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 16:34:39 2020 initial square root is modulo 53 Tue Oct 13 16:48:45 2020 Newton iteration failed to converge Tue Oct 13 16:48:45 2020 algebraic square root failed Tue Oct 13 16:48:45 2020 reading relations for dependency 5 Tue Oct 13 16:48:47 2020 read 5764827 cycles Tue Oct 13 16:48:59 2020 cycles contain 18298276 unique relations Tue Oct 13 16:56:13 2020 read 18298276 relations Tue Oct 13 16:57:42 2020 multiplying 18298276 relations Tue Oct 13 17:05:07 2020 multiply complete, coefficients have about 543.64 million bits Tue Oct 13 17:05:10 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 17:05:10 2020 initial square root is modulo 53 Tue Oct 13 17:19:20 2020 Newton iteration failed to converge Tue Oct 13 17:19:20 2020 algebraic square root failed Tue Oct 13 17:19:20 2020 reading relations for dependency 6 Tue Oct 13 17:19:22 2020 read 5766844 cycles Tue Oct 13 17:19:34 2020 cycles contain 18302212 unique relations Tue Oct 13 17:26:52 2020 read 18302212 relations Tue Oct 13 17:28:21 2020 multiplying 18302212 relations Tue Oct 13 17:35:49 2020 multiply complete, coefficients have about 543.75 million bits Tue Oct 13 17:35:52 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 17:35:53 2020 initial square root is modulo 53 Tue Oct 13 17:49:59 2020 Newton iteration failed to converge Tue Oct 13 17:49:59 2020 algebraic square root failed Tue Oct 13 17:49:59 2020 reading relations for dependency 7 Tue Oct 13 17:50:09 2020 read 5766512 cycles Tue Oct 13 17:50:21 2020 cycles contain 18300514 unique relations Tue Oct 13 17:57:37 2020 read 18300514 relations Tue Oct 13 17:59:06 2020 multiplying 18300514 relations Tue Oct 13 18:06:33 2020 multiply complete, coefficients have about 543.71 million bits Tue Oct 13 18:06:36 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 18:06:36 2020 initial square root is modulo 53 Tue Oct 13 18:21:43 2020 Newton iteration failed to converge Tue Oct 13 18:21:43 2020 algebraic square root failed Tue Oct 13 18:21:43 2020 reading relations for dependency 8 Tue Oct 13 18:21:45 2020 read 5766212 cycles Tue Oct 13 18:21:57 2020 cycles contain 18301454 unique relations Tue Oct 13 18:45:37 2020 read 18301454 relations Tue Oct 13 18:47:05 2020 multiplying 18301454 relations Tue Oct 13 18:54:31 2020 multiply complete, coefficients have about 543.74 million bits Tue Oct 13 18:54:34 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 18:54:35 2020 initial square root is modulo 53 Tue Oct 13 19:08:43 2020 Newton iteration failed to converge Tue Oct 13 19:08:43 2020 algebraic square root failed Tue Oct 13 19:08:43 2020 reading relations for dependency 9 Tue Oct 13 19:08:53 2020 read 5763949 cycles Tue Oct 13 19:09:05 2020 cycles contain 18297726 unique relations Tue Oct 13 19:16:36 2020 read 18297726 relations Tue Oct 13 19:18:04 2020 multiplying 18297726 relations Tue Oct 13 19:25:28 2020 multiply complete, coefficients have about 543.62 million bits Tue Oct 13 19:25:31 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 19:25:32 2020 initial square root is modulo 53 Tue Oct 13 19:39:36 2020 Newton iteration failed to converge Tue Oct 13 19:39:36 2020 algebraic square root failed Tue Oct 13 19:39:36 2020 reading relations for dependency 10 Tue Oct 13 19:39:46 2020 read 5767626 cycles Tue Oct 13 19:39:57 2020 cycles contain 18304652 unique relations Tue Oct 13 19:47:08 2020 read 18304652 relations Tue Oct 13 19:48:37 2020 multiplying 18304652 relations Tue Oct 13 19:56:03 2020 multiply complete, coefficients have about 543.83 million bits Tue Oct 13 19:56:05 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 19:56:06 2020 initial square root is modulo 53 Tue Oct 13 20:10:15 2020 GCD is 1, no factor found Tue Oct 13 20:10:15 2020 reading relations for dependency 11 Tue Oct 13 20:10:25 2020 read 5764699 cycles Tue Oct 13 20:10:37 2020 cycles contain 18296956 unique relations Tue Oct 13 20:17:53 2020 read 18296956 relations Tue Oct 13 20:19:21 2020 multiplying 18296956 relations Tue Oct 13 20:26:46 2020 multiply complete, coefficients have about 543.60 million bits Tue Oct 13 20:26:49 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 20:26:51 2020 initial square root is modulo 53 Tue Oct 13 20:40:56 2020 Newton iteration failed to converge Tue Oct 13 20:40:56 2020 algebraic square root failed Tue Oct 13 20:40:56 2020 reading relations for dependency 12 Tue Oct 13 20:41:06 2020 read 5766795 cycles Tue Oct 13 20:41:18 2020 cycles contain 18302378 unique relations Tue Oct 13 20:48:24 2020 read 18302378 relations Tue Oct 13 20:49:54 2020 multiplying 18302378 relations Tue Oct 13 20:57:20 2020 multiply complete, coefficients have about 543.77 million bits Tue Oct 13 20:57:23 2020 warning: no irreducible prime found, switching to small primes Tue Oct 13 20:57:24 2020 initial square root is modulo 53 Tue Oct 13 21:11:41 2020 Newton iteration failed to converge Tue Oct 13 21:11:41 2020 algebraic square root failed Tue Oct 13 21:11:41 2020 reading relations for dependency 13 Tue Oct 13 21:11:52 2020 read 5766540 cycles Tue Oct 13 21:12:04 2020 cycles contain 18300940 unique relations Code: http://factordb.com/index.php?query=227289709170775626007585710867309934693162572916668346006138666559388922469472389295406521342510427966571237053766292936031495286594901935034616836180690107776493460879759323119637541757189
 2020-10-13, 21:09 #10 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 3,463 Posts in my limited experience of having a factor found and still not finished, the first found has been the smaller of the three. If that is the case with yours, you're still looking at trying to pull a 60+ digit factor from the c125. How long would that take for your ECM process? Please post the other factors (or at least their sizes) when it completes. I would like to see if your results are similar to mine in this. BTW, many of my recent factorizations with Msieve LA/SR have taken several dependencies to complete. I don't remember this from the past, but maybe I was less aware of how long SR seems to take these days and perhaps I was factoring fewer composites then.
 2020-10-13, 21:10 #11 VBCurtis     "Curtis" Feb 2005 Riverside, CA 450610 Posts You can do a C125 by GNFS in about 4 hours on a desktop quad-core. ECM woudn't be helpful, since the original composite passed ECM pretesting at a much higher level than you'd typically try for a C125. I'd just let it run; 15-18 thread-hours for GNFS is likely more compute than a few more square roots.

 Similar Threads Thread Thread Starter Forum Replies Last Post wreck Msieve 15 2019-08-07 22:32 MARTHA Computer Science & Computational Number Theory 25 2018-11-27 23:38 paul0 Computer Science & Computational Number Theory 4 2015-01-09 14:57 RickC Hardware 8 2010-10-28 03:31 dsouza123 Math 2 2003-07-19 17:17

All times are UTC. The time now is 15:40.

Sat Dec 5 15:40:39 UTC 2020 up 2 days, 11:51, 0 users, load averages: 1.51, 1.78, 2.05