intt_n256_l8_s32_mont.s

///
/// Copyright (c) 2021 Arm Limited
/// Copyright (c) 2022 Hanno Becker
/// Copyright (c) 2023 Amin Abdulrahman, Matthias Kannwischer
/// SPDX-License-Identifier: MIT
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to deal
/// in the Software without restriction, including without limitation the rights
/// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
/// copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all
/// copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
/// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
/// SOFTWARE.
///

#define INVNTT_REDUCE_AFTER_L56
#define INVNTT_REDUCE_AFTER_L34

.data
roots_inv:
// block
.word   20558213 // zeta^510 * 2^31 = 28678040^510 * 2^31
.word   66424611 // zeta^382 * 2^31 = 28678040^382 * 2^31
.word   59465515 // zeta^446 * 2^31 = 28678040^446 * 2^31
.word   39560591 // zeta^318 * 2^31 = 28678040^318 * 2^31
// block twisted
.word 2042724475 // zeta^510 * (q^(-1) mod 2^32) * 2^31 = 28678040^510 * 375649793 * 2^31
.word 2817904349 // zeta^382 * (q^(-1) mod 2^32) * 2^31 = 28678040^382 * 375649793 * 2^31
.word 2405453525 // zeta^446 * (q^(-1) mod 2^32) * 2^31 = 28678040^446 * 375649793 * 2^31
.word 2621436017 // zeta^318 * (q^(-1) mod 2^32) * 2^31 = 28678040^318 * 375649793 * 2^31
// block
.word   35339857 // zeta^511 * 2^31 = 28678040^511 * 2^31
.word   13377101 // zeta^447 * 2^31 = 28678040^447 * 2^31
.word   33252123 // zeta^479 * 2^31 = 28678040^479 * 2^31
.word   16713319 // zeta^415 * 2^31 = 28678040^415 * 2^31
// block twisted
.word 3232754607 // zeta^511 * (q^(-1) mod 2^32) * 2^31 = 28678040^511 * 375649793 * 2^31
.word 2219762611 // zeta^447 * (q^(-1) mod 2^32) * 2^31 = 28678040^447 * 375649793 * 2^31
.word 3344411365 // zeta^479 * (q^(-1) mod 2^32) * 2^31 = 28678040^479 * 375649793 * 2^31
.word 2600796057 // zeta^415 * (q^(-1) mod 2^32) * 2^31 = 28678040^415 * 375649793 * 2^31
// block
.word   10815985 // zeta^383 * 2^31 = 28678040^383 * 2^31
.word   56247925 // zeta^319 * 2^31 = 28678040^319 * 2^31
.word   26943959 // zeta^351 * 2^31 = 28678040^351 * 2^31
.word   51316823 // zeta^287 * 2^31 = 28678040^287 * 2^31
// block twisted
.word 3650773007 // zeta^383 * (q^(-1) mod 2^32) * 2^31 = 28678040^383 * 375649793 * 2^31
.word 4021439371 // zeta^319 * (q^(-1) mod 2^32) * 2^31 = 28678040^319 * 375649793 * 2^31
.word 1538999337 // zeta^351 * (q^(-1) mod 2^32) * 2^31 = 28678040^351 * 375649793 * 2^31
.word 3611844009 // zeta^287 * (q^(-1) mod 2^32) * 2^31 = 28678040^287 * 375649793 * 2^31
// block
.word   42042379 // zeta^478 * 2^31 = 28678040^478 * 2^31
.word   26419651 // zeta^350 * 2^31 = 28678040^350 * 2^31
.word   61522009 // zeta^414 * 2^31 = 28678040^414 * 2^31
.word   23758817 // zeta^286 * 2^31 = 28678040^286 * 2^31
// block twisted
.word 2254105077 // zeta^478 * (q^(-1) mod 2^32) * 2^31 = 28678040^478 * 375649793 * 2^31
.word 3415374909 // zeta^350 * (q^(-1) mod 2^32) * 2^31 = 28678040^350 * 375649793 * 2^31
.word 3742677415 // zeta^414 * (q^(-1) mod 2^32) * 2^31 = 28678040^414 * 375649793 * 2^31
.word 3187687967 // zeta^286 * (q^(-1) mod 2^32) * 2^31 = 28678040^286 * 375649793 * 2^31
// block
.word   35776599 // zeta^495 * 2^31 = 28678040^495 * 2^31
.word    6731445 // zeta^431 * 2^31 = 28678040^431 * 2^31
.word    3030459 // zeta^463 * 2^31 = 28678040^463 * 2^31
.word   41085059 // zeta^399 * 2^31 = 28678040^399 * 2^31
// block twisted
.word  351632809 // zeta^495 * (q^(-1) mod 2^32) * 2^31 = 28678040^495 * 375649793 * 2^31
.word  369646411 // zeta^431 * (q^(-1) mod 2^32) * 2^31 = 28678040^431 * 375649793 * 2^31
.word 2670661701 // zeta^463 * (q^(-1) mod 2^32) * 2^31 = 28678040^463 * 375649793 * 2^31
.word 1702245757 // zeta^399 * (q^(-1) mod 2^32) * 2^31 = 28678040^399 * 375649793 * 2^31
// block
.word    6685305 // zeta^367 * 2^31 = 28678040^367 * 2^31
.word   24840267 // zeta^303 * 2^31 = 28678040^303 * 2^31
.word   21119839 // zeta^335 * 2^31 = 28678040^335 * 2^31
.word   32376869 // zeta^271 * 2^31 = 28678040^271 * 2^31
// block twisted
.word 2658056071 // zeta^367 * (q^(-1) mod 2^32) * 2^31 = 28678040^367 * 375649793 * 2^31
.word  495707573 // zeta^303 * (q^(-1) mod 2^32) * 2^31 = 28678040^303 * 375649793 * 2^31
.word  440627873 // zeta^335 * (q^(-1) mod 2^32) * 2^31 = 28678040^335 * 375649793 * 2^31
.word 3991890395 // zeta^271 * (q^(-1) mod 2^32) * 2^31 = 28678040^271 * 375649793 * 2^31
// block
.word   11319751 // zeta^494 * 2^31 = 28678040^494 * 2^31
.word   57449959 // zeta^366 * 2^31 = 28678040^366 * 2^31
.word   47736605 // zeta^430 * 2^31 = 28678040^430 * 2^31
.word   25310795 // zeta^302 * 2^31 = 28678040^302 * 2^31
// block twisted
.word  316214329 // zeta^494 * (q^(-1) mod 2^32) * 2^31 = 28678040^494 * 375649793 * 2^31
.word 2994890777 // zeta^366 * (q^(-1) mod 2^32) * 2^31 = 28678040^366 * 375649793 * 2^31
.word 2883238627 // zeta^430 * (q^(-1) mod 2^32) * 2^31 = 28678040^430 * 375649793 * 2^31
.word 1834006453 // zeta^302 * (q^(-1) mod 2^32) * 2^31 = 28678040^302 * 375649793 * 2^31
// block
.word    5649915 // zeta^503 * 2^31 = 28678040^503 * 2^31
.word   25847843 // zeta^439 * 2^31 = 28678040^439 * 2^31
.word   62444027 // zeta^471 * 2^31 = 28678040^471 * 2^31
.word   57855139 // zeta^407 * 2^31 = 28678040^407 * 2^31
// block twisted
.word 3048839173 // zeta^503 * (q^(-1) mod 2^32) * 2^31 = 28678040^503 * 375649793 * 2^31
.word 3067803101 // zeta^439 * (q^(-1) mod 2^32) * 2^31 = 28678040^439 * 375649793 * 2^31
.word 2624519173 // zeta^471 * (q^(-1) mod 2^32) * 2^31 = 28678040^471 * 375649793 * 2^31
.word 2262798685 // zeta^407 * (q^(-1) mod 2^32) * 2^31 = 28678040^407 * 375649793 * 2^31
// block
.word   43953263 // zeta^375 * 2^31 = 28678040^375 * 2^31
.word    3973257 // zeta^311 * 2^31 = 28678040^311 * 2^31
.word   45754835 // zeta^343 * 2^31 = 28678040^343 * 2^31
.word   47438647 // zeta^279 * 2^31 = 28678040^279 * 2^31
// block twisted
.word 1254205841 // zeta^375 * (q^(-1) mod 2^32) * 2^31 = 28678040^375 * 375649793 * 2^31
.word 3800349047 // zeta^311 * (q^(-1) mod 2^32) * 2^31 = 28678040^311 * 375649793 * 2^31
.word 3397129261 // zeta^343 * (q^(-1) mod 2^32) * 2^31 = 28678040^343 * 375649793 * 2^31
.word 3896527561 // zeta^279 * (q^(-1) mod 2^32) * 2^31 = 28678040^279 * 375649793 * 2^31
// block
.word   34946213 // zeta^462 * 2^31 = 28678040^462 * 2^31
.word   33401995 // zeta^334 * 2^31 = 28678040^334 * 2^31
.word   57707227 // zeta^398 * 2^31 = 28678040^398 * 2^31
.word   43655235 // zeta^270 * 2^31 = 28678040^270 * 2^31
// block twisted
.word 4090836315 // zeta^462 * (q^(-1) mod 2^32) * 2^31 = 28678040^462 * 375649793 * 2^31
.word 2389950837 // zeta^334 * (q^(-1) mod 2^32) * 2^31 = 28678040^334 * 375649793 * 2^31
.word 1383072549 // zeta^398 * (q^(-1) mod 2^32) * 2^31 = 28678040^398 * 375649793 * 2^31
.word 2793176509 // zeta^270 * (q^(-1) mod 2^32) * 2^31 = 28678040^270 * 375649793 * 2^31
// block
.word   30218957 // zeta^487 * 2^31 = 28678040^487 * 2^31
.word   13073717 // zeta^423 * 2^31 = 28678040^423 * 2^31
.word   41547715 // zeta^455 * 2^31 = 28678040^455 * 2^31
.word   51082899 // zeta^391 * 2^31 = 28678040^391 * 2^31
// block twisted
.word 3945457459 // zeta^487 * (q^(-1) mod 2^32) * 2^31 = 28678040^487 * 375649793 * 2^31
.word 1399362763 // zeta^423 * (q^(-1) mod 2^32) * 2^31 = 28678040^423 * 375649793 * 2^31
.word  923248189 // zeta^455 * (q^(-1) mod 2^32) * 2^31 = 28678040^455 * 375649793 * 2^31
.word 2083145581 // zeta^391 * (q^(-1) mod 2^32) * 2^31 = 28678040^391 * 375649793 * 2^31
// block
.word    6539853 // zeta^359 * 2^31 = 28678040^359 * 2^31
.word   52712977 // zeta^295 * 2^31 = 28678040^295 * 2^31
.word   15171525 // zeta^327 * 2^31 = 28678040^327 * 2^31
.word   41070365 // zeta^263 * 2^31 = 28678040^263 * 2^31
// block twisted
.word 1097807795 // zeta^359 * (q^(-1) mod 2^32) * 2^31 = 28678040^359 * 375649793 * 2^31
.word 1402229743 // zeta^295 * (q^(-1) mod 2^32) * 2^31 = 28678040^295 * 375649793 * 2^31
.word  857879099 // zeta^327 * (q^(-1) mod 2^32) * 2^31 = 28678040^327 * 375649793 * 2^31
.word 2467328739 // zeta^263 * (q^(-1) mod 2^32) * 2^31 = 28678040^263 * 375649793 * 2^31
// block
.word    1421525 // zeta^502 * 2^31 = 28678040^502 * 2^31
.word    5608953 // zeta^374 * 2^31 = 28678040^374 * 2^31
.word    3344309 // zeta^438 * 2^31 = 28678040^438 * 2^31
.word   54192527 // zeta^310 * 2^31 = 28678040^310 * 2^31
// block twisted
.word 2006884651 // zeta^502 * (q^(-1) mod 2^32) * 2^31 = 28678040^502 * 375649793 * 2^31
.word 1547838471 // zeta^374 * (q^(-1) mod 2^32) * 2^31 = 28678040^374 * 375649793 * 2^31
.word 1835403851 // zeta^438 * (q^(-1) mod 2^32) * 2^31 = 28678040^438 * 375649793 * 2^31
.word 3288902769 // zeta^310 * (q^(-1) mod 2^32) * 2^31 = 28678040^310 * 375649793 * 2^31
// block
.word   55532487 // zeta^507 * 2^31 = 28678040^507 * 2^31
.word   25878283 // zeta^443 * 2^31 = 28678040^443 * 2^31
.word    7519477 // zeta^475 * 2^31 = 28678040^475 * 2^31
.word   10400227 // zeta^411 * 2^31 = 28678040^411 * 2^31
// block twisted
.word  579496505 // zeta^507 * (q^(-1) mod 2^32) * 2^31 = 28678040^507 * 375649793 * 2^31
.word 1491046133 // zeta^443 * (q^(-1) mod 2^32) * 2^31 = 28678040^443 * 375649793 * 2^31
.word 2637878539 // zeta^475 * (q^(-1) mod 2^32) * 2^31 = 28678040^475 * 375649793 * 2^31
.word  866659357 // zeta^411 * (q^(-1) mod 2^32) * 2^31 = 28678040^411 * 375649793 * 2^31
// block
.word   66449241 // zeta^379 * 2^31 = 28678040^379 * 2^31
.word    4428811 // zeta^315 * 2^31 = 28678040^315 * 2^31
.word   30618985 // zeta^347 * 2^31 = 28678040^347 * 2^31
.word   46942975 // zeta^283 * 2^31 = 28678040^283 * 2^31
// block twisted
.word 1923058343 // zeta^379 * (q^(-1) mod 2^32) * 2^31 = 28678040^379 * 375649793 * 2^31
.word 3711490549 // zeta^315 * (q^(-1) mod 2^32) * 2^31 = 28678040^315 * 375649793 * 2^31
.word 1530848407 // zeta^347 * (q^(-1) mod 2^32) * 2^31 = 28678040^347 * 375649793 * 2^31
.word 3263539969 // zeta^283 * (q^(-1) mod 2^32) * 2^31 = 28678040^283 * 375649793 * 2^31
// block
.word   34238409 // zeta^470 * 2^31 = 28678040^470 * 2^31
.word    7278675 // zeta^342 * 2^31 = 28678040^342 * 2^31
.word   26316985 // zeta^406 * 2^31 = 28678040^406 * 2^31
.word    1738533 // zeta^278 * 2^31 = 28678040^278 * 2^31
// block twisted
.word 1976527415 // zeta^470 * (q^(-1) mod 2^32) * 2^31 = 28678040^470 * 375649793 * 2^31
.word 3553111469 // zeta^342 * (q^(-1) mod 2^32) * 2^31 = 28678040^342 * 375649793 * 2^31
.word 1070704967 // zeta^406 * (q^(-1) mod 2^32) * 2^31 = 28678040^406 * 375649793 * 2^31
.word  280554203 // zeta^278 * (q^(-1) mod 2^32) * 2^31 = 28678040^278 * 375649793 * 2^31
// block
.word   29493541 // zeta^491 * 2^31 = 28678040^491 * 2^31
.word   46179537 // zeta^427 * 2^31 = 28678040^427 * 2^31
.word   61070425 // zeta^459 * 2^31 = 28678040^459 * 2^31
.word   47641435 // zeta^395 * 2^31 = 28678040^395 * 2^31
// block twisted
.word 3525667035 // zeta^491 * (q^(-1) mod 2^32) * 2^31 = 28678040^491 * 375649793 * 2^31
.word  738952495 // zeta^427 * (q^(-1) mod 2^32) * 2^31 = 28678040^427 * 375649793 * 2^31
.word 2855509415 // zeta^459 * (q^(-1) mod 2^32) * 2^31 = 28678040^459 * 375649793 * 2^31
.word 2166266533 // zeta^395 * (q^(-1) mod 2^32) * 2^31 = 28678040^395 * 375649793 * 2^31
// block
.word    8700655 // zeta^363 * 2^31 = 28678040^363 * 2^31
.word   49217369 // zeta^299 * 2^31 = 28678040^299 * 2^31
.word   14037329 // zeta^331 * 2^31 = 28678040^331 * 2^31
.word   57068693 // zeta^267 * 2^31 = 28678040^267 * 2^31
// block twisted
.word 2143064849 // zeta^363 * (q^(-1) mod 2^32) * 2^31 = 28678040^363 * 375649793 * 2^31
.word 3997596327 // zeta^299 * (q^(-1) mod 2^32) * 2^31 = 28678040^299 * 375649793 * 2^31
.word  594737327 // zeta^331 * (q^(-1) mod 2^32) * 2^31 = 28678040^331 * 375649793 * 2^31
.word 1214449003 // zeta^267 * (q^(-1) mod 2^32) * 2^31 = 28678040^267 * 375649793 * 2^31
// block
.word    5988919 // zeta^486 * 2^31 = 28678040^486 * 2^31
.word   27781261 // zeta^358 * 2^31 = 28678040^358 * 2^31
.word   33650523 // zeta^422 * 2^31 = 28678040^422 * 2^31
.word   40314383 // zeta^294 * 2^31 = 28678040^294 * 2^31
// block twisted
.word 2046739401 // zeta^486 * (q^(-1) mod 2^32) * 2^31 = 28678040^486 * 375649793 * 2^31
.word 2556008819 // zeta^358 * (q^(-1) mod 2^32) * 2^31 = 28678040^358 * 375649793 * 2^31
.word 2602309285 // zeta^422 * (q^(-1) mod 2^32) * 2^31 = 28678040^422 * 375649793 * 2^31
.word 3711528945 // zeta^294 * (q^(-1) mod 2^32) * 2^31 = 28678040^294 * 375649793 * 2^31
// block
.word   25356533 // zeta^499 * 2^31 = 28678040^499 * 2^31
.word   59712043 // zeta^435 * 2^31 = 28678040^435 * 2^31
.word   59431885 // zeta^467 * 2^31 = 28678040^467 * 2^31
.word   42783775 // zeta^403 * 2^31 = 28678040^403 * 2^31
// block twisted
.word  232958219 // zeta^499 * (q^(-1) mod 2^32) * 2^31 = 28678040^499 * 375649793 * 2^31
.word 2298121173 // zeta^435 * (q^(-1) mod 2^32) * 2^31 = 28678040^435 * 375649793 * 2^31
.word 4009174579 // zeta^467 * (q^(-1) mod 2^32) * 2^31 = 28678040^467 * 375649793 * 2^31
.word 4154483169 // zeta^403 * (q^(-1) mod 2^32) * 2^31 = 28678040^403 * 375649793 * 2^31
// block
.word   15118727 // zeta^371 * 2^31 = 28678040^371 * 2^31
.word   16104593 // zeta^307 * 2^31 = 28678040^307 * 2^31
.word   66551101 // zeta^339 * 2^31 = 28678040^339 * 2^31
.word   27099659 // zeta^275 * 2^31 = 28678040^275 * 2^31
// block twisted
.word  256676985 // zeta^371 * (q^(-1) mod 2^32) * 2^31 = 28678040^371 * 375649793 * 2^31
.word 2042883439 // zeta^307 * (q^(-1) mod 2^32) * 2^31 = 28678040^307 * 375649793 * 2^31
.word 2098783427 // zeta^339 * (q^(-1) mod 2^32) * 2^31 = 28678040^339 * 375649793 * 2^31
.word 1730866165 // zeta^275 * (q^(-1) mod 2^32) * 2^31 = 28678040^275 * 375649793 * 2^31
// block
.word   52622279 // zeta^454 * 2^31 = 28678040^454 * 2^31
.word   48542309 // zeta^326 * 2^31 = 28678040^326 * 2^31
.word   28412919 // zeta^390 * 2^31 = 28678040^390 * 2^31
.word   61490063 // zeta^262 * 2^31 = 28678040^262 * 2^31
// block twisted
.word  111596089 // zeta^454 * (q^(-1) mod 2^32) * 2^31 = 28678040^454 * 375649793 * 2^31
.word 2392801179 // zeta^326 * (q^(-1) mod 2^32) * 2^31 = 28678040^326 * 375649793 * 2^31
.word  122296841 // zeta^390 * (q^(-1) mod 2^32) * 2^31 = 28678040^390 * 375649793 * 2^31
.word 4112339569 // zeta^262 * (q^(-1) mod 2^32) * 2^31 = 28678040^262 * 375649793 * 2^31
// block
.word   17544659 // zeta^483 * 2^31 = 28678040^483 * 2^31
.word   26761761 // zeta^419 * 2^31 = 28678040^419 * 2^31
.word   28138345 // zeta^451 * 2^31 = 28678040^451 * 2^31
.word    6006005 // zeta^387 * 2^31 = 28678040^387 * 2^31
// block twisted
.word 1268942893 // zeta^483 * (q^(-1) mod 2^32) * 2^31 = 28678040^483 * 375649793 * 2^31
.word 3876122591 // zeta^419 * (q^(-1) mod 2^32) * 2^31 = 28678040^419 * 375649793 * 2^31
.word  148946583 // zeta^451 * (q^(-1) mod 2^32) * 2^31 = 28678040^451 * 375649793 * 2^31
.word  375516427 // zeta^387 * (q^(-1) mod 2^32) * 2^31 = 28678040^387 * 375649793 * 2^31
// block
.word   49338991 // zeta^355 * 2^31 = 28678040^355 * 2^31
.word   59052279 // zeta^291 * 2^31 = 28678040^291 * 2^31
.word   54131019 // zeta^323 * 2^31 = 28678040^323 * 2^31
.word   49172137 // zeta^259 * 2^31 = 28678040^259 * 2^31
// block twisted
.word 2285599633 // zeta^355 * (q^(-1) mod 2^32) * 2^31 = 28678040^355 * 375649793 * 2^31
.word 1420334345 // zeta^291 * (q^(-1) mod 2^32) * 2^31 = 28678040^291 * 375649793 * 2^31
.word 1832318133 // zeta^323 * (q^(-1) mod 2^32) * 2^31 = 28678040^323 * 375649793 * 2^31
.word  203443031 // zeta^259 * (q^(-1) mod 2^32) * 2^31 = 28678040^259 * 375649793 * 2^31
// block
.word   41164657 // zeta^506 * 2^31 = 28678040^506 * 2^31
.word   23553921 // zeta^378 * 2^31 = 28678040^378 * 2^31
.word   51075303 // zeta^442 * 2^31 = 28678040^442 * 2^31
.word   11244857 // zeta^314 * 2^31 = 28678040^314 * 2^31
// block twisted
.word 2292337295 // zeta^506 * (q^(-1) mod 2^32) * 2^31 = 28678040^506 * 375649793 * 2^31
.word 2218762879 // zeta^378 * (q^(-1) mod 2^32) * 2^31 = 28678040^378 * 375649793 * 2^31
.word 3660688665 // zeta^442 * (q^(-1) mod 2^32) * 2^31 = 28678040^442 * 375649793 * 2^31
.word 2196022471 // zeta^314 * (q^(-1) mod 2^32) * 2^31 = 28678040^314 * 375649793 * 2^31
// block
.word   27161421 // zeta^509 * 2^31 = 28678040^509 * 2^31
.word   12259351 // zeta^445 * 2^31 = 28678040^445 * 2^31
.word   42183787 // zeta^477 * 2^31 = 28678040^477 * 2^31
.word     260949 // zeta^413 * 2^31 = 28678040^413 * 2^31
// block twisted
.word 2261683891 // zeta^509 * (q^(-1) mod 2^32) * 2^31 = 28678040^509 * 375649793 * 2^31
.word  183096809 // zeta^445 * (q^(-1) mod 2^32) * 2^31 = 28678040^445 * 375649793 * 2^31
.word 2523693461 // zeta^477 * (q^(-1) mod 2^32) * 2^31 = 28678040^477 * 375649793 * 2^31
.word 2895730347 // zeta^413 * (q^(-1) mod 2^32) * 2^31 = 28678040^413 * 375649793 * 2^31
// block
.word   49379395 // zeta^381 * 2^31 = 28678040^381 * 2^31
.word   45318697 // zeta^317 * 2^31 = 28678040^317 * 2^31
.word   65417737 // zeta^349 * 2^31 = 28678040^349 * 2^31
.word   60522221 // zeta^285 * 2^31 = 28678040^285 * 2^31
// block twisted
.word 2945787325 // zeta^381 * (q^(-1) mod 2^32) * 2^31 = 28678040^381 * 375649793 * 2^31
.word 2724075479 // zeta^317 * (q^(-1) mod 2^32) * 2^31 = 28678040^317 * 375649793 * 2^31
.word 2827626487 // zeta^349 * (q^(-1) mod 2^32) * 2^31 = 28678040^349 * 375649793 * 2^31
.word  482722579 // zeta^285 * (q^(-1) mod 2^32) * 2^31 = 28678040^285 * 375649793 * 2^31
// block
.word    3629237 // zeta^474 * 2^31 = 28678040^474 * 2^31
.word   60326323 // zeta^346 * 2^31 = 28678040^346 * 2^31
.word   30569867 // zeta^410 * 2^31 = 28678040^410 * 2^31
.word   31921231 // zeta^282 * 2^31 = 28678040^282 * 2^31
// block twisted
.word 3571167563 // zeta^474 * (q^(-1) mod 2^32) * 2^31 = 28678040^474 * 375649793 * 2^31
.word 3851189325 // zeta^346 * (q^(-1) mod 2^32) * 2^31 = 28678040^346 * 375649793 * 2^31
.word 1517877365 // zeta^410 * (q^(-1) mod 2^32) * 2^31 = 28678040^410 * 375649793 * 2^31
.word 1275593137 // zeta^282 * (q^(-1) mod 2^32) * 2^31 = 28678040^282 * 375649793 * 2^31
// block
.word   51477925 // zeta^493 * 2^31 = 28678040^493 * 2^31
.word   23177153 // zeta^429 * 2^31 = 28678040^429 * 2^31
.word   42516129 // zeta^461 * 2^31 = 28678040^461 * 2^31
.word   23261199 // zeta^397 * 2^31 = 28678040^397 * 2^31
// block twisted
.word 1768092763 // zeta^493 * (q^(-1) mod 2^32) * 2^31 = 28678040^493 * 375649793 * 2^31
.word 2982666815 // zeta^429 * (q^(-1) mod 2^32) * 2^31 = 28678040^429 * 375649793 * 2^31
.word  134581087 // zeta^461 * (q^(-1) mod 2^32) * 2^31 = 28678040^461 * 375649793 * 2^31
.word 3424757233 // zeta^397 * (q^(-1) mod 2^32) * 2^31 = 28678040^397 * 375649793 * 2^31
// block
.word   50523083 // zeta^365 * 2^31 = 28678040^365 * 2^31
.word   29024109 // zeta^301 * 2^31 = 28678040^301 * 2^31
.word   62634975 // zeta^333 * 2^31 = 28678040^333 * 2^31
.word    5116371 // zeta^269 * 2^31 = 28678040^269 * 2^31
// block twisted
.word 2363949621 // zeta^365 * (q^(-1) mod 2^32) * 2^31 = 28678040^365 * 375649793 * 2^31
.word 2792055443 // zeta^301 * (q^(-1) mod 2^32) * 2^31 = 28678040^301 * 375649793 * 2^31
.word 3296655905 // zeta^333 * (q^(-1) mod 2^32) * 2^31 = 28678040^333 * 375649793 * 2^31
.word 4093127725 // zeta^269 * (q^(-1) mod 2^32) * 2^31 = 28678040^269 * 375649793 * 2^31
// block
.word   55626043 // zeta^490 * 2^31 = 28678040^490 * 2^31
.word   15630981 // zeta^362 * 2^31 = 28678040^362 * 2^31
.word   43717491 // zeta^426 * 2^31 = 28678040^426 * 2^31
.word   14342369 // zeta^298 * 2^31 = 28678040^298 * 2^31
// block twisted
.word 2004845765 // zeta^490 * (q^(-1) mod 2^32) * 2^31 = 28678040^490 * 375649793 * 2^31
.word 3862343547 // zeta^362 * (q^(-1) mod 2^32) * 2^31 = 28678040^362 * 375649793 * 2^31
.word 2436590221 // zeta^426 * (q^(-1) mod 2^32) * 2^31 = 28678040^426 * 375649793 * 2^31
.word 2109337887 // zeta^298 * (q^(-1) mod 2^32) * 2^31 = 28678040^298 * 375649793 * 2^31
// block
.word    6776583 // zeta^501 * 2^31 = 28678040^501 * 2^31
.word   33530533 // zeta^437 * 2^31 = 28678040^437 * 2^31
.word   43598203 // zeta^469 * 2^31 = 28678040^469 * 2^31
.word   59373651 // zeta^405 * 2^31 = 28678040^405 * 2^31
// block twisted
.word  820174585 // zeta^501 * (q^(-1) mod 2^32) * 2^31 = 28678040^501 * 375649793 * 2^31
.word 1139199835 // zeta^437 * (q^(-1) mod 2^32) * 2^31 = 28678040^437 * 375649793 * 2^31
.word 3555298437 // zeta^469 * (q^(-1) mod 2^32) * 2^31 = 28678040^469 * 375649793 * 2^31
.word 1035814317 // zeta^405 * (q^(-1) mod 2^32) * 2^31 = 28678040^405 * 375649793 * 2^31
// block
.word   37946425 // zeta^373 * 2^31 = 28678040^373 * 2^31
.word   47668559 // zeta^309 * 2^31 = 28678040^309 * 2^31
.word   10775673 // zeta^341 * 2^31 = 28678040^341 * 2^31
.word    3826249 // zeta^277 * 2^31 = 28678040^277 * 2^31
// block twisted
.word  262354375 // zeta^373 * (q^(-1) mod 2^32) * 2^31 = 28678040^373 * 375649793 * 2^31
.word  703707313 // zeta^309 * (q^(-1) mod 2^32) * 2^31 = 28678040^309 * 375649793 * 2^31
.word 2790542727 // zeta^341 * (q^(-1) mod 2^32) * 2^31 = 28678040^341 * 375649793 * 2^31
.word 2635626423 // zeta^277 * (q^(-1) mod 2^32) * 2^31 = 28678040^277 * 375649793 * 2^31
// block
.word   53733071 // zeta^458 * 2^31 = 28678040^458 * 2^31
.word   10734019 // zeta^330 * 2^31 = 28678040^330 * 2^31
.word   25306471 // zeta^394 * 2^31 = 28678040^394 * 2^31
.word   54139625 // zeta^266 * 2^31 = 28678040^266 * 2^31
// block twisted
.word  284438321 // zeta^458 * (q^(-1) mod 2^32) * 2^31 = 28678040^458 * 375649793 * 2^31
.word 3541161021 // zeta^330 * (q^(-1) mod 2^32) * 2^31 = 28678040^330 * 375649793 * 2^31
.word 2646073497 // zeta^394 * (q^(-1) mod 2^32) * 2^31 = 28678040^394 * 375649793 * 2^31
.word 3100573463 // zeta^266 * (q^(-1) mod 2^32) * 2^31 = 28678040^266 * 375649793 * 2^31
// block
.word    1468391 // zeta^485 * 2^31 = 28678040^485 * 2^31
.word    4426959 // zeta^421 * 2^31 = 28678040^421 * 2^31
.word   42735737 // zeta^453 * 2^31 = 28678040^453 * 2^31
.word   38665093 // zeta^389 * 2^31 = 28678040^389 * 2^31
// block twisted
.word 1874632217 // zeta^485 * (q^(-1) mod 2^32) * 2^31 = 28678040^485 * 375649793 * 2^31
.word 3630205233 // zeta^421 * (q^(-1) mod 2^32) * 2^31 = 28678040^421 * 375649793 * 2^31
.word 2166661511 // zeta^453 * (q^(-1) mod 2^32) * 2^31 = 28678040^453 * 375649793 * 2^31
.word 1536243323 // zeta^389 * (q^(-1) mod 2^32) * 2^31 = 28678040^389 * 375649793 * 2^31
// block
.word   33133879 // zeta^357 * 2^31 = 28678040^357 * 2^31
.word    7139481 // zeta^293 * 2^31 = 28678040^293 * 2^31
.word    8438111 // zeta^325 * 2^31 = 28678040^325 * 2^31
.word   50341189 // zeta^261 * 2^31 = 28678040^261 * 2^31
// block twisted
.word 3126759625 // zeta^357 * (q^(-1) mod 2^32) * 2^31 = 28678040^357 * 375649793 * 2^31
.word  523569511 // zeta^293 * (q^(-1) mod 2^32) * 2^31 = 28678040^293 * 375649793 * 2^31
.word 1408300193 // zeta^325 * (q^(-1) mod 2^32) * 2^31 = 28678040^325 * 375649793 * 2^31
.word 2172685499 // zeta^261 * (q^(-1) mod 2^32) * 2^31 = 28678040^261 * 375649793 * 2^31
// block
.word   47558821 // zeta^498 * 2^31 = 28678040^498 * 2^31
.word   33268441 // zeta^370 * 2^31 = 28678040^370 * 2^31
.word   63536237 // zeta^434 * 2^31 = 28678040^434 * 2^31
.word   26272521 // zeta^306 * 2^31 = 28678040^306 * 2^31
// block twisted
.word  664584539 // zeta^498 * (q^(-1) mod 2^32) * 2^31 = 28678040^498 * 375649793 * 2^31
.word 2409420583 // zeta^370 * (q^(-1) mod 2^32) * 2^31 = 28678040^370 * 375649793 * 2^31
.word 3799958931 // zeta^434 * (q^(-1) mod 2^32) * 2^31 = 28678040^434 * 375649793 * 2^31
.word  835286775 // zeta^306 * (q^(-1) mod 2^32) * 2^31 = 28678040^306 * 375649793 * 2^31
// block
.word    1854317 // zeta^505 * 2^31 = 28678040^505 * 2^31
.word    2223865 // zeta^441 * 2^31 = 28678040^441 * 2^31
.word   22962475 // zeta^473 * 2^31 = 28678040^473 * 2^31
.word   36888515 // zeta^409 * 2^31 = 28678040^409 * 2^31
// block twisted
.word 1178728083 // zeta^505 * (q^(-1) mod 2^32) * 2^31 = 28678040^505 * 375649793 * 2^31
.word 2481965831 // zeta^441 * (q^(-1) mod 2^32) * 2^31 = 28678040^441 * 375649793 * 2^31
.word  128011477 // zeta^473 * (q^(-1) mod 2^32) * 2^31 = 28678040^473 * 375649793 * 2^31
.word 3495870013 // zeta^409 * (q^(-1) mod 2^32) * 2^31 = 28678040^409 * 375649793 * 2^31
// block
.word   59868297 // zeta^377 * 2^31 = 28678040^377 * 2^31
.word   15191207 // zeta^313 * 2^31 = 28678040^313 * 2^31
.word   59108143 // zeta^345 * 2^31 = 28678040^345 * 2^31
.word    4355773 // zeta^281 * 2^31 = 28678040^281 * 2^31
// block twisted
.word  538432887 // zeta^377 * (q^(-1) mod 2^32) * 2^31 = 28678040^377 * 375649793 * 2^31
.word 3252336985 // zeta^313 * (q^(-1) mod 2^32) * 2^31 = 28678040^313 * 375649793 * 2^31
.word 1330506449 // zeta^345 * (q^(-1) mod 2^32) * 2^31 = 28678040^345 * 375649793 * 2^31
.word 4169984835 // zeta^281 * (q^(-1) mod 2^32) * 2^31 = 28678040^281 * 375649793 * 2^31
// block
.word   27411989 // zeta^466 * 2^31 = 28678040^466 * 2^31
.word   52176833 // zeta^338 * 2^31 = 28678040^338 * 2^31
.word   52660121 // zeta^402 * 2^31 = 28678040^402 * 2^31
.word   23140553 // zeta^274 * 2^31 = 28678040^274 * 2^31
// block twisted
.word  652643307 // zeta^466 * (q^(-1) mod 2^32) * 2^31 = 28678040^466 * 375649793 * 2^31
.word 4178403903 // zeta^338 * (q^(-1) mod 2^32) * 2^31 = 28678040^338 * 375649793 * 2^31
.word 1113879143 // zeta^402 * (q^(-1) mod 2^32) * 2^31 = 28678040^402 * 375649793 * 2^31
.word 3574776119 // zeta^274 * (q^(-1) mod 2^32) * 2^31 = 28678040^274 * 375649793 * 2^31
// block
.word   50275685 // zeta^489 * 2^31 = 28678040^489 * 2^31
.word   12903773 // zeta^425 * 2^31 = 28678040^425 * 2^31
.word   25228433 // zeta^457 * 2^31 = 28678040^457 * 2^31
.word   55395235 // zeta^393 * 2^31 = 28678040^393 * 2^31
// block twisted
.word 2869087387 // zeta^489 * (q^(-1) mod 2^32) * 2^31 = 28678040^489 * 375649793 * 2^31
.word  433896611 // zeta^425 * (q^(-1) mod 2^32) * 2^31 = 28678040^425 * 375649793 * 2^31
.word  157857135 // zeta^457 * (q^(-1) mod 2^32) * 2^31 = 28678040^457 * 375649793 * 2^31
.word 2477464157 // zeta^393 * (q^(-1) mod 2^32) * 2^31 = 28678040^393 * 375649793 * 2^31
// block
.word    3868449 // zeta^361 * 2^31 = 28678040^361 * 2^31
.word   66432231 // zeta^297 * 2^31 = 28678040^297 * 2^31
.word   31236859 // zeta^329 * 2^31 = 28678040^329 * 2^31
.word   13658415 // zeta^265 * 2^31 = 28678040^265 * 2^31
// block twisted
.word 2938651359 // zeta^361 * (q^(-1) mod 2^32) * 2^31 = 28678040^361 * 375649793 * 2^31
.word  814700825 // zeta^297 * (q^(-1) mod 2^32) * 2^31 = 28678040^297 * 375649793 * 2^31
.word 1618291461 // zeta^329 * (q^(-1) mod 2^32) * 2^31 = 28678040^329 * 375649793 * 2^31
.word   49245393 // zeta^265 * (q^(-1) mod 2^32) * 2^31 = 28678040^265 * 375649793 * 2^31
// block
.word   34409967 // zeta^482 * 2^31 = 28678040^482 * 2^31
.word   12619783 // zeta^354 * 2^31 = 28678040^354 * 2^31
.word   54561811 // zeta^418 * 2^31 = 28678040^418 * 2^31
.word   61632377 // zeta^290 * 2^31 = 28678040^290 * 2^31
// block twisted
.word 2233616401 // zeta^482 * (q^(-1) mod 2^32) * 2^31 = 28678040^482 * 375649793 * 2^31
.word 2820912633 // zeta^354 * (q^(-1) mod 2^32) * 2^31 = 28678040^354 * 375649793 * 2^31
.word  684470765 // zeta^418 * (q^(-1) mod 2^32) * 2^31 = 28678040^418 * 375649793 * 2^31
.word 3345631879 // zeta^290 * (q^(-1) mod 2^32) * 2^31 = 28678040^290 * 375649793 * 2^31
// block
.word    7605279 // zeta^497 * 2^31 = 28678040^497 * 2^31
.word   58319315 // zeta^433 * 2^31 = 28678040^433 * 2^31
.word   16342937 // zeta^465 * 2^31 = 28678040^465 * 2^31
.word   48148431 // zeta^401 * 2^31 = 28678040^401 * 2^31
// block twisted
.word  568928737 // zeta^497 * (q^(-1) mod 2^32) * 2^31 = 28678040^497 * 375649793 * 2^31
.word 1726766125 // zeta^433 * (q^(-1) mod 2^32) * 2^31 = 28678040^433 * 375649793 * 2^31
.word 1056873063 // zeta^465 * (q^(-1) mod 2^32) * 2^31 = 28678040^465 * 375649793 * 2^31
.word  958621233 // zeta^401 * (q^(-1) mod 2^32) * 2^31 = 28678040^401 * 375649793 * 2^31
// block
.word   62377755 // zeta^369 * 2^31 = 28678040^369 * 2^31
.word   35459369 // zeta^305 * 2^31 = 28678040^305 * 2^31
.word   27513701 // zeta^337 * 2^31 = 28678040^337 * 2^31
.word   18346679 // zeta^273 * 2^31 = 28678040^273 * 2^31
// block twisted
.word 4057153253 // zeta^369 * (q^(-1) mod 2^32) * 2^31 = 28678040^369 * 375649793 * 2^31
.word 3867838679 // zeta^305 * (q^(-1) mod 2^32) * 2^31 = 28678040^305 * 375649793 * 2^31
.word  589962907 // zeta^337 * (q^(-1) mod 2^32) * 2^31 = 28678040^337 * 375649793 * 2^31
.word 1692873545 // zeta^273 * (q^(-1) mod 2^32) * 2^31 = 28678040^273 * 375649793 * 2^31
// block
.word    1824951 // zeta^450 * 2^31 = 28678040^450 * 2^31
.word   40410247 // zeta^322 * 2^31 = 28678040^322 * 2^31
.word   25935987 // zeta^386 * 2^31 = 28678040^386 * 2^31
.word   53409853 // zeta^258 * 2^31 = 28678040^258 * 2^31
// block twisted
.word 3034533193 // zeta^450 * (q^(-1) mod 2^32) * 2^31 = 28678040^450 * 375649793 * 2^31
.word 1425582457 // zeta^322 * (q^(-1) mod 2^32) * 2^31 = 28678040^322 * 375649793 * 2^31
.word 1695333773 // zeta^386 * (q^(-1) mod 2^32) * 2^31 = 28678040^386 * 375649793 * 2^31
.word 2628741571 // zeta^258 * (q^(-1) mod 2^32) * 2^31 = 28678040^258 * 375649793 * 2^31
// block
.word   44896477 // zeta^481 * 2^31 = 28678040^481 * 2^31
.word   66621379 // zeta^417 * 2^31 = 28678040^417 * 2^31
.word   35702907 // zeta^449 * 2^31 = 28678040^449 * 2^31
.word   44158149 // zeta^385 * 2^31 = 28678040^385 * 2^31
// block twisted
.word  732401955 // zeta^481 * (q^(-1) mod 2^32) * 2^31 = 28678040^481 * 375649793 * 2^31
.word 3346599485 // zeta^417 * (q^(-1) mod 2^32) * 2^31 = 28678040^417 * 375649793 * 2^31
.word 1671955845 // zeta^449 * (q^(-1) mod 2^32) * 2^31 = 28678040^449 * 375649793 * 2^31
.word 1684661563 // zeta^385 * (q^(-1) mod 2^32) * 2^31 = 28678040^385 * 375649793 * 2^31
// block
.word   32881793 // zeta^353 * 2^31 = 28678040^353 * 2^31
.word   18033685 // zeta^289 * 2^31 = 28678040^289 * 2^31
.word   29367795 // zeta^321 * 2^31 = 28678040^321 * 2^31
.word   16787671 // zeta^257 * 2^31 = 28678040^257 * 2^31
// block twisted
.word 3741535615 // zeta^353 * (q^(-1) mod 2^32) * 2^31 = 28678040^353 * 375649793 * 2^31
.word 3094455787 // zeta^289 * (q^(-1) mod 2^32) * 2^31 = 28678040^289 * 375649793 * 2^31
.word 3934216205 // zeta^321 * (q^(-1) mod 2^32) * 2^31 = 28678040^321 * 375649793 * 2^31
.word 2459712809 // zeta^257 * (q^(-1) mod 2^32) * 2^31 = 28678040^257 * 375649793 * 2^31
.word   57730785 // zeta^504 * 2^31 = 28678040^504 * 2^31 = 25085703 * 2^31
.word 3752846111 // zeta^504 * f(q^(-1) mod 2^32) * 2^31 = 28678040^504 * 375649793 * 2^31
.word   42601623 // zeta^508 * 2^31 = 28678040^508 * 2^31 = 32762154 * 2^31
.word 2096617833 // zeta^508 * f(q^(-1) mod 2^32) * 2^31 = 28678040^508 * 375649793 * 2^31
.word   43352521 // zeta^380 * 2^31 = 28678040^380 * 2^31 = 24111249 * 2^31
.word 3690485815 // zeta^380 * f(q^(-1) mod 2^32) * 2^31 = 28678040^380 * 375649793 * 2^31
.word   59392861 // zeta^376 * 2^31 = 28678040^376 * 2^31 = 5443354 * 2^31
.word  348348067 // zeta^376 * f(q^(-1) mod 2^32) * 2^31 = 28678040^376 * 375649793 * 2^31
.word   65052633 // zeta^444 * 2^31 = 28678040^444 * 2^31 = 11430609 * 2^31
.word 2878986791 // zeta^444 * f(q^(-1) mod 2^32) * 2^31 = 28678040^444 * 375649793 * 2^31
.word   58217677 // zeta^316 * 2^31 = 28678040^316 * 2^31 = 29824921 * 2^31
.word 4056132915 // zeta^316 * f(q^(-1) mod 2^32) * 2^31 = 28678040^316 * 375649793 * 2^31
.word   57130935 // zeta^440 * 2^31 = 28678040^440 * 2^31 = 28470806 * 2^31
.word 1821992521 // zeta^440 * f(q^(-1) mod 2^32) * 2^31 = 28678040^440 * 375649793 * 2^31
.word   14439459 // zeta^476 * 2^31 = 28678040^476 * 2^31 = 15403199 * 2^31
.word 3133213149 // zeta^476 * f(q^(-1) mod 2^32) * 2^31 = 28678040^476 * 375649793 * 2^31
.word   30030779 // zeta^348 * 2^31 = 28678040^348 * 2^31 = 32900632 * 2^31
.word 2105479749 // zeta^348 * f(q^(-1) mod 2^32) * 2^31 = 28678040^348 * 375649793 * 2^31
.word    3784291 // zeta^312 * 2^31 = 28678040^312 * 2^31 = 25309194 * 2^31
.word 1619664797 // zeta^312 * f(q^(-1) mod 2^32) * 2^31 = 28678040^312 * 375649793 * 2^31
.word   48646815 // zeta^412 * 2^31 = 28678040^412 * 2^31 = 11510556 * 2^31
.word  736619361 // zeta^412 * f(q^(-1) mod 2^32) * 2^31 = 28678040^412 * 375649793 * 2^31
.word   15892551 // zeta^284 * 2^31 = 28678040^284 * 2^31 = 17389126 * 2^31
.word 1112819129 // zeta^284 * f(q^(-1) mod 2^32) * 2^31 = 28678040^284 * 375649793 * 2^31
.word   50479773 // zeta^472 * 2^31 = 28678040^472 * 2^31 = 4264131 * 2^31
.word 2420367203 // zeta^472 * f(q^(-1) mod 2^32) * 2^31 = 28678040^472 * 375649793 * 2^31
.word   20532335 // zeta^492 * 2^31 = 28678040^492 * 2^31 = 22651623 * 2^31
.word 3597076881 // zeta^492 * f(q^(-1) mod 2^32) * 2^31 = 28678040^492 * 375649793 * 2^31
.word   46242673 // zeta^364 * 2^31 = 28678040^364 * 2^31 = 8172970 * 2^31
.word  523030159 // zeta^364 * f(q^(-1) mod 2^32) * 2^31 = 28678040^364 * 375649793 * 2^31
.word   58797193 // zeta^344 * 2^31 = 28678040^344 * 2^31 = 24307701 * 2^31
.word 3703057783 // zeta^344 * f(q^(-1) mod 2^32) * 2^31 = 28678040^344 * 375649793 * 2^31
.word   34903951 // zeta^428 * 2^31 = 28678040^428 * 2^31 = 20443666 * 2^31
.word 1308294769 // zeta^428 * f(q^(-1) mod 2^32) * 2^31 = 28678040^428 * 375649793 * 2^31
.word   48022295 // zeta^300 * 2^31 = 28678040^300 * 2^31 = 28778784 * 2^31
.word 1841701609 // zeta^300 * f(q^(-1) mod 2^32) * 2^31 = 28678040^300 * 375649793 * 2^31
.word   62080381 // zeta^408 * 2^31 = 28678040^408 * 2^31 = 6865022 * 2^31
.word  439327875 // zeta^408 * f(q^(-1) mod 2^32) * 2^31 = 28678040^408 * 375649793 * 2^31
.word   55892463 // zeta^460 * 2^31 = 28678040^460 * 2^31 = 8866965 * 2^31
.word 2714926097 // zeta^460 * f(q^(-1) mod 2^32) * 2^31 = 28678040^460 * 375649793 * 2^31
.word    5286953 // zeta^332 * 2^31 = 28678040^332 * 2^31 = 25271104 * 2^31
.word 1617227223 // zeta^332 * f(q^(-1) mod 2^32) * 2^31 = 28678040^332 * 375649793 * 2^31
.word   40872659 // zeta^280 * 2^31 = 28678040^280 * 2^31 = 32984098 * 2^31
.word 2110821165 // zeta^280 * f(q^(-1) mod 2^32) * 2^31 = 28678040^280 * 375649793 * 2^31
.word   42133307 // zeta^396 * 2^31 = 28678040^396 * 2^31 = 14019017 * 2^31
.word 3044632261 // zeta^396 * f(q^(-1) mod 2^32) * 2^31 = 28678040^396 * 375649793 * 2^31
.word   54343827 // zeta^268 * 2^31 = 28678040^268 * 2^31 = 9843973 * 2^31
.word 2777449837 // zeta^268 * f(q^(-1) mod 2^32) * 2^31 = 28678040^268 * 375649793 * 2^31
.word    6014597 // zeta^488 * 2^31 = 28678040^488 * 2^31 = 7194579 * 2^31
.word 2607901563 // zeta^488 * f(q^(-1) mod 2^32) * 2^31 = 28678040^488 * 375649793 * 2^31
.word   25291403 // zeta^500 * 2^31 = 28678040^500 * 2^31 = 355881 * 2^31
.word 2170258293 // zeta^500 * f(q^(-1) mod 2^32) * 2^31 = 28678040^500 * 375649793 * 2^31
.word   14166063 // zeta^372 * 2^31 = 28678040^372 * 2^31 = 13728463 * 2^31
.word 3026038225 // zeta^372 * f(q^(-1) mod 2^32) * 2^31 = 28678040^372 * 375649793 * 2^31
.word   31380141 // zeta^360 * 2^31 = 28678040^360 * 2^31 = 2302061 * 2^31
.word 2294804307 // zeta^360 * f(q^(-1) mod 2^32) * 2^31 = 28678040^360 * 375649793 * 2^31
.word   31709009 // zeta^436 * 2^31 = 28678040^436 * 2^31 = 21728197 * 2^31
.word 3537982127 // zeta^436 * f(q^(-1) mod 2^32) * 2^31 = 28678040^436 * 375649793 * 2^31
.word   12550399 // zeta^308 * 2^31 = 28678040^308 * 2^31 = 11713874 * 2^31
.word  749630721 // zeta^308 * f(q^(-1) mod 2^32) * 2^31 = 28678040^308 * 375649793 * 2^31
.word   21111903 // zeta^424 * 2^31 = 28678040^424 * 2^31 = 13908588 * 2^31
.word  890081697 // zeta^424 * f(q^(-1) mod 2^32) * 2^31 = 28678040^424 * 375649793 * 2^31
.word   65984707 // zeta^468 * 2^31 = 28678040^468 * 2^31 = 25787077 * 2^31
.word 3797730621 // zeta^468 * f(q^(-1) mod 2^32) * 2^31 = 28678040^468 * 375649793 * 2^31
.word   52266271 // zeta^340 * 2^31 = 28678040^340 * 2^31 = 31977548 * 2^31
.word 2046406881 // zeta^340 * f(q^(-1) mod 2^32) * 2^31 = 28678040^340 * 375649793 * 2^31
.word   12778219 // zeta^296 * 2^31 = 28678040^296 * 2^31 = 27066590 * 2^31
.word 1732129557 // zeta^296 * f(q^(-1) mod 2^32) * 2^31 = 28678040^296 * 375649793 * 2^31
.word   39517177 // zeta^404 * 2^31 = 28678040^404 * 2^31 = 14739293 * 2^31
.word 3090726407 // zeta^404 * f(q^(-1) mod 2^32) * 2^31 = 28678040^404 * 375649793 * 2^31
.word   12656259 // zeta^276 * 2^31 = 28678040^276 * 2^31 = 24450888 * 2^31
.word 1564737405 // zeta^276 * f(q^(-1) mod 2^32) * 2^31 = 28678040^276 * 375649793 * 2^31
.word   56722355 // zeta^456 * 2^31 = 28678040^456 * 2^31 = 31418183 * 2^31
.word 4158093901 // zeta^456 * f(q^(-1) mod 2^32) * 2^31 = 28678040^456 * 375649793 * 2^31
.word   27185869 // zeta^484 * 2^31 = 28678040^484 * 2^31 = 15870328 * 2^31
.word 1015623475 // zeta^484 * f(q^(-1) mod 2^32) * 2^31 = 28678040^484 * 375649793 * 2^31
.word   14750755 // zeta^356 * 2^31 = 28678040^356 * 2^31 = 27851125 * 2^31
.word 3929819613 // zeta^356 * f(q^(-1) mod 2^32) * 2^31 = 28678040^356 * 375649793 * 2^31
.word   65797823 // zeta^328 * 2^31 = 28678040^328 * 2^31 = 18723698 * 2^31
.word 1198225217 // zeta^328 * f(q^(-1) mod 2^32) * 2^31 = 28678040^328 * 375649793 * 2^31
.word   13164949 // zeta^420 * 2^31 = 28678040^420 * 2^31 = 28267567 * 2^31
.word 3956469867 // zeta^420 * f(q^(-1) mod 2^32) * 2^31 = 28678040^420 * 375649793 * 2^31
.word    1145583 // zeta^292 * 2^31 = 28678040^292 * 2^31 = 8225248 * 2^31
.word  526375697 // zeta^292 * f(q^(-1) mod 2^32) * 2^31 = 28678040^292 * 375649793 * 2^31
.word   12271567 // zeta^392 * 2^31 = 28678040^392 * 2^31 = 6528331 * 2^31
.word 2565264945 // zeta^392 * f(q^(-1) mod 2^32) * 2^31 = 28678040^392 * 375649793 * 2^31
.word   22449375 // zeta^452 * 2^31 = 28678040^452 * 2^31 = 12336210 * 2^31
.word  789457185 // zeta^452 * f(q^(-1) mod 2^32) * 2^31 = 28678040^452 * 375649793 * 2^31
.word   31982975 // zeta^324 * 2^31 = 28678040^324 * 2^31 = 33215913 * 2^31
.word 4273139841 // zeta^324 * f(q^(-1) mod 2^32) * 2^31 = 28678040^324 * 375649793 * 2^31
.word   35394733 // zeta^264 * 2^31 = 28678040^264 * 2^31 = 9731484 * 2^31
.word  622767443 // zeta^264 * f(q^(-1) mod 2^32) * 2^31 = 28678040^264 * 375649793 * 2^31
.word   23998611 // zeta^388 * 2^31 = 28678040^388 * 2^31 = 12857867 * 2^31
.word 2970324333 // zeta^388 * f(q^(-1) mod 2^32) * 2^31 = 28678040^388 * 375649793 * 2^31
.word   62038423 // zeta^260 * 2^31 = 28678040^260 * 2^31 = 24546403 * 2^31
.word 3718333545 // zeta^260 * f(q^(-1) mod 2^32) * 2^31 = 28678040^260 * 375649793 * 2^31
.word   32686385 // zeta^480 * 2^31 = 28678040^480 * 2^31 = 20044445 * 2^31
.word 3430230223 // zeta^480 * f(q^(-1) mod 2^32) * 2^31 = 28678040^480 * 375649793 * 2^31
.word   58757463 // zeta^496 * 2^31 = 28678040^496 * 2^31 = 17352831 * 2^31
.word 3257980073 // zeta^496 * f(q^(-1) mod 2^32) * 2^31 = 28678040^496 * 375649793 * 2^31
.word   41196349 // zeta^368 * 2^31 = 28678040^368 * 2^31 = 10953311 * 2^31
.word 2848442051 // zeta^368 * f(q^(-1) mod 2^32) * 2^31 = 28678040^368 * 375649793 * 2^31
.word    2430825 // zeta^352 * 2^31 = 28678040^352 * 2^31 = 18811302 * 2^31
.word 1203831447 // zeta^352 * f(q^(-1) mod 2^32) * 2^31 = 28678040^352 * 375649793 * 2^31
.word   26613973 // zeta^432 * 2^31 = 28678040^432 * 2^31 = 23642097 * 2^31
.word 3660462379 // zeta^432 * f(q^(-1) mod 2^32) * 2^31 = 28678040^432 * 375649793 * 2^31
.word    7832335 // zeta^304 * 2^31 = 28678040^304 * 2^31 = 12267508 * 2^31
.word  785060593 // zeta^304 * f(q^(-1) mod 2^32) * 2^31 = 28678040^304 * 375649793 * 2^31
.word   62228979 // zeta^416 * 2^31 = 28678040^416 * 2^31 = 20647416 * 2^31
.word 1321333773 // zeta^416 * f(q^(-1) mod 2^32) * 2^31 = 28678040^416 * 375649793 * 2^31
.word   12542317 // zeta^464 * 2^31 = 28678040^464 * 2^31 = 3271804 * 2^31
.word  209379475 // zeta^464 * f(q^(-1) mod 2^32) * 2^31 = 28678040^464 * 375649793 * 2^31
.word   18302687 // zeta^336 * 2^31 = 28678040^336 * 2^31 = 3819232 * 2^31
.word  244412193 // zeta^336 * f(q^(-1) mod 2^32) * 2^31 = 28678040^336 * 375649793 * 2^31
.word   48515911 // zeta^288 * 2^31 = 28678040^288 * 2^31 = 26823146 * 2^31
.word 1716550329 // zeta^288 * f(q^(-1) mod 2^32) * 2^31 = 28678040^288 * 375649793 * 2^31
.word   21796399 // zeta^400 * 2^31 = 28678040^400 * 2^31 = 18930340 * 2^31
.word 1211449297 // zeta^400 * f(q^(-1) mod 2^32) * 2^31 = 28678040^400 * 375649793 * 2^31
.word   27114239 // zeta^272 * 2^31 = 28678040^272 * 2^31 = 13128918 * 2^31
.word  840186625 // zeta^272 * f(q^(-1) mod 2^32) * 2^31 = 28678040^272 * 375649793 * 2^31
.word   38018305 // zeta^384 * 2^31 = 28678040^384 * 2^31 = 15854702 * 2^31
.word 1014623487 // zeta^384 * f(q^(-1) mod 2^32) * 2^31 = 28678040^384 * 375649793 * 2^31
.word   23796181 // zeta^448 * 2^31 = 28678040^448 * 2^31 = 18977417 * 2^31
.word 3361945643 // zeta^448 * f(q^(-1) mod 2^32) * 2^31 = 28678040^448 * 375649793 * 2^31
.word   52637069 // zeta^320 * 2^31 = 28678040^320 * 2^31 = 30296666 * 2^31
.word 1938838643 // zeta^320 * f(q^(-1) mod 2^32) * 2^31 = 28678040^320 * 375649793 * 2^31
.text

