[parent]

A-12.1 Rescaling Modulo of Congruence Relations

Remember from §A-1 that a mod q is the remainder of a divided by k, and the congruence relation a ≡b mod q means that the remainder of a divided by q is the same as the remainder of b divided by q. Its equivalent numeric equation is a = b + k ⋅q, meaning that a and b differ by some multiple of q. The congruence and equation are two different ways of describing the relationship between two numbers a and b.

In this section, we introduce another way of describing the relationship between numbers. We will describe two numbers a and b in terms of a different modulo q′ instead of the original modulo q. Such a change of modulo of a congruence relation is called modulo scaling. When we rescale the modulo of a congruence relation, we also need to rescale the numbers involved in the congruence relation.

Suppose we have the following congruence relations:

a ≡b mod q

a + c ≡b + d mod q

a ⋅c ≡b ⋅d mod q

Now, suppose we want to rescale the modulo of the above congruence relations from q →q′, where q′ | q (i.e., q′ divides all of q, or q is a multiple of q′). Then, the accordingly updated congruence relations are as shown in Table 3.

Congruence Rescaled Congruence Relation Rescaled Congruence Relation
Relation – Exact – Approximate
a ≡b mod q ⌈aq′ q ⌋ ≡⌈bq′ q ⌋ mod q′ ⌈aq′ q ⌋≅⌈bq′ q ⌋ mod q′
(if q divides all of: aq′,bq′) (if q does not divide: aq′ or bq′)
a + c ≡b + d mod q ⌈aq′ q ⌋ + ⌈cq′ q ⌋ ≡⌈bq′ q ⌋ + ⌈dq′ q ⌋ mod q′ ⌈aq′ q ⌋ + ⌈cq′ q ⌋≅⌈bq′ q ⌋ + ⌈dq′ q ⌋ mod q′
(if q divides all of: aq′,bq′,cq′,dq′) (if q does not divide: aq′,bq′,cq′, or dq′)
a ⋅c ≡b ⋅d mod q ⌈𝑎𝑐q′ q ⌋ ≡⌈𝑏𝑑q′ q ⌋ mod q′ ⌈𝑎𝑐q′ q ⌋≅⌈𝑏𝑑q′ q ⌋ mod q′
(if q divides both: 𝑎𝑐q′,𝑏𝑑q′) (if q does not divide: 𝑎𝑐q′ or 𝑏𝑑q′)
Table 3: Rescaling the congruence relations from modulo q →q′ (where ⌈⌋ rounds to the nearest integer)

Proof.

1.
a ≡b mod q ⟺ a = b + q ⋅k (for some integer k)

⟺a ⋅q′ q = b ⋅q′ q + q ⋅k ⋅q′ q

⟺a ⋅q′ q = b ⋅q′ q + k ⋅q′

(a)
If q divides all of aq′, bq′, cq′, and dq′, then a ⋅q′ q = ⌈aq′ q ⌋, b ⋅q′ q = ⌈bq′ q ⌋. Therefore:

a ⋅q′ q = b ⋅q′ q + k ⋅q′

⟺⌈aq′ q ⌋ = ⌈bq′ q ⌋ + k ⋅q′

⟺⌈aq′ q ⌋ ≡⌈bq′ q ⌋ mod q′ (⟺a ≡b mod q)

(b)
If q does not divide any of aq′, bq′, cq′, or dq′, then a ⋅q′ q ≈⌈aq′ q ⌋, b ⋅q′ q ≈⌈bq′ q ⌋. Therefore:

a ⋅q′ q = b ⋅q′ q + k ⋅q′

⟺⌈aq′ q ⌋ ≈⌈bq′ q ⌋ + k ⋅q′

⟺⌈aq′ q ⌋≅⌈bq′ q ⌋ mod q′ (⟺a ≡b mod q)

2.
a + c ≡b + d mod q ⟺ a + c = b + d + q ⋅k (for some integer q)

⟺a ⋅q′ q + c ⋅q′ q = b ⋅q′ q + d ⋅q′ q + q ⋅k ⋅q′ q

⟺a ⋅q′ q + c ⋅q′ q = b ⋅q′ q + d ⋅q′ q + k ⋅q′

(a)
If q divides all of aq′, bq′, cq′, and dq′, then

aq′ q + cq′ q = ⌈aq′ q ⌋ + ⌈cq′ q ⌋, bq′ q + dq′ q = ⌈bq′ q ⌋ + ⌈dq′ q ⌋

Therefore:

a ⋅q′ q + c ⋅q′ q = b ⋅q′ q + d ⋅q′ q + k ⋅q′

⟺⌈aq′ q ⌋ + ⌈cq′ q ⌋ = ⌈bq′ q ⌋ + ⌈dq′ q ⌋ + k ⋅q′

⟺⌈aq′ q ⌋ + ⌈cq′ q ⌋ ≡⌈bq′ q ⌋ + ⌈dq′ q ⌋ mod q′ (⟺a ≡b mod q)

(b)
If q does not divide any of aq′, bq′, cq′, or dq′, then

