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. 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 $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}$. 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 \in Z_30^*$ such that $29=7^x (\mod{30})$

Knowing $g_i^{p_i}=1$ (this is also a condition for well-posed question that $g_i$ must be a generator of $(Z_{p_i}^*,\cdot)$, say, for $(Z_7^*,\cdot)$) only 3 and 5 possible for $g_i$, there is some $k_i$ such that $x=a_i+k_i p_i$ aka $x=a_i (\mod{p_i})$

Then by the black box hint, $x$ is found

A side note. 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$

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