View Single Post
Old 2019-05-16, 20:06   #11
bsquared's Avatar
Feb 2007

357810 Posts

Originally Posted by henryzz View Post
The aim with SIQS is to make switching polynomial very fast such that many more polynomials can be used than MPQS. However, I believe that my implementation still spends 10% of its time switching A.
Is that time spent just building new A polys or does it also include setup time for the new poly (e.g., computing A^-1 mod p for all factor base p)? 10% seems high either way but if that's just for building new A polys then it seems *really* high. In contrast I usually spend < 3% total for building new A's and all of the setup for new A's.

Originally Posted by henryzz View Post
At 50 digits I use about 11 As. This increases rapidly from here as numbers get bigger. Unless you are spending all your time generating them I wouldn't worry about having a few As. Each A had 6 factors allowing for 64 Bs per A .
Seems reasonable given your other parameters. I typically see anywhere from 50 to 150 A's at 50 digits, using 6 factors per A, but I use a far smaller factor base and sieve interval. It is all a tradeoff.

Originally Posted by tabidots View Post

So my basic question is, what kind of gotchas should I look for with the polynomials to make sure they can capture as many smooth relations as possible? I have already verified that b^2 or (a - b)^2 is congruent to N mod a for each b.
I would ask, how are you determining smoothness exactly? In other words, the sieve value above (or below) which you try to find a relation. If your polynomials and roots are good then maybe it is as simple as tweaking your smoothness bound so as to generate more potential relation reports.

The value I use is obtained from a bunch of empirically determined magic numbers, loosely related to Contini's suggestion along the lines of:
"compute the number of bits in M/2*sqrt(N/2), then subtract some slack". M is the size of your sieve interval.
bsquared is offline   Reply With Quote