mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2016-12-04, 16:47   #1
chris2be8
 
chris2be8's Avatar
 
Sep 2009

29·67 Posts
Default 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
File Type: log ggnfs.log (77.5 KB, 215 views)
chris2be8 is offline   Reply With Quote
Old 2016-12-04, 18:37   #2
kurtb
 
"Beschorner Kurt"
Jul 2016
Germany

1316 Posts
Default

I guess: 380M - 420 M unique relations are necessary
Kurt
kurtb is offline   Reply With Quote
Old 2016-12-04, 18:52   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×19×241 Posts
Default

Welcome to the forum, Kurt!
Batalov is offline   Reply With Quote
Old 2016-12-05, 05:48   #4
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

63B16 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
jyb is offline   Reply With Quote
Old 2016-12-11, 16:58   #5
chris2be8
 
chris2be8's Avatar
 
Sep 2009

194310 Posts
Default

@jasonp: Any comments?

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

Chris
chris2be8 is offline   Reply With Quote
Old 2016-12-12, 11:34   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2017-02-05, 16:39   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

79716 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2017-02-06, 03:34   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2020-10-13, 20:22   #9
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

112458 Posts
Default

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
pinhodecarlos is online now   Reply With Quote
Old 2020-10-13, 21:09   #10
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

1101011101012 Posts
Default

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.
EdH is offline   Reply With Quote
Old 2020-10-13, 21:10   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,237 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:48.

Thu Nov 26 13:48:20 UTC 2020 up 77 days, 10:59, 3 users, load averages: 1.35, 1.31, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.