Timeline for Question about degree of regularity
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2019 at 19:34 | comment | added | Partha | I am reading the first paper that you cited, and it deals with a lot of the questions that I asked. Again, thanks a lot for the papers and your follow-up comments! | |
| Jan 12, 2019 at 19:32 | vote | accept | Partha | ||
| Jan 12, 2019 at 0:05 | comment | added | Alan | Your interpretation of the empirical test is exactly correct. For small but growing parameters you can plot the theoretical degree of regularity and the observed one, and extrapolate from there. In my experience, there tends to be a linear relation. However, that might depend on the type of polynomial system in question. | |
| Jan 11, 2019 at 23:58 | comment | added | Alan | I do not think this bound is tight. However, the paper by Bardet that you cite seems to contradict my intuition. It states that the degree of regularity is the maximal degree in the Gröbner basis for grevlex order (i.e. the standard degree-refining order). I am not sure how to validate or refute this claim. Certainly, Magali Bardet is a better authority than I am :) | |
| Jan 11, 2019 at 23:52 | comment | added | Alan | Yes, the degree of regularity, defined via the Hilbert function, is an upper bound on the degrees of polynomials in the Gröbner basis for degree-refining term orders. If the Gröbner basis had polynomials of higher degree, then they would not be found by a Gröbner basis algorithm that only processes polynomials of strictly lower degree, thereby disqualifying that algorithm from being a Gröbner basis algorithm. | |
| Jan 11, 2019 at 23:41 | history | edited | Alan | CC BY-SA 4.0 |
1. [...] degree *of regularity* of the resulting [...]
|
| Jan 10, 2019 at 21:24 | comment | added | Partha | So, when you say I should empirically check for small parameters, you are saying - take the theoretical estimates for semi-regular systems of the same degrees, no. of variables and run some experiments on my own system instances and check how the highest degrees of the GBs compare? | |
| Jan 10, 2019 at 21:24 | comment | added | Partha | If I could bother you just a little bit more, I wanted to ask you if my understanding is correct. So when dealing with MQ based cryptosytems (semi-regular or not), the index/degree of regularity (defined as smallest d when Hilbert function equals Hilbert Polynomial) is what determines the difficulty of calculating GB. This degree of regularity is also an upper bound (but perhaps not tight?) on the largest degree of its GB? | |
| Jan 10, 2019 at 21:09 | comment | added | Partha | Thanks for the links. I had seen a previous answer by you on a similar question which was also very helpful to me. | |
| Jan 10, 2019 at 19:42 | history | answered | Alan | CC BY-SA 4.0 |