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

I guess: 380M - 420 M unique relations are necessary
Kurt

Welcome to the forum, Kurt!

[QUOTE=chris2be8;448354]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[/QUOTE]

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.

@jasonp: Any comments?

I've still got the dat file etc if you want them to help you investigate.

Chris

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.

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 [B]initial square root is modulo 101[/B]
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
[/code]
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

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

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]

[CODE]http://factordb.com/index.php?query=227289709170775626007585710867309934693162572916668346006138666559388922469472389295406521342510427966571237053766292936031495286594901935034616836180690107776493460879759323119637541757189[/CODE]

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.

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.

[B]VBCurtis[/B] is correct, GNFS would be pretty quick. You're almost there with the sqrt.

You can run the sqrt in parallel if you have idle cores. Something like:
[CODE]./msieve -nc3 11,13
./msieve -nc3 14,16
./msieve -nc3 17,19
...[/CODE]
You might want to use a different folder for each or point them to a different log file so you won't intersperse the output of each run.

[QUOTE=RichD;559795]You can run the sqrt in parallel if you have idle cores. Something like:
[CODE]./msieve -nc3 11,13
./msieve -nc3 14,16
./msieve -nc3 17,19
...[/CODE]You might want to use a different folder for each or point them to a different log file so you won't intersperse the output of each run.[/QUOTE]Interesting!

:tu:

Thanks guys, my message was before going to bed so I left msieve running, results here: [url]https://www.mersenneforum.org/showpost.php?p=559831&postcount=33[/url]