mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2017-05-17, 21:20   #1
sean
 
sean's Avatar
 
Aug 2004
New Zealand

3418 Posts
Default SNFS of C112 cofactor of 608^60+480^76

I've been trying to complete 608^60+480^76 by SNFS using yafu. I first took out the obvious 2^300, then generated a degree 5 polynomial from (19^12)^5+15(2^16 * 5^75)^5. There is also a small factor 193. My input looks like:

Code:
n: 1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657
m: 938653510572529699833798948683334366050403278236720135828886826556700342961769485489321955075594682751310365305
deg: 5
skew: 1.718
type: snfs
c5: 1
c0: 15
Y0: -2213314919066161
Y1: 28697814000000000000000
rlim: 588500
alim: 588500
lpbr: 25
lpba: 25
mfbr: 47
mfba: 47
rlambda: 2.3
alambda: 2.3
When I run yafu, sieving appears to proceed well with good yield etc. Yet when it gets to filtering things go awry, the nfs.log is full of messages like

Code:
Wed May 17 20:14:24 2017  error -11 reading relation 0
Wed May 17 20:14:24 2017  error -11 reading relation 1
Wed May 17 20:14:24 2017  error -11 reading relation 2
...
My first thought was that there must have been some corruption of files left over from a previous run. So I repeated the whole thing in a clean directory and the same thing happened. It only takes half an hour or so do the sieving. My next suspicion is that there is something wrong with my polynomials. Any ideas?
sean is offline   Reply With Quote
Old 2017-05-17, 21:42   #2
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

23×431 Posts
Default

Quote:
Originally Posted by sean View Post
My first thought was that there must have been some corruption of files left over from a previous run. So I repeated the whole thing in a clean directory and the same thing happened. It only takes half an hour or so do the sieving. My next suspicion is that there is something wrong with my polynomials. Any ideas?
In the second term 480 = 2^5 * 3 * 5.
It appears you forgot the 3^75.

Edit: Actually it should be 3^15 * 5^15 if raised to the fifth power.

Last fiddled with by RichD on 2017-05-17 at 21:44
RichD is offline   Reply With Quote
Old 2017-05-17, 21:47   #3
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Default

Quote:
Originally Posted by RichD View Post
In the second term 480 = 2^5 * 3 * 5.
It appears you forgot the 3^75.

Edit: Actually it should be 3^15 * 5^15 if raised to the fifth power.
Ugh! Sorry, that was typo in my explanation, that should read (19^12)^5+15(2^16 * 15^15)^5, giving
2^16*15^15 = 28697814000000000000000.

So although my formula in explanation was wrong, I think I have the correct value in my polynomial.
sean is offline   Reply With Quote
Old 2017-05-17, 21:50   #4
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

23·431 Posts
Default

After further review, I think it should be 2^30 * 15^15.

Edit: Never mind. I can't do math. You are correct.

Last fiddled with by RichD on 2017-05-17 at 22:03
RichD is offline   Reply With Quote
Old 2017-05-17, 22:07   #5
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Default

Quote:
Originally Posted by RichD View Post
After further review, I think it should be 2^30 * 15^15.
Thanks for your time looking at this, but 2^30 * 15^15 doesn't work: not a common root of the polynomial.

How did you get 2^30?

I'm seeing it like this 480^76 = 2^(5*76) * 3^76 * 5^76. Then remove 2^300, to get 2^80*3^76*5^76 = 15*(2^16*15^15)^5.
sean is offline   Reply With Quote
Old 2017-05-17, 23:10   #6
swellman
 
swellman's Avatar
 
Jun 2012

320310 Posts
Default

You could let Yafu choose the poly automatically, for comparison purposes. It will almost certainly choose the same poly as you but adds parameters etc as required by yafu for sieving. Maybe something will show up that is missing, like "size:" (I don't think yafu requires that parameter but I'm not sure). It is missing from your nfs.job file.