// Montgomery multiplication via rounding
.macro mulmod dst, src, const, const_twisted
        vqrdmulh.s32   \dst,  \src, \const
        vmul.u32       \src,  \src, \const_twisted
        vqrdmlah.s32   \dst,  \src, modulus
.endm

.macro gs_butterfly a, b, root, root_twisted
        vsub.u32       tmp, \a,  \b
        vadd.u32       \a,  \a,  \b
        mulmod         \b,  tmp, \root, \root_twisted
.endm

.align 4
roots_addr: .word roots_inv
.syntax unified
.type invntt_n256_u32_33556993_28678040_complete_manual, %function
.global invntt_n256_u32_33556993_28678040_complete_manual
invntt_n256_u32_33556993_28678040_complete_manual:

        push {r4-r11,lr}
        // Save MVE vector registers
        vpush {d8-d15}

        modulus     .req r12
        root_ptr    .req r11

        .equ modulus_const, 33556993
        movw modulus, #:lower16:modulus_const
        movt modulus, #:upper16:modulus_const
        ldr  root_ptr, roots_addr

        in .req r0

        data0 .req q0
        data1 .req q1
        data2 .req q2
        data3 .req q3

        root0         .req q5
        root0_twisted .req q6
        root1         .req q5
        root1_twisted .req q6
        root2         .req q5
        root2_twisted .req q6


        tmp .req q4

        // Layers 7,8

        mov lr, #16
