task 1

a

because there is inverse $a^{-1} \in Z_m^*$, so $x=a^{-1} \cdot b (\mod{m})$

b

because $a$ is not coprime with $m$, let $g$ be the gcd of $a$ and $m$, there are two integers $p,q$ such that $a p + m q =g>1$. Therefore any number who is not multiple of $g$ is a candidate of $b$ as it must be $\exists k, b=a x + m k$

c

Given another group generator $g^i$, the group is $\{g^{i \cdot 1}, g^{i \cdot 2}, \cdots, g^{i \cdot (m-1)}, g^{i \cdot m}=(g^m)^i=1^i=1\}$

if $i$ is not coprime with $m$, then there would be some smaller number $a<m, g^{i a}=1$ already; to have $g^{i a}=1$, it means $i a = m k$ for some $k$. By 質因數分解 $i$ and $m$, not coprime means some common prime factor for both, for example, $i=3^1 \cdot 5^2, m=2^3 \cdot 3^4$ have 3 as common prime factor, then $(3^1 \cdot 5^2)a=(2^3 \cdot 3^4)k$, a smaller $a$ to be $2^3 \cdot 3^3 < 2^3 \cdot 3^4$ and accordingly $k=5^2$

The set of all generators is $\{g^i | \text{i and m coprime}\}$

A side note about subgroup. The order of a subgroup $S$ must be $\frac{1}{h}$ of the order of the group $G$ for some positive integer $h$. To prove this, define $x S \equiv \{x \cdot s | s \in S\}$ who has the same size as $S$, then $x_1 S$ and $x_2 S$ are two either identical or disjoint sets for any group element $x_1,x_2$, never partial intersection, therefore $G$ treated as a set must be disjoint union of $x_1 S, x_2 S, \cdots, x_h S$ for some $x_1, x_2, \cdots, x_h$. Then a trivial collary is that a group of order of a prime number has no trivial subgroup and any element other than 1 is a generator. Also, the set $\{x^j| \text{j is an integer}\}$ must be a subgroup for any group element $x$, therefore $x^{|G|}=1$ for any group element $x$

d

