Question: clarification about the LogBabyStepGianStepRatio parameter in LinearTransform

[LenaMartens]

Hi all,

According to the documentation:

// LogBabyStepGianStepRatio is the log2 of the ratio n1/n2 for n = n1 * n2 and
// n is the dimension of the linear transformation.

So the LogBabyStepGianStepRatio and n will determine the values of n1 and n2. I assume n1 is the baby-step dimension and n2 is the giant-step dimension, and are both integers.
I was wondering what the values of n1 and n2 will be if there are no n1 and n2 with this ratio where n1*n2==n.
eg. if we set LogBabyStepGianStepRatio=1 and n=16, the ratio between n1 and n2 should be 2, which is not possible for the integer divisors of 16. In this case will it be n1=8, n2=2 (ratio=4) or n1=4, n2=4 (ratio=1)?

Thanks!

[lehugueni]

Hi!

Indeed, I think the comment is a bit misleading. This value is used to find the maximal n1 s.t.
number of rotations in baby step / number of rotations in giant step <= 2^LogBabyStepGianStepRatio.

However, this does not only depend on the dimension of the linear transformation, but also on the indices of the non-zero diagonals of the linear transformation matrix. You can find the corresponding logic here:

lattigo/circuits/common/lintrans/lintrans.go

Line 321 in 84f6bc3

func FindBestBSGSRatio(nonZeroDiags []int, maxN int, logMaxRatio int) (minN int) {

Don't hesitate if you want further precision.

[LenaMartens]

Ah interesting, I hadn't considered it would consider the non-zero diagonal indices and how that affects the amount of rotations in the baby- and giant-step. That clarifies the code I found in FindBestBSGSRatio, thanks! I think this fully answers my question.