Recall The Standard Statement Of The Chinese Remainder Theorem

Decent Essays
The Quotient Ring Transform is an alternate encoding and decoding process developed by Dr. Anna
Johnston [5]. The utility of this error detection and correction process is that it is not dependent on a fixed set of primitive roots. Thus, a standard encryption procedure can be efficiently included in the process. This section lays out Dr. Johnston’s work and provides a simple worked example.
3.1 The Chinese Remainder Theorem
Recall the standard statement of the Chinese Remainder Theorem [1]:
Theorem 3.1 (Chinese Remainder Theorem). Let n1, n2, . . . , nk ∈ Z with every ni pairwise coprime and ni > 1. Let N = n1n2 . . . nk. Then there exists a unique x ∈ Z with 0 ≤ x < N such that x ≡ a1 mod n1 x ≡ a2 mod n2
.
.
.
x ≡ ak mod nk
Stated another way, Z/NZ ∼= Z/n1Z×· · ·×Z/nkZ given by x mod N 7→ (x mod n1, . . . , x mod nk) is a ring homomorphism.
Proof. Let N = n1n2 . . . nk, yi =
N
ni for all i = 1, 2, . . . , k, and zi = y
−1
i mod ni
. Note that y
−1
i mod ni exist since yi and ni are coprime by construction. Notice that when j 6= r, yjzj ≡ 0 mod nr and when j = r, yjzj ≡ 1 mod nr. Then x =
X
k i=1 aiyizi (7) satisfies all of the congruences in the statement of the theorem.
6
For example, suppose we want to find x such that x ≡ 1 mod 5 x ≡ 3 mod 7 x ≡ 2 mod 9.
We then have that N = (5)(7)(9) = 315 and y1 = 315/5 = 63, y2 = 315/7 = 45, and y3 = 315/9 = 35.
This gives us that
2 ≡ 63−1 mod 5
5 ≡ 45−1 mod 7
8 ≡ 35−1 mod 9 and so z1 = 2, z2 = 5, and z3 = 8. Therefore, x = 1(63)(2)