Code:
nfs(1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657) -v
swellman is online now   Reply With Quote
Old 2017-05-17, 23:22   #7
sean
 
sean's Avatar
 
Aug 2004
New Zealand

22510 Posts
Default

Quote:
Originally Posted by swellman View Post
You could let Yafu choose the poly automatically, for comparison purposes. It will almost certainly choose the same poly as you but adds parameters etc as required by yafu for sieving. Maybe something will show up that is missing, like "size:" (I don't think yafu requires that parameter but I'm not sure). It is missing from your nfs.job file.

Code:
nfs(1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657) -v
If I try the above, yafu starts searching for a polynomial as a GNFS job. I know that wouldn't take that long for this number, but I'm curious why the SNFS approach is not working.

I've done a bunch of somewhat similar cases without problem, but there must be something unusual or special about this one or some error I've made in my polynomials. I have yafu, v1.34.5.
sean is offline   Reply With Quote
Old 2017-05-17, 23:41   #8
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

23×431 Posts
Default

I removed the parameters and ran the poly through factMsieve and it factored it into p44 * p68. factMsieve used similar parameters so nothing wrong with the poly.

If you want the solution I can post to FDB but I'm sure you want to solve the problem resolve the issues because you may have other similar numbers of this size.

Last fiddled with by RichD on 2017-05-17 at 23:48 Reason: clarification
RichD is offline   Reply With Quote
Old 2017-05-17, 23:43   #9
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

Yeah I guess your composite is not derived from the forms yafu checks during SNFS poly selection, so it defaults to GNFS.

Well if your poly was incorrect yafu would quickly crash. Since that is not happening, the poly works. The only thing missing is a line

size: 200 (or whatever the difficulty is for this composite).

Try adding the size?

Also, you don't need deg: 5. Yafu probably ignores it, but maybe it's causing problems?

ETA: the recent ggnfs sievers sometimes act strangely for me when I do small jobs like this. Maybe try with an older version of ggnfs?

Last fiddled with by swellman on 2017-05-17 at 23:46
swellman is online now   Reply With Quote
Old 2017-05-18, 01:34   #10
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Default

Quote:
Originally Posted by RichD View Post
I removed the parameters and ran the poly through factMsieve and it factored it into p44 * p68. factMsieve used similar parameters so nothing wrong with the poly.

If you want the solution I can post to FDB but I'm sure you want to solve the problem resolve the issues because you may have other similar numbers of this size.
Thanks for that. I've now replicated the run using factMsieve (I'd never used that before) and was able to factor as you indicated.

I tried various other things around the job file for yafu, including the suggestions of swellman, but I still couldn't get it to work -- and I'm sick of trying various combinations now. Since both are pointing at the same underlying siever, I can only assume it must be some issue with the filtering in yafu.

I've actually found a second case where yafu does the same thing, so I will try doing that one with factMsieve as well.
sean is offline   Reply With Quote
Old 2017-05-18, 02:15   #11
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

This is a puzzling bug. I'll try to duplicate it tomorrow once I'm back in front of a computer.

I've got a bunch of computers with different versions of yafu, giving a nice cross section of environments. Maybe something will turn up.

Have you tried compiling the dev branch of yafu discussed here? Apparently a lot of bugs fixed, maybe this one too?

Last fiddled with by swellman on 2017-05-18 at 02:15
swellman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cofactor Search carpetpool Information & Answers 4 2016-12-12 04:35
122^99+99^122 cofactor, matrix not dense enough, retrying pinhodecarlos NFS@Home 2 2016-10-18 17:43
Formula for cofactor for Fermat numbers. literka Factoring 7 2012-04-05 09:51
Polynomial search for 204-digit cofactor of M1009 fivemack Factoring 45 2012-02-14 08:50
Certification of a 10064 bit prp cofactor MatWur-S530113 PrimeNet 9 2010-02-16 12:52

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


Thu Oct 21 13:09:54 UTC 2021 up 90 days, 7:38, 1 user, load averages: 1.50, 1.42, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.