View Single Post
Old 2005-08-08, 11:59   #4
Mar 2005

3510 Posts

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?


Washuu is offline   Reply With Quote