20050807, 19:02  #1 
Mar 2005
Poland
23_{16} Posts 
is GGNFS checking for SNFS number?
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^3712321) 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 
20050807, 20:37  #2 
"Nancy"
Aug 2002
Alexandria
2^{5}×7×11 Posts 
We've been thinking about something similar for GMPECM, 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 nonzero digits as c, see how often you can divide b out of Nc 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 nonunit k and c. Edit2: this will only detect numbers with positive c. For negative c, look for a lot of b1 digits in the middle. Neither will work if known factors have been divided out of N already. Last fiddled with by akruppa on 20050807 at 21:48 
20050808, 06:16  #3  
Oct 2004
tropical Massachusetts
3·23 Posts 
To Washuu's first question, the simple answer is "no". Or "only by accident". At least with "pol51m0b", it chooses nonmonic 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. Quote:
Quote:
 Sam 

20050808, 11:59  #4  
Mar 2005
Poland
5·7 Posts 
Quote:
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 

20050808, 12:30  #5  
Nov 2003
7232_{10} Posts 
Quote:
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? 

20050808, 17:28  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
27D2_{16} Posts 
Quote:
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 

20050808, 18:30  #7  
Mar 2005
Poland
5×7 Posts 
Quote:
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^1431 obvious poly could be f(x)=4*x^525, but a slightly less obvious would be f(x)=x^5200. 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 Last fiddled with by Washuu on 20050808 at 18:40 

20050808, 20:19  #8  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:


20050809, 00:09  #9  
Mar 2005
Poland
5·7 Posts 
Quote:
Washuu 

20050809, 07:53  #10  
"Sander"
Oct 2002
52.345322,5.52471
2245_{8} Posts 
Quote:


20050811, 05:09  #11 
Mar 2003
New Zealand
1157_{10} Posts 
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?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
checking very large number for primality.  WhoCares  Math  51  20170420 17:17 
Round Off Checking and Sum (Inputs) Error Checking  Forceman  Software  2  20130130 17:32 
Number of relations from ggnfs  Greebley  Msieve  2  20120305 21:56 
SNFS basics (ggnfs + factLat)  CRGreathouse  Factoring  4  20090525 08:05 
checking smaller number  fortega  Data  2  20050616 22:48 