View Single Post
Old 2021-05-30, 14:47   #4
VBCurtis's Avatar
Feb 2005
Riverside, CA

2·11·227 Posts

For your proth searches, you want to write your input number as a * (x^5) + c.
Then c5 = a, c0 = c, y1 = 1, y0 = x (I forget if it's positive or negative).

5th degree polys are best for roughly 120 to 200 digits; above 200 digits you would use the same concept but a 6th degree polynomial. There's a gray area where you might test both 5th and 6th degree.

So, say you want to factor 13*2^698 + 1.
698 is close to 700, so multiplying my input by 4 gives me 13*2^700 + 4.
My poly would be 13*(2^140)^5 + 4, so c5 = 13, c0 = 4, and y0 = 2^140.

For 13*2^697+1, I would take out 2 2's from the large power, making 52*2^695+1. c5=52, c0 = 1, y0=2^139.

In your efforts, since your leading coefficient is already large, you won't want to pull out 2's in this manner- rather, you'll use the first style to make c0 bigger rather than making c1 bigger. SNFS difficulty is mostly linked to the size of the largest poly coefficient, so you want to avoid making c5 bigger.

I use wolfram alpha to get the expansions of large powers of 2.

The reference sites mentioned in earlier posts are much more detailed, but I thought maybe a concrete example would be of use.
VBCurtis is offline   Reply With Quote