205:
1679:
110:
25:
66:
340:, because it provides faster computation than with the usual numeral systems, even when the time for converting between numeral systems is taken into account. Other applications of multi-modular arithmetic include
868:
463:
equal to one). Residue number systems have been defined for non-coprime moduli, but are not commonly used because of worse properties. Therefore, they will not be considered in the remainder of this article.
1213:
1271:) is difficult and, usually, requires to convert integers to the standard representation. As a consequence, this representation of numbers is not suitable for algorithms using inequality tests, such as
1716:. By decomposing in this a large integer into a set of smaller integers, a large calculation can be performed as a series of smaller calculations that can be performed independently and in parallel.
1498:
446:
550:
612:
1239:
For a succession of operations, it is not necessary to apply the modulo operation at each step. It may be applied at the end of the computation, or, during the computation, for avoiding
1412:
664:
1254:
If two integers are equal, then all their residues are equal. Conversely, if all residues are equal, then the two integers are equal, or their differences is a multiple of
1358:
791:
1610:
234:
1531:
1664:
1637:
704:
1246:
However, operations such as magnitude comparison, sign computation, overflow detection, scaling, and division are difficult to perform in a residue number system.
2086:
1935:
1575:
1555:
1325:
1305:
1132:
1073:
888:
753:
1018:
955:
120:
2032:
2258:
Orange, Sébastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012). "Efficient arithmetic in successive algebraic extension fields using symmetries".
38:
1993:
2144:
2102:
2064:
1765:
2128:
796:
2310:
341:
1912:
1900:
276:
256:
178:
52:
1140:
1771:
150:
2335:
2320:
157:
135:
1423:
1948:
370:
477:
2389:
898:
For adding, subtracting and multiplying numbers represented in a residue number system, it suffices to perform the same
2163:
565:
217:
164:
2384:
227:
221:
213:
2357:
Isupov, Konstantin (2021). "High-Performance
Computation in Residue Number System Using Floating-Point Arithmetic".
2204:
84:
78:
44:
2287:
Yokoyama, Kazuhiro (September 2012). "Usage of modular techniques for efficient computation of ideal operations".
146:
720:
314:
238:
2245:
Lecerf, Grégoire; Schost, Éric (2003). "Fast multivariate power series multiplication in characteristic zero".
2013:
1757:
460:
2296:
HladĂk, Jakub; Ĺ imeÄŤek, Ivan (January 2012). "Modular
Arithmetic for Solving Linear Equations on the GPU".
1943:
1366:
2056:
2009:
1730:
1534:
623:
326:
2010:
Residue Number System-Based
Solution for Reducing the Hardware Cost of a Convolutional Neural Network
1842:
1931:
1932:
Residue-to-binary conversion for general moduli sets based on approximate
Chinese remainder theorem
1713:
1276:
171:
1330:
758:
325:, exactly one integer having any given set of modular values. Using a residue numeral system for
2275:
2233:
2213:
2182:
1989:
1981:
1895:
Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J., eds. (1986).
1272:
1233:
899:
556:
306:
1580:
2150:
2140:
2108:
2098:
2060:
2021:
1973:
1965:
1918:
1908:
1860:
1795:"An approximate sign detection method for residue numbers and its application to RNS division"
1761:
2076:
2344:
2307:
Proceedings of the 2015 ACM on
International Symposium on Symbolic and Algebraic Computation
2267:
2223:
2132:
2090:
1957:
1850:
1809:
1506:
1240:
1229:
456:
345:
310:
2331:"Multi-Modular Approach to Polynomial-Time Factorization of Bivariate Integral Polynomials"
2122:
1642:
1615:
682:
1997:
1725:
336:
Multi-modular arithmetic is widely used for computation with large integers, typically in
2318:
Lecerf, Grégoire (2018). "On the complexity of the
Lickteig–Roy subresultant algorithm".
2121:
Amir
Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, eds. (2017-03-21).
1961:
1846:
83:
Please expand the article to include this information. Further details may exist on the
2190:
1560:
1540:
1310:
1290:
1082:
1023:
873:
738:
337:
298:
2305:
Pernet, Clément (June 2015). "Exact linear algebra algorithmic: Theory and practice".
1829:"Using Floating-Point Intervals for Non-Modular Computations in Residue Number System"
1751:
1678:
971:
908:
2378:
2082:
1985:
1813:
728:
2279:
2237:
2228:
2199:
127:
2029:
IMACS'05: World
Congress: Scientific Computation Applied Mathematics and Simulation
1710:
349:
1897:
Residue Number System
Arithmetic: Modern Applications in Digital Signal Processing
2368:
1887:
1855:
1833:
1828:
109:
1944:"Large Systems of Boolean Functions: Realization by Modular Arithmetic Methods"
1794:
2271:
2136:
2094:
1904:
1969:
1864:
1236:
by the right operand). Subtraction and multiplication are defined similarly.
2167:
2359:
2349:
2330:
65:
1287:
Division in residue numeral systems is problematic. On the other hand, if
710:
have the same representation in the residue numeral system defined by the
471:
is represented in the residue numeral system by the set of its remainders
302:
2020:
Bajard, Jean-Claude; MĂ©loni, Nicolas; Plantard, Thomas (2006-10-06) .
863:{\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }
2001:
2289:
International
Workshop on Computer Algebra in Scientific Computing
2218:
2154:
2124:
Embedded Systems Design with Special Arithmetic and Number Systems
2112:
313:
integers called the moduli. This representation is allowed by the
321:
is the product of the moduli, there is, in an interval of length
1977:
1922:
2247:
SADIO Electronic Journal on Informatics and Operations Research
1930:
Chervyakov, N. I.; Molahosseini, A. S.; Lyakhov, P. A. (2017).
735:. That is, each set of residues represents exactly one integer
1884:
Residue Arithmetic and its Applications to Computer Technology
1673:
198:
103:
59:
18:
1208:{\displaystyle z_{i}=(x_{i}+y_{i})\operatorname {mod} m_{i},}
2329:
Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994).
890:
is even, generally an extra negative value is represented).
2291:. Berlin / Heidelberg, Germany: Springer. pp. 361–362.
2008:
Chervyakov, N. I.; Lyakhov, P. A.; Deryabin, M. A. (2020).
727:
different sets of possible residues represents exactly one
2200:"A multimodular algorithm for computing Bernoulli numbers"
1899:. IEEE Press Reprint Series (1 ed.). New York, USA:
1690:
131:
1938:, 94:9, 1833-1849, doi: 10.1080/00207160.2016.1247439.
1493:{\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},}
799:
1645:
1618:
1583:
1563:
1543:
1509:
1426:
1369:
1333:
1313:
1293:
1143:
1085:
1026:
974:
911:
876:
761:
741:
685:
626:
568:
480:
373:
1753:
Computer Arithmetic: Algorithms and Hardware Designs
441:{\displaystyle \{m_{1},m_{2},m_{3},\ldots ,m_{k}\},}
545:{\displaystyle \{x_{1},x_{2},x_{3},\ldots ,x_{k}\}}
2016:, 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
1658:
1631:
1604:
1569:
1549:
1525:
1492:
1406:
1352:
1319:
1299:
1207:
1126:
1067:
1012:
949:
882:
862:
785:
747:
698:
658:
606:
544:
440:
2053:Residue Number Systems: Theory and Implementation
706:. Two integers whose difference is a multiple of
607:{\displaystyle x_{i}=x\operatorname {mod} m_{i},}
360:A residue numeral system is defined by a set of
226:but its sources remain unclear because it lacks
2078:Residue Number Systems: Theory and Applications
1882:Szabo, Nicholas S.; Tanaka, Richard I. (1967).
960:is the list of moduli, the sum of the integers
902:on each pair of residues. More precisely, if
2087:Springer International Publishing Switzerland
1936:International Journal of Computer Mathematics
1802:Computers & Mathematics with Applications
8:
1258:. It follows that testing equality is easy.
857:
831:
818:
804:
539:
481:
432:
374:
136:introducing citations to additional sources
968:, respectively represented by the residues
793:. For signed numbers, the dynamic range is
77:about many aspects of the subject (see the
53:Learn how and when to remove these messages
2051:Omondi, Amos; Premkumar, Benjamin (2007).
1232:consisting of taking the remainder of the
2348:
2227:
2217:
2031:. Paris, France. HAL Id: lirmm-00106470.
1854:
1650:
1644:
1623:
1617:
1593:
1588:
1582:
1562:
1542:
1514:
1508:
1481:
1476:
1475:
1462:
1457:
1444:
1431:
1425:
1400:
1399:
1386:
1368:
1338:
1332:
1312:
1292:
1196:
1177:
1164:
1148:
1142:
1112:
1093:
1084:
1053:
1034:
1025:
1001:
982:
973:
938:
919:
910:
875:
849:
810:
800:
798:
760:
740:
690:
684:
650:
637:
625:
595:
573:
567:
533:
514:
501:
488:
479:
426:
407:
394:
381:
372:
277:Learn how and when to remove this message
257:Learn how and when to remove this message
1942:Fin'ko , Oleg Anatolevich (June 2004).
126:Relevant discussion may be found on the
1742:
1261:At the opposite, testing inequalities (
2022:"Efficient RNS bases for Cryptography"
1793:Hung, C.Y.; Parhami, B. (1994-02-01).
1709:RNS have applications in the field of
1407:{\displaystyle C=A\cdot B^{-1}\mod M}
455:, which are generally supposed to be
7:
2129:Springer International Publishing AG
659:{\displaystyle 0\leq x_{i}<m_{i}}
2311:Association for Computing Machinery
1962:10.1023/B:AURC.0000030901.74901.44
1827:Isupov, Konstantin (2020-04-07) .
342:polynomial greatest common divisor
14:
1901:IEEE Circuits and Systems Society
459:(that is, any two of them have a
34:This article has multiple issues.
1677:
203:
119:relies largely or entirely on a
108:
64:
23:
2336:Journal of Symbolic Computation
2321:Journal of Symbolic Computation
2260:Mathematics in Computer Science
2229:10.1090/S0025-5718-2010-02367-1
2187:The Art of Computer Programming
2038:from the original on 2021-01-23
1774:from the original on 2020-08-04
1471:
1395:
42:or discuss these issues on the
2369:doi:10.3390/computation9020009
1183:
1157:
1118:
1086:
1059:
1027:
1007:
975:
944:
912:
846:
834:
1:
2298:Seminar on Numerical Analysis
1949:Automation and Remote Control
1886:(1 ed.). New York, USA:
1756:(2 ed.). New York, USA:
1612:is multiplicative inverse of
2075:Mohan, P. V. Ananda (2016).
1814:10.1016/0898-1221(94)90052-3
1417:can be easily calculated by
1353:{\displaystyle b_{i}\not =0}
786:{\displaystyle 0,\dots ,M-1}
1856:10.1109/ACCESS.2020.2982365
1228:(as usual, mod denotes the
2406:
2205:Mathematics of Computation
1925:. IEEE order code PC01982.
1605:{\displaystyle b_{i}^{-1}}
679:be the product of all the
2272:10.1007/s11786-012-0112-y
2137:10.1007/978-3-319-49742-6
2095:10.1007/978-3-319-41385-3
1750:Parhami, Behrooz (2010).
723:asserts that each of the
721:Chinese remainder theorem
317:, which asserts that, if
315:Chinese remainder theorem
1243:of hardware operations.
559:by the moduli. That is
331:multi-modular arithmetic
212:This article includes a
16:Multi-modular arithmetic
1758:Oxford University Press
719:s. More precisely, the
461:greatest common divisor
241:more precise citations.
147:"Residue number system"
2350:10.1006/jsco.1994.1034
2198:Harvey, David (2010).
2057:Imperial College Press
1731:Reduced residue system
1660:
1633:
1606:
1571:
1551:
1535:multiplicative inverse
1527:
1526:{\displaystyle B^{-1}}
1494:
1408:
1354:
1321:
1301:
1209:
1128:
1069:
1014:
951:
884:
864:
787:
749:
700:
660:
608:
546:
442:
291:residue numeral system
75:is missing information
2164:"Division algorithms"
1661:
1659:{\displaystyle m_{i}}
1634:
1632:{\displaystyle b_{i}}
1607:
1572:
1552:
1528:
1495:
1409:
1355:
1322:
1302:
1210:
1129:
1070:
1015:
952:
894:Arithmetic operations
885:
865:
788:
750:
701:
699:{\displaystyle m_{i}}
661:
609:
547:
443:
327:arithmetic operations
1643:
1616:
1581:
1561:
1541:
1507:
1424:
1367:
1331:
1311:
1291:
1141:
1083:
1024:
972:
909:
874:
797:
759:
739:
683:
624:
566:
478:
371:
132:improve this article
2390:Computer arithmetic
2183:Knuth, Donald Ervin
1847:2020IEEEA...858603I
1714:computer arithmetic
1601:
1470:
1277:Euclidean algorithm
2385:Modular arithmetic
2212:(272): 2361–2370.
1927:(viii+418+6 pages)
1689:. You can help by
1656:
1629:
1602:
1584:
1567:
1547:
1523:
1490:
1453:
1404:
1350:
1317:
1297:
1273:Euclidean division
1234:Euclidean division
1205:
1124:
1065:
1010:
947:
880:
860:
783:
745:
696:
656:
604:
557:Euclidean division
542:
438:
214:list of references
2371:. ISSN 2079-3197.
2313:. pp. 17–18.
2300:. pp. 68–70.
2146:978-3-319-49741-9
2104:978-3-319-41383-9
2066:978-1-86094-866-4
1767:978-0-19-532848-6
1707:
1706:
1570:{\displaystyle M}
1550:{\displaystyle B}
1320:{\displaystyle M}
1300:{\displaystyle B}
1127:{\displaystyle ,}
1068:{\displaystyle ,}
900:modular operation
883:{\displaystyle M}
748:{\displaystyle X}
287:
286:
279:
267:
266:
259:
197:
196:
182:
102:
101:
57:
2397:
2354:
2352:
2325:
2314:
2301:
2292:
2283:
2254:
2241:
2231:
2221:
2194:
2178:
2176:
2175:
2166:. Archived from
2158:
2116:
2070:
2046:
2044:
2043:
2037:
2026:
2005:
1926:
1891:
1869:
1868:
1858:
1824:
1818:
1817:
1799:
1790:
1784:
1782:
1780:
1779:
1747:
1702:
1699:
1681:
1674:
1665:
1663:
1662:
1657:
1655:
1654:
1638:
1636:
1635:
1630:
1628:
1627:
1611:
1609:
1608:
1603:
1600:
1592:
1576:
1574:
1573:
1568:
1556:
1554:
1553:
1548:
1532:
1530:
1529:
1524:
1522:
1521:
1499:
1497:
1496:
1491:
1486:
1485:
1469:
1461:
1449:
1448:
1436:
1435:
1413:
1411:
1410:
1405:
1394:
1393:
1359:
1357:
1356:
1351:
1343:
1342:
1326:
1324:
1323:
1318:
1307:is coprime with
1306:
1304:
1303:
1298:
1270:
1257:
1230:modulo operation
1227:
1214:
1212:
1211:
1206:
1201:
1200:
1182:
1181:
1169:
1168:
1153:
1152:
1133:
1131:
1130:
1125:
1117:
1116:
1098:
1097:
1078:
1074:
1072:
1071:
1066:
1058:
1057:
1039:
1038:
1019:
1017:
1016:
1013:{\displaystyle }
1011:
1006:
1005:
987:
986:
967:
963:
956:
954:
953:
950:{\displaystyle }
948:
943:
942:
924:
923:
889:
887:
886:
881:
869:
867:
866:
861:
853:
821:
814:
792:
790:
789:
784:
755:in the interval
754:
752:
751:
746:
734:
726:
718:
709:
705:
703:
702:
697:
695:
694:
678:
672:
665:
663:
662:
657:
655:
654:
642:
641:
613:
611:
610:
605:
600:
599:
578:
577:
551:
549:
548:
543:
538:
537:
519:
518:
506:
505:
493:
492:
470:
457:pairwise coprime
447:
445:
444:
439:
431:
430:
412:
411:
399:
398:
386:
385:
363:
348:computation and
324:
320:
311:pairwise coprime
305:by their values
282:
275:
262:
255:
251:
248:
242:
237:this article by
228:inline citations
207:
206:
199:
192:
189:
183:
181:
140:
112:
104:
97:
94:
88:
68:
60:
49:
27:
26:
19:
2405:
2404:
2400:
2399:
2398:
2396:
2395:
2394:
2375:
2374:
2328:
2317:
2304:
2295:
2286:
2257:
2244:
2197:
2181:
2173:
2171:
2162:
2147:
2120:
2105:
2074:
2067:
2050:
2041:
2039:
2035:
2024:
2019:
1941:
1915:
1894:
1881:
1878:
1876:Further reading
1873:
1872:
1841:: 58603–58619.
1826:
1825:
1821:
1797:
1792:
1791:
1787:
1783:(xxv+641 pages)
1777:
1775:
1768:
1749:
1748:
1744:
1739:
1726:Covering system
1722:
1703:
1697:
1694:
1687:needs expansion
1672:
1646:
1641:
1640:
1619:
1614:
1613:
1579:
1578:
1559:
1558:
1539:
1538:
1510:
1505:
1504:
1477:
1440:
1427:
1422:
1421:
1382:
1365:
1364:
1334:
1329:
1328:
1309:
1308:
1289:
1288:
1285:
1262:
1255:
1252:
1219:
1192:
1173:
1160:
1144:
1139:
1138:
1108:
1089:
1081:
1080:
1079:represented by
1076:
1075:is the integer
1049:
1030:
1022:
1021:
997:
978:
970:
969:
965:
961:
934:
915:
907:
906:
896:
872:
871:
795:
794:
757:
756:
737:
736:
732:
724:
716:
711:
707:
686:
681:
680:
676:
670:
646:
633:
622:
621:
591:
569:
564:
563:
529:
510:
497:
484:
476:
475:
468:
422:
403:
390:
377:
369:
368:
361:
358:
329:is also called
322:
318:
283:
272:
271:
270:
263:
252:
246:
243:
232:
218:related reading
208:
204:
193:
187:
184:
141:
139:
125:
113:
98:
92:
89:
82:
69:
28:
24:
17:
12:
11:
5:
2403:
2401:
2393:
2392:
2387:
2377:
2376:
2373:
2372:
2355:
2343:(6): 545–563.
2326:
2315:
2302:
2293:
2284:
2266:(3): 217–233.
2255:
2242:
2195:
2191:Addison Wesley
2179:
2160:
2145:
2127:(1 ed.).
2118:
2103:
2081:(1 ed.).
2072:
2065:
2055:. London, UK:
2048:
2017:
2014:Neurocomputing
2006:
1956:(6): 871–892.
1939:
1928:
1913:
1892:
1877:
1874:
1871:
1870:
1819:
1785:
1766:
1741:
1740:
1738:
1735:
1734:
1733:
1728:
1721:
1718:
1705:
1704:
1684:
1682:
1671:
1668:
1653:
1649:
1626:
1622:
1599:
1596:
1591:
1587:
1566:
1546:
1520:
1517:
1513:
1501:
1500:
1489:
1484:
1480:
1474:
1468:
1465:
1460:
1456:
1452:
1447:
1443:
1439:
1434:
1430:
1415:
1414:
1403:
1398:
1392:
1389:
1385:
1381:
1378:
1375:
1372:
1349:
1346:
1341:
1337:
1316:
1296:
1284:
1281:
1251:
1248:
1216:
1215:
1204:
1199:
1195:
1191:
1188:
1185:
1180:
1176:
1172:
1167:
1163:
1159:
1156:
1151:
1147:
1123:
1120:
1115:
1111:
1107:
1104:
1101:
1096:
1092:
1088:
1064:
1061:
1056:
1052:
1048:
1045:
1042:
1037:
1033:
1029:
1009:
1004:
1000:
996:
993:
990:
985:
981:
977:
958:
957:
946:
941:
937:
933:
930:
927:
922:
918:
914:
895:
892:
879:
859:
856:
852:
848:
845:
842:
839:
836:
833:
830:
827:
824:
820:
817:
813:
809:
806:
803:
782:
779:
776:
773:
770:
767:
764:
744:
714:
693:
689:
667:
666:
653:
649:
645:
640:
636:
632:
629:
615:
614:
603:
598:
594:
590:
587:
584:
581:
576:
572:
553:
552:
541:
536:
532:
528:
525:
522:
517:
513:
509:
504:
500:
496:
491:
487:
483:
449:
448:
437:
434:
429:
425:
421:
418:
415:
410:
406:
402:
397:
393:
389:
384:
380:
376:
357:
354:
338:linear algebra
299:numeral system
285:
284:
265:
264:
222:external links
211:
209:
202:
195:
194:
130:. Please help
116:
114:
107:
100:
99:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
2402:
2391:
2388:
2386:
2383:
2382:
2380:
2370:
2366:
2362:
2361:
2356:
2351:
2346:
2342:
2338:
2337:
2332:
2327:
2323:
2322:
2316:
2312:
2308:
2303:
2299:
2294:
2290:
2285:
2281:
2277:
2273:
2269:
2265:
2261:
2256:
2252:
2248:
2243:
2239:
2235:
2230:
2225:
2220:
2215:
2211:
2207:
2206:
2201:
2196:
2192:
2188:
2184:
2180:
2170:on 2005-02-17
2169:
2165:
2161:
2156:
2152:
2148:
2142:
2138:
2134:
2130:
2126:
2125:
2119:
2114:
2110:
2106:
2100:
2096:
2092:
2088:
2084:
2080:
2079:
2073:
2068:
2062:
2058:
2054:
2049:
2034:
2030:
2023:
2018:
2015:
2011:
2007:
2003:
1999:
1995:
1991:
1987:
1983:
1979:
1975:
1971:
1967:
1963:
1959:
1955:
1951:
1950:
1945:
1940:
1937:
1933:
1929:
1924:
1920:
1916:
1914:0-87942-205-X
1910:
1906:
1902:
1898:
1893:
1889:
1885:
1880:
1879:
1875:
1866:
1862:
1857:
1852:
1848:
1844:
1840:
1836:
1835:
1830:
1823:
1820:
1815:
1811:
1807:
1803:
1796:
1789:
1786:
1773:
1769:
1763:
1759:
1755:
1754:
1746:
1743:
1736:
1732:
1729:
1727:
1724:
1723:
1719:
1717:
1715:
1712:
1701:
1692:
1688:
1685:This section
1683:
1680:
1676:
1675:
1669:
1667:
1651:
1647:
1624:
1620:
1597:
1594:
1589:
1585:
1564:
1544:
1536:
1518:
1515:
1511:
1487:
1482:
1478:
1472:
1466:
1463:
1458:
1454:
1450:
1445:
1441:
1437:
1432:
1428:
1420:
1419:
1418:
1401:
1396:
1390:
1387:
1383:
1379:
1376:
1373:
1370:
1363:
1362:
1361:
1347:
1344:
1339:
1335:
1314:
1294:
1282:
1280:
1278:
1274:
1269:
1265:
1259:
1249:
1247:
1244:
1242:
1237:
1235:
1231:
1226:
1222:
1202:
1197:
1193:
1189:
1186:
1178:
1174:
1170:
1165:
1161:
1154:
1149:
1145:
1137:
1136:
1135:
1121:
1113:
1109:
1105:
1102:
1099:
1094:
1090:
1062:
1054:
1050:
1046:
1043:
1040:
1035:
1031:
1002:
998:
994:
991:
988:
983:
979:
939:
935:
931:
928:
925:
920:
916:
905:
904:
903:
901:
893:
891:
877:
854:
850:
843:
840:
837:
828:
825:
822:
815:
811:
807:
801:
780:
777:
774:
771:
768:
765:
762:
742:
730:
729:residue class
722:
717:
691:
687:
673:
651:
647:
643:
638:
634:
630:
627:
620:
619:
618:
601:
596:
592:
588:
585:
582:
579:
574:
570:
562:
561:
560:
558:
534:
530:
526:
523:
520:
515:
511:
507:
502:
498:
494:
489:
485:
474:
473:
472:
465:
462:
458:
454:
435:
427:
423:
419:
416:
413:
408:
404:
400:
395:
391:
387:
382:
378:
367:
366:
365:
355:
353:
351:
347:
346:Gröbner basis
343:
339:
334:
332:
328:
316:
312:
308:
304:
301:representing
300:
296:
292:
281:
278:
269:
261:
258:
250:
240:
236:
230:
229:
223:
219:
215:
210:
201:
200:
191:
180:
177:
173:
170:
166:
163:
159:
156:
152:
149: –
148:
144:
143:Find sources:
137:
133:
129:
123:
122:
121:single source
117:This article
115:
111:
106:
105:
96:
86:
80:
76:
73:This article
71:
67:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
2364:
2358:
2340:
2334:
2319:
2306:
2297:
2288:
2263:
2259:
2250:
2246:
2209:
2203:
2186:
2172:. Retrieved
2168:the original
2123:
2077:
2052:
2040:. Retrieved
2028:
1953:
1947:
1896:
1883:
1838:
1832:
1822:
1808:(4): 23–35.
1805:
1801:
1788:
1776:. Retrieved
1752:
1745:
1708:
1695:
1691:adding to it
1686:
1670:Applications
1502:
1416:
1286:
1267:
1263:
1260:
1253:
1245:
1238:
1224:
1220:
1217:
959:
897:
712:
674:
668:
616:
554:
466:
452:
450:
359:
350:cryptography
335:
330:
294:
290:
288:
273:
268:
253:
244:
233:Please help
225:
185:
175:
168:
161:
154:
142:
118:
90:
74:
50:
43:
37:
36:Please help
33:
2360:Computation
2159:(389 pages)
2117:(351 pages)
2071:(296 pages)
2047:(1+7 pages)
1888:McGraw-Hill
1834:IEEE Access
467:An integer
451:called the
239:introducing
2379:Categories
2253:(1): 1–10.
2174:2023-08-24
2155:2017934074
2113:2016947081
2083:Birkhäuser
2042:2021-01-23
1905:IEEE Press
1778:2021-01-23
1737:References
1250:Comparison
1223:= 1, ...,
1134:such that
669:for every
356:Definition
158:newspapers
39:improve it
2219:0807.1347
1986:123623780
1970:0005-1179
1865:2169-3536
1698:July 2018
1595:−
1516:−
1464:−
1451:⋅
1388:−
1380:⋅
1327:(that is
1190:
1103:…
1044:…
992:…
929:…
858:⌋
841:−
832:⌊
829:≤
823:≤
819:⌋
805:⌊
802:−
778:−
769:…
631:≤
589:
524:…
417:…
364:integers
247:July 2018
188:July 2018
128:talk page
93:July 2018
85:talk page
79:talk page
45:talk page
2367:(2): 9.
2280:14360845
2238:11329343
2033:Archived
1978:56038628
1923:86-10516
1772:Archived
1720:See also
1345:≠
1283:Division
1241:overflow
309:several
303:integers
1843:Bibcode
1711:digital
1639:modulo
1557:modulo
1360:) then
731:modulo
297:) is a
235:improve
172:scholar
2278:
2236:
2153:
2143:
2111:
2101:
2063:
2002:at1588
2000:
1994:AURCAT
1992:
1984:
1976:
1968:
1921:
1911:
1863:
1764:
1577:, and
1503:where
870:(when
555:under
453:moduli
307:modulo
174:
167:
160:
153:
145:
2276:S2CID
2234:S2CID
2214:arXiv
2036:(PDF)
2025:(PDF)
1990:CODEN
1982:S2CID
1798:(PDF)
1266:<
220:, or
179:JSTOR
165:books
2151:LCCN
2141:ISBN
2109:LCCN
2099:ISBN
2061:ISBN
1974:LCCN
1966:ISSN
1919:LCCN
1909:ISBN
1861:ISSN
1762:ISBN
1275:and
1218:for
1020:and
964:and
675:Let
644:<
617:and
151:news
2345:doi
2268:doi
2224:doi
2133:doi
2091:doi
1958:doi
1851:doi
1810:doi
1693:.
1537:of
1533:is
1473:mod
1397:mod
1187:mod
586:mod
295:RNS
134:by
2381::
2363:.
2341:17
2339:.
2333:.
2309:.
2274:.
2262:.
2249:.
2232:.
2222:.
2210:79
2208:.
2202:.
2189:.
2185:.
2149:.
2139:.
2131:.
2107:.
2097:.
2089:.
2085:/
2059:.
2027:.
2012:.
1998:Mi
1996:.
1988:.
1980:.
1972:.
1964:.
1954:65
1952:.
1946:.
1934:.
1917:.
1907:.
1903:,
1859:.
1849:.
1837:.
1831:.
1806:27
1804:.
1800:.
1770:.
1760:.
1666:.
1279:.
352:.
344:,
333:.
289:A
224:,
216:,
81:).
48:.
2365:9
2353:.
2347::
2324:.
2282:.
2270::
2264:6
2251:5
2240:.
2226::
2216::
2193:.
2177:.
2157:.
2135::
2115:.
2093::
2069:.
2045:.
2004:.
1960::
1890:.
1867:.
1853::
1845::
1839:8
1816:.
1812::
1781:.
1700:)
1696:(
1652:i
1648:m
1625:i
1621:b
1598:1
1590:i
1586:b
1565:M
1545:B
1519:1
1512:B
1488:,
1483:i
1479:m
1467:1
1459:i
1455:b
1446:i
1442:a
1438:=
1433:i
1429:c
1402:M
1391:1
1384:B
1377:A
1374:=
1371:C
1348:0
1340:i
1336:b
1315:M
1295:B
1268:y
1264:x
1256:M
1225:k
1221:i
1203:,
1198:i
1194:m
1184:)
1179:i
1175:y
1171:+
1166:i
1162:x
1158:(
1155:=
1150:i
1146:z
1122:,
1119:]
1114:k
1110:z
1106:,
1100:,
1095:1
1091:z
1087:[
1077:z
1063:,
1060:]
1055:k
1051:y
1047:,
1041:,
1036:1
1032:y
1028:[
1008:]
1003:k
999:x
995:,
989:,
984:1
980:x
976:[
966:y
962:x
945:]
940:k
936:m
932:,
926:,
921:1
917:m
913:[
878:M
855:2
851:/
847:)
844:1
838:M
835:(
826:X
816:2
812:/
808:M
781:1
775:M
772:,
766:,
763:0
743:X
733:M
725:M
715:i
713:m
708:M
692:i
688:m
677:M
671:i
652:i
648:m
639:i
635:x
628:0
602:,
597:i
593:m
583:x
580:=
575:i
571:x
540:}
535:k
531:x
527:,
521:,
516:3
512:x
508:,
503:2
499:x
495:,
490:1
486:x
482:{
469:x
436:,
433:}
428:k
424:m
420:,
414:,
409:3
405:m
401:,
396:2
392:m
388:,
383:1
379:m
375:{
362:k
323:M
319:M
293:(
280:)
274:(
260:)
254:(
249:)
245:(
231:.
190:)
186:(
176:·
169:·
162:·
155:·
138:.
124:.
95:)
91:(
87:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
