Algebraic side not a square

[bur]

I ran into a strange problem with msieve, square root failed with an error about "negative leading coefficient". Apparently the only workaround is to change the sign of all coefficients in .fb and rerun -nc3.

Unfortunately this gives me algebraic side is not a square! errors. Do I have to rerun the whole LA?

[chris2be8]

Please post the failing .fb here. And the full text of the error messages.

I hit this once and managed to fix it by changing the signs of all the coefficients. But I can't remember if I had to change the signs of R0 and R1 as well.

Chris

[VBCurtis]

This happens somewhat often when using CADO to poly select and sieve, but msieve for post-processing. CADO doesn't care if the leading coeff is negative, but msieve does.

That's just to say this is a known issue- Chris has the same suggestions I have.

[bur]

With all the changing I managed to end up with a rels.mat of size 0, I can't say for sure whether that was the problem from the beginning. I thought I saved all files, but even the saved matrix has 0 file size.

So now I'm running the whole -nc again. This time with changed signs (incl. R#) at all steps, not just for square root. I hope that isn't a problem, the matrix build well though.


The initial error message at square root step was just cannot handle negative leading algebraic polynomial coefficient. The next one was algebraic side is not a square! but for now I'd disregard that as maybe being part of my screwing up the files.



Modified c160.fb (all signs changed)

N 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889
R0 -7698967607232752087818786728770
R1 161284160064118998521987
A0 4135620860504355622499174259170049420
A1 -24531502056077805025989666373431
A2 -123052303382820975668065696
A3 13397578100486512027
A4 9522226167600
A5 478800

[charybdis]

Originally Posted by bur

N 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889

Factordb tells me this is a factor of the 163-digit number 2^520*1281979+1. This is a very easy SNFS, roughly equivalent to 120-digit GNFS, with algebraic polynomial 1281979x^5+1 and rational polynomial x-2^104:

N: 615852095139018818180740532155742854813285752039357209617222174313731523072704248288595303399267379211703243385678043310396893565702501281889421988426549324889
skew: 0.060038
c5: 1281979
c4: 0
c3: 0
c2: 0
c1: 0
c0: 1
Y1: 1
Y0: -20282409603651670423947251286016

Edit: if you want to try this out with CADO, use the same parameters as for a c120 GNFS but with tasks.sieve.sqside = 0 and all the rational and algebraic side parameters flipped, that is, swap tasks.lim0 with tasks.lim1, tasks.sieve.mfb0 with tasks.sieve.mfb1 and so on. This won't be optimal but should be better than just using normal GNFS-120 parameters.

[bur]

edit: since it's off-topic in this thread, I opened a new one: https://mersenneforum.org/showthread.php?t=26852






I knew one day this would happen... I always wanted to get into the differences between SNFS and GNFS, now it's apparent why.


How can I find out if SNFS can be used? Here it seems to be the case because exponent n can be divided by 5? Is it always like that in base 2? Furthermore, the way you write, it seems like CADO isn't the best choice for SNFS? So how should it be done?


Basically, my question is, how do I identify SNFS candidates among Proth/Riesel numbers and with which software should they be factorized?



Btw, for the original question of this thread, the GNFS factorization finished succesfully with changing the sign of all (incl R#) coefficients. I ran filtering/LA/square root all with the modified fb file. Now I just need to come up with a script that notices such polynomials and modifies them. I guess sed can do it... :)