20161204, 16:47  #1 
Sep 2009
2^{2}×3×167 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 rerunning filtering etc be likely to work? Chris 
20161204, 18:37  #2 
"Beschorner Kurt"
Jul 2016
Germany
14_{16} Posts 
I guess: 380M  420 M unique relations are necessary
Kurt 
20161204, 18:52  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
19·491 Posts 
Welcome to the forum, Kurt!

20161205, 05:48  #4  
Aug 2005
Seattle, WA
2×3^{3}×31 Posts 
Quote:
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. 

20161211, 16:58  #5 
Sep 2009
2^{2}×3×167 Posts 
@jasonp: Any comments?
I've still got the dat file etc if you want them to help you investigate. Chris 
20161212, 11:34  #6 
Tribal Bullet
Oct 2004
2·3·19·31 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.

20170205, 16:39  #7 
Sep 2009
2^{2}·3·167 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 15digit factors Sat Feb 4 22:36:15 2017 commencing number field sieve (106digit 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.334e13, alpha 0.020, combined = 2.911e08 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 have the relations any more, my script deleted them since it successfully factored the number. Chris 
20170206, 03:34  #8 
Tribal Bullet
Oct 2004
2×3×19×31 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 
20201013, 20:22  #9 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
5×7×139 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 
20201013, 21:09  #10 
"Ed Hall"
Dec 2009
Adirondack Mtns
3632_{10} 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. 
20201013, 21:10  #11 
"Curtis"
Feb 2005
Riverside, CA
1243_{16} Posts 
You can do a C125 by GNFS in about 4 hours on a desktop quadcore. 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; 1518 threadhours for GNFS is likely more compute than a few more square roots. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
NFS Square Root failed  wreck  Msieve  15  20190807 22:32 
Difference of Square Roots  MARTHA  Computer Science & Computational Number Theory  25  20181127 23:38 
Ring Square Roots in NFS  paul0  Computer Science & Computational Number Theory  4  20150109 14:57 
Can an OS config be OK after RAM failed?  RickC  Hardware  8  20101028 03:31 
Identifing perfect squares and calculating square roots..  dsouza123  Math  2  20030719 17:17 