search

fplll / g6k

The General Sieve Kernel
GNU General Public License v2.0
99 stars 30 forks source link

Ask for an explanation of the "saturation condition" #99

Closed Summwer closed 2 years ago

Summwer commented 3 years ago

Hello, developer, while I try to solve an lwe instance, and find the following output.

Warning: Triple sieve exceeded maximum number of resorts
Warning: Saturation condition could not be reached during triplesieve.
root: saturation 0.489 at [b:84 P: 87 - 171 / 226], radius 1.333, goal: 0.500
root: Could not reach saturation, progress may slow.

May I ask what does it mean? What is the implication of "saturation condition" it mentioned? Why will it become slow when the actual saturation is lower than the goal saturation? And how could I do something to reach the expected saturation? Moreover, I want to ask about the reference of the saturation selection since I have not even solve my obstacle of lwe instance in 225 dimension over one week, and want to ask about whether it could be improved in some way？

And hope a response, thanks for reading~

lducas commented 2 years ago

Saturation issues remain mysterious to us as well, and occur in specific scenario indeed. We have not found a satisfying solution to the issue.