View Single Post
Old 2005-08-08, 12:30   #5
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

11101001001002 Posts
Thumbs up

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?



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?
R.D. Silverman is offline   Reply With Quote