is GGNFS checking for SNFS number?

[Washuu]

Hi, quick questions for those familiar with polynomial selection tool in new GGNFS suite:

let's assume we have a general number N, that can be represented as SNFS k*x^p+c (example: 3049*1067^37-12321) But, somehow, user forgot to check this.

Can "polyselect" or "pol51m0b" find suitable polynomial for SNFS case? If the answer is: "only by accident", or "only with very small coefficients k,c of k*x^p+c" can you try to precise the conditions?

Maybe we can write some tool to check if the general number N is close to some power, or it's multiple, in some range of k,x,p,c?

In fact, I wrote such a procedure and seems to work (p<1024,k<2^18), hovewer it's very rough and stupid and without any smart optimisations, so I'd prefer not to share it yet. But another questions arises: Which one of the parameters is most important? For now it's sorting results by ascending c, dropping results when c > 10^10.

Washuu

[akruppa]

We've been thinking about something similar for GMP-ECM, so we can identify numbers suitable for George's DWT stage 1. I think writing numbers in base b, b=2,3,... might work.

After all, b^p = 100....00 in base b. Since c is likely going to be small, it will only affect the lowest couple of digits, and the multiplication by k will only affect the highest couple of digits.

So for b=2...(highest base you want to check), write N in base b (check Knuth vol.2 about how to do it quickly), see if there are a lot of zeros in the middle, if there are take the low non-zero digits as c, see how often you can divide b out of N-c to get p and take the remainder as k.

Alex

Edit: in fact, this is something that could go into phi.c. The code to tweak the poly coefficients should be general enough to handle non-unit k and c.
Edit2: this will only detect numbers with positive c. For negative c, look for a lot of b-1 digits in the middle. Neither will work if known factors have been divided out of N already.

[trilliwig]

To Washuu's first question, the simple answer is "no". Or "only by accident". At least with "pol51m0b", it chooses non-monic linear polynomials which I do believe will eliminate any reasonable possibility of finding simple polynomials for numbers of this form. I can't really give a better answer than that; the polynomial selection programs in GGNFS were never intended to check for SNFS numbers.

Second, I don't even think such a program would solve a real problem.

Originally Posted by Washuu

let's assume we have a general number N, that can be represented as SNFS k*x^p+c (example: 3049*1067^37-12321) But, somehow, user forgot to check this.

What conceivable circumstance could exist where the user would "forget"? If a user wants to factor a number, he or she should be intimately familiar with where it comes from! It's saner all around to write a program that parses "3049*1067^37-12321" as input and does the right thing automatically, than expecting the user to give the raw decimal expansion and expecting the program to figure out if a good SNFS polynomial exists for it.

Originally Posted by akruppa

this will only detect numbers with positive c. For negative c, look for a lot of b-1 digits in the middle. Neither will work if known factors have been divided out of N already.

That will be a fatal deficiency. The proper input value of N requires that all known factors be divided out. If this program is to have any hope of guessing if SNFS is possible on a particular N, it would need the algebraic form in addition to N, and the most convenient method of input should already tell the program everything it needs to know.

--
Sam

[Washuu]

Originally Posted by trilliwig

I don't even think such a program would solve a real problem.
What conceivable circumstance could exist where the user would "forget"? If a user wants to factor a number, he or she should be intimately familiar with where it comes from! It's saner all around to write a program that parses "3049*1067^37-12321" as input and does the right thing automatically, than expecting the user to give the raw decimal expansion and expecting the program to figure out if a good SNFS polynomial exists for it.

But there is always a chance (small, I know) that general number is close to some multiple of power of some number. Smart program could check this in seconds, and a prize (however not very likely) is pretty big: we can cut factorization time by 30%, I believe. And algorithm seems to be rather easy - why not to try?

And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.

BTW: I was thinking also about writing small program for optimal chosing of polynomial for SNFS, when we know algebraic form of the number. It seems to be not very difficult, and could be helpful for beginners - not everyone can see good polynomial in the first sight...
What do you think?

Regards,

Washuu

[R.D. Silverman]

Originally Posted by Washuu

But there is always a chance (small, I know) that general number is close to some multiple of power of some number. Smart program could check this in seconds, and a prize (however not very likely) is pretty big: we can cut factorization time by 30%, I believe. And algorithm seems to be rather easy - why not to try?

And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.

BTW: I was thinking also about writing small program for optimal chosing of polynomial for SNFS, when we know algebraic form of the number. It seems to be not very difficult, and could be helpful for beginners - not everyone can see good polynomial in the first sight...
What do you think?

Regards,

Washuu

Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?

[xilman]

Originally Posted by R.D. Silverman

Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?

Not trivial. put probably worth attempting, even if only as a learning exercise.

Even when one has considered all the ramifications, should that even be possible, one doesn't have to write a program that deals with every case. If 2,1450L turns out to be too hard, and I'm not claiming it is, a program that deals correctly with enough other interesting cases can still be very useful.

Some time ago I wrote a program to help maintain my factor tables. It deduces which table it may be processing by examining the first few lines of the table. It doesn't recognize all tables by any means, but because it recognizes Cunningham, BMtR, Cullen, Woodall, Generalized (Cullen&Woodall) and N!\pm1 I find it incredibly useful. Extending it to more cases will be straightforward if the need arises.

Rule of thumb: good may not be perfect, but can be useful.


Paul

[Washuu]

Originally Posted by R.D. Silverman

Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?

Hey, you are the master of poly selection! You tell me! :)

OK, seriously: I was only thinking about rather simple cases (at least in the beginning), for numbers like k*x^p+c. The program should make a few tests (about presence of Aurfeillian factors, for example), and try to compute some polynomials, and present the one with smallest coefficents. There are some tricks to do, and beginner not always can see it, and even more advanced (but still amateur) can miss, or simply miscalculate. (I can for sure).
Simple example from ggnfs doc: for N=16*10^143-1 obvious poly could be f(x)=4*x^5-25, but a slightly less obvious would be f(x)=x^5-200. Newbie can easily miss this, and amateur should check if his poly is good enough. (Experts can manage by themselves.) :)

As for program checking for "closeness" of N to some multiple of some power of some number :), I also would ask you about advice, what "closeness" condition should be. I thought about range of k,c<10^((logN)/10), so for n=10^120 cutoff point would be at 10^12.

For now, I have got mainly ideas, and want to listen what others are thinking and advicing. If someone wants to write such a program, you are very welcome, I am not good at it.

Washuu

[smh]

Originally Posted by Washuu

And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.

I guess he is doing a General Cullen/Woodall numbers? What number is he doing? I've done all remaining with SNFS difficulty below 153 and currently doing the smallest available composite (c111) by GNFS. Planning to do a few more general numbers <115 digits so i would like to avoid duplication.

[Washuu]

Originally Posted by smh

I guess he is doing a General Cullen/Woodall numbers? What number is he doing? I've done all remaining with SNFS difficulty below 153 and currently doing the smallest available composite (c111) by GNFS. Planning to do a few more general numbers <115 digits so i would like to avoid duplication.

It was for sure >C115, something about C120, maybe C119 or C121, don't quite remember now, hovewer when we calculated the time we used approx. data for C120 (and calculated that whole factorization will take about 120 hrs, so 30% will be less than 48hrs, for his computer, so starting again won't be faster at this point). I will ask him tomorrow, and let you know in priv.

Washuu

[smh]

It was for sure >C115, something about C120

Great. I plan to work my way up the smallest composites, so please let me know if you do anything < 115 digits

[geoff]

Is it possible to calculate a Murphy_E score for a SNFS polynomial and compare it to the score for a GNFS polynomial as given by pol51opt?