How can I approach the following exercise:
Source: An Introduction to Mathematical Cryptography by Hoffstein
This exercise describes an approach similar to ElGamal cryptosystem with a numerical example, and in order to solve it, one should do some "reverse-engineering" and find a ay how to deduce a general algorithm from the example given.
I copied the entire text so that you get some extra context of this task. I don't know in which relationship are the exponents.
The only conclusion I've managed to made is: $m ^{ a \cdot b \cdot a' \cdot b' } = m$ with $m, a$ and $b$ defined as above and $a'= 15619$ and $b'=31883$.
One can be very fast trapped to think of an obvious solution - namely that $a$ and $a'$ are inverses in $\mathbb{Z}_p$, but they are not because: $gcd(3589,32611) = 1 = 822*32611 - 7469*3589 \Rightarrow - 7469 = 25142 (\mod 32611)$ and $25142$ is not equal to $15619$.
(This also means that I was barking barking up the wrong tree saying that $aa'$ and $bb'$ are such numbers that $\exists k: m^{ k \varphi ( p + 1 )} mod p = 1$, ie $m^{(aa')(bb')} mod p =m$ => $k \varphi ( p + 1 ) = aa'bb'$, where $\varphi(n)$ is defined like in the Euler Theorem. This is wrong because we should be able to calculate a' without any knowledge about b).
Here are a few pointers.
You have realized that the basic idea is that $m^{abxy} = m \mod p$. For that to hold, it's sufficient of course that both $m^{ax} = m \mod p$ and $m^{by} = m \mod p$. Now compare this to euler's theorem (actually, fermat's little theorem will suffice). Given a prime $p$, what are the requirements on $a$ for there to be an $x$ with $m^{ax} = m \mod p$, and how do you find $x$ from $a$?