all elements except 0 (operator's 1) can be generator by c above

task 2

any cyclic group $(G,\cdot)$ of order $m$ is isomorphic to $(Z_m,+)$ with translation: $g^k \Leftrightarrow \sum_{i=1}^k {1}$

a

$\{g^{\alpha \cdot 1}, g^{\alpha \cdot 2}, \cdots, g^{\alpha \cdot (n-1)}, g^{\alpha \cdot n}=g^m=1\}$

b

let the answer be $p$, then $g^{\alpha p}=g^{x \alpha}$

so $\exists k, \alpha p =x \alpha + k m$

so $p-x=k n$

so $p=x (\mod{n})$

c

what DDH?

$m=2 \times 3 \times 5=30$

$(Z_m^*,\cdot)$ is not necessarily cyclic (so nothing to do with task 2?)

$Z_30^*=\{1, 7, 11, 13, 17, 19, 23, 29\}$

but with an excel, $7^4=11^4=13^4=17^4=19^2=23^4=29^2=1$ and each element only forms a subgroup of order 2 or 4, never the whole group of order 8

$(Z_m,+)$ is cyclic group

d

as $(Z_m^*,\cdot)$ is not necessarily cyclic, a $X \in Z_m^*$ might not be of the form $X=g^x$ except trivial one

however, If $X,g,p_1,p_2, \cdots,p_44$ are known and $X$ is pre-determined as $X=g^x (\mod{m})$ for some $x$, then

Define:

$X_i \equiv X (\mod{p_i})$

$g_i \equiv g (\mod{p_i})$

By $X=g^x (\mod{m})$

$X_i=g_i^x (\mod{p_i})$ and there is $a_i$ such that $X_i=g_i^{a_i} (\mod{p_i})$. If NOT such $a_i$, for example $g_i=1$ and $X_i \neq 1$, then the original quesntion is, as mentioned above, not well-posed and has no solution. To have a taste of such case, consider the problem of finding $x$ such that $29=7^x (\mod{30})$ which, by c above already seen $7^i$ has no 29, leads to

$1=1^x (\mod{2})$

$2=1^x (\mod{3})$ an impossibility condition

$4=2^x (\mod{5})$

Assume $g_i$ has period $q_i$ which is a factor of $p_i-1$, then $g_i^{a_i+k_i q_i}$ satisfy the condition $X_i=g_i^{a_i+k_i q_i} (\mod{p_i})$ as well for any integer $k_i$, $x=a_i+k_i q_i$ aka $x=a_i (\mod{q_i})$ who also leads to more $x$ mod equations of prime factors $p_{i,j}$ of $q_i$, many $x=a_i (\mod{p_{i,j}^{h_{i,j}}})$ listed as the result

Then, in case no contradiction of these listed equations, by the black box hint $x$ is found.

A side note of the blackbox hint. This is the story of 韓信點兵, 韓信 as a general in 秦末漢初 good at math used this method to count the head count of soldiers by grouping the soldiers by $p_i$ and getting the $a_i$. The method is, given $m=p_1 \cdot p_2 \cdot \cdots p_n$, to assume $x=\sum_i^n {c_i \prod_{j \neq i} p_j}$. Then $a_k=x (\mod{p_k})=c_k \left( \prod_{j \neq k} p_j (\mod{p_k}) \right)$ to solve $c_k$ then a general solution of $x$ is $x=\left( \sum_i^n {c_i \prod_{j \neq i} p_j} \right) + t \cdot \prod_i^n p_i$ with any integer $t$. One can actually group by $p_i^{h_i}$ then the setting is to assume $x=\sum_i^n {c_i \prod_{j \neq i} p_j^{h_j}}$ and remember once the residual of $p_i^{h_i}$ is out, no need to see the residual of $p_i$ because it is determned already and introduce no new information about $x$.

Example 1

Solve $x=8 (\mod{18})$

Then $x=0 (\mod{2})$ and $x=8 (\mod{3^2})$, set $x=c_1 \cdot 2 + c_2 \cdot 3^2$ so $0=c_2 \cdot 1$ and $8=c_1 \cdot 2$ therefore $c_1=4,c_2=0$ so $x=8$ and the general solution is $x=8+18t$. Of course!

Example 2

Find $x$ such that $13=7^x (\mod{30})$

$30=2^1 \times 3^1 \times 5^1$

$1=1^x (\mod{2^1})$ a dummy condition

$1=1^x (\mod{3^1})$ another dummy condition

$3=2^x (\mod{5^1})$ has a solution $x=3$. 2 is period 4 in mod 5, therefore $x=3 (\mod{4})$ so all the mod equations are:

• $x=3 (\mod{2^2})$

Then the 韓信 solution is $x=3 + 4t$. Check: $7^{3+4t} (\mod{30})=13 \cdot (7^4)^t (\mod{30})=13 \cdot 1^t (\mod{30})=13$

A historian side note is that 韓信 was holding large army and was so inteligent so the king 劉邦 who was so afraid of possible 韓信's coup killed 韓信 later once 韓信 won all wars against other countries

task 3

task 4

Because cyclic, let $S=g^r$, given $g^p=1$, then the collision is

$g^{x_1+r x_2}=g^{x_1'+r x_2'}$ aka

$x_1-x_1'=r (x_2-x_2') (\mod{p})$

Since $p$ is prime, $(Z_p^*, \cdot)$ is itself a group having $x_2-x_2'$ and the inverse of $x_2-x_2'$ exists, therefore

$r= (x_1-x_1') \cdot (x_2-x_2')^{-1} (\mod{p})$

task 5

a

$k,r,t \in Z_2^n$ and $s=k+r$ where + in in sense of $Z_2^n$

$u=s+t=k+r+t$

$w=u+r=k+r+t+r=k+t$

$w+t=k+t+t=k$

Alice answer $k$ and Bob answer $w+t$, both the same

b

$(S,U,W)=(K+R,K+R+T,K+R+T+R)$

$R=U+W$

therefore $K=S+R=S+U+W$

So the D can compute $K=S+U+W$ which should be the same as the 4rd argument for $K$ by answering true iff $S+U+W$ and 4rd argument the same