Choosing the best polynomial

[R.D. Silverman]

Originally Posted by Batalov

Good news! RSA-210 is not squareful.

Well, it's old news, but relevant to RSA-210 factoring ...or not. ;-)

I believe that I have said this. Multiple times in multiple public forums.

[wombatman]

Curtis,

Did your -nps step run a fair bit slower with 6th degree polynomials compared to 5th degree? I'm used to it screaming with CUDA, but the lines are basically ticking by.

[VBCurtis]

nps does not run on CUDA; only stage 1 runs on the video card. I'm getting 2-3 a second with a laptop i7 running 6 other threads; I have never run nps on anything else, so I have no speed to compare it to. With my stage 1 norm at 6e25, nps takes longer to run than np1; I have two separate processes running nps. When I had the norm at 5e25, fewer hits were generated so nps was about the same speed as np1.

Every poly with score better than 5.50 has come from stage 2 norm below 2e26, and I have dozens at that size per day to run npr on, so I'm only running npr on hits below 3e26.
-Curtis

[wombatman]

Hmm...ok, then I don't feel so bad about my speeds. When you say you're running nps in two threads, do you mean for the same file? Or for two separate files?

[VBCurtis]

I am stopping my GPU run a couple times a day, changing the min-coeff to whatever the previous run ended at, and restarting with a -s newfilename. Each time I do that, I start -nps on the previous filename, and -npr in a 3rd terminal whenever I'm around to watch it run 'cause it's fun.

So, when I mentioned the "speed" of -nps, I was talking about that terminal's ability to finish its task before I next reset the GPU window's process.

Each of these ~8hr GPU-time files has produced polys at score 5.7 or better, with about a dozen over 6.0 so far. I only have -npr output polys above 5e-16, so that the screen output is of some interest.

Note I am being detailed mostly so that the experts can tell me if I'm doing something incorrectly- such as Jason chiming in that my stage 1 norm was too low, restricting the search space per coeff unnecessarily.
-Curtis

[xilman]

Originally Posted by R.D. Silverman

I believe that I have said this. Multiple times in multiple public forums.

Sure, and everyone believes you.

The reported result, as I understand it, is that they have proved the claim. It is analogous to the difference between an integer not failing dozens of Miller-Rabin tests (or even one for that matter) and providing a ECPP certificate to prove that the integer is prime.

[jasonp]

Originally Posted by VBCurtis

Note I am being detailed mostly so that the experts can tell me if I'm doing something incorrectly- such as Jason chiming in that my stage 1 norm was too low, restricting the search space per coeff unnecessarily.

Much of this is new territory for me too, but it doesn't sound like you're doing anything wrong.

Stage 2 for degree 5 polynomials is pretty straightforward and runs quickly. Stage 2 for degree 6 polynomials is a bear, and is very slow; the size optimization is very numerically unstable, and the search space for improving the root score is enormous. Conversely, many degree 5 polynomials can have their size optimized enough that it makes sense to optimize the root score. For degree 6, very very few polynomials achieve a good enough size, and the number of successes drops exponentially as N becomes larger.

More details here

[wombatman]

Originally Posted by VBCurtis

I am stopping my GPU run a couple times a day, changing the min-coeff to whatever the previous run ended at, and restarting with a -s newfilename. Each time I do that, I start -nps on the previous filename, and -npr in a 3rd terminal whenever I'm around to watch it run 'cause it's fun.

So, when I mentioned the "speed" of -nps, I was talking about that terminal's ability to finish its task before I next reset the GPU window's process.

Each of these ~8hr GPU-time files has produced polys at score 5.7 or better, with about a dozen over 6.0 so far. I only have -npr output polys above 5e-16, so that the screen output is of some interest.

Note I am being detailed mostly so that the experts can tell me if I'm doing something incorrectly- such as Jason chiming in that my stage 1 norm was too low, restricting the search space per coeff unnecessarily.
-Curtis

Ah! That's a great idea, and one that I will be using as well! Jason, thanks as well for your further explanation on the degree 5/degree 6 difference.

[wombatman]

Better late than never, I suppose. Here's the best result from a coefficient range from 1 to ~1,000,000. I'm still working on a higher coefficient range (3,000,000+), but the alpha on this was so good, I figured I would share:

R0: -24817559944241631757129134224570832
R1: 85250930370400571
A0: 66264829651472705954641834109195675572029672125
A1: 208388337312553419577559442375988133407800
A2: -612705429478275985972934799043948930
A3: -9993800213457872775328448574
A4: 35662049466686876853605
A5: 186928192386294
A6: 372240
skew 7909212.49, size 1.300e-015, alpha -10.287, combined = 5.551e-016 rroots = 4

E-value is pretty much the same, but the alpha is way better (I think?).

[jasonp]

The alpha is better but the size score is worse. This is pretty typical when a polynomial search is just starting: you get lucky with the alpha because it's a separate roll of the dice, but wait long enough and you'll find a polynomial that has almost the best alpha combined with almost the best size. That one will be the best overall.

[wombatman]

Ah, ok. Thanks!