Number theory related to crypto I have a question related to a piece of coursework that is for cryptography and more for encryption that relies on Number theory, now I have no knowledge of number theory and the tutor did not cover it well enough, and I am starting to learn it slowly, but I have an exam coming up and one question will be like the one below, so any help from you guys would be appreciated.enter image description here
Consider the group $G=\mathbb{Z}^*_{61}$ with respect to multiplication. Compute the following
o Find the inverse element of 53 in $G$.
o Compute the order of the element 15 in $G$.
o Let $H := \langle 8 \rangle$ be a group containt in $G$, i.e. H is generated by the of powers of 8 modulo 61. Find two non-trivial subgroups of H. The trivial subgroups of $H$ are $\langle 1 \rangle$ (which only contains the identity element and $H$ itself.
 A: Since p (here p=61) is a prime you should know that it holds $x^{p-1} = 1 \mod p$.
Therefore $x^{p-1-u} \cdot x^u = 1 \mod p$ and so $x^{p-1-u}$ and $x^u$ are inverses. Therefore $x^{-1} = x^{p-2} \mod p$  
To answer the first point we simply have to calculate $53^{59} \mod 61$, which is 38. You can check this by, $53 \cdot 38 \equiv 1 \mod 61$   
To compute the order of an element x, we simply have to find the lowest power n, where $x^n \equiv 1 \mod p$ (note that n has to be a divisor of p-1). In our case we find that $15^{15} \equiv 1 \mod 61$ and therefore order of 15 is 15.  
Note that H has 20 elements since the order of 8 is 20. To find subgroups of H, you have to find subgroups of order of divisors of 20 (2,4,5,10) and therefore simply solve the equations $x^y \equiv 1 \mod 61$, where $y \in \{2,4,5,10\}$. To find a subgroup with just 2 elements we can take $\langle 60 \rangle$, which only contains the elements 60 and 1. For a subgroup with 4 elements we can take $\langle 50 \rangle$ or $\langle 11 \rangle$, which contain the elements 50,60,11,1.
A: Hints:


*

*For the inverse of $53$ mod $61$, you have to find a Bézout's relation between $53$ and $61$: $53 u+61 v=1$. The inverse is $u$, and you should find $38$. The coefficients are found through the extended Euclidean algorithm.

*The order of $15$ is a divisor of $60$, i.e. is is one of $\{1,2,3,4,5,6,10,15,20,30,60\}$. You only have to test these exponents, using for the greatest exponents. the fast exponentiation algorithm.

*You should find with the same method $8$ has order $20$. Hence the (cyclic) subgroup $\langle8\rangle$ is isomorphic to $\mathbf Z/20\mathbf Z$, and an element $8^k$ generates a subgroup of order $\dfrac{20}{\gcd(20,k)}$, so all you have to do is choosing an exponent $k\in(1,20)$, not coprime to $20$.

A: For the first question, you want to use Euclid's algorithm to find an expression of the form $53a + 61b = 1$, i.e. $53a \equiv 1 \pmod {61}$ Then $a$ is the inverse to 53.
For the second question, you need to find the smallest $n$ such that $15^n \equiv 1 \pmod {61}$, so you would just keep multiplying by 15 and reducing mod 61 until you get to 1. (Note the reducing is important! Otherwise you might have to multiply really big numbers by 15 after a couple of steps.)
For the third question, have you calculated which elements are in $H$? If you do, then you should be able to work out the subgroup generated by each element, and hopefully find two which are different!
A: 
I have no knowledge of number theory and the tutor did not cover it well enough, and I am starting to learn it slowly

The best method then is to formalize what has been covered in the lessons:
First, we must know what is the order of $G$. The notation for that is $|G|$ or $|\mathbb{(Z/61\mathbb{Z})^x}|$. The order gives you the amount of numbers coprime with the modulus. This is calculated using Euler's Totient function.
Since $61$ is prime then all numbers below are coprime with it, thus $|G| = \varphi(61) = 61-1 = 60$. This is important since if the modulus is composite (product of primes) the order won't be $p-1$.
Now let's proceed to solve the first question:

Find the inverse element of 53 in $G$.

There's a method for calculating modular multiplicative inverses using Euler's Totient.
Inverses satisfy $1\equiv ab \pmod{p}$. For calculating them we just apply the theorem linked above:
$1\equiv 53b \pmod{61} \Rightarrow b\equiv 53^{\varphi(61)-1} \pmod{61} \Rightarrow 44\equiv 53^{59} \pmod{61}$.
You can check that $1\equiv 53\cdot44 \pmod{61}$ which is correct.

Compute the order of the element 15 in G.

Each element of the group $G$ has a multiplicative order denoted by $Ord_{p}(a)$ and this means "the order of element $a$ in $p$. An element of G can have multiplicative order equal to the order of G or equal to a divisor of the order of G (Lagrange Theorem).
So you now can think about
$Ord_{61}(15) = |G| = \varphi(61) = 60$ or $Ord_{61}(15) = d$ and $d|\varphi(p) \Rightarrow d|61$
Factors of $|G|=60$ are $30\cdot20=2^2\cdot3\cdot5$
Then we find that $15|60$ and $1\equiv 15^{15} \pmod{61}$. So $Ord_{61}(15)=15$
With all the theory I've shown to you here, I left the last problem to you to encourage your learning. It's been solved by other member, but with all the concepts you can now understand the underlying math.
