{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2026-04-06T14:01:22.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":"2026-04-06T00: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":46636,"title":"Montgomery Multiplication","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=\"\"\u003eMultiply all elements of an input matrix (A) modulo N, given all elements are less than R (2^number of bits). Where gcd(R,N)=1 and N\u0026lt;R. Output the final result, P (in normal form) and all intermediate products (p) in Montgomery form \u003c/span\u003e\u003cspan style=\"border-block-end-style: solid; border-block-end-width: 1px; border-bottom-style: solid; border-bottom-width: 1px; \"\u003e(\u003c/span\u003e\u003cspan style=\"\"\u003efirst product is just first element of matrix (A)*R modulo N\u003c/span\u003e\u003cspan style=\"border-block-end-style: solid; border-block-end-width: 1px; border-bottom-style: solid; border-bottom-width: 1px; \"\u003e)\u003c/span\u003e\u003cspan style=\"\"\u003e.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function [P,p] = montgomeryMult(a,R,N)\r\n P=N-1;\r\n p=mod(a,N);\r\nend","test_suite":"%%\r\nR=2^16;\r\nN=3329;\r\nY=2050;\r\ny =[ 1263 470 2922 960 982 369 2562 2142 1318 744];\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44576 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51731 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22389\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n%%\r\nN=3347;\r\nR=2^16;\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44596 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51771 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22389\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\nY=1870;\r\ny=[130,1496,2440,2533,1292,1876,783,751,107,3006];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n%%\r\nR=2^16;\r\nN=3967;\r\nY=3799;\r\ny=[788,2020,2960,1688,2874,3752,1280,2265,1542,1371];\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44596 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51771 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22999\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":145982,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":4,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-09-30T21:17:47.000Z","updated_at":"2025-10-12T15:14:20.000Z","published_at":"2020-09-30T21:17:47.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\u003eMultiply all elements of an input matrix (A) modulo N, given all elements are less than R (2^number of bits). Where gcd(R,N)=1 and N\u0026lt;R. Output the final result, P (in normal form) and all intermediate products (p) in Montgomery form (first product is just first element of matrix (A)*R modulo N).\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":46636,"title":"Montgomery Multiplication","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=\"\"\u003eMultiply all elements of an input matrix (A) modulo N, given all elements are less than R (2^number of bits). Where gcd(R,N)=1 and N\u0026lt;R. Output the final result, P (in normal form) and all intermediate products (p) in Montgomery form \u003c/span\u003e\u003cspan style=\"border-block-end-style: solid; border-block-end-width: 1px; border-bottom-style: solid; border-bottom-width: 1px; \"\u003e(\u003c/span\u003e\u003cspan style=\"\"\u003efirst product is just first element of matrix (A)*R modulo N\u003c/span\u003e\u003cspan style=\"border-block-end-style: solid; border-block-end-width: 1px; border-bottom-style: solid; border-bottom-width: 1px; \"\u003e)\u003c/span\u003e\u003cspan style=\"\"\u003e.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function [P,p] = montgomeryMult(a,R,N)\r\n P=N-1;\r\n p=mod(a,N);\r\nend","test_suite":"%%\r\nR=2^16;\r\nN=3329;\r\nY=2050;\r\ny =[ 1263 470 2922 960 982 369 2562 2142 1318 744];\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44576 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51731 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22389\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n%%\r\nN=3347;\r\nR=2^16;\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44596 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51771 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22389\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\nY=1870;\r\ny=[130,1496,2440,2533,1292,1876,783,751,107,3006];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n%%\r\nR=2^16;\r\nN=3967;\r\nY=3799;\r\ny=[788,2020,2960,1688,2874,3752,1280,2265,1542,1371];\r\na =[ 1112 36822 19271 42840 48879 33433 48232 54170 3299 62565\r\n 7920 12071 15556 62713 53288 59399 52080 25560 14987 28219\r\n 56538 39138 34791 61324 25120 41217 35710 32630 54669 63016\r\n 31738 19656 5996 30008 40454 6654 44972 45534 1025 49965\r\n 55368 8789 26562 15759 37715 25615 58565 54681 56604 481\r\n 13723 13933 6871 50062 34737 3579 3590 39952 5116 44567\r\n 36194 58650 7358 49763 18026 32852 19900 37665 43846 46265\r\n 41280 4682 51408 48539 16294 28293 3027 21367 32781 42279\r\n 2096 15891 19108 48738 29598 65376 12810 29912 14286 36196\r\n 40285 3522 39553 6941 14923 53189 47196 46779 37461 14293\r\n 23750 28948 63204 44666 52720 31827 47300 57960 8007 50617\r\n 3246 870 28343 30360 64625 58618 57527 47241 43985 14944\r\n 32084 58798 45531 13904 1965 9014 38170 1219 39294 24304\r\n 12616 12888 49682 6456 35105 25559 4632 44222 3668 58387\r\n 8066 6119 28353 53973 5706 60775 60472 28738 3692 56123\r\n 13467 20143 42958 11469 52565 60128 52453 28692 9994 26373\r\n 9602 29888 7192 10719 64824 46764 18739 7670 1285 20841\r\n 12391 6663 61194 43646 4387 40523 35629 53390 28519 39887\r\n 2795 65233 12285 58614 61564 22497 64538 21289 54540 59650\r\n 41628 21764 17444 33853 1191 61343 46902 16136 40461 59578\r\n 18472 19486 52286 46052 44816 8177 54982 22460 34087 38770\r\n 35297 4066 31955 10065 51362 47879 28394 24621 56614 21795\r\n 45558 19545 50394 62485 35005 42367 30842 35818 6402 55906\r\n 32710 3037 25952 35447 58022 54601 36746 36825 59510 28992\r\n 35114 33123 17887 44547 58917 26101 17635 25940 7078 59267\r\n 29175 49900 2440 2396 41021 49140 49087 26091 33881 2174\r\n 8122 41357 44125 53031 9035 54737 33022 33775 9381 34893\r\n 32136 5891 28151 49061 14273 21132 42389 43091 36658 46956\r\n 55902 5299 29605 7876 11936 36193 20168 62319 300 11750\r\n 57273 50937 39967 34409 2740 64168 9091 47339 50245 22055\r\n 17714 59318 3893 21353 7008 35999 31167 26219 55621 12301\r\n 13661 34981 20697 35812 40399 21654 23754 54517 60084 21097\r\n 37026 7153 50641 26141 61581 40597 51649 8803 64681 26467\r\n 41963 54120 45641 27203 23229 23634 51137 3962 33104 35950\r\n 27330 22157 8213 11844 26910 49578 43811 5521 17787 3194\r\n 13498 19265 8529 16737 64510 27125 8749 10741 6602 36223\r\n 62123 48910 6052 1345 61969 32266 1412 21248 33282 18010\r\n 5378 677 512 60534 44344 45530 36689 19773 38378 15827\r\n 6927 3175 27728 42840 64769 63749 19714 765 49996 15934\r\n 9308 43772 42963 61119 50255 21479 61565 35383 5437 10102\r\n 10909 39548 47377 10715 22065 54906 64284 6250 43358 62679\r\n 40695 34478 34813 60365 43409 48435 18783 9601 33880 61319\r\n 37598 47822 7131 52078 16001 62532 52482 41362 11209 53655\r\n 3412 46350 41403 37840 19366 2092 58727 56316 61509 47727\r\n 61027 51208 8290 28838 44596 23387 39159 63846 38697 11521\r\n 47753 18872 8801 16882 34592 43427 57934 37410 28877 23617\r\n 48355 45385 6461 49279 26974 18448 61848 65329 61729 12372\r\n 4155 36481 9307 14986 39494 15098 35989 36276 42985 78\r\n 56389 25986 11026 4206 49186 46604 47735 33781 29618 20736\r\n 61237 4036 12861 50287 38242 40932 37798 21671 55030 45850\r\n 64513 51129 20806 43987 36162 38706 1694 28180 34906 40976\r\n 56291 22123 20737 46872 38244 43282 29263 32231 36299 35590\r\n 51482 39837 14258 42078 33542 3116 42356 4655 44568 28772\r\n 33644 48578 16452 27462 5412 22857 34157 58178 24064 18836\r\n 11639 6869 58518 25608 47157 29579 24399 4235 15682 32876\r\n 26121 8381 46086 53486 65284 15787 61416 28585 37940 49908\r\n 8777 36014 36420 20802 23234 46861 54364 54173 56812 49965\r\n 2024 31799 12087 53381 63652 56110 55645 25856 26658 37752\r\n 61547 58358 13895 51712 22704 18448 24414 40204 7380 48998\r\n 19746 52360 5069 55853 58100 47910 38874 53650 29087 42305\r\n 19368 48125 59886 33137 29798 9028 57183 58080 19672 8075\r\n 21819 3364 46315 41658 27094 54835 61177 61021 26305 33056\r\n 30609 4776 36555 62317 14269 9083 43808 12503 54615 22758\r\n 42480 5801 20540 29095 8234 38548 13551 16946 26452 6038\r\n 1653 52320 10892 3933 20245 23996 42850 58842 25570 9689\r\n 55194 61800 40795 56803 47585 52871 4721 38886 23622 12987\r\n 36636 44807 64745 41365 51306 33015 26655 33019 9191 44057\r\n 55974 8656 11169 23270 45468 32086 43708 40161 17047 28279\r\n 22798 47364 16894 65339 642 57478 61192 53701 5689 45508\r\n 29230 7232 26004 14691 55260 23143 53146 34857 28140 16828\r\n 3554 7700 4849 42759 60445 29454 31755 13243 16861 639\r\n 11606 41990 44832 39648 50525 63145 49594 29746 19500 34883\r\n 43437 21549 26370 25378 2795 2772 27331 28043 27843 18310\r\n 21681 42848 64411 9318 24784 63763 63686 63311 7812 62012\r\n 58883 49095 26357 1647 46159 12399 64747 40635 32444 59404\r\n 7743 38219 40676 27598 47809 43720 56632 45573 46295 25734\r\n 64776 48498 10116 12065 14698 38432 25485 47196 15962 1628\r\n 35388 15389 24991 47564 17632 44244 29801 22734 51450 44003\r\n 46328 48166 10560 24272 44107 23659 16166 33881 4855 54864\r\n 65502 63609 49683 55152 31292 40650 51407 36483 25813 63668\r\n 18864 56815 57089 48118 40875 53159 57857 10256 222 3731\r\n 27166 5651 22988 37422 15495 1262 59881 36834 14462 29512\r\n 30463 24014 44927 11590 11607 5496 36587 45534 85 38172\r\n 50066 24195 19277 62743 54371 63884 39247 27948 12398 44999\r\n 53621 44894 34775 17388 50260 42686 9756 54805 9337 47148\r\n 6568 39186 54553 60593 61241 15154 58963 47932 17568 42601\r\n 11673 51771 39157 14665 7070 26443 29516 23594 11461 47639\r\n 23569 24094 21974 24481 11942 7996 13478 29767 9086 24500\r\n 3716 13502 19610 5734 6494 17592 58959 25322 39248 38114\r\n 34202 5679 29661 41950 32097 16898 49976 50826 59051 7609\r\n 22010 50589 27698 11836 12664 21736 57834 48121 61563 3778\r\n 11512 13479 23567 2952 58713 9976 18674 28198 14495 64209\r\n 13693 25445 36590 47393 6493 22807 44120 45465 31632 18666\r\n 59320 36161 48663 22769 2894 7973 43534 61945 24642 38992\r\n 44262 15004 27809 43294 36522 57943 8048 51395 34326 63056\r\n 30701 42070 28138 25157 50626 6178 26694 46240 17358 12175\r\n 59777 31750 8183 41113 20443 60951 18041 7165 4479 12651\r\n 6816 9951 1601 1418 11729 26150 46967 25554 28595 22999\r\n 48860 51244 19017 59675 22213 3106 18571 38725 11393 61138\r\n 48252 6593 20809 52465 13772 22437 58733 30105 1710 25602];\r\n[P,p]=montgomeryMult(a,R,N);\r\nassert(isequal(P,Y))\r\nassert(isequal(y,p(10:100:end)))\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":145982,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":4,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-09-30T21:17:47.000Z","updated_at":"2025-10-12T15:14:20.000Z","published_at":"2020-09-30T21:17:47.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\u003eMultiply all elements of an input matrix (A) modulo N, given all elements are less than R (2^number of bits). Where gcd(R,N)=1 and N\u0026lt;R. Output the final result, P (in normal form) and all intermediate products (p) in Montgomery form (first product is just first element of matrix (A)*R modulo N).\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:\"montgomery multiplication\"","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:\"montgomery multiplication\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"montgomery multiplication\"","","\"","montgomery multiplication","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f0f57da69a8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f0f57da6908\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f0f57dfdc08\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f0f57da6f48\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f0f57da6d68\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f0f57da6ae8\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f0f57da6a48\u003e":"tag:\"montgomery multiplication\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f0f57da6a48\u003e":"tag:\"montgomery multiplication\""},"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":"cody-search","password":"78X075ddcV44","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:\"montgomery multiplication\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"montgomery multiplication\"","","\"","montgomery multiplication","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f0f57da69a8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f0f57da6908\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f0f57dfdc08\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f0f57da6f48\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f0f57da6d68\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f0f57da6ae8\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f0f57da6a48\u003e":"tag:\"montgomery multiplication\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f0f57da6a48\u003e":"tag:\"montgomery multiplication\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":46636,"difficulty_rating":"medium-hard"}]}}