View Single Post
Old 2005-08-08, 06:16   #3
trilliwig's Avatar
Oct 2004
tropical Massachusetts

10001012 Posts

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.

trilliwig is offline   Reply With Quote