Related Documents

  • Decent Essays

    Using Triangle Inequality

    • 1571 Words
    • 7 Pages

    Theorem 3.2. Suppose that u ∈ Cp+1(Ω); s = 1; 2;∞;Ω ⊂ R2 and that uh ∈ Wh on a quasi-uniform family {Qh} of meshes on Ω into quadrilaterals. Then a necessary condition for ∥u − uh∥ Ls(Ω) = O(hp+1) is for uh to be Wp+1 s smooth. In particular, for ∥u − uh∥ L∞(Ω) = O(hp+1) a necessary condition is that all the kth partial derivatives at xi ∈ T satisfy (41) @ (u − uh)(xi) = O(hp+1−k); | | = k; 0 ≤ k ≤ p: In other words, we have a simultaneous approximation result. Here all smoothness refers to interior smoothness and {xi} is any collection of points, one from each element.…

    • 1571 Words
    • 7 Pages
    Decent Essays
  • Decent Essays

    * Based on point 3 * Based on point 3 * Based on point 2 Expression based on above truth table is XY’Z+ XYZ+X’YZ +XYZ’ XY’Z+ XYZ+X’YZ +XYZ’ XY’Z+YZ (X+X’) +XYZ’ //Distributive Law// XY’Z+YZ (1) +XYZ’ //Inverse Law// XY’Z+YZ+XYZ’ Z (XY’+Y) +XYZ’ //Distributive Law// Z(Y+Y’X) +XYZ’ //Commutative Law// Z ((Y+Y’)(Y+X))+XYZ’ //Distributive over AND// Z ((1)(Y+X))+XYZ’ //Inverse Law// Z(Y+X) +XYZ’ //Identity Law // ZY+ZX+XYZ’ //Distributive Law// ZY+X (Z+YZ’) //Distributive Law// ZY+X (Z+Z’Y) //Commutative Law// ZY+X ((Z+Z’)(Z+Y)) //Distributive over AND// ZY+X ((1)(Z+Y)) //Inverse Law// ZY+X(Z+Y) //Identity Law// ZY+XZ+XY //Distributive Law// XY+YZ+XZ //Commutative Law// OR XY’Z+ XYZ+X’YZ +XYZ’ XY’Z+ XYZ+XYZ+X’YZ +XYZ’ //Idempotent Law// XY’Z+ XYZ+XYZ+XYZ+X’YZ +XYZ’ //Idempotent Law// XY’Z+XYZ+XYZ+X’YZ+XYZ+XYZ’ //Commutative Law// XZ (Y’+Y) +YZ (X+X’) +XY (Z+Z’) //Commutative Law// XZ (1) +YZ (1) +XY (1) //Inverse Law// XZ+YZ+XY //Identity…

    • 533 Words
    • 3 Pages
    Decent Essays
  • Decent Essays

    ( 5 ) cov ( X, Y ) = ( 1/n)sum Xi Yi - barX barY sigma X2 = ( 1/n )sum X2i - barX 2 Multiplying equation ( 4 ) with X and sub from ( 5 ) cov ( X , Y ) = b sigma X2 b = cov ( X , Y ) / sigma X2 Substitute the value of b in ( 4 ) rArr barY = a + cov ( X , Y ) barX / sigma X2 a = barY - cov ( X , Y ) barX / sigma X2 Substitute the value of a in ( 1 ) Y = barY - cov ( X , Y ) barX / sigma X2 + cov ( X , Y ) X / sigma X2 Y - barY = cov ( X , Y ) ( X - barX ) / sigma X2 Y - barY = rsigma X sigma Y ( X -barX ) / sigma X2 Y - barY = r sigma Y ( X - barX ) / sigma X Y - barY = bYX ( X - barX ) Similarly, we can prove that regression equation of X-on-Y is X - barX = bXY ( Y - barY ) Types of Linear Regression There are two different types of linear regression. They are, Simple Linear Regression Multiple Linear Regression Examples Given below are some examples on how to calculate linear regression. Example: 10 observations on price X and supply "Y" the following data was obtained sum X = 130, sum Y = 220, sum X2 = 2288, sum2 = 5506, sum XY = 3467 Find the line of regression of Y on X. Y Solution: The line of regression of Y on…

    • 740 Words
    • 3 Pages
    Decent Essays
  • Decent Essays

    PRELIMINARIES 2.1. The Bilinear Pairings and Complexity Assumptions We briefly show theoretical background and complexity assumptions that used throughout our paper. Bilinear maps: We say a map e ̂:G_1×G_1→ G_2 is a bilinear map if the following properties hold: G_1and G_2are cyclic groups of the same prime order q and e ̂(g,g) is efficiently computable; For all a,b∈Z_q and g∈G_1, then e ̂(g^a,g^b) = e ̂〖(g,g)〗^ab; e ̂(g,g) is non-degenerate. That is, if g generates G_1 the e ̂(g,g) generates G_2. The above bilinear map is called symmetric pairings.…

    • 2042 Words
    • 8 Pages
    Decent Essays
  • Decent Essays

    (14) To get [(D.E/vol.) Y.P.]T.T. Substitute σ1 = σ = Syt/N , σ2 = σ3 = 0 in equation (14) [(D.E/vol.) Y.P. ]T.T.= (1+μ)/3E (Syt/N)^2--------------Eq.…

    • 1300 Words
    • 6 Pages
    Decent Essays
  • Decent Essays

    Axiom of choice was formulated by Zermelo in 1904 and is known as Zermelo’s axiom of choice. This axiom stated that we can choose a member from each set in a collection of nonempty disjoint sets, C (Schechter, 2009). Additionally, according to Janes (2008), there exists a set X which consisting of one element taken from each set belonging to Y given that any nonempty set Y members are pairwise disjoint sets. Taking a role as a basic assumption used in many parts of mathematics as stated by Schechter (2009), there are numbers of theorems which must use the application of axiom of choice in order for them to work smoothly To illustrate the concept, we can use a physical analogy as follows which was mentioned by Kelly et al., (2012). Assume there…

    • 956 Words
    • 4 Pages
    Decent Essays
  • Decent Essays

    Ex-Touch Triangle Essay

    • 785 Words
    • 4 Pages

    It is named in honor of Benjamin Bevan. The Bevan point is the reflection of Incenter in the Circumcenter and it is also the reflection of orthocenter in the Spieker center. The Bevan point(V) is the midpoint of line segment joining the Nagel point and de-Longchamps point.The Bevan point(V) is a triangle center and it is listed as the point X(40) in Clark Kimberling’s Encyclopedia of Triangle Centers[15]. Lemma – 1 If is the area of pedal’s triangle with respect to the any arbitrary point P, and if is the area of reference triangle then prove that Among all the pedal’s triangles, the pedal triangle with respect to some point P whose area is one fourth of the area of the reference triangle, has maximum area. That is .…

    • 785 Words
    • 4 Pages
    Decent Essays
  • Decent Essays

    Failure Mechanistics

    • 1636 Words
    • 7 Pages

    √(a/2r ) (cos⁡〖θ/2〗-i sin⁡〖θ/2〗 ) Similarly, we can compute Z’ as Z(_^')(z) =σ_(∞^. )/2r √(a/2r) (cos⁡〖3θ/2〗-i sin⁡〖3θ/2〗…

    • 1636 Words
    • 7 Pages
    Decent Essays
  • Decent Essays

    Pt1420 Unit 1 Essay

    • 508 Words
    • 3 Pages

    1. What are the least, and most, amount of distinct zeroes of a 7th degree polynomial, given that at least one root is a complex number? Answer: If the equation is 7th degree then it has 7 roots. Those roots can be complex or real. Complex roots always come in pairs, so if it has one, then it has 2, the other one being the conjugate of the first one.…

    • 508 Words
    • 3 Pages
    Decent Essays
  • Decent Essays

    qt CV or MB amount that adsorbed onto unit weight of adsorbent at any time t (mg/g) K1 is the rate constant for pseudo-first-order model (L/min). The value of qe and K1 were found from slope and intercept of linear relation between log (qe- qt) with t at the given concentrations. The straight line between log (qe- qt) and the time emphasize the applicability of the equation (7) , fig. (11). The pseudo second-order is given in equation: ........................................................................................................(8) Where: qe CV or MB amount that adsorbed onto unit weight of adsorbent at equilibrium (mg/gm).…

    • 1209 Words
    • 5 Pages
    Decent Essays