Hot answers tagged

2

Your solution to part 1) is ok. A zero $a$ of $x^3-x^2+1$ will, indeed, give you a normal basis $\mathcal{B}=\{a,a^9, a^{81}=a^3\}$. I'm relatively sure that in part 2) you are asked to do the following. Let $$z=c_1a+c_2a^9+c_3a^{81}$$ be an arbitrary element of $GF(3^6)$ - written using the basis $\mathcal{B}$, so the coefficients $c_1,c_2,c_3\in GF(9)$ ...


2

There are different ways to find out. For such a big number we need a method without having to factorize it. One way to start, is to prove that N is composite. Therefore we choose a strong primality-test like the one of Miller–Rabin,Solovay–Strassen or the newer APRCL-test. If this test returns false, the compositeness of N is proven. Next choose a test ...


2

If you are using cyclic notation, $\pi=(1234)$. And $\pi^{-1}=(4321)$, which is just $\pi$ written backwards. But in the matrix notation that you are using, you form the inverse by exchanging the top and bottom rows. So $$\pi^{-1} = \begin{pmatrix}2&3&4&1\\1&2&3&4\end{pmatrix}$$ which, after rearranging the columns, is the same as ...


1

No. The inverse permutation is the one that puts everything back where it came from ($\pi(1) = 2$, so $\pi^{-1}(2) = 1$, and so on), which means that you get the inverse by swapping the two rows: $$ \pi^{-1} = \begin{pmatrix}2&3&4&1\\1&2&3&4\end{pmatrix} $$ Usually one also sorts the columns for easy readability, so that we get $$ ...


1

The girth for directed graphs is usually defined as the directed girth, that is, the minimum length of a directed cycle (or $\infty$ if no directed cycles exist). For instance, see Jørgen Bang-Jensen and Gregory Gutin, Digraphs: Theory, Algorithms and Applications (Second Edition), Springer Monographs in Mathematics. (The definition is given in chapter 1. ...


1

This is a simple RSA problem: $d$ is the inverse of $e$ modulo $\phi(n)$, where $n = pq$ So apply the extended Euclidean algorithm (see here) to $e$ and $\phi(n)$. You get integers $k,l \in \mathbb{Z}$ with $ke + l\phi(n) = 1$. Then $k$ is easily seen to be the required inverse, i.e. $d$ (just take the previous equation modulo $\phi(n)$ where the right ...


1

Yes, if there is no known plaintext, and just a single cipher text $m^\ast$, you do need $k$ even if $p$ is known to everyone. In this case the plaintexts are numbers of a special form (because they're built up from smaller alphabet numbers in your case), so there might be a weakness there, and there are some other issues, but essentially yes. But as said, ...


1

The rule is already given here: Let $\begin{matrix}\blacksquare\square\\\square\blacksquare\end{matrix}$ be pattern 1 and $\begin{matrix}\square\blacksquare\\\blacksquare\square\end{matrix}$ be pattern 2. Notice that they add up to a black square, and when added to themselves, they create a half-black square. If the source pixel is black: For half of ...


1

The correctness of the cryptosystem (in the sense that decryption is inverse to encryption) depends on $$m^{k\phi(n)+1}\equiv m\pmod n$$ for all $m$. Euler's theorem says that this is the case when $m$ and $n$ are coprime -- which is not enough here -- but if $n$ is known to be square-free it is actually the case for all $m$. Constructing $n$ as the ...


1

Let's see what the right question is. The basic proposition is this. Suppose, given $y$, $b$ and prime $p$, you want to find $x$ such that $b^x \equiv y \mod p$, where $b$ is a primitive root mod $p$. Suppose $p-1 = cd$ with $c$ and $d$ coprime. Then $y^c \equiv b^{xc} \equiv (b^c)^x \mod p$, where $b^c$ is a $d$'th root of $1$ mod $p$. This will ...


1

Chinese remainder theorem says: if $a$ and $b$ are co-prime and $pa + qb = 1$ and $x\equiv n(\mod a)\\ x\equiv m(\mod b)$ then $x\equiv pam+qbn (\mod ab)$ $19*64=1216\\ 27*19-8*64 = 1\\ x\equiv 40(\mod 64)\\ x\equiv 13(\mod 19)\\ x\equiv 13*(-8)*64+40*27*19 (\mod 1216)\\ $


1

Let $$a=q_an+r_a$$ $$b=q_bn+r_b$$ for quotients $q_a,q_b$ and remainders $0\le r_a,r_b<n$ of $a,b$ modulo $n$. Then $$\begin{align} a+b&=(q_a+q_b)n+(r_a+r_b)\\ &=\left(q_a+q_b+\delta\right)n +\left(r_a+r_b-\delta n\right) \end{align}$$ for $$\delta=\left\lfloor\frac{r_a+r_b}{n}\right\rfloor$$ where $\lfloor x\rfloor$ is the greatest integer (less ...



Only top voted, non community-wiki answers of a minimum length are eligible