4412:
become more difficult. Both of these features can be used to advantage. In particular, in the RSA algorithm, encrypting and decrypting a message is done using a pair of numbers that are multiplicative inverses with respect to a carefully selected modulus. One of these numbers is made public and can be used in a rapid encryption procedure, while the other, used in the decryption procedure, is kept hidden. Determining the hidden number from the public number is considered to be computationally infeasible and this is what makes the system work to ensure privacy.
3251:
congruence classes represented by these numbers is again one of these four congruence classes. This implies that these four congruence classes form a group, in this case the cyclic group of order four, having either 3 or 7 as a (multiplicative) generator. The represented congruence classes form the group of units of the ring
1269:
objects in the following way: To either add or multiply two congruence classes, first pick a representative (in any way) from each class, then perform the usual operation for integers on the two representatives and finally take the congruence class that the result of the integer operation lies in as
3250:
A complete residue system modulo 10 can be the set {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} where each integer is in a different congruence class modulo 10. The unique least residue system modulo 10 is {0, 1, 2, ..., 9}. A reduced residue system modulo 10 could be {1, 3, 7, 9}. The product of any two
4411:
Finding a modular multiplicative inverse has many applications in algorithms that rely on the theory of modular arithmetic. For instance, in cryptography the use of modular arithmetic permits some operations to be carried out more quickly and with fewer storage requirements, while other operations
2861:
will have solutions, that is, modular multiplicative inverses of 3 modulo 10 will exist. In fact, 7 satisfies this congruence (i.e., 21 − 1 = 20). However, other integers also satisfy the congruence, for instance 17 and −3 (i.e., 3(17) − 1 = 50 and 3(−3) − 1 = −10). In particular, every integer in
3013:
is divisible by 10. This congruence has only this one congruence class of solutions. The solution in this case could have been obtained by checking all possible cases, but systematic algorithms would be needed for larger moduli and these will be given in the next section.
3527:
has been calculated. A more efficient version of the algorithm is the extended
Euclidean algorithm, which, by using auxiliary equations, reduces two passes through the algorithm (back substitution can be thought of as passing through the algorithm in reverse) to just one.
3336:, this gcd must be 1. The last of several equations produced by the algorithm may be solved for this gcd. Then, using a method called "back substitution", an expression connecting the original parameters and this gcd can be obtained. In other words, integers
4463:
On many machines, particularly those without hardware support for division, division is a slower operation than multiplication, so this approach can yield a considerable speedup. The first step is relatively slow but only needs to be done once.
1641:. In working with arithmetic problems it is sometimes more convenient to work with a complete system of residues and use the language of congruences while at other times the point of view of the congruence classes of the ring
675:
1467:
3210:
308:
1393:
2773:
2523:
2687:
2605:
3947:
This method is generally slower than the extended
Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:
3823:
4242:
991:
3008:
3212:. Addition is defined in a similar way. The ten congruence classes together with these operations of addition and multiplication of congruence classes form the ring of integers modulo 10, i.e.,
3942:
3657:
1062:
2343:
3729:
2295:
2247:
3284:
3245:
1975:
1940:
1674:
1527:
1178:
2199:
2435:
3518:
2391:
883:
733:
412:
107:
520:
3408:
769:
is also a solution, so, when speaking of the number of solutions of a linear congruence we are referring to the number of different congruence classes that contain solutions.
1586:
3150:
3123:
3096:
3069:
3042:
2887:
2811:
1244:
767:
590:
242:
215:
180:
1557:
3871:
1905:
549:
3464:
1322:
338:
2067:
4016:
3979:
1849:
1734:
4415:
As another example in a different context, consider the exact division problem in computer science where you have a list of odd word-sized numbers each divisible by
2028:
3680:
2120:
1754:
1295:
2093:
1209:
1697:
has a modular multiplicative inverse, for instance, zero never does. After removing the elements of a complete residue system that are not relatively prime to
912:(i.e. coprime). Furthermore, when this condition holds, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique: If
4100:, with a single invocation of the Euclidean algorithm and three multiplications per additional input. The basic idea is to form the product of all the
363:
As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form
602:
1404:
3155:
250:
2348:
The following example uses the modulus 10: Two integers are congruent mod 10 if and only if their difference is divisible by 10, for instance
1330:
2694:
2447:
2611:
2529:
1688:
1599:, reflecting the fact that all the elements of a congruence class have the same remainder (i.e., "residue") upon being divided by
1246:, as the multiplicative inverse of a congruence class is a congruence class with the multiplication defined in the next section.
4975:
4935:
4864:
4826:
4629:
3751:
4859:. Cambridge Monographs on Computational and Applied Mathematics. Vol. 18. Cambridge University Press. pp. 67–68.
4467:
Modular multiplicative inverses are used to obtain a solution of a system of linear congruences that is guaranteed by the
4157:
2906:
4450:
is the number of bits in a word. This inverse will exist since the numbers are odd and the modulus has no odd factors.
3879:
3601:
934:
4956:
4917:
4779:
4682:
1476:, meaning that the end result does not depend on the choices of representatives that were made to obtain the result.
2300:
1707:, all of whose elements have modular multiplicative inverses. The number of elements in a reduced residue system is
4623:
1608:
3693:
2252:
2204:
429:. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the
4843:
3254:
3215:
1617:
1002:
3564:
As an alternative to the extended
Euclidean algorithm, Euler's theorem may be used to compute modular inverses.
1945:
1910:
1644:
1497:
1128:
2125:
2398:
1633:
3475:
2354:
840:
690:
369:
64:
3300:
480:
430:
140:
5029:
3683:
1757:
3354:
5034:
3556:, and is considered to be very fast and generally more efficient than its alternative, exponentiation.
738:
Unlike linear equations over the reals, linear congruences may have zero, one or several solutions. If
47:
1562:
4468:
4041:, which is what was to be calculated in the first place. Without the Montgomery method, the standard
3128:
3101:
3074:
3047:
3020:
2865:
2789:
1222:
745:
568:
220:
193:
158:
1532:
4399:
It is possible to perform the multiplications in a tree structure rather than linearly to exploit
3835:
1869:
532:
4070:
3419:
777:
422:
3345:
1300:
316:
4026:
3989:. Factorization is widely believed to be a computationally hard problem. However, calculating
2033:
1776:
1703:
1188:
345:
4847:
4818:
3992:
3955:
3286:. These congruence classes are precisely the ones which have modular multiplicative inverses.
1825:
1710:
4769:
4604:
4042:
5013:
2007:
1607:
integers selected so that each comes from a different congruence class modulo m is called a
4034:
3665:
2098:
1819:
1739:
1273:
526:
8:
4074:
4061:
of this technique is that there are no conditional branches which depend on the value of
4025:
The relative cost of exponentiation. Though it can be implemented more efficiently using
3317:
2072:
1786:
417:
Finding modular multiplicative inverses also has practical applications in the field of
4854:
4400:
3568:
1780:
1484:
1194:
442:
426:
55:
4610:
Also, the modular multiplicative inverse figures prominently in the definition of the
1265:
congruence classes. Operations of addition and multiplication can be defined on these
1211:(which, contrary to the modular multiplicative inverse, is not an integer except when
4992:
4971:
4952:
4931:
4913:
4860:
4822:
4775:
4678:
3125:, say −2, and observing that their product (25)(−2) = −50 is in the congruence class
1184:
356:
is clearly represented, replacing the numbers by congruence classes and altering the
4995:
4944:
4839:
1772:
909:
357:
139:, then there are an infinite number of solutions of this congruence, which form a
4611:
471:
349:
4710:
3731:
3532:
1559:, but several elementary texts and application areas use a simplified notation
670:{\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}
155:'s congruence class as a modular multiplicative inverse. Using the notation of
5023:
3986:
4626:– a pseudo-random number generator that uses modular multiplicative inverses
2786:
has no solutions since the integers that are congruent to 5 (i.e., those in
143:
with respect to this modulus. Furthermore, any integer that is congruent to
4765:
1986:
1978:
1859:
1803:
is the name of the ring. The group of units of the ring of integers modulo
1494:. There are several notations used for these algebraic objects, most often
1473:
433:) that can be used for the calculation of modular multiplicative inverses.
418:
1462:{\displaystyle {\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.}
1324:
representing the operations on congruence classes, these definitions are
3205:{\displaystyle {\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}}
1815:
353:
303:{\displaystyle {\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},}
20:
1270:
the result of the operation on the congruence classes. In symbols, with
4152:
4078:
24:
5009:
5016:
of solving the modulo multiplicative inverse using Euclid's
Algorithm
5000:
4143:
More specifically, the algorithm is (all arithmetic performed modulo
3745:. Therefore, a modular multiplicative inverse can be found directly:
2441:
Some of the ten congruence classes with respect to this modulus are:
1388:{\displaystyle {\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}}
1785:. As the product of two units is a unit, the units of a ring form a
2768:{\displaystyle {\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.}
2518:{\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}}
3320:
determines the greatest common divisor (gcd) of two integers, say
2682:{\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}}
2600:{\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}}
4502:
3738:
3576:
32:
3981:
must be known and the most efficient known computation requires
4566:= 6 is the modular multiplicative inverse of 5 × 11 (mod 7) and
2889:
will satisfy the congruence since these integers have the form
888:
The previous result says that a solution exists if and only if
344:. Written in this way, the analogy with the usual concept of a
4588:= 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504
4037:
method, that method, itself, requiring a modular inverse mod
1097:
won't even have a modular multiplicative inverse. Therefore,
4774:, Cambridge University Press, Theorem 2.4, p. 15,
4577:= 6 is the modular multiplicative inverse of 5 × 7 (mod 11).
4555:= 3 is the modular multiplicative inverse of 7 × 11 (mod 5),
1981:. In this case, the multiplicative group of integers modulo
1679:
1483:
congruence classes with these two defined operations form a
1219:
is interpreted as a token standing for the congruence class
4708:
742:
is a solution of a linear congruence then every element in
4709:
Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. (2016).
4089:
It is possible to compute the inverse of multiple numbers
4949:
Chapter Zero: Fundamental
Notions of Abstract Mathematics
4771:
1588:
when confusion with other algebraic objects is unlikely.
340:
denotes the multiplication of equivalence classes modulo
112:
which is the shorthand way of writing the statement that
4990:
4033:
are involved this is most efficiently computed with the
3313:
can be found by using the extended
Euclidean algorithm.
3818:{\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}
4711:"PKCS #1: RSA Cryptography Specifications Version 2.2"
4160:
1693:
Not every element of a complete residue system modulo
4237:{\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}
3995:
3958:
3882:
3838:
3754:
3696:
3668:
3604:
3478:
3422:
3357:
3257:
3218:
3158:
3131:
3104:
3077:
3050:
3023:
2909:
2868:
2792:
2697:
2614:
2532:
2450:
2401:
2357:
2303:
2255:
2207:
2128:
2101:
2075:
2036:
2010:
1948:
1913:
1872:
1828:
1742:
1713:
1647:
1565:
1535:
1500:
1407:
1333:
1303:
1276:
1225:
1197:
1131:
1005:
937:
843:
748:
693:
605:
571:
535:
483:
372:
319:
253:
223:
196:
161:
67:
3003:{\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}
123:, or, put another way, the remainder after dividing
4501:has common solutions since 5,7 and 11 are pairwise
4077:. For this reason, the standard implementation of
4018:is straightforward when the prime factorization of
1818:to a reduced residue system. In particular, it has
592:denote the congruence class containing the integer
4459:and take the least significant word of the result.
4236:
4010:
3973:
3936:
3865:
3817:
3723:
3674:
3651:
3512:
3458:
3402:
3278:
3239:
3204:
3144:
3117:
3090:
3063:
3036:
3002:
2881:
2805:
2767:
2681:
2599:
2517:
2429:
2385:
2337:
2289:
2241:
2193:
2114:
2087:
2061:
2022:
1969:
1934:
1899:
1843:
1760:, i.e., the number of positive integers less than
1748:
1728:
1668:
1580:
1551:
1521:
1461:
1387:
1316:
1289:
1238:
1203:
1172:
1056:
985:
877:
761:
727:
669:
584:
543:
514:
406:
332:
302:
236:
209:
174:
101:
1122:has a solution it is often denoted in this way −
5021:
4965:
4910:A Classical Introduction to Modern Number Theory
4891:
4879:
4696:
4431:Use the extended Euclidean algorithm to compute
3937:{\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}
3652:{\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}
3376:
986:{\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}
4968:Introduction to Cryptography with Coding Theory
4838:
4735:Other notations are often used, including and
3294:
2820:is always even. However, the linear congruence
826:A modular multiplicative inverse of an integer
4966:Trappe, Wade; Washington, Lawrence C. (2006),
2338:{\displaystyle 5\times 13\equiv 1{\pmod {16}}}
1591:The congruence classes of the integers modulo
4928:Elementary Number Theory and its Applications
1215:is 1 or -1). The notation would be proper if
4907:
4805:
4752:
4453:For each number in the list, multiply it by
3724:{\displaystyle (\mathbb {Z} /m\mathbb {Z} )}
2846:and 2 does not divide 5, but does divide 6.
2759:
2711:
2676:
2628:
2594:
2546:
2512:
2464:
2290:{\displaystyle 4\times 7\equiv 1{\pmod {9}}}
2242:{\displaystyle 3\times 3\equiv 1{\pmod {4}}}
920:are both modular multiplicative inverses of
661:
619:
182:to indicate the congruence class containing
4081:uses this technique to compute an inverse.
3279:{\displaystyle \mathbb {Z} /10\mathbb {Z} }
3240:{\displaystyle \mathbb {Z} /10\mathbb {Z} }
3071:can be obtained by selecting an element of
1057:{\displaystyle a(b-b')\equiv 0{\pmod {m}}.}
186:, this can be expressed by saying that the
4943:
4819:Elementary number theory with applications
4660:
1970:{\displaystyle \mathbb {Z} /p\mathbb {Z} }
1935:{\displaystyle \mathbb {Z} /p\mathbb {Z} }
1669:{\displaystyle \mathbb {Z} /m\mathbb {Z} }
1628:form a complete system of residues modulo
1522:{\displaystyle \mathbb {Z} /m\mathbb {Z} }
1173:{\displaystyle x\equiv a^{-1}{\pmod {m}},}
4908:Ireland, Kenneth; Rosen, Michael (1990),
3714:
3701:
3272:
3259:
3233:
3220:
2069:is the modular multiplicative inverse of
1963:
1950:
1928:
1915:
1689:Multiplicative group of integers modulo n
1662:
1649:
1568:
1537:
1515:
1502:
629:
551:, and the equivalence classes are called
537:
4715:Internet Engineering Task Force RFC 8017
4437:, the modular multiplicative inverse of
4049:at every step, is a slow operation when
3559:
3523:so, a modular multiplicative inverse of
2194:{\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}
1809:multiplicative group of integers modulo
1680:Multiplicative group of integers modulo
1187:since it could be misinterpreted as the
151:'s congruence class) has any element of
4672:
4642:
2430:{\displaystyle 111\equiv 1{\pmod {10}}}
834:is a solution of the linear congruence
5022:
4069:, which may be an important secret in
3513:{\displaystyle ax\equiv 1{\pmod {m}},}
2386:{\displaystyle 32\equiv 2{\pmod {10}}}
1261:, partitions the set of integers into
878:{\displaystyle ax\equiv 1{\pmod {m}}.}
728:{\displaystyle ax\equiv b{\pmod {m}}.}
407:{\displaystyle ax\equiv b{\pmod {m}}.}
102:{\displaystyle ax\equiv 1{\pmod {m}},}
4991:
4925:
4793:
4764:
4648:
4630:Rational reconstruction (mathematics)
515:{\displaystyle a\equiv b{\pmod {m}}.}
436:
4084:
3690:belongs to the multiplicative group
3332:has a multiplicative inverse modulo
3305:A modular multiplicative inverse of
1249:
684:is a modular congruence of the form
4848:"§2.5.1 Several inversions at once"
4421:and you wish to divide them all by
3923:
3873:and a modular inverse is given by
3804:
3638:
3499:
2419:
2375:
2327:
2279:
2231:
1942:have multiplicative inverses, thus
1610:complete system of residues modulo
1159:
1043:
972:
864:
714:
653:
501:
393:
88:
13:
4675:Cryptography / Theory and Practice
3686:. This follows from the fact that
3403:{\displaystyle ax+my=\gcd(a,m)=1.}
3017:The product of congruence classes
14:
5046:
4984:
4912:(2nd ed.), Springer-Verlag,
4717:. Internet Engineering Task Force
4654:
2393:since 10 divides 32 − 2 = 30, and
1907:and all the non-zero elements of
50:to 1 with respect to the modulus
4930:(3rd ed.), Addison-Wesley,
4624:Inversive congruential generator
4107:, invert that, then multiply by
1620:shows that the set of integers,
1581:{\displaystyle \mathbb {Z} _{m}}
1257:The congruence relation, modulo
4970:(2nd ed.), Prentice-Hall,
4885:
4873:
4832:
4811:
4799:
4677:, CRC Press, pp. 124–128,
4592:and in its unique reduced form
4406:
3916:
3797:
3631:
3492:
3145:{\displaystyle {\overline {0}}}
3118:{\displaystyle {\overline {8}}}
3091:{\displaystyle {\overline {5}}}
3064:{\displaystyle {\overline {8}}}
3037:{\displaystyle {\overline {5}}}
2882:{\displaystyle {\overline {7}}}
2806:{\displaystyle {\overline {5}}}
2437:since 10 divides 111 − 1 = 110.
2412:
2368:
2320:
2272:
2224:
1239:{\displaystyle {\overline {a}}}
1152:
1036:
965:
857:
762:{\displaystyle {\overline {x}}}
707:
646:
585:{\displaystyle {\overline {a}}}
494:
470:divides their difference. This
386:
237:{\displaystyle {\overline {x}}}
210:{\displaystyle {\overline {a}}}
175:{\displaystyle {\overline {w}}}
81:
4787:
4758:
4746:
4729:
4702:
4690:
4666:
4427:. One solution is as follows:
4273:using any available algorithm.
4045:, which requires division mod
4005:
3999:
3968:
3962:
3927:
3917:
3848:
3842:
3808:
3798:
3769:
3763:
3718:
3697:
3642:
3632:
3619:
3613:
3535:, this algorithm runs in time
3503:
3493:
3447:
3438:
3391:
3379:
3289:
2994:
2979:
2928:
2913:
2423:
2413:
2379:
2369:
2331:
2321:
2283:
2273:
2235:
2225:
2169:
2144:
2141:
2129:
1882:
1876:
1838:
1832:
1723:
1717:
1552:{\displaystyle \mathbb {Z} /m}
1183:but this can be considered an
1163:
1153:
1047:
1037:
1026:
1009:
976:
966:
868:
858:
718:
708:
657:
647:
505:
495:
397:
387:
116:divides (evenly) the quantity
92:
82:
58:this congruence is written as
54:. In the standard notation of
29:modular multiplicative inverse
23:, particularly in the area of
1:
4901:
1779:and those that do are called
1764:that are relatively prime to
803:has solutions if and only if
447:For a given positive integer
188:modulo multiplicative inverse
16:Concept in modular arithmetic
4892:Trappe & Washington 2006
4880:Trappe & Washington 2006
4697:Trappe & Washington 2006
4673:Stinson, Douglas R. (1995),
3866:{\displaystyle \phi (m)=m-1}
3301:Extended Euclidean algorithm
3295:Extended Euclidean algorithm
3197:
3184:
3164:
3137:
3110:
3098:, say 25, and an element of
3083:
3056:
3029:
2874:
2798:
2703:
2620:
2538:
2456:
2095:with respect to the modulus
2030:, it's always the case that
1900:{\displaystyle \phi (p)=p-1}
1635:least residue system modulo
1595:were traditionally known as
1451:
1433:
1413:
1380:
1359:
1339:
1231:
830:with respect to the modulus
754:
611:
577:
544:{\displaystyle \mathbb {Z} }
431:extended Euclidean algorithm
292:
279:
259:
229:
202:
167:
135:does have an inverse modulo
7:
4617:
3459:{\displaystyle ax-1=(-y)m,}
2828:has two solutions, namely,
1701:, what is left is called a
788:then the linear congruence
10:
5053:
4926:Rosen, Kenneth H. (1993),
4856:Modern Computer Arithmetic
4124:to leave only the desired
3828:In the special case where
3298:
1999:
1791:group of units of the ring
1686:
1317:{\displaystyle \cdot _{m}}
553:congruence classes modulo
440:
333:{\displaystyle \cdot _{m}}
5010:Guevara Vasquez, Fernando
4505:. A solution is given by
4469:Chinese Remainder Theorem
2062:{\displaystyle n^{2}-n+1}
819:, then there are exactly
4806:Ireland & Rosen 1990
4753:Ireland & Rosen 1990
4635:
4474:For example, the system
4073:, can be protected from
4065:, and thus the value of
4011:{\displaystyle \phi (m)}
3974:{\displaystyle \phi (m)}
3684:Euler's totient function
3344:can be found to satisfy
2853:, the linear congruence
1844:{\displaystyle \phi (m)}
1775:not every element has a
1729:{\displaystyle \phi (m)}
1597:residue classes modulo m
1489:ring of integers modulo
529:on the set of integers,
217:is the congruence class
190:of the congruence class
4071:public-key cryptography
4029:, when large values of
924:respect to the modulus
778:greatest common divisor
560:residue classes modulo
423:public-key cryptography
4238:
4194:
4027:modular exponentiation
4012:
3975:
3938:
3867:
3819:
3725:
3676:
3653:
3514:
3460:
3404:
3280:
3241:
3206:
3146:
3119:
3092:
3065:
3038:
3004:
2883:
2807:
2778:The linear congruence
2769:
2683:
2601:
2519:
2431:
2387:
2339:
2291:
2243:
2195:
2116:
2089:
2063:
2024:
2023:{\displaystyle n>1}
1971:
1936:
1901:
1845:
1777:multiplicative inverse
1758:Euler totient function
1750:
1730:
1704:reduced residue system
1670:
1582:
1553:
1523:
1463:
1389:
1318:
1291:
1240:
1205:
1174:
1058:
987:
879:
763:
729:
671:
586:
545:
516:
408:
346:multiplicative inverse
334:
304:
238:
211:
176:
103:
42:such that the product
4599:≡ 3504 ≡ 39 (mod 385)
4239:
4174:
4043:binary exponentiation
4013:
3976:
3939:
3868:
3820:
3726:
3677:
3675:{\displaystyle \phi }
3654:
3560:Using Euler's theorem
3515:
3461:
3405:
3281:
3242:
3207:
3147:
3120:
3093:
3066:
3039:
3005:
2884:
2808:
2770:
2684:
2602:
2520:
2432:
2388:
2340:
2292:
2244:
2196:
2117:
2115:{\displaystyle n^{2}}
2090:
2064:
2025:
1972:
1937:
1902:
1846:
1793:and often denoted by
1751:
1749:{\displaystyle \phi }
1731:
1671:
1583:
1554:
1524:
1472:These operations are
1464:
1390:
1319:
1292:
1290:{\displaystyle +_{m}}
1241:
1206:
1175:
1059:
988:
880:
764:
730:
672:
587:
546:
517:
409:
335:
305:
239:
212:
177:
104:
4158:
4075:side-channel attacks
4035:Montgomery reduction
3993:
3956:
3880:
3836:
3752:
3694:
3666:
3602:
3476:
3420:
3355:
3255:
3216:
3156:
3129:
3102:
3075:
3048:
3021:
2907:
2866:
2813:) are all odd while
2790:
2695:
2612:
2530:
2448:
2399:
2355:
2301:
2253:
2205:
2126:
2099:
2073:
2034:
2008:
1946:
1911:
1870:
1826:
1740:
1711:
1645:
1563:
1533:
1498:
1405:
1331:
1301:
1274:
1223:
1195:
1129:
1003:
935:
841:
746:
691:
603:
569:
533:
527:equivalence relation
481:
370:
317:
251:
221:
194:
159:
65:
4699:, pp. 164−169.
4284:down to 2, compute
3413:Rewritten, this is
3318:Euclidean algorithm
2088:{\displaystyle n+1}
5030:Modular arithmetic
4993:Weisstein, Eric W.
4951:. Addison-Wesley.
4401:parallel computing
4234:
4096:, modulo a common
4008:
3971:
3934:
3863:
3815:
3721:
3672:
3649:
3510:
3456:
3400:
3276:
3237:
3202:
3142:
3115:
3088:
3061:
3034:
3000:
2879:
2803:
2765:
2679:
2597:
2515:
2427:
2383:
2335:
2287:
2239:
2191:
2112:
2085:
2059:
2020:
1967:
1932:
1897:
1841:
1746:
1726:
1666:
1618:division algorithm
1578:
1549:
1519:
1459:
1385:
1314:
1287:
1236:
1201:
1170:
1054:
983:
875:
759:
725:
667:
582:
541:
512:
443:Modular arithmetic
437:Modular arithmetic
404:
330:
300:
234:
207:
172:
99:
56:modular arithmetic
5035:Binary operations
4996:"Modular Inverse"
4977:978-0-13-186239-5
4945:Schumacher, Carol
4937:978-0-201-57889-8
4866:978-0-521-19469-3
4846:(December 2010).
4840:Brent, Richard P.
4827:978-0-12-372487-8
4603:since 385 is the
4085:Multiple inverses
3346:Bézout's identity
3200:
3187:
3167:
3140:
3113:
3086:
3059:
3032:
2896:for some integer
2877:
2801:
2706:
2623:
2541:
2459:
1854:In the case that
1454:
1436:
1416:
1383:
1362:
1342:
1234:
1204:{\displaystyle a}
1185:abuse of notation
757:
682:linear congruence
614:
580:
461:congruent modulo
459:, are said to be
360:appropriately.
313:where the symbol
295:
282:
262:
232:
205:
170:
5042:
5006:
5005:
4980:
4962:
4940:
4922:
4895:
4889:
4883:
4877:
4871:
4870:
4852:
4844:Zimmermann, Paul
4836:
4830:
4815:
4809:
4803:
4797:
4791:
4785:
4784:
4762:
4756:
4750:
4744:
4742:
4733:
4727:
4726:
4724:
4722:
4706:
4700:
4694:
4688:
4687:
4670:
4664:
4658:
4652:
4646:
4598:
4587:
4576:
4565:
4554:
4538:
4529:
4520:
4511:
4494:
4488:
4482:
4458:
4449:
4443:
4436:
4426:
4420:
4394:
4393:
4392:
4381:
4380:
4363:
4356:
4355:
4342:
4341:
4324:
4314:
4313:
4300:
4299:
4283:
4279:
4272:
4271:
4270:
4253:
4243:
4241:
4240:
4235:
4233:
4232:
4217:
4216:
4204:
4203:
4193:
4188:
4170:
4169:
4146:
4139:
4138:
4137:
4123:
4113:
4106:
4099:
4095:
4068:
4064:
4052:
4048:
4040:
4032:
4021:
4017:
4015:
4014:
4009:
3984:
3980:
3978:
3977:
3972:
3943:
3941:
3940:
3935:
3930:
3914:
3913:
3895:
3894:
3872:
3870:
3869:
3864:
3831:
3824:
3822:
3821:
3816:
3811:
3795:
3794:
3779:
3778:
3744:
3736:
3730:
3728:
3727:
3722:
3717:
3709:
3704:
3689:
3681:
3679:
3678:
3673:
3658:
3656:
3655:
3650:
3645:
3623:
3622:
3594:
3582:
3574:
3555:
3550:
3542:
3526:
3519:
3517:
3516:
3511:
3506:
3465:
3463:
3462:
3457:
3409:
3407:
3406:
3401:
3343:
3339:
3335:
3331:
3327:
3323:
3312:
3308:
3285:
3283:
3282:
3277:
3275:
3267:
3262:
3246:
3244:
3243:
3238:
3236:
3228:
3223:
3211:
3209:
3208:
3203:
3201:
3193:
3188:
3180:
3178:
3177:
3168:
3160:
3151:
3149:
3148:
3143:
3141:
3133:
3124:
3122:
3121:
3116:
3114:
3106:
3097:
3095:
3094:
3089:
3087:
3079:
3070:
3068:
3067:
3062:
3060:
3052:
3043:
3041:
3040:
3035:
3033:
3025:
3009:
3007:
3006:
3001:
2899:
2895:
2888:
2886:
2885:
2880:
2878:
2870:
2860:
2852:
2845:
2841:
2834:
2827:
2819:
2812:
2810:
2809:
2804:
2802:
2794:
2785:
2774:
2772:
2771:
2766:
2707:
2699:
2688:
2686:
2685:
2680:
2624:
2616:
2606:
2604:
2603:
2598:
2542:
2534:
2524:
2522:
2521:
2516:
2460:
2452:
2436:
2434:
2433:
2428:
2426:
2392:
2390:
2389:
2384:
2382:
2344:
2342:
2341:
2336:
2334:
2296:
2294:
2293:
2288:
2286:
2248:
2246:
2245:
2240:
2238:
2200:
2198:
2197:
2192:
2184:
2183:
2156:
2155:
2121:
2119:
2118:
2113:
2111:
2110:
2094:
2092:
2091:
2086:
2068:
2066:
2065:
2060:
2046:
2045:
2029:
2027:
2026:
2021:
2004:For any integer
1995:
1984:
1976:
1974:
1973:
1968:
1966:
1958:
1953:
1941:
1939:
1938:
1933:
1931:
1923:
1918:
1906:
1904:
1903:
1898:
1865:
1857:
1850:
1848:
1847:
1842:
1812:
1806:
1802:
1798:
1767:
1763:
1755:
1753:
1752:
1747:
1735:
1733:
1732:
1727:
1700:
1696:
1683:
1676:is more useful.
1675:
1673:
1672:
1667:
1665:
1657:
1652:
1638:
1631:
1627:
1613:
1606:
1602:
1594:
1587:
1585:
1584:
1579:
1577:
1576:
1571:
1558:
1556:
1555:
1550:
1545:
1540:
1528:
1526:
1525:
1520:
1518:
1510:
1505:
1492:
1482:
1468:
1466:
1465:
1460:
1455:
1450:
1442:
1437:
1429:
1427:
1426:
1417:
1409:
1394:
1392:
1391:
1386:
1384:
1379:
1368:
1363:
1355:
1353:
1352:
1343:
1335:
1323:
1321:
1320:
1315:
1313:
1312:
1296:
1294:
1293:
1288:
1286:
1285:
1268:
1264:
1260:
1253:
1250:Integers modulo
1245:
1243:
1242:
1237:
1235:
1227:
1218:
1214:
1210:
1208:
1207:
1202:
1179:
1177:
1176:
1171:
1166:
1150:
1149:
1121:
1107:
1096:
1092:
1077:
1063:
1061:
1060:
1055:
1050:
1025:
992:
990:
989:
984:
979:
957:
927:
923:
919:
915:
910:relatively prime
907:
903:
899:
884:
882:
881:
876:
871:
833:
829:
822:
818:
814:
810:
806:
802:
787:
783:
775:
768:
766:
765:
760:
758:
750:
741:
734:
732:
731:
726:
721:
676:
674:
673:
668:
660:
632:
615:
607:
595:
591:
589:
588:
583:
581:
573:
563:
556:
550:
548:
547:
542:
540:
521:
519:
518:
513:
508:
474:is denoted by,
469:
464:
458:
454:
451:, two integers,
450:
413:
411:
410:
405:
400:
358:binary operation
343:
339:
337:
336:
331:
329:
328:
309:
307:
306:
301:
296:
288:
283:
275:
273:
272:
263:
255:
243:
241:
240:
235:
233:
225:
216:
214:
213:
208:
206:
198:
185:
181:
179:
178:
173:
171:
163:
154:
150:
146:
141:congruence class
138:
134:
130:
126:
122:
115:
108:
106:
105:
100:
95:
53:
45:
41:
37:
5052:
5051:
5045:
5044:
5043:
5041:
5040:
5039:
5020:
5019:
4987:
4978:
4959:
4938:
4920:
4904:
4899:
4898:
4890:
4886:
4878:
4874:
4867:
4850:
4837:
4833:
4821:, 2nd edition.
4816:
4812:
4804:
4800:
4792:
4788:
4782:
4763:
4759:
4751:
4747:
4741:
4736:
4734:
4730:
4720:
4718:
4707:
4703:
4695:
4691:
4685:
4671:
4667:
4661:Schumacher 1996
4659:
4655:
4647:
4643:
4638:
4620:
4612:Kloosterman sum
4607:of 5,7 and 11.
4596:
4585:
4575:
4569:
4564:
4558:
4553:
4547:
4537:
4531:
4530:(5 × 11) × 4 +
4528:
4522:
4521:(7 × 11) × 4 +
4519:
4513:
4509:
4492:
4486:
4480:
4454:
4445:
4438:
4432:
4422:
4416:
4409:
4391:
4388:
4387:
4386:
4379:
4376:
4375:
4374:
4370:
4361:
4354:
4349:
4348:
4347:
4340:
4334:
4333:
4332:
4328:
4323:
4312:
4307:
4306:
4305:
4298:
4293:
4292:
4291:
4287:
4281:
4277:
4269:
4264:
4263:
4262:
4258:
4245:
4222:
4218:
4212:
4208:
4199:
4195:
4189:
4178:
4165:
4161:
4159:
4156:
4155:
4153:prefix products
4144:
4136:
4131:
4130:
4129:
4125:
4115:
4112:
4108:
4105:
4101:
4097:
4094:
4090:
4087:
4066:
4062:
4050:
4046:
4038:
4030:
4019:
3994:
3991:
3990:
3982:
3957:
3954:
3953:
3915:
3903:
3899:
3887:
3883:
3881:
3878:
3877:
3837:
3834:
3833:
3829:
3796:
3787:
3783:
3759:
3755:
3753:
3750:
3749:
3742:
3734:
3713:
3705:
3700:
3695:
3692:
3691:
3687:
3667:
3664:
3663:
3630:
3609:
3605:
3603:
3600:
3599:
3584:
3580:
3572:
3569:Euler's theorem
3562:
3546:
3544:
3536:
3524:
3491:
3477:
3474:
3473:
3421:
3418:
3417:
3356:
3353:
3352:
3341:
3337:
3333:
3329:
3325:
3321:
3310:
3306:
3303:
3297:
3292:
3271:
3263:
3258:
3256:
3253:
3252:
3232:
3224:
3219:
3217:
3214:
3213:
3192:
3179:
3173:
3169:
3159:
3157:
3154:
3153:
3132:
3130:
3127:
3126:
3105:
3103:
3100:
3099:
3078:
3076:
3073:
3072:
3051:
3049:
3046:
3045:
3024:
3022:
3019:
3018:
2908:
2905:
2904:
2897:
2890:
2869:
2867:
2864:
2863:
2854:
2850:
2843:
2836:
2829:
2821:
2814:
2793:
2791:
2788:
2787:
2779:
2698:
2696:
2693:
2692:
2615:
2613:
2610:
2609:
2533:
2531:
2528:
2527:
2451:
2449:
2446:
2445:
2411:
2400:
2397:
2396:
2367:
2356:
2353:
2352:
2319:
2302:
2299:
2298:
2271:
2254:
2251:
2250:
2223:
2206:
2203:
2202:
2201:. Examples are
2179:
2175:
2151:
2147:
2127:
2124:
2123:
2106:
2102:
2100:
2097:
2096:
2074:
2071:
2070:
2041:
2037:
2035:
2032:
2031:
2009:
2006:
2005:
2002:
1990:
1982:
1962:
1954:
1949:
1947:
1944:
1943:
1927:
1919:
1914:
1912:
1909:
1908:
1871:
1868:
1867:
1863:
1855:
1827:
1824:
1823:
1810:
1804:
1800:
1794:
1773:ring with unity
1765:
1761:
1741:
1738:
1737:
1712:
1709:
1708:
1698:
1694:
1691:
1685:
1681:
1661:
1653:
1648:
1646:
1643:
1642:
1636:
1632:, known as the
1629:
1622:{0, 1, 2, ...,
1621:
1611:
1604:
1600:
1592:
1572:
1567:
1566:
1564:
1561:
1560:
1541:
1536:
1534:
1531:
1530:
1514:
1506:
1501:
1499:
1496:
1495:
1490:
1480:
1443:
1441:
1428:
1422:
1418:
1408:
1406:
1403:
1402:
1369:
1367:
1354:
1348:
1344:
1334:
1332:
1329:
1328:
1308:
1304:
1302:
1299:
1298:
1281:
1277:
1275:
1272:
1271:
1266:
1262:
1258:
1255:
1251:
1226:
1224:
1221:
1220:
1216:
1212:
1196:
1193:
1192:
1151:
1142:
1138:
1130:
1127:
1126:
1112:
1098:
1094:
1079:
1068:
1035:
1018:
1004:
1001:
1000:
964:
950:
936:
933:
932:
925:
921:
917:
913:
905:
901:
889:
856:
842:
839:
838:
831:
827:
820:
816:
812:
808:
804:
789:
785:
781:
773:
749:
747:
744:
743:
739:
706:
692:
689:
688:
645:
628:
606:
604:
601:
600:
593:
572:
570:
567:
566:
561:
554:
536:
534:
531:
530:
493:
482:
479:
478:
472:binary relation
467:
462:
456:
452:
448:
445:
439:
385:
371:
368:
367:
341:
324:
320:
318:
315:
314:
287:
274:
268:
264:
254:
252:
249:
248:
224:
222:
219:
218:
197:
195:
192:
191:
183:
162:
160:
157:
156:
152:
148:
144:
136:
132:
128:
127:by the integer
124:
117:
113:
80:
66:
63:
62:
51:
43:
39:
35:
17:
12:
11:
5:
5050:
5049:
5038:
5037:
5032:
5018:
5017:
5014:solved example
5007:
4986:
4985:External links
4983:
4982:
4981:
4976:
4963:
4957:
4941:
4936:
4923:
4918:
4903:
4900:
4897:
4896:
4884:
4872:
4865:
4831:
4817:Thomas Koshy.
4810:
4798:
4786:
4780:
4757:
4745:
4737:
4728:
4701:
4689:
4683:
4665:
4653:
4651:, p. 132.
4640:
4639:
4637:
4634:
4633:
4632:
4627:
4619:
4616:
4601:
4600:
4590:
4589:
4579:
4578:
4573:
4567:
4562:
4556:
4551:
4541:
4540:
4535:
4526:
4517:
4499:
4498:
4497:
4496:
4490:
4484:
4461:
4460:
4451:
4408:
4405:
4397:
4396:
4389:
4377:
4367:
4366:
4365:
4359:
4350:
4335:
4326:
4318:
4308:
4294:
4274:
4265:
4255:
4231:
4228:
4225:
4221:
4215:
4211:
4207:
4202:
4198:
4192:
4187:
4184:
4181:
4177:
4173:
4168:
4164:
4132:
4110:
4103:
4092:
4086:
4083:
4055:
4054:
4023:
4007:
4004:
4001:
3998:
3970:
3967:
3964:
3961:
3945:
3944:
3933:
3929:
3926:
3922:
3919:
3912:
3909:
3906:
3902:
3898:
3893:
3890:
3886:
3862:
3859:
3856:
3853:
3850:
3847:
3844:
3841:
3826:
3825:
3814:
3810:
3807:
3803:
3800:
3793:
3790:
3786:
3782:
3777:
3774:
3771:
3768:
3765:
3762:
3758:
3732:if and only if
3720:
3716:
3712:
3708:
3703:
3699:
3671:
3660:
3659:
3648:
3644:
3641:
3637:
3634:
3629:
3626:
3621:
3618:
3615:
3612:
3608:
3561:
3558:
3533:big O notation
3521:
3520:
3509:
3505:
3502:
3498:
3495:
3490:
3487:
3484:
3481:
3467:
3466:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3411:
3410:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3363:
3360:
3299:Main article:
3296:
3293:
3291:
3288:
3274:
3270:
3266:
3261:
3235:
3231:
3227:
3222:
3199:
3196:
3191:
3186:
3183:
3176:
3172:
3166:
3163:
3139:
3136:
3112:
3109:
3085:
3082:
3058:
3055:
3031:
3028:
3011:
3010:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2876:
2873:
2851:gcd(3, 10) = 1
2844:gcd(4, 10) = 2
2800:
2797:
2776:
2775:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2705:
2702:
2690:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2648:
2645:
2642:
2639:
2636:
2633:
2630:
2627:
2622:
2619:
2607:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2540:
2537:
2525:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2458:
2455:
2439:
2438:
2425:
2422:
2418:
2415:
2410:
2407:
2404:
2394:
2381:
2378:
2374:
2371:
2366:
2363:
2360:
2333:
2330:
2326:
2323:
2318:
2315:
2312:
2309:
2306:
2285:
2282:
2278:
2275:
2270:
2267:
2264:
2261:
2258:
2237:
2234:
2230:
2227:
2222:
2219:
2216:
2213:
2210:
2190:
2187:
2182:
2178:
2174:
2171:
2168:
2165:
2162:
2159:
2154:
2150:
2146:
2143:
2140:
2137:
2134:
2131:
2109:
2105:
2084:
2081:
2078:
2058:
2055:
2052:
2049:
2044:
2040:
2019:
2016:
2013:
2001:
1998:
1965:
1961:
1957:
1952:
1930:
1926:
1922:
1917:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1840:
1837:
1834:
1831:
1807:is called the
1745:
1725:
1722:
1719:
1716:
1687:Main article:
1684:
1678:
1664:
1660:
1656:
1651:
1575:
1570:
1548:
1544:
1539:
1517:
1513:
1509:
1504:
1470:
1469:
1458:
1453:
1449:
1446:
1440:
1435:
1432:
1425:
1421:
1415:
1412:
1396:
1395:
1382:
1378:
1375:
1372:
1366:
1361:
1358:
1351:
1347:
1341:
1338:
1311:
1307:
1284:
1280:
1254:
1248:
1233:
1230:
1200:
1181:
1180:
1169:
1165:
1162:
1158:
1155:
1148:
1145:
1141:
1137:
1134:
1065:
1064:
1053:
1049:
1046:
1042:
1039:
1034:
1031:
1028:
1024:
1021:
1017:
1014:
1011:
1008:
994:
993:
982:
978:
975:
971:
968:
963:
960:
956:
953:
949:
946:
943:
940:
886:
885:
874:
870:
867:
863:
860:
855:
852:
849:
846:
756:
753:
736:
735:
724:
720:
717:
713:
710:
705:
702:
699:
696:
678:
677:
666:
663:
659:
656:
652:
649:
644:
641:
638:
635:
631:
627:
624:
621:
618:
613:
610:
579:
576:
539:
523:
522:
511:
507:
504:
500:
497:
492:
489:
486:
441:Main article:
438:
435:
415:
414:
403:
399:
396:
392:
389:
384:
381:
378:
375:
348:in the set of
327:
323:
311:
310:
299:
294:
291:
286:
281:
278:
271:
267:
261:
258:
231:
228:
204:
201:
169:
166:
110:
109:
98:
94:
91:
87:
84:
79:
76:
73:
70:
38:is an integer
15:
9:
6:
4:
3:
2:
5048:
5047:
5036:
5033:
5031:
5028:
5027:
5025:
5015:
5011:
5008:
5003:
5002:
4997:
4994:
4989:
4988:
4979:
4973:
4969:
4964:
4960:
4958:0-201-82653-4
4954:
4950:
4946:
4942:
4939:
4933:
4929:
4924:
4921:
4919:0-387-97329-X
4915:
4911:
4906:
4905:
4893:
4888:
4881:
4876:
4868:
4862:
4858:
4857:
4849:
4845:
4841:
4835:
4828:
4824:
4820:
4814:
4807:
4802:
4796:, p. 121
4795:
4790:
4783:
4781:9780521851541
4777:
4773:
4772:
4767:
4766:Shoup, Victor
4761:
4754:
4749:
4740:
4732:
4716:
4712:
4705:
4698:
4693:
4686:
4684:0-8493-8521-0
4680:
4676:
4669:
4663:, p. 88.
4662:
4657:
4650:
4645:
4641:
4631:
4628:
4625:
4622:
4621:
4615:
4613:
4608:
4606:
4595:
4594:
4593:
4584:
4583:
4582:
4572:
4568:
4561:
4557:
4550:
4546:
4545:
4544:
4534:
4525:
4516:
4508:
4507:
4506:
4504:
4495:≡ 6 (mod 11)
4491:
4485:
4479:
4478:
4477:
4476:
4475:
4472:
4470:
4465:
4457:
4452:
4448:
4441:
4435:
4430:
4429:
4428:
4425:
4419:
4413:
4404:
4402:
4385:
4373:
4368:
4362:
4353:
4346:
4338:
4331:
4327:
4321:
4317:
4311:
4304:
4297:
4290:
4286:
4285:
4275:
4268:
4261:
4256:
4252:
4248:
4229:
4226:
4223:
4219:
4213:
4209:
4205:
4200:
4196:
4190:
4185:
4182:
4179:
4175:
4171:
4166:
4162:
4154:
4150:
4149:
4148:
4141:
4135:
4128:
4122:
4118:
4082:
4080:
4076:
4072:
4060:
4044:
4036:
4028:
4024:
4002:
3996:
3988:
3987:factorization
3965:
3959:
3951:
3950:
3949:
3931:
3924:
3920:
3910:
3907:
3904:
3900:
3896:
3891:
3888:
3884:
3876:
3875:
3874:
3860:
3857:
3854:
3851:
3845:
3839:
3812:
3805:
3801:
3791:
3788:
3784:
3780:
3775:
3772:
3766:
3760:
3756:
3748:
3747:
3746:
3740:
3733:
3710:
3706:
3685:
3669:
3646:
3639:
3635:
3627:
3624:
3616:
3610:
3606:
3598:
3597:
3596:
3592:
3588:
3578:
3570:
3567:According to
3565:
3557:
3554:
3549:
3540:
3534:
3529:
3507:
3500:
3496:
3488:
3485:
3482:
3479:
3472:
3471:
3470:
3453:
3450:
3444:
3441:
3435:
3432:
3429:
3426:
3423:
3416:
3415:
3414:
3397:
3394:
3388:
3385:
3382:
3373:
3370:
3367:
3364:
3361:
3358:
3351:
3350:
3349:
3347:
3319:
3314:
3302:
3287:
3268:
3264:
3248:
3229:
3225:
3194:
3189:
3181:
3174:
3170:
3161:
3134:
3107:
3080:
3053:
3026:
3015:
2997:
2991:
2988:
2985:
2982:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2946:
2943:
2940:
2937:
2934:
2931:
2925:
2922:
2919:
2916:
2910:
2903:
2902:
2901:
2894:
2871:
2858:
2847:
2839:
2832:
2825:
2818:
2795:
2783:
2762:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2708:
2700:
2691:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2625:
2617:
2608:
2591:
2588:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2543:
2535:
2526:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2461:
2453:
2444:
2443:
2442:
2420:
2416:
2408:
2405:
2402:
2395:
2376:
2372:
2364:
2361:
2358:
2351:
2350:
2349:
2346:
2328:
2324:
2316:
2313:
2310:
2307:
2304:
2280:
2276:
2268:
2265:
2262:
2259:
2256:
2232:
2228:
2220:
2217:
2214:
2211:
2208:
2188:
2185:
2180:
2176:
2172:
2166:
2163:
2160:
2157:
2152:
2148:
2138:
2135:
2132:
2107:
2103:
2082:
2079:
2076:
2056:
2053:
2050:
2047:
2042:
2038:
2017:
2014:
2011:
1997:
1993:
1988:
1980:
1959:
1955:
1924:
1920:
1894:
1891:
1888:
1885:
1879:
1873:
1861:
1852:
1835:
1829:
1821:
1817:
1813:
1797:
1792:
1788:
1784:
1783:
1778:
1774:
1771:In a general
1769:
1759:
1743:
1720:
1714:
1706:
1705:
1690:
1677:
1658:
1654:
1640:
1639:
1625:
1619:
1615:
1614:
1603:. Any set of
1598:
1589:
1573:
1546:
1542:
1511:
1507:
1493:
1487:, called the
1486:
1477:
1475:
1456:
1447:
1444:
1438:
1430:
1423:
1419:
1410:
1401:
1400:
1399:
1376:
1373:
1370:
1364:
1356:
1349:
1345:
1336:
1327:
1326:
1325:
1309:
1305:
1282:
1278:
1247:
1228:
1198:
1190:
1186:
1167:
1160:
1156:
1146:
1143:
1139:
1135:
1132:
1125:
1124:
1123:
1119:
1115:
1109:
1105:
1101:
1091:
1087:
1083:
1075:
1071:
1051:
1044:
1040:
1032:
1029:
1022:
1019:
1015:
1012:
1006:
999:
998:
997:
980:
973:
969:
961:
958:
954:
951:
947:
944:
941:
938:
931:
930:
929:
911:
897:
893:
872:
865:
861:
853:
850:
847:
844:
837:
836:
835:
824:
800:
796:
792:
779:
770:
751:
722:
715:
711:
703:
700:
697:
694:
687:
686:
685:
683:
664:
654:
650:
642:
639:
636:
633:
625:
622:
616:
608:
599:
598:
597:
574:
564:
557:
528:
509:
502:
498:
490:
487:
484:
477:
476:
475:
473:
465:
444:
434:
432:
428:
427:RSA algorithm
424:
420:
401:
394:
390:
382:
379:
376:
373:
366:
365:
364:
361:
359:
355:
351:
347:
325:
321:
297:
289:
284:
276:
269:
265:
256:
247:
246:
245:
226:
199:
189:
164:
142:
120:
96:
89:
85:
77:
74:
71:
68:
61:
60:
59:
57:
49:
34:
30:
26:
22:
4999:
4967:
4948:
4927:
4909:
4887:
4875:
4855:
4834:
4813:
4808:, p. 31
4801:
4789:
4770:
4760:
4755:, p. 32
4748:
4738:
4731:
4719:. Retrieved
4714:
4704:
4692:
4674:
4668:
4656:
4644:
4609:
4602:
4591:
4580:
4570:
4559:
4548:
4542:
4532:
4523:
4514:
4500:
4489:≡ 4 (mod 7)
4483:≡ 4 (mod 5)
4473:
4466:
4462:
4455:
4446:
4439:
4433:
4423:
4417:
4414:
4410:
4407:Applications
4398:
4383:
4371:
4357:
4351:
4344:
4336:
4329:
4319:
4315:
4309:
4302:
4295:
4288:
4266:
4259:
4250:
4246:
4151:Compute the
4142:
4133:
4126:
4120:
4116:
4088:
4058:
4057:One notable
4056:
3946:
3832:is a prime,
3827:
3661:
3590:
3586:
3566:
3563:
3552:
3551:| <
3547:
3538:
3530:
3522:
3468:
3412:
3315:
3304:
3249:
3016:
3012:
2892:
2859:≡ 1 (mod 10)
2856:
2848:
2837:
2830:
2826:≡ 6 (mod 10)
2823:
2816:
2784:≡ 5 (mod 10)
2781:
2777:
2440:
2347:
2003:
1991:
1987:cyclic group
1979:finite field
1853:
1814:, and it is
1808:
1795:
1790:
1781:
1770:
1702:
1692:
1634:
1623:
1609:
1596:
1590:
1488:
1478:
1474:well-defined
1471:
1397:
1256:
1182:
1117:
1113:
1110:
1103:
1099:
1089:
1085:
1081:
1073:
1069:
1066:
995:
895:
891:
887:
825:
798:
794:
790:
771:
737:
681:
679:
559:
552:
524:
460:
446:
419:cryptography
416:
362:
354:real numbers
312:
187:
118:
111:
28:
18:
5012:provides a
4721:January 21,
4539:(5 × 7) × 6
3583:, that is,
3543:, assuming
3290:Computation
2345:and so on.
900:, that is,
823:solutions.
525:This is an
244:such that:
21:mathematics
5024:Categories
4902:References
4794:Rosen 1993
4649:Rosen 1993
4079:Curve25519
3952:The value
1816:isomorphic
1189:reciprocal
996:therefore
147:(i.e., in
25:arithmetic
5001:MathWorld
4829:. P. 346.
4369:Finally,
4227:−
4176:∏
4059:advantage
4053:is large.
4022:is known.
3997:ϕ
3960:ϕ
3908:−
3897:≡
3889:−
3858:−
3840:ϕ
3789:−
3781:≡
3773:−
3761:ϕ
3670:ϕ
3625:≡
3611:ϕ
3486:≡
3469:that is,
3442:−
3430:−
3198:¯
3185:¯
3171:⋅
3165:¯
3138:¯
3111:¯
3084:¯
3057:¯
3030:¯
2953:−
2932:−
2875:¯
2799:¯
2757:⋯
2730:−
2721:−
2715:⋯
2704:¯
2674:⋯
2647:−
2638:−
2632:⋯
2621:¯
2592:⋯
2565:−
2556:−
2550:⋯
2539:¯
2510:⋯
2483:−
2474:−
2468:⋯
2457:¯
2406:≡
2362:≡
2314:≡
2308:×
2266:≡
2260:×
2218:≡
2212:×
2158:−
2048:−
1989:of order
1892:−
1874:ϕ
1830:ϕ
1744:ϕ
1715:ϕ
1452:¯
1434:¯
1420:⋅
1414:¯
1381:¯
1360:¯
1340:¯
1306:⋅
1232:¯
1144:−
1136:≡
1116:≡ 1 (mod
1072:≡ 0 (mod
1030:≡
1016:−
959:≡
945:≡
851:≡
755:¯
701:≡
640:≡
634:∣
626:∈
612:¯
578:¯
488:≡
380:≡
322:⋅
293:¯
280:¯
266:⋅
260:¯
230:¯
203:¯
168:¯
131:is 1. If
75:≡
48:congruent
4947:(1996).
4894:, p. 165
4882:, p. 167
4768:(2005),
4618:See also
4444:, where
4257:Compute
4244:for all
4114:for all
3152:. Thus,
2122:, since
1822:(size),
1736:, where
1023:′
955:′
908:must be
815:divides
807:divides
425:and the
350:rational
4503:coprime
3739:coprime
3595:, then
3577:coprime
3309:modulo
2000:Example
1985:form a
1866:, then
1756:is the
1078:, then
928:, then
776:is the
596:, then
421:, e.g.
33:integer
4974:
4955:
4934:
4916:
4863:
4825:
4778:
4681:
4581:Thus,
4543:where
3662:where
3545:|
3537:O(log(
2891:7 + 10
2849:Since
2842:. The
1862:, say
1789:, the
1616:. The
1100:b ≡ b'
1093:, and
565:. Let
31:of an
4851:(PDF)
4636:Notes
4442:mod 2
4280:from
3593:) = 1
3571:, if
3328:. If
2900:and
1977:is a
1860:prime
1858:is a
1820:order
1787:group
1782:units
1626:− 1}
1111:When
1102:(mod
898:) = 1
811:. If
797:(mod
4972:ISBN
4953:ISBN
4932:ISBN
4914:ISBN
4861:ISBN
4823:ISBN
4776:ISBN
4723:2017
4679:ISBN
4276:For
3585:gcd(
3340:and
3324:and
3316:The
3044:and
2835:and
2015:>
1485:ring
1479:The
1398:and
1297:and
1088:) =
1080:gcd(
916:and
904:and
890:gcd(
784:and
455:and
27:, a
4605:LCM
4471:.
4325:and
4147:):
3985:'s
3921:mod
3802:mod
3741:to
3737:is
3682:is
3636:mod
3579:to
3575:is
3531:In
3497:mod
3377:gcd
2840:= 9
2833:= 4
2689:and
2417:mod
2403:111
2373:mod
2325:mod
2277:mod
2229:mod
1994:− 1
1799:if
1529:or
1191:of
1157:mod
1067:If
1041:mod
970:mod
862:mod
780:of
772:If
712:mod
651:mod
558:or
499:mod
466:if
391:mod
352:or
121:− 1
86:mod
46:is
19:In
5026::
4998:.
4853:.
4842:;
4713:.
4614:.
4512:=
4403:.
4382:=
4343:=
4339:−1
4322:−1
4301:=
4249:≤
4140:.
4119:≠
3589:,
3541:))
3398:1.
3348:,
3269:10
3247:.
3230:10
3175:10
2977:10
2968:30
2962:20
2947:30
2941:21
2923:10
2751:29
2745:19
2724:11
2668:25
2662:15
2641:15
2586:21
2580:11
2559:19
2504:20
2498:10
2486:10
2477:20
2421:10
2377:10
2359:32
2329:16
2311:13
2297:,
2249:,
1996:.
1851:.
1768:.
1114:ax
1108:.
1084:,
918:b'
894:,
793:≡
791:ax
680:A
125:ax
119:ax
44:ax
5004:.
4961:.
4869:.
4743:.
4739:m
4725:.
4597:X
4586:X
4574:3
4571:t
4563:2
4560:t
4552:1
4549:t
4536:3
4533:t
4527:2
4524:t
4518:1
4515:t
4510:X
4493:X
4487:X
4481:X
4456:k
4447:w
4440:k
4434:k
4424:k
4418:k
4395:.
4390:1
4384:b
4378:1
4372:a
4364:.
4360:i
4358:a
4352:i
4345:b
4337:i
4330:b
4320:i
4316:b
4310:i
4303:b
4296:i
4289:a
4282:n
4278:i
4267:n
4260:b
4254:.
4251:n
4247:i
4230:1
4224:i
4220:b
4214:i
4210:a
4206:=
4201:j
4197:a
4191:i
4186:1
4183:=
4180:j
4172:=
4167:i
4163:b
4145:m
4134:i
4127:a
4121:i
4117:j
4111:j
4109:a
4104:i
4102:a
4098:m
4093:i
4091:a
4067:a
4063:a
4051:m
4047:m
4039:m
4031:m
4020:m
4006:)
4003:m
4000:(
3983:m
3969:)
3966:m
3963:(
3932:.
3928:)
3925:m
3918:(
3911:2
3905:m
3901:a
3892:1
3885:a
3861:1
3855:m
3852:=
3849:)
3846:m
3843:(
3830:m
3813:.
3809:)
3806:m
3799:(
3792:1
3785:a
3776:1
3770:)
3767:m
3764:(
3757:a
3743:m
3735:a
3719:)
3715:Z
3711:m
3707:/
3702:Z
3698:(
3688:a
3647:,
3643:)
3640:m
3633:(
3628:1
3620:)
3617:m
3614:(
3607:a
3591:m
3587:a
3581:m
3573:a
3553:m
3548:a
3539:m
3525:a
3508:,
3504:)
3501:m
3494:(
3489:1
3483:x
3480:a
3454:,
3451:m
3448:)
3445:y
3439:(
3436:=
3433:1
3427:x
3424:a
3395:=
3392:)
3389:m
3386:,
3383:a
3380:(
3374:=
3371:y
3368:m
3365:+
3362:x
3359:a
3342:y
3338:x
3334:m
3330:a
3326:m
3322:a
3311:m
3307:a
3273:Z
3265:/
3260:Z
3234:Z
3226:/
3221:Z
3195:0
3190:=
3182:8
3162:5
3135:0
3108:8
3081:5
3054:8
3027:5
2998:,
2995:)
2992:r
2989:3
2986:+
2983:2
2980:(
2974:=
2971:r
2965:+
2959:=
2956:1
2950:r
2944:+
2938:=
2935:1
2929:)
2926:r
2920:+
2917:7
2914:(
2911:3
2898:r
2893:r
2872:7
2857:x
2855:3
2838:x
2831:x
2824:x
2822:4
2817:x
2815:4
2796:5
2782:x
2780:4
2763:.
2760:}
2754:,
2748:,
2742:,
2739:9
2736:,
2733:1
2727:,
2718:,
2712:{
2709:=
2701:9
2677:}
2671:,
2665:,
2659:,
2656:5
2653:,
2650:5
2644:,
2635:,
2629:{
2626:=
2618:5
2595:}
2589:,
2583:,
2577:,
2574:1
2571:,
2568:9
2562:,
2553:,
2547:{
2544:=
2536:1
2513:}
2507:,
2501:,
2495:,
2492:0
2489:,
2480:,
2471:,
2465:{
2462:=
2454:0
2424:)
2414:(
2409:1
2380:)
2370:(
2365:2
2332:)
2322:(
2317:1
2305:5
2284:)
2281:9
2274:(
2269:1
2263:7
2257:4
2236:)
2233:4
2226:(
2221:1
2215:3
2209:3
2189:1
2186:+
2181:3
2177:n
2173:=
2170:)
2167:1
2164:+
2161:n
2153:2
2149:n
2145:(
2142:)
2139:1
2136:+
2133:n
2130:(
2108:2
2104:n
2083:1
2080:+
2077:n
2057:1
2054:+
2051:n
2043:2
2039:n
2018:1
2012:n
1992:p
1983:p
1964:Z
1960:p
1956:/
1951:Z
1929:Z
1925:p
1921:/
1916:Z
1895:1
1889:p
1886:=
1883:)
1880:p
1877:(
1864:p
1856:m
1839:)
1836:m
1833:(
1811:m
1805:m
1801:R
1796:R
1766:m
1762:m
1724:)
1721:m
1718:(
1699:m
1695:m
1682:m
1663:Z
1659:m
1655:/
1650:Z
1637:m
1630:m
1624:m
1612:m
1605:m
1601:m
1593:m
1574:m
1569:Z
1547:m
1543:/
1538:Z
1516:Z
1512:m
1508:/
1503:Z
1491:m
1481:m
1457:.
1448:b
1445:a
1439:=
1431:b
1424:m
1411:a
1377:b
1374:+
1371:a
1365:=
1357:b
1350:m
1346:+
1337:a
1310:m
1283:m
1279:+
1267:m
1263:m
1259:m
1252:m
1229:a
1217:a
1213:a
1199:a
1168:,
1164:)
1161:m
1154:(
1147:1
1140:a
1133:x
1120:)
1118:m
1106:)
1104:m
1095:a
1090:a
1086:m
1082:a
1076:)
1074:m
1070:a
1052:.
1048:)
1045:m
1038:(
1033:0
1027:)
1020:b
1013:b
1010:(
1007:a
981:,
977:)
974:m
967:(
962:1
952:b
948:a
942:b
939:a
926:m
922:a
914:b
906:m
902:a
896:m
892:a
873:.
869:)
866:m
859:(
854:1
848:x
845:a
832:m
828:a
821:d
817:b
813:d
809:b
805:d
801:)
799:m
795:b
786:m
782:a
774:d
752:x
740:x
723:.
719:)
716:m
709:(
704:b
698:x
695:a
665:.
662:}
658:)
655:m
648:(
643:b
637:a
630:Z
623:b
620:{
617:=
609:a
594:a
575:a
562:m
555:m
538:Z
510:.
506:)
503:m
496:(
491:b
485:a
468:m
463:m
457:b
453:a
449:m
402:.
398:)
395:m
388:(
383:b
377:x
374:a
342:m
326:m
298:,
290:1
285:=
277:x
270:m
257:a
227:x
200:a
184:w
165:w
153:x
149:a
145:a
137:m
133:a
129:m
114:m
97:,
93:)
90:m
83:(
78:1
72:x
69:a
52:m
40:x
36:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.