Cody

Problem 46633. Montgomery Reduction Algorithm (REDC)

Solution 3033298

Submitted on 2 Oct 2020 by David Hill
  • Size: 51
  • This is the leading solution.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Test Suite

Test Status Code Input and Output
1   Pass
R=2.^[12:22]; N=primes(3329); N=N(end-10:end); [R,N]=meshgrid(R,N); T =[ 245 2125 3406 4031 1103 2731 1888 927 2393 733 2175 2794 3986 3291 685 1732 730 4021 1576 442 1733 2681 174 2659 248 436 2245 525 641 2388 3713 386 1670 293 3279 1636 1526 3862 4093 3505 1032 3604 2452 3359 2137 1859 2159 812 1712 701 2641 1190 3350 1929 2943 397 1772 1708 2006 4027 134 1542 2528 1068 2851 3968 3352 3381 2691 1391 1235 2299 783 1087 2435 2867 2177 3349 342 2573 3898 2872 3613 1755 3377 93 2616 1332 2960 546 1196 3770 2730 2741 1975 4025 1742 138 433 614 711 1769 216 2209 781 495 2992 1281 282 2503 2702 1602 64 3023 2860 1512 2415 1409 662 1310 3190]; t =[ 965 2824 466 632 1786 471 83 3114 3135 2021 1616 3008 903 1415 316 2406 3151 239 2361 949 663 74 374 1378 845 2346 1114 994 433 2825 3084 3120 2190 266 2482 282 1831 1556 2344 71 1834 3139 1400 3056 1944 2255 2061 2374 650 1006 2248 1547 528 2029 437 96 2426 968 2447 1649 1057 1278 354 80 1986 1323 3043 2649 683 1846 2303 2169 1003 2582 2390 694 816 2818 1790 59 2204 1259 1217 2483 2892 3033 978 173 636 1615 2401 1800 2254 2757 897 809 1943 3013 25 349 37 913 129 1375 3105 1335 2927 184 1530 38 2382 2054 3316 3100 635 1262 2996 2717 2415 2133 3118]; assert(isequal(REDC(T,R,N),t))