layer78_loop:
        vldrw.u32 data0, [in]
        vldrw.u32 data1, [in, #(4*4*1)]
        vldrw.u32 data2, [in, #(4*4*2)]
        vldrw.u32 data3, [in, #(4*4*3)]

        vldrw.u32 root1,         [root_ptr, #(32)]
        vldrw.u32 root1_twisted, [root_ptr, #(32+16)]
        gs_butterfly data0, data1, root1, root1_twisted

        vldrw.u32 root2,         [root_ptr, #(64)]
        vldrw.u32 root2_twisted, [root_ptr, #(64+16)]
        gs_butterfly data2, data3, root2, root2_twisted

        vldrw.u32 root0,         [root_ptr], #(3*32)
        vldrw.u32 root0_twisted, [root_ptr, #(16 - 3*32)]
        gs_butterfly data0, data2, root0, root0_twisted
        gs_butterfly data1, data3, root0, root0_twisted

        vstrw.u32 data0, [in], #64
        vstrw.u32 data1, [in, #(4*4*1 - 64)]
        vstrw.u32 data2, [in, #(4*4*2 - 64)]
        vstrw.u32 data3, [in, #(4*4*3 - 64)]

        le lr, layer78_loop

        sub in, in, #(4*256)

        .unreq root0
        .unreq root0_twisted
        .unreq root1
        .unreq root1_twisted
        .unreq root2
        .unreq root2_twisted

        root0         .req r2
        root0_twisted .req r3
        root1         .req r4
        root1_twisted .req r5
        root2         .req r6
        root2_twisted .req r7

        // Layers 5,6

        mov lr, #16
layer56_loop:
        ldrd root0, root0_twisted, [root_ptr], #24
        ldrd root1, root1_twisted, [root_ptr, #-16]
        ldrd root2, root2_twisted, [root_ptr, #-8]

        vld40.u32 {data0, data1, data2, data3}, [in]
        vld41.u32 {data0, data1, data2, data3}, [in]
        vld42.u32 {data0, data1, data2, data3}, [in]
        vld43.u32 {data0, data1, data2, data3}, [in]

        gs_butterfly data0, data1, root1, root1_twisted
        gs_butterfly data2, data3, root2, root2_twisted
        gs_butterfly data0, data2, root0, root0_twisted
        gs_butterfly data1, data3, root0, root0_twisted

        vstrw.u32 data0, [in], #(64)
        vstrw.u32 data1, [in, #(4*4*1 - 64)]
        vstrw.u32 data2, [in, #(4*4*2 - 64)]
        vstrw.u32 data3, [in, #(4*4*3 - 64)]

        le lr, layer56_loop

        sub in, in, #(4*256)

        // TEMPORARY: Barrett reduction
        modulus_neg .req r10
        neg modulus_neg, modulus
        barrett_const .req r1
        .equ const_barrett, 63
        movw barrett_const, #:lower16:const_barrett
        movt barrett_const, #:upper16:const_barrett
        mov lr, #64
1:
        vldrw.u32 data0, [in]
        vqrdmulh.s32 tmp, data0, barrett_const
        vmla.s32 data0, tmp, modulus_neg
        vstrw.u32 data0, [in], #16
        le lr, 1b
2:
        sub in, in, #(4*256)
        .unreq barrett_const
        .unreq modulus_neg

        // Layers 3,4

        // 4 butterfly blocks per root config, 4 root configs
        // loop over root configs

        count .req r1
        mov count, #4

out_start:
        ldrd root0, root0_twisted, [root_ptr], #+8
        ldrd root1, root1_twisted, [root_ptr], #+8
        ldrd root2, root2_twisted, [root_ptr], #+8

        mov lr, #4
layer34_loop:
        vldrw.u32 data0, [in]
        vldrw.u32 data1, [in, #(4*1*16)]
        vldrw.u32 data2, [in, #(4*2*16)]
        vldrw.u32 data3, [in, #(4*3*16)]

        gs_butterfly data0, data1, root1, root1_twisted
        gs_butterfly data2, data3, root2, root2_twisted
        gs_butterfly data0, data2, root0, root0_twisted
        gs_butterfly data1, data3, root0, root0_twisted

        vstrw.u32 data0, [in], #(16)
        vstrw.u32 data1, [in, #(4*16*1 - 16)]
        vstrw.u32 data2, [in, #(4*16*2 - 16)]
        vstrw.u32 data3, [in, #(4*16*3 - 16)]

        le lr, layer34_loop
        add in, in, #(4*64 - 4*16)

        subs count, count, #1
        bne out_start

        sub in, in, #(4*256)

        // TEMPORARY: Barrett reduction
        modulus_neg .req r10
        neg modulus_neg, modulus
        barrett_const .req r1
        movw barrett_const, #:lower16:const_barrett
        movt barrett_const, #:upper16:const_barrett
        mov lr, #64
1:
        vldrw.u32 data0, [in]
        vqrdmulh.s32 tmp, data0, barrett_const
        vmla.s32 data0, tmp, modulus_neg
        vstrw.u32 data0, [in], #16
        le lr, 1b
2:
        sub in, in, #(4*256)
        .unreq barrett_const
        .unreq modulus_neg

        in_low       .req r0
        in_high      .req r1
        add in_high, in_low, #(4*128)

        // Layers 1,2

        ldrd root0, root0_twisted, [root_ptr], #+8
        ldrd root1, root1_twisted, [root_ptr], #+8
        ldrd root2, root2_twisted, [root_ptr], #+8

        mov lr, #16
layer12_loop:

        vldrw.u32 data0, [in_low]
        vldrw.u32 data1, [in_low,  #(4*64)]
        vldrw.u32 data2, [in_high]
        vldrw.u32 data3, [in_high, #(4*64)]

        gs_butterfly data0, data1, root1, root1_twisted
        gs_butterfly data2, data3, root2, root2_twisted
        gs_butterfly data0, data2, root0, root0_twisted
        gs_butterfly data1, data3, root0, root0_twisted

        vstrw.u32 data0, [in_low], #16
        vstrw.u32 data1, [in_low, #(4*64 - 16)]
        vstrw.u32 data2, [in_high], #16
        vstrw.u32 data3, [in_high, #(4*64 - 16)]

        le lr, layer12_loop

        // Restore MVE vector registers
        vpop {d8-d15}
        // Restore GPRs
        pop {r4-r11,lr}
        bx lr