aq′ q + cq′ q ≈⌈aq′ q ⌋ + ⌈cq′ q ⌋, bq′ q + dq′ q ≈⌈bq′ q ⌋ + ⌈dq′ q ⌋

Therefore:

a ⋅q′ q + c ⋅q′ q = b ⋅q′ q + d ⋅q′ q + k ⋅q′

⟺⌈aq′ q ⌋ + ⌈cq′ q ⌋ ≈⌈bq′ q ⌋ + ⌈dq′ q ⌋ + k ⋅q′

⟺⌈aq′ q ⌋ + ⌈cq′ q ⌋≅⌈bq′ q ⌋ + ⌈dq′ q ⌋ mod q′ (⟺a + c ≡b + d mod q)

3.
a ⋅c ≡b ⋅d mod q ⟺ a ⋅c = b ⋅d + q ⋅k (for some integer q)

⟺𝑎𝑐 ⋅q′ q = 𝑏𝑑 ⋅q′ q + q ⋅k ⋅q′ q

⟺𝑎𝑐 ⋅q′ q = 𝑏𝑑 ⋅q′ q + k ⋅q′

(a)
If q divides all of aq′, bq′, cq′, and dq′, then

𝑎𝑐 ⋅q′ q = ⌈𝑎𝑐q′ q ⌋, 𝑏𝑑 ⋅q′ q = ⌈𝑏𝑑q′ q ⌋

Therefore:

𝑎𝑐 ⋅q′ q = 𝑏𝑑 ⋅q′ q + k ⋅q′

⟺⌈𝑎𝑐q′ q ⌋ = ⌈𝑏𝑑q′ q ⌋ + k ⋅q′

⟺⌈𝑎𝑐q′ q ⌋ ≡⌈𝑏𝑑q′ q ⌋ mod q′ (⟺a ⋅c ≡b ⋅d mod q)

(b)
If q does not divide any of aq′, bq′, cq′, or dq′, then

𝑎𝑐 ⋅q′ q ≈⌈𝑎𝑐q′ q ⌋, 𝑏𝑑 ⋅q′ q ≈⌈𝑏𝑑q′ q ⌋

Therefore:

𝑎𝑐 ⋅q′ q = 𝑏𝑑 ⋅q′ q + k ⋅q′

⟺⌈𝑎𝑐q′ q ⌋ ≈⌈𝑏𝑑q′ q ⌋ + k ⋅q′

⟺⌈𝑎𝑐q′ q ⌋≅⌈𝑏𝑑q′ q ⌋ mod q′ (⟺a ⋅c ≡b ⋅d mod q)

□

As shown in the proof, if all numbers in the congruence relations are exactly divisible by the rescaling factor during the modulo rescaling, then the rescaled result gives exact congruence relations in the new modulo. On the other hand, if any numbers in the congruence relations are not divisible by the rescaling factor during the modulo rescaling (i.e., we need to round some decimals), then the rescaled result gives approximate congruence relations in the new modulo.

In a more complicated congruence relation that contains many (+,−,⋅) operations, the same principle of modulo rescaling explained above can be recursively applied to each pair of operands surrounding each operator.

A-12.1.1 Example

Suppose we have the following congruence relation:

b ≡a ⋅s + Δ ⋅m + e mod q, where: q = 30, s = 5, a = 10, Δ = 10, m = 1, e = 10, b = 40

First, we can test if the above congruence relation is true by plugging in the given example values as follows:

b ≡a ⋅s + Δ ⋅m + e mod 30

40 ≡10 ⋅5 + 10 ⋅1 + 10 mod 30

40 ≡70 mod 30

This congruence relation is true.

Now, suppose we want to rescale the modulo from 30 →3. Then, based on the rescaling principles described in Table 3, we compute the rescaled values as follows:

q′ = 3, s = 5, m = 1

a^ = ⌈a ⋅ 3 30⌋ = ⌈10 ⋅ 3 30⌋ = 1

Δ^ = ⌈Δ ⋅ 3 30⌋ = ⌈10 ⋅ 3 30⌋ = 1

e^ = ⌈e ⋅ 3 30⌋ = ⌈10 ⋅ 3 30⌋ = 1

b^ = ⌈b ⋅ 3 30⌋ = ⌈40 ⋅ 3 30⌋ = 4

The rescaled congruence relation from modulo 30 →3 is derived as follows:

⌈b 3 30⌋ ≡⌈s ⋅a 3 30⌋ + ⌈m ⋅Δ 3 30⌋ + ⌈e 3 30⌋ mod 3

b^ ≡a^ ⋅s + Δ^ ⋅m + e^ mod 3 (an exact congruence relation, as all rescaled values have no decimals)

4 ≡1 ⋅5 + 1 ⋅1 + 1 mod 3

4 ≡7 mod 3

As shown above, the rescaled congruence relation preserves correctness, because all rescaled values are divisible by the rescaling factor. By contrast, if q q′ = 30 3 = 10 did not divide any of a ⋅s, Δm, or e, then the rescaled congruence relation would be an approximate (i.e., ≅) congruence relation.

[parent]