Question about fftInv and fftSpecialInv

snucrypto / HEAAN

Other

359 stars 94 forks source link

Question about fftInv and fftSpecialInv #5

Closed fionser closed 6 years ago

fionser commented 6 years ago

Hi, I have a question about the fftInv and fftSpecialInv;

Why bitReverse is placed differently in these two methods: fftInv call bitReverse after the butterfly steps while fftSpecialInv call before the butterfly steps;

kimandrik commented 6 years ago

Hello, fftInv is a real fff inverse transformation, and ffiSpecialInv is an embedding transformation (may be we should rename this function to avoid misunderstandings). For embedding transformation the method is a little bit different from fft

fionser commented 6 years ago

@kimandrik In my understanding, the specialized operations are used for rotating embedded values; do the order of bitReverse matters in the fftSpecialnv ?

kimandrik commented 6 years ago

The specialized operations are used to encode/decode the array of values to/from the polynomial. I'm not sure about the possible position of bitReverse. We found a method to evaluate fftSpecialInv, and it works. Maybe you can find another method of evaluating this specialized transformation when bitReverse operation is called after butterfly steps.