All square roots failed

chris2be8 · 2016-12-04, 16:47

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

kurtb · 2016-12-04, 18:37

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

Batalov · 2016-12-04, 18:52

Welcome to the forum, Kurt!

jyb · 2016-12-05, 05:48

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.

chris2be8 · 2016-12-11, 16:58

@jasonp: Any comments?

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

Chris

jasonp · 2016-12-12, 11:34

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.

chris2be8 · 2017-02-05, 16:39

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

jasonp · 2017-02-06, 03:34

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

pinhodecarlos · 2020-10-13, 20:22

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

EdH · 2020-10-13, 21:09

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.

VBCurtis · 2020-10-13, 21:10

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
NFS Square Root failed	wreck	Msieve	15	2019-08-07 22:32
Difference of Square Roots	MARTHA	Computer Science & Computational Number Theory	25	2018-11-27 23:38
Ring Square Roots in NFS	paul0	Computer Science & Computational Number Theory	4	2015-01-09 14:57
Can an OS config be OK after RAM failed?	RickC	Hardware	8	2010-10-28 03:31
Identifing perfect squares and calculating square roots..	dsouza123	Math	2	2003-07-19 17:17

2016-12-04, 18:37	#2
kurtb "Beschorner Kurt" Jul 2016 Germany 14₁₆ 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 19·491 Posts	Welcome to the forum, Kurt!

2016-12-11, 16:58	#5
chris2be8 Sep 2009 2²×3×167 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 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.

2017-02-06, 03:34	#8
jasonp 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

2020-10-13, 21:09	#10
EdH "Ed Hall" Dec 2009 Adirondack Mtns 3632₁₀ 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 1243₁₆ 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.