{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2025-12-14T01:33:56.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2025-12-14T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":46696,"title":"Number Theoretic Transform (NTT)","description":null,"description_html":"\u003cdiv style = \"text-align: start; line-height: 20.44px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: none solid rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 63px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 31.5px; transform-origin: 407px 31.5px; vertical-align: baseline; \"\u003e\u003cdiv style=\"font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eGiven an input polynomial (r) of length \u0026lt;=n and a prime number (p) such that an nth root of unity exists and the modular inverse of (n) modulus p exists. Convert the polynominal coefficents by Number Theoretic Transform (NTT) using the primitive nth root of unity as the generator mod p.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function rhat = numberTheoreticTransform(r,n,p)\r\n rhat=r;\r\nend","test_suite":"%%\r\nn=210;\r\np=5881;\r\nr=[8669,57047,39514,17386,56675,3808,29999,47330,22216,26294,34536,58604,51010,4546,18270,24862,...\r\n 56667,27522,15720,39167,31418,58887,61257,53601,46459,48707,58963,4275,22014,284,54270,33255,...\r\n 23996,14853,35050,18971,4480,5568,4478,26857,8085,29033,58912,23176,7875,37297,57346,22844,...\r\n 2747,9328,5019,48531,29918,43794,45825,37444,41202,57525,43407,57371,30639,9262,4465,46808,...\r\n 20184,43985,42757,34802,46865,33083,31981,32626,61340,25511,7677,15756,44886,55001,63579,14101,...\r\n 49829,38279,26407,33426,32482,42688,48739,19788,5872,54130,25531,50810,11755,7167,59320,57432,...\r\n 65522,56639,2416,35696,65379,33489,57246,4602,64719,60470,36979,28276,22140,47233,894,24514,...\r\n 60469,35814,31056,32541,20248,62314,64355,33656,65050,29874,27921,13973,12664,54575,47620,34717,...\r\n 54334,33546,36173,13977,38523,9356,3422,44781,39882,14395,26625,41281,36392,8361,11088,65,...\r\n 27404,32013,10477,43701,1174,7843,62398,63953,2026,32367,56539,15917,54674,53319,41220,146,...\r\n 24885,59271,44587,24826,41415,15942,37448,64338,55684,18575,44725,23470,64679,5504,16404,53172,...\r\n 5532,34816,52469,48419,9284,28697,22962,31358,38496,9555,59331,41955,10678,37087,61054,51321,...\r\n 44937,30554,17060,37307,16303,20925,59690,58013];\r\nrhat=[4391 3275 5259 1238 4797 2486 919 3786 5067 4389\r\n 2255 3368 968 3027 4274 3358 2953 3646 2967 4281\r\n 5348 229 5498 5448 3419 3720 100 5376 2968 3437\r\n 404 3686 3576 4743 4840 4942 4237 1414 102 2806\r\n 3832 5075 5084 1139 2483 2021 5541 1332 5022 5155\r\n 5235 4306 797 2739 911 3669 4133 547 5678 5162\r\n 1905 4772 2478 1657 1905 2539 4053 3185 3567 113\r\n 1985 674 1359 182 1645 1249 1752 922 1178 5427\r\n 2476 1241 2496 1703 3691 5044 802 304 905 2280\r\n 2211 4163 4845 690 4246 3016 3159 1555 3762 1416\r\n 105 4332 2706 308 2230 2117 787 1189 5549 72\r\n 4092 4428 4103 3397 5700 5630 1803 840 4153 4385\r\n 5537 1564 5437 5553 377 3468 2885 4827 3523 2618\r\n 2238 3633 2254 4028 3660 1909 5874 1850 3153 2253\r\n 3 2286 1953 81 5161 5764 5063 2887 4983 3481\r\n 5044 770 1225 4832 1673 5556 2434 21 1735 5422\r\n 1003 2672 3262 982 2344 269 2638 3485 3278 4882\r\n 4604 5118 4587 2136 3361 478 5289 808 3170 3752\r\n 2862 4604 4813 3077 5849 813 1214 135 3691 4774\r\n 1668 4361 5564 3949 5019 71 2441 4481 722 5462\r\n 4925 2693 41 3294 3971 361 1224 445 5386 186];\r\nassert(isequal(numberTheoreticTransform(r,n,p),rhat(:)'))\r\n%%\r\nn=1024\r\np=12289;\r\nr=[52074 13446 46646 7881 15396 46708 6135 41514 35944 46632\r\n 60673 28779 56867 40989 26142 30972 42638 64624 10831 31518\r\n 11720 1785 7753 22717 17571 46438 14101 13576 32367 47787\r\n 33917 57421 2557 21929 54559 62787 15982 49616 35069 61443\r\n 41091 39983 39203 37658 65232 33146 22261 58086 13029 33898\r\n 59846 13342 39604 56619 42582 19991 12967 30948 40839 59183\r\n 43513 34073 33844 13013 46134 51761 33215 10414 1724 14299\r\n 25506 3527 492 44069 61099 15491 62308 53144 20892 57227\r\n 48497 56504 45149 59102 45065 15355 25860 31228 34930 5419\r\n 53584 29028 61998 13051 37247 30454 38303 7621 21415 30500\r\n 39344 35914 57248 19548 24959 40592 39750 57391 39465 1437\r\n 5570 37149 7423 32539 41587 40326 46834 41627 23719 52971\r\n 60447 44590 23237 58320 23804 8036 26315 6375 8842 11744\r\n 3512 24338 15855 32860 26713 8112 56275 59535 59887 10839\r\n 34539 5126 36722 18153 24163 18642 60324 2294 41979 11901\r\n 7789 29907 40155 34993 30696 48216 49206 2605 43173 45313\r\n 24913 3135 19713 37634 32991 26955 18716 64786 44258 14009\r\n 53269 48382 52307 27053 59672 54328 52220 44969 48795 19536\r\n 15997 2490 52143 967 13528 61283 9356 24686 55192 50353\r\n 57961 62537 51189 46056 22190 26153 33066 33051 33859 32843\r\n 46704 48652 23009 33210 37625 3421 40022 50036 9952 59602\r\n 24782 61436 3558 24986 31911 37433 46124 3203 24947 3791\r\n 16313 33643 46445 4255 17184 48999 25122 47574 53806 28622\r\n 16571 15787 65072 23499 37984 20987 47754 45962 11230 37503\r\n 50282 17037 10648 15351 57562 32304 58149 30073 21625 37032\r\n 3267 49740 7442 13336 3994 14526 3660 38161 63338 53989\r\n 44911 65099 59826 53331 28893 61556 9058 22222 52841 8264\r\n 40650 23377 31565 25784 5521 31608 56561 11182 14561 19668\r\n 48934 49339 55823 3511 36912 35389 27639 26161 65521 139\r\n 64045 7212 53078 24579 35344 14487 26955 60278 4177 62331\r\n 25160 39127 12239 50790 50335 6287 62858 14814 27884 50220\r\n 17052 28219 16200 10832 15275 3943 49168 23658 26498 49237\r\n 57505 47888 3551 59783 38493 53707 64290 21270 26233 9100\r\n 52828 17116 39908 20919 30079 50559 15303 5477 7334 22893\r\n 30220 6213 50936 21612 56425 12825 6306 33598 27807 9918\r\n 5961 29554 33493 13384 43308 58662 25203 54582 40209 32553\r\n 36979 41947 1818 50280 23191 44846 32785 59284 64753 52995\r\n 12280 8653 64905 4585 22753 43047 37372 47421 14411 41475\r\n 34844 29676 32829 62261 16627 64905 64004 25100 23205 45115\r\n 23267 42742 21757 10368 62424 2208 32299 19530 17448 41914\r\n 20629 54198 11395 18772 19542 27803 26272 45332 19103 47796\r\n 47627 20190 41001 45031 10381 32111 65207 57701 12346 56350\r\n 33801 26369 37692 9250 23677 38240 17104 60591 1498 41088\r\n 51815 57948 49216 33560 48603 5457 43602 5324 29452 11835\r\n 13401 45913 10061 47272 46261 43263 63193 31632 15967 37572\r\n 44440 15851 23382 60872 45933 3427 43984 8405 56932 10719\r\n 3439 49796 9433 47979 408 36492 19606 16574 34643 59379\r\n 52505 19066 55745 49142 24533 46663 34807 57931 59908 5068\r\n 44470 18182 22142 26694 59080 31975 95 12863 63827 22186\r\n 61997 400 18035 15695 20863 40475 57919 7953 38366 38051\r\n 6000 24557 393 34134 39130 14010 26501 35631 7797 31145\r\n 59535 28634 52554 14357 19516 42313 19739 20618 60721 52777\r\n 33420 19942 32598 55206 8192 24945 62297 25037 38899 34785\r\n 40298 19061 35248 43445 25451 6796 30189 51874 57908 14897\r\n 20714 15893 57076 53492 53587 24740 18851 54996 27818 46496\r\n 5078 61386 47372 52027 64302 17226 5546 44579 39797 9740\r\n 55745 56373 43783 30743 56491 15812 38153 27323 4637 43130\r\n 9471 26032 11719 20285 5493 40823 10031 42132 60605 41548\r\n 24280 31419 36077 45061 22132 34270 4790 14030 42079 15027\r\n 40789 37027 62906 64674 15474 27081 38047 40453 6848 11942\r\n 65375 32087 39060 50458 20827 14273 18809 44249 45889 10902\r\n 33904 17682 52990 54367 64516 56266 23718 39388 25939 9804\r\n 64914 64863 64522 46273 35930 56427 47502 22695 5564 13287\r\n 14846 12037 58059 39015 49102 18608 56250 23881 14056 62584\r\n 26083 56469 14014 49340 55171 40330 22801 11238 16305 1042\r\n 45650 2138 2269 32553 10937 51084 63028 52124 14853 62751\r\n 4236 21755 29564 56697 59185 62576 62493 32287 46072 1683\r\n 48998 49069 904 4458 6889 60267 13502 23240 49424 63642\r\n 27551 42229 31045 63474 48830 25219 50347 50794 35866 19503\r\n 53170 11091 62337 6472 47800 10658 40339 15519 36273 34411\r\n 24877 62403 16315 35846 47020 52215 60222 55367 41325 56514\r\n 20910 35603 25324 26409 8744 7459 39487 53511 64582 58746\r\n 64621 16476 28274 7014 29215 10408 46015 55458 41568 12386\r\n 47066 37917 54452 47458 33343 23319 48737 24260 39351 43300\r\n 27078 59996 54044 40218 34766 55558 25238 25115 59584 61684\r\n 6463 58693 29687 51312 56342 38193 16482 56448 37410 63943\r\n 48140 31621 24940 37134 44415 38415 2409 30402 21982 7073\r\n 41766 29015 60677 53170 52811 60675 30941 37391 62727 11724\r\n 4839 20431 48551 37799 34815 37688 42275 45567 28830 48925\r\n 7897 3625 48341 61867 62645 653 18282 62974 39422 3241\r\n 64329 49400 62057 57111 4369 53043 33938 35803 47203 4671\r\n 32558 8647 33429 33266 35488 39898 16100 41718 44484 32055\r\n 1468 23325 51896 51696 18458 31451 19497 37414 13943 55698\r\n 3527 25943 29633 31000 31516 17592 42629 60759 5349 65342\r\n 9232 58033 55653 54316 44883 16914 58418 56607 17988 287\r\n 58554 1391 25587 21134 13648 31523 56433 11130 56853 35560\r\n 30527 55317 48390 63972 39856 14899 13756 11711 36658 56449\r\n 36756 18878 63991 18232 21376 3185 26155 15958 30449 59581\r\n 32404 16406 34294 4773 57727 11091 58188 49268 28200 55400\r\n 4442 32006 28174 49232 8742 16937 16811 13050 50723 57597\r\n 58828 47778 13576 54472 6711 12970 63360 64417 42855 48901\r\n 18911 13278 21194 60446 62856 39694 40577 46506 43104 7699\r\n 17632 14173 7265 21431 10020 53982 10836 11497 10552 33359\r\n 38941 63985 24589 52695 9996 53124 54145 56249 28336 11064\r\n 31187 38878 21620 35274 10194 52575 42971 59599 33101 54467\r\n 24137 19949 22420 30362 5870 46406 35812 63023 24597 60818\r\n 42966 63419 53550 53788 29781 56320 16471 37394 31481 11107\r\n 61485 58718 34844 62384 43836 51189 2631 36888 22440 57916\r\n 40660 12453 34152 4998 54480 13356 15294 11577 50931 25418\r\n 18536 117 50745 46443 51788 65099 23665 33664 25162 25072];\r\nrhat=[8149 10593 825 1418 8962 1559 3161 152\r\n 5086 9561 11949 5217 5798 11589 3150 5329\r\n 8984 3998 7095 390 2183 9925 6985 11431\r\n 3249 1053 7833 4160 13 1692 1976 8920\r\n 9291 9284 9074 2974 5068 10375 80 4023\r\n 11492 5804 6645 1044 7322 19 7192 7839\r\n 9217 4466 10449 3187 2137 119 9226 6202\r\n 7603 5162 8758 12104 7195 7646 6527 5506\r\n 6225 12166 3612 9329 470 7699 9996 11300\r\n 10722 1986 5330 10948 843 4540 11096 7298\r\n 446 7352 2390 5148 9522 11654 1156 8749\r\n 3736 11720 11276 6342 9275 11013 782 1253\r\n 3336 5994 12271 10025 4567 8321 1619 6205\r\n 2010 3243 4122 2079 9240 989 12020 7584\r\n 9610 6632 9036 11327 11665 9187 1417 4616\r\n 3768 1590 10149 3400 4707 5141 3973 5828\r\n 9623 3436 997 6446 10458 5845 8785 4056\r\n 10876 4226 7775 4853 8562 9793 8662 8391\r\n 6182 3663 10851 2565 5271 5953 11059 715\r\n 7529 4284 2244 8402 12053 7689 541 5153\r\n 8110 5951 6609 335 3517 6766 6683 3012\r\n 4955 3196 8713 6749 246 5847 2747 7607\r\n 8485 2656 4214 985 4827 2550 11484 11457\r\n 3124 1611 3563 382 1919 3058 8499 5773\r\n 1423 2757 1327 11084 6349 455 1929 417\r\n 9081 10604 613 10502 7325 8929 7125 8483\r\n 9465 10411 2134 3556 986 530 9950 1448\r\n 10951 8652 3309 7995 6767 315 3390 507\r\n 11937 8868 12228 5740 6625 1837 388 11209\r\n 3858 829 1248 12057 7320 3536 2756 5663\r\n 10974 3976 8957 11721 4338 9767 11429 8609\r\n 6564 1713 9831 10924 912 9766 6373 7233\r\n 3700 1269 4315 8607 4546 8196 9941 7644\r\n 878 11980 10491 2706 3912 9513 2567 8190\r\n 643 379 4709 9262 11112 1860 4737 11022\r\n 1323 3739 8110 8196 11511 2236 8007 9557\r\n 12024 10027 11760 11831 2394 500 6894 389\r\n 8560 4490 168 8370 1272 5988 6261 8753\r\n 4943 2775 2362 2464 10956 12172 2558 5757\r\n 1707 7697 6861 2490 6732 4772 9887 8195\r\n 4315 3792 1287 580 3928 6061 9571 1812\r\n 783 5756 2086 9790 5118 7639 6449 7058\r\n 11898 3862 2787 12173 4520 5695 212 1507\r\n 5346 9561 654 9830 5535 5850 4702 3448\r\n 5173 7945 740 8601 2757 3408 1153 7755\r\n 8707 6923 4891 11539 7076 10827 10657 1702\r\n 11981 8090 5301 856 10035 6307 10356 11679\r\n 9453 2222 1223 9948 10545 6152 6122 5565\r\n 10032 113 4049 4053 8376 11269 10270 1305\r\n 2126 1286 6659 881 3528 8590 10609 9754\r\n 11887 3876 1784 6936 1034 6381 1763 12219\r\n 5357 1336 7692 2667 7716 9060 8531 5530\r\n 5945 11985 2654 2560 6865 4738 11695 801\r\n 5824 6645 6710 6940 2131 2231 1940 4950\r\n 746 3214 6012 8276 8247 3992 9384 5457\r\n 7807 4112 9317 2273 1130 10350 8548 8193\r\n 3642 8624 8082 4908 10678 1835 7296 848\r\n 10867 11073 9696 2669 5746 1260 7347 4877\r\n 11495 5170 991 10986 8479 5253 2646 10197\r\n 5326 2942 11788 1621 2984 294 10203 9804\r\n 4494 2383 294 5111 1339 10478 8541 9356\r\n 2187 172 5127 8875 8915 789 2201 5140\r\n 5160 10441 4096 9010 10106 11593 6362 9775\r\n 4295 10907 1824 1894 5510 5337 9922 3371\r\n 8127 5345 4006 5209 10033 2859 4601 5742\r\n 3793 8908 6314 7883 8653 11031 10085 5403\r\n 3859 7385 4404 8611 5490 3923 8187 480\r\n 9766 12182 901 3569 10257 6668 3709 6931\r\n 2481 9841 9271 2472 11437 391 12053 4980\r\n 11992 3545 10994 9307 11791 322 3678 9815\r\n 1904 6151 10952 4868 10935 8320 9856 9570\r\n 6752 254 9868 7270 9019 3920 1414 1270\r\n 10364 4598 11037 3621 3234 9263 10271 11024\r\n 5000 1675 5510 7650 440 5417 10452 1974\r\n 5922 4450 6056 5245 1126 2867 2645 7398\r\n 1290 5398 5692 8986 3751 7506 2269 488\r\n 1909 5213 4327 8275 5794 534 11630 11908\r\n 53 6833 5782 5954 9629 5503 2239 5699\r\n 10980 10804 4193 10615 236 6096 2895 8953\r\n 5824 11122 7883 2053 6154 4548 5701 5575\r\n 1747 6519 6826 4063 11574 7423 9720 4636\r\n 11375 6605 1810 10176 6039 587 10520 10310\r\n 1100 3029 3862 8091 10427 4614 10870 2274\r\n 8785 11559 6971 4077 925 4907 5804 7863\r\n 3296 12221 8683 3445 3022 7680 11201 3591\r\n 773 3117 2404 968 4600 2668 10518 468\r\n 215 6056 7487 11731 2328 6050 2762 8744\r\n 677 1468 5443 8970 9622 8609 391 9362\r\n 850 9053 2676 10194 5487 10187 1917 5679\r\n 2586 415 8841 4002 8329 9123 1706 6923\r\n 4346 8013 11694 7230 4849 5346 958 9474\r\n 5828 10768 3592 11256 12214 6209 5772 4820\r\n 8719 3551 5014 187 8099 3338 9425 8455\r\n 11193 3088 2025 7193 3726 6393 4237 10983\r\n 7306 3335 9019 6401 11140 9163 2214 8141\r\n 2901 2598 7927 9127 3635 7468 2931 9271\r\n 6188 83 8923 5051 213 3750 10987 11744\r\n 3529 829 6394 6310 8428 11624 392 10014\r\n 10407 6190 4717 10647 8578 4959 8400 9476\r\n 11730 3977 3410 10130 8954 3171 6364 1588\r\n 9146 6763 11717 2289 12045 329 1489 4830\r\n 6135 7211 568 10450 9554 3037 5529 9\r\n 3995 1662 12272 11074 5671 1469 7367 4854\r\n 4549 8081 2025 3242 8687 5009 9142 2004\r\n 10161 2020 4083 1333 4743 5254 194 6885\r\n 226 11966 6259 3939 5004 11828 3961 10006\r\n 3966 8223 9013 2152 7274 11391 120 3271\r\n 12189 1703 2227 5125 5269 7245 8442 8137\r\n 4036 7892 8282 9848 5536 4409 7306 8365\r\n 4788 10993 10891 2650 5180 9379 5748 3115\r\n 1578 10933 4035 6497 8116 7574 4788 9184\r\n 7292 2637 2829 2197 6402 5607 8814 3297\r\n 12163 6864 3905 4982 6710 7802 10831 1012\r\n 8629 6883 3876 2358 3998 1465 7663 5577\r\n 1940 6499 1233 11847 8131 8283 577 8690\r\n 8536 1709 11555 7614 1606 7021 2479 10991\r\n 7673 6724 9074 5707 3131 11008 10835 5567\r\n 6706 321 12276 3407 4790 11852 3340 4209\r\n 887 6216 706 7716 9370 2905 8846 170\r\n 9563 7171 5219 7938 3769 7095 68 2976\r\n 3914 3867 11656 347 7395 8967 5517 894\r\n 2589 4130 10205 5493 3040 4057 10259 5751\r\n 248 10770 3157 1900 1428 11496 3608 7411\r\n 11099 5378 8023 1291 11427 1273 10747 9407\r\n 1600 586 9694 4493 2681 3073 2814 9289\r\n 11724 11813 7932 7385 3639 1582 135 5276\r\n 8990 10675 10619 10670 6193 10730 4885 10384\r\n 5511 2999 4965 9346 562 3131 11572 6417];\r\nassert(isequal(numberTheoreticTransform(r(:)',n,p),rhat(:)'))\r\n%%\r\nn=256;\r\np=3329;\r\nr=[17789 14064 31398 7235 4452 54042 17029 9244 41506 19221 25101 62219 54529 40064 62923 42789\r\n 56877 51841 65136 14198 13625 50288 57544 47986 60999 3380 64958 16802 49403 3404 61808 25001\r\n 48595 42905 39615 53151 2595 65348 12338 45289 64079 33038 18797 64871 40754 37730 7385 19662\r\n 29351 1713 61925 9087 30759 14919 49754 2260 6133 50356 46280 22925 25827 55203 42486 22291\r\n 46506 51496 32141 57796 9836 60263 2076 32037 43367 18545 35075 13665 23545 32750 31509 60222\r\n 61887 60461 28701 60526 64966 42074 42096 63661 39503 14769 12662 43635 5823 28771 4359 29901\r\n 11410 32264 50636 835 27987 6902 37150 7369 31052 21711 45182 63789 22392 9768 58836 28999\r\n 16029 54657 48763 24717 62611 17574 24668 48707 23347 29704 3306 40809 35957 1853 32586 29765\r\n 42003 8608 29026 10997 47464 50059 13929 41847 31167 48325 12087 4164 30182 49589 50548 61950\r\n 52993 49793 3473 35404 38069 52789 51914 38940 43976 33415 2992 24478 42300 52173 3955 14360\r\n 55926 60669 5755 6662 35406 6832 9531 32677 62891 25068 58002 10895 33654 19238 17200 57829\r\n 26091 54572 52296 2573 46231 30786 32056 37214 5838 59341 55036 15157 53374 7550 42668 1302\r\n 7569 17000 42964 61160 329 14356 841 27951 52280 63259 7743 3421 6368 24582 8755 22397\r\n 5261 13960 2119 63674 51282 60470 12229 4996 38717 41174 26896 59097 30389 54322 41847 50202\r\n 23623 34230 36507 23653 60742 20992 31800 19043 59781 8652 7879 51989 38654 55166 25227 22465\r\n 54323 26041 47172 42218 543 56199 54933 36787 6627 40521 37492 24445 12266 43597 50180 40554];\r\nrhat=[1004 2562 12 2074 386 769 3081 923 234 324 3276 3310 1457 2786 1538 1203\r\n 2725 438 1145 992 1049 2056 79 1027 2483 2538 4 2926 2235 1721 1323 1176\r\n 545 183 3074 501 2640 855 1161 2419 1203 813 3106 2589 2852 1456 1682 1723\r\n 69 623 2891 274 813 1126 3161 654 3073 693 2162 3089 2845 612 3031 293\r\n 592 1068 1284 749 404 1253 426 1999 2639 2516 1092 2077 453 1649 2336 3163\r\n 2039 495 51 1711 1959 1829 200 3273 2348 141 1326 760 3201 400 2955 3279\r\n 1452 1853 1912 973 666 1696 2042 965 1095 210 3132 160 766 740 1804 2075\r\n 2315 2977 2197 3084 1811 340 140 1425 1279 3194 758 2224 2692 1839 2400 1477\r\n 2429 1148 2851 2684 3141 1255 2870 3295 2652 899 716 1549 406 517 1155 2856\r\n 3116 1361 1678 2120 1646 915 1518 1631 1685 2535 2169 1417 1796 828 1899 911\r\n 309 738 754 2490 1194 2757 1105 1086 1929 1892 1032 1186 1805 1880 2454 621\r\n 1514 1448 2271 2505 856 47 1949 2456 1700 1041 112 2844 2723 1705 981 781\r\n 3026 1470 145 2240 171 2116 3322 2831 2726 1800 1228 873 2341 2557 246 887\r\n 1275 2019 1990 1422 1937 820 605 925 2552 93 1790 1408 1989 2718 2353 3141\r\n 1249 376 831 1305 2941 1750 2254 2190 2703 774 1527 1776 1829 2916 661 2171\r\n 1503 1689 2004 368 643 2582 2079 2419 999 2909 3317 764 1712 2256 2638 3065];\r\nassert(isequal(numberTheoreticTransform(r(:)',n,p),rhat(:)'))\r\n\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":145982,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":3,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-10-06T20:08:10.000Z","updated_at":"2025-10-13T12:54:40.000Z","published_at":"2020-10-06T20:17:36.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven an input polynomial (r) of length \u0026lt;=n and a prime number (p) such that an nth root of unity exists and the modular inverse of (n) modulus p exists. Convert the polynominal coefficents by Number Theoretic Transform (NTT) using the primitive nth root of unity as the generator mod p.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":46696,"title":"Number Theoretic Transform (NTT)","description":null,"description_html":"\u003cdiv style = \"text-align: start; line-height: 20.44px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: none solid rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 63px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 31.5px; transform-origin: 407px 31.5px; vertical-align: baseline; \"\u003e\u003cdiv style=\"font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eGiven an input polynomial (r) of length \u0026lt;=n and a prime number (p) such that an nth root of unity exists and the modular inverse of (n) modulus p exists. Convert the polynominal coefficents by Number Theoretic Transform (NTT) using the primitive nth root of unity as the generator mod p.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function rhat = numberTheoreticTransform(r,n,p)\r\n rhat=r;\r\nend","test_suite":"%%\r\nn=210;\r\np=5881;\r\nr=[8669,57047,39514,17386,56675,3808,29999,47330,22216,26294,34536,58604,51010,4546,18270,24862,...\r\n 56667,27522,15720,39167,31418,58887,61257,53601,46459,48707,58963,4275,22014,284,54270,33255,...\r\n 23996,14853,35050,18971,4480,5568,4478,26857,8085,29033,58912,23176,7875,37297,57346,22844,...\r\n 2747,9328,5019,48531,29918,43794,45825,37444,41202,57525,43407,57371,30639,9262,4465,46808,...\r\n 20184,43985,42757,34802,46865,33083,31981,32626,61340,25511,7677,15756,44886,55001,63579,14101,...\r\n 49829,38279,26407,33426,32482,42688,48739,19788,5872,54130,25531,50810,11755,7167,59320,57432,...\r\n 65522,56639,2416,35696,65379,33489,57246,4602,64719,60470,36979,28276,22140,47233,894,24514,...\r\n 60469,35814,31056,32541,20248,62314,64355,33656,65050,29874,27921,13973,12664,54575,47620,34717,...\r\n 54334,33546,36173,13977,38523,9356,3422,44781,39882,14395,26625,41281,36392,8361,11088,65,...\r\n 27404,32013,10477,43701,1174,7843,62398,63953,2026,32367,56539,15917,54674,53319,41220,146,...\r\n 24885,59271,44587,24826,41415,15942,37448,64338,55684,18575,44725,23470,64679,5504,16404,53172,...\r\n 5532,34816,52469,48419,9284,28697,22962,31358,38496,9555,59331,41955,10678,37087,61054,51321,...\r\n 44937,30554,17060,37307,16303,20925,59690,58013];\r\nrhat=[4391 3275 5259 1238 4797 2486 919 3786 5067 4389\r\n 2255 3368 968 3027 4274 3358 2953 3646 2967 4281\r\n 5348 229 5498 5448 3419 3720 100 5376 2968 3437\r\n 404 3686 3576 4743 4840 4942 4237 1414 102 2806\r\n 3832 5075 5084 1139 2483 2021 5541 1332 5022 5155\r\n 5235 4306 797 2739 911 3669 4133 547 5678 5162\r\n 1905 4772 2478 1657 1905 2539 4053 3185 3567 113\r\n 1985 674 1359 182 1645 1249 1752 922 1178 5427\r\n 2476 1241 2496 1703 3691 5044 802 304 905 2280\r\n 2211 4163 4845 690 4246 3016 3159 1555 3762 1416\r\n 105 4332 2706 308 2230 2117 787 1189 5549 72\r\n 4092 4428 4103 3397 5700 5630 1803 840 4153 4385\r\n 5537 1564 5437 5553 377 3468 2885 4827 3523 2618\r\n 2238 3633 2254 4028 3660 1909 5874 1850 3153 2253\r\n 3 2286 1953 81 5161 5764 5063 2887 4983 3481\r\n 5044 770 1225 4832 1673 5556 2434 21 1735 5422\r\n 1003 2672 3262 982 2344 269 2638 3485 3278 4882\r\n 4604 5118 4587 2136 3361 478 5289 808 3170 3752\r\n 2862 4604 4813 3077 5849 813 1214 135 3691 4774\r\n 1668 4361 5564 3949 5019 71 2441 4481 722 5462\r\n 4925 2693 41 3294 3971 361 1224 445 5386 186];\r\nassert(isequal(numberTheoreticTransform(r,n,p),rhat(:)'))\r\n%%\r\nn=1024\r\np=12289;\r\nr=[52074 13446 46646 7881 15396 46708 6135 41514 35944 46632\r\n 60673 28779 56867 40989 26142 30972 42638 64624 10831 31518\r\n 11720 1785 7753 22717 17571 46438 14101 13576 32367 47787\r\n 33917 57421 2557 21929 54559 62787 15982 49616 35069 61443\r\n 41091 39983 39203 37658 65232 33146 22261 58086 13029 33898\r\n 59846 13342 39604 56619 42582 19991 12967 30948 40839 59183\r\n 43513 34073 33844 13013 46134 51761 33215 10414 1724 14299\r\n 25506 3527 492 44069 61099 15491 62308 53144 20892 57227\r\n 48497 56504 45149 59102 45065 15355 25860 31228 34930 5419\r\n 53584 29028 61998 13051 37247 30454 38303 7621 21415 30500\r\n 39344 35914 57248 19548 24959 40592 39750 57391 39465 1437\r\n 5570 37149 7423 32539 41587 40326 46834 41627 23719 52971\r\n 60447 44590 23237 58320 23804 8036 26315 6375 8842 11744\r\n 3512 24338 15855 32860 26713 8112 56275 59535 59887 10839\r\n 34539 5126 36722 18153 24163 18642 60324 2294 41979 11901\r\n 7789 29907 40155 34993 30696 48216 49206 2605 43173 45313\r\n 24913 3135 19713 37634 32991 26955 18716 64786 44258 14009\r\n 53269 48382 52307 27053 59672 54328 52220 44969 48795 19536\r\n 15997 2490 52143 967 13528 61283 9356 24686 55192 50353\r\n 57961 62537 51189 46056 22190 26153 33066 33051 33859 32843\r\n 46704 48652 23009 33210 37625 3421 40022 50036 9952 59602\r\n 24782 61436 3558 24986 31911 37433 46124 3203 24947 3791\r\n 16313 33643 46445 4255 17184 48999 25122 47574 53806 28622\r\n 16571 15787 65072 23499 37984 20987 47754 45962 11230 37503\r\n 50282 17037 10648 15351 57562 32304 58149 30073 21625 37032\r\n 3267 49740 7442 13336 3994 14526 3660 38161 63338 53989\r\n 44911 65099 59826 53331 28893 61556 9058 22222 52841 8264\r\n 40650 23377 31565 25784 5521 31608 56561 11182 14561 19668\r\n 48934 49339 55823 3511 36912 35389 27639 26161 65521 139\r\n 64045 7212 53078 24579 35344 14487 26955 60278 4177 62331\r\n 25160 39127 12239 50790 50335 6287 62858 14814 27884 50220\r\n 17052 28219 16200 10832 15275 3943 49168 23658 26498 49237\r\n 57505 47888 3551 59783 38493 53707 64290 21270 26233 9100\r\n 52828 17116 39908 20919 30079 50559 15303 5477 7334 22893\r\n 30220 6213 50936 21612 56425 12825 6306 33598 27807 9918\r\n 5961 29554 33493 13384 43308 58662 25203 54582 40209 32553\r\n 36979 41947 1818 50280 23191 44846 32785 59284 64753 52995\r\n 12280 8653 64905 4585 22753 43047 37372 47421 14411 41475\r\n 34844 29676 32829 62261 16627 64905 64004 25100 23205 45115\r\n 23267 42742 21757 10368 62424 2208 32299 19530 17448 41914\r\n 20629 54198 11395 18772 19542 27803 26272 45332 19103 47796\r\n 47627 20190 41001 45031 10381 32111 65207 57701 12346 56350\r\n 33801 26369 37692 9250 23677 38240 17104 60591 1498 41088\r\n 51815 57948 49216 33560 48603 5457 43602 5324 29452 11835\r\n 13401 45913 10061 47272 46261 43263 63193 31632 15967 37572\r\n 44440 15851 23382 60872 45933 3427 43984 8405 56932 10719\r\n 3439 49796 9433 47979 408 36492 19606 16574 34643 59379\r\n 52505 19066 55745 49142 24533 46663 34807 57931 59908 5068\r\n 44470 18182 22142 26694 59080 31975 95 12863 63827 22186\r\n 61997 400 18035 15695 20863 40475 57919 7953 38366 38051\r\n 6000 24557 393 34134 39130 14010 26501 35631 7797 31145\r\n 59535 28634 52554 14357 19516 42313 19739 20618 60721 52777\r\n 33420 19942 32598 55206 8192 24945 62297 25037 38899 34785\r\n 40298 19061 35248 43445 25451 6796 30189 51874 57908 14897\r\n 20714 15893 57076 53492 53587 24740 18851 54996 27818 46496\r\n 5078 61386 47372 52027 64302 17226 5546 44579 39797 9740\r\n 55745 56373 43783 30743 56491 15812 38153 27323 4637 43130\r\n 9471 26032 11719 20285 5493 40823 10031 42132 60605 41548\r\n 24280 31419 36077 45061 22132 34270 4790 14030 42079 15027\r\n 40789 37027 62906 64674 15474 27081 38047 40453 6848 11942\r\n 65375 32087 39060 50458 20827 14273 18809 44249 45889 10902\r\n 33904 17682 52990 54367 64516 56266 23718 39388 25939 9804\r\n 64914 64863 64522 46273 35930 56427 47502 22695 5564 13287\r\n 14846 12037 58059 39015 49102 18608 56250 23881 14056 62584\r\n 26083 56469 14014 49340 55171 40330 22801 11238 16305 1042\r\n 45650 2138 2269 32553 10937 51084 63028 52124 14853 62751\r\n 4236 21755 29564 56697 59185 62576 62493 32287 46072 1683\r\n 48998 49069 904 4458 6889 60267 13502 23240 49424 63642\r\n 27551 42229 31045 63474 48830 25219 50347 50794 35866 19503\r\n 53170 11091 62337 6472 47800 10658 40339 15519 36273 34411\r\n 24877 62403 16315 35846 47020 52215 60222 55367 41325 56514\r\n 20910 35603 25324 26409 8744 7459 39487 53511 64582 58746\r\n 64621 16476 28274 7014 29215 10408 46015 55458 41568 12386\r\n 47066 37917 54452 47458 33343 23319 48737 24260 39351 43300\r\n 27078 59996 54044 40218 34766 55558 25238 25115 59584 61684\r\n 6463 58693 29687 51312 56342 38193 16482 56448 37410 63943\r\n 48140 31621 24940 37134 44415 38415 2409 30402 21982 7073\r\n 41766 29015 60677 53170 52811 60675 30941 37391 62727 11724\r\n 4839 20431 48551 37799 34815 37688 42275 45567 28830 48925\r\n 7897 3625 48341 61867 62645 653 18282 62974 39422 3241\r\n 64329 49400 62057 57111 4369 53043 33938 35803 47203 4671\r\n 32558 8647 33429 33266 35488 39898 16100 41718 44484 32055\r\n 1468 23325 51896 51696 18458 31451 19497 37414 13943 55698\r\n 3527 25943 29633 31000 31516 17592 42629 60759 5349 65342\r\n 9232 58033 55653 54316 44883 16914 58418 56607 17988 287\r\n 58554 1391 25587 21134 13648 31523 56433 11130 56853 35560\r\n 30527 55317 48390 63972 39856 14899 13756 11711 36658 56449\r\n 36756 18878 63991 18232 21376 3185 26155 15958 30449 59581\r\n 32404 16406 34294 4773 57727 11091 58188 49268 28200 55400\r\n 4442 32006 28174 49232 8742 16937 16811 13050 50723 57597\r\n 58828 47778 13576 54472 6711 12970 63360 64417 42855 48901\r\n 18911 13278 21194 60446 62856 39694 40577 46506 43104 7699\r\n 17632 14173 7265 21431 10020 53982 10836 11497 10552 33359\r\n 38941 63985 24589 52695 9996 53124 54145 56249 28336 11064\r\n 31187 38878 21620 35274 10194 52575 42971 59599 33101 54467\r\n 24137 19949 22420 30362 5870 46406 35812 63023 24597 60818\r\n 42966 63419 53550 53788 29781 56320 16471 37394 31481 11107\r\n 61485 58718 34844 62384 43836 51189 2631 36888 22440 57916\r\n 40660 12453 34152 4998 54480 13356 15294 11577 50931 25418\r\n 18536 117 50745 46443 51788 65099 23665 33664 25162 25072];\r\nrhat=[8149 10593 825 1418 8962 1559 3161 152\r\n 5086 9561 11949 5217 5798 11589 3150 5329\r\n 8984 3998 7095 390 2183 9925 6985 11431\r\n 3249 1053 7833 4160 13 1692 1976 8920\r\n 9291 9284 9074 2974 5068 10375 80 4023\r\n 11492 5804 6645 1044 7322 19 7192 7839\r\n 9217 4466 10449 3187 2137 119 9226 6202\r\n 7603 5162 8758 12104 7195 7646 6527 5506\r\n 6225 12166 3612 9329 470 7699 9996 11300\r\n 10722 1986 5330 10948 843 4540 11096 7298\r\n 446 7352 2390 5148 9522 11654 1156 8749\r\n 3736 11720 11276 6342 9275 11013 782 1253\r\n 3336 5994 12271 10025 4567 8321 1619 6205\r\n 2010 3243 4122 2079 9240 989 12020 7584\r\n 9610 6632 9036 11327 11665 9187 1417 4616\r\n 3768 1590 10149 3400 4707 5141 3973 5828\r\n 9623 3436 997 6446 10458 5845 8785 4056\r\n 10876 4226 7775 4853 8562 9793 8662 8391\r\n 6182 3663 10851 2565 5271 5953 11059 715\r\n 7529 4284 2244 8402 12053 7689 541 5153\r\n 8110 5951 6609 335 3517 6766 6683 3012\r\n 4955 3196 8713 6749 246 5847 2747 7607\r\n 8485 2656 4214 985 4827 2550 11484 11457\r\n 3124 1611 3563 382 1919 3058 8499 5773\r\n 1423 2757 1327 11084 6349 455 1929 417\r\n 9081 10604 613 10502 7325 8929 7125 8483\r\n 9465 10411 2134 3556 986 530 9950 1448\r\n 10951 8652 3309 7995 6767 315 3390 507\r\n 11937 8868 12228 5740 6625 1837 388 11209\r\n 3858 829 1248 12057 7320 3536 2756 5663\r\n 10974 3976 8957 11721 4338 9767 11429 8609\r\n 6564 1713 9831 10924 912 9766 6373 7233\r\n 3700 1269 4315 8607 4546 8196 9941 7644\r\n 878 11980 10491 2706 3912 9513 2567 8190\r\n 643 379 4709 9262 11112 1860 4737 11022\r\n 1323 3739 8110 8196 11511 2236 8007 9557\r\n 12024 10027 11760 11831 2394 500 6894 389\r\n 8560 4490 168 8370 1272 5988 6261 8753\r\n 4943 2775 2362 2464 10956 12172 2558 5757\r\n 1707 7697 6861 2490 6732 4772 9887 8195\r\n 4315 3792 1287 580 3928 6061 9571 1812\r\n 783 5756 2086 9790 5118 7639 6449 7058\r\n 11898 3862 2787 12173 4520 5695 212 1507\r\n 5346 9561 654 9830 5535 5850 4702 3448\r\n 5173 7945 740 8601 2757 3408 1153 7755\r\n 8707 6923 4891 11539 7076 10827 10657 1702\r\n 11981 8090 5301 856 10035 6307 10356 11679\r\n 9453 2222 1223 9948 10545 6152 6122 5565\r\n 10032 113 4049 4053 8376 11269 10270 1305\r\n 2126 1286 6659 881 3528 8590 10609 9754\r\n 11887 3876 1784 6936 1034 6381 1763 12219\r\n 5357 1336 7692 2667 7716 9060 8531 5530\r\n 5945 11985 2654 2560 6865 4738 11695 801\r\n 5824 6645 6710 6940 2131 2231 1940 4950\r\n 746 3214 6012 8276 8247 3992 9384 5457\r\n 7807 4112 9317 2273 1130 10350 8548 8193\r\n 3642 8624 8082 4908 10678 1835 7296 848\r\n 10867 11073 9696 2669 5746 1260 7347 4877\r\n 11495 5170 991 10986 8479 5253 2646 10197\r\n 5326 2942 11788 1621 2984 294 10203 9804\r\n 4494 2383 294 5111 1339 10478 8541 9356\r\n 2187 172 5127 8875 8915 789 2201 5140\r\n 5160 10441 4096 9010 10106 11593 6362 9775\r\n 4295 10907 1824 1894 5510 5337 9922 3371\r\n 8127 5345 4006 5209 10033 2859 4601 5742\r\n 3793 8908 6314 7883 8653 11031 10085 5403\r\n 3859 7385 4404 8611 5490 3923 8187 480\r\n 9766 12182 901 3569 10257 6668 3709 6931\r\n 2481 9841 9271 2472 11437 391 12053 4980\r\n 11992 3545 10994 9307 11791 322 3678 9815\r\n 1904 6151 10952 4868 10935 8320 9856 9570\r\n 6752 254 9868 7270 9019 3920 1414 1270\r\n 10364 4598 11037 3621 3234 9263 10271 11024\r\n 5000 1675 5510 7650 440 5417 10452 1974\r\n 5922 4450 6056 5245 1126 2867 2645 7398\r\n 1290 5398 5692 8986 3751 7506 2269 488\r\n 1909 5213 4327 8275 5794 534 11630 11908\r\n 53 6833 5782 5954 9629 5503 2239 5699\r\n 10980 10804 4193 10615 236 6096 2895 8953\r\n 5824 11122 7883 2053 6154 4548 5701 5575\r\n 1747 6519 6826 4063 11574 7423 9720 4636\r\n 11375 6605 1810 10176 6039 587 10520 10310\r\n 1100 3029 3862 8091 10427 4614 10870 2274\r\n 8785 11559 6971 4077 925 4907 5804 7863\r\n 3296 12221 8683 3445 3022 7680 11201 3591\r\n 773 3117 2404 968 4600 2668 10518 468\r\n 215 6056 7487 11731 2328 6050 2762 8744\r\n 677 1468 5443 8970 9622 8609 391 9362\r\n 850 9053 2676 10194 5487 10187 1917 5679\r\n 2586 415 8841 4002 8329 9123 1706 6923\r\n 4346 8013 11694 7230 4849 5346 958 9474\r\n 5828 10768 3592 11256 12214 6209 5772 4820\r\n 8719 3551 5014 187 8099 3338 9425 8455\r\n 11193 3088 2025 7193 3726 6393 4237 10983\r\n 7306 3335 9019 6401 11140 9163 2214 8141\r\n 2901 2598 7927 9127 3635 7468 2931 9271\r\n 6188 83 8923 5051 213 3750 10987 11744\r\n 3529 829 6394 6310 8428 11624 392 10014\r\n 10407 6190 4717 10647 8578 4959 8400 9476\r\n 11730 3977 3410 10130 8954 3171 6364 1588\r\n 9146 6763 11717 2289 12045 329 1489 4830\r\n 6135 7211 568 10450 9554 3037 5529 9\r\n 3995 1662 12272 11074 5671 1469 7367 4854\r\n 4549 8081 2025 3242 8687 5009 9142 2004\r\n 10161 2020 4083 1333 4743 5254 194 6885\r\n 226 11966 6259 3939 5004 11828 3961 10006\r\n 3966 8223 9013 2152 7274 11391 120 3271\r\n 12189 1703 2227 5125 5269 7245 8442 8137\r\n 4036 7892 8282 9848 5536 4409 7306 8365\r\n 4788 10993 10891 2650 5180 9379 5748 3115\r\n 1578 10933 4035 6497 8116 7574 4788 9184\r\n 7292 2637 2829 2197 6402 5607 8814 3297\r\n 12163 6864 3905 4982 6710 7802 10831 1012\r\n 8629 6883 3876 2358 3998 1465 7663 5577\r\n 1940 6499 1233 11847 8131 8283 577 8690\r\n 8536 1709 11555 7614 1606 7021 2479 10991\r\n 7673 6724 9074 5707 3131 11008 10835 5567\r\n 6706 321 12276 3407 4790 11852 3340 4209\r\n 887 6216 706 7716 9370 2905 8846 170\r\n 9563 7171 5219 7938 3769 7095 68 2976\r\n 3914 3867 11656 347 7395 8967 5517 894\r\n 2589 4130 10205 5493 3040 4057 10259 5751\r\n 248 10770 3157 1900 1428 11496 3608 7411\r\n 11099 5378 8023 1291 11427 1273 10747 9407\r\n 1600 586 9694 4493 2681 3073 2814 9289\r\n 11724 11813 7932 7385 3639 1582 135 5276\r\n 8990 10675 10619 10670 6193 10730 4885 10384\r\n 5511 2999 4965 9346 562 3131 11572 6417];\r\nassert(isequal(numberTheoreticTransform(r(:)',n,p),rhat(:)'))\r\n%%\r\nn=256;\r\np=3329;\r\nr=[17789 14064 31398 7235 4452 54042 17029 9244 41506 19221 25101 62219 54529 40064 62923 42789\r\n 56877 51841 65136 14198 13625 50288 57544 47986 60999 3380 64958 16802 49403 3404 61808 25001\r\n 48595 42905 39615 53151 2595 65348 12338 45289 64079 33038 18797 64871 40754 37730 7385 19662\r\n 29351 1713 61925 9087 30759 14919 49754 2260 6133 50356 46280 22925 25827 55203 42486 22291\r\n 46506 51496 32141 57796 9836 60263 2076 32037 43367 18545 35075 13665 23545 32750 31509 60222\r\n 61887 60461 28701 60526 64966 42074 42096 63661 39503 14769 12662 43635 5823 28771 4359 29901\r\n 11410 32264 50636 835 27987 6902 37150 7369 31052 21711 45182 63789 22392 9768 58836 28999\r\n 16029 54657 48763 24717 62611 17574 24668 48707 23347 29704 3306 40809 35957 1853 32586 29765\r\n 42003 8608 29026 10997 47464 50059 13929 41847 31167 48325 12087 4164 30182 49589 50548 61950\r\n 52993 49793 3473 35404 38069 52789 51914 38940 43976 33415 2992 24478 42300 52173 3955 14360\r\n 55926 60669 5755 6662 35406 6832 9531 32677 62891 25068 58002 10895 33654 19238 17200 57829\r\n 26091 54572 52296 2573 46231 30786 32056 37214 5838 59341 55036 15157 53374 7550 42668 1302\r\n 7569 17000 42964 61160 329 14356 841 27951 52280 63259 7743 3421 6368 24582 8755 22397\r\n 5261 13960 2119 63674 51282 60470 12229 4996 38717 41174 26896 59097 30389 54322 41847 50202\r\n 23623 34230 36507 23653 60742 20992 31800 19043 59781 8652 7879 51989 38654 55166 25227 22465\r\n 54323 26041 47172 42218 543 56199 54933 36787 6627 40521 37492 24445 12266 43597 50180 40554];\r\nrhat=[1004 2562 12 2074 386 769 3081 923 234 324 3276 3310 1457 2786 1538 1203\r\n 2725 438 1145 992 1049 2056 79 1027 2483 2538 4 2926 2235 1721 1323 1176\r\n 545 183 3074 501 2640 855 1161 2419 1203 813 3106 2589 2852 1456 1682 1723\r\n 69 623 2891 274 813 1126 3161 654 3073 693 2162 3089 2845 612 3031 293\r\n 592 1068 1284 749 404 1253 426 1999 2639 2516 1092 2077 453 1649 2336 3163\r\n 2039 495 51 1711 1959 1829 200 3273 2348 141 1326 760 3201 400 2955 3279\r\n 1452 1853 1912 973 666 1696 2042 965 1095 210 3132 160 766 740 1804 2075\r\n 2315 2977 2197 3084 1811 340 140 1425 1279 3194 758 2224 2692 1839 2400 1477\r\n 2429 1148 2851 2684 3141 1255 2870 3295 2652 899 716 1549 406 517 1155 2856\r\n 3116 1361 1678 2120 1646 915 1518 1631 1685 2535 2169 1417 1796 828 1899 911\r\n 309 738 754 2490 1194 2757 1105 1086 1929 1892 1032 1186 1805 1880 2454 621\r\n 1514 1448 2271 2505 856 47 1949 2456 1700 1041 112 2844 2723 1705 981 781\r\n 3026 1470 145 2240 171 2116 3322 2831 2726 1800 1228 873 2341 2557 246 887\r\n 1275 2019 1990 1422 1937 820 605 925 2552 93 1790 1408 1989 2718 2353 3141\r\n 1249 376 831 1305 2941 1750 2254 2190 2703 774 1527 1776 1829 2916 661 2171\r\n 1503 1689 2004 368 643 2582 2079 2419 999 2909 3317 764 1712 2256 2638 3065];\r\nassert(isequal(numberTheoreticTransform(r(:)',n,p),rhat(:)'))\r\n\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":145982,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":3,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-10-06T20:08:10.000Z","updated_at":"2025-10-13T12:54:40.000Z","published_at":"2020-10-06T20:17:36.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven an input polynomial (r) of length \u0026lt;=n and a prime number (p) such that an nth root of unity exists and the modular inverse of (n) modulus p exists. Convert the polynominal coefficents by Number Theoretic Transform (NTT) using the primitive nth root of unity as the generator mod p.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"term":"tag:\"number theoretic transform\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"number theoretic transform\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"number theoretic transform\"","","\"","number theoretic transform","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f4f2619bb90\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f4f2619ba50\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f4f2619b0f0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f4f2619be10\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f4f2619bd70\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f4f2619bcd0\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f4f2619bc30\u003e":"tag:\"number theoretic transform\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f4f2619bc30\u003e":"tag:\"number theoretic transform\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"search","password":"J3bGPZzQ7asjJcCk","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"number theoretic transform\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"number theoretic transform\"","","\"","number theoretic transform","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f4f2619bb90\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f4f2619ba50\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f4f2619b0f0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f4f2619be10\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f4f2619bd70\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f4f2619bcd0\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f4f2619bc30\u003e":"tag:\"number theoretic transform\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f4f2619bc30\u003e":"tag:\"number theoretic transform\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":46696,"difficulty_rating":"medium-hard"}]}}