3 votes
Accepted

How to prove that $f(x)=x^3 \pmod{pq}$ is bijective for any non negative integer $x<pq$ where 3 is not a factor of $p-1$ and $q-1$?

Well you might begin by observing that if $x^3\equiv y^3$ then $x^3-y^3=(x-y)(x^2+xy+y^2)\equiv 0$ Then $pq$ cannot be a factor of $x-y$ because $x$ and $y$ are too small by hypothesis. So this means ...
  • 97.1k
2 votes

How to prove that $f(x)=x^3 \pmod{pq}$ is bijective for any non negative integer $x<pq$ where 3 is not a factor of $p-1$ and $q-1$?

It is relatively elementary to prove that $f$ is bijective on the four following (invariant) subsets, which form a partition of $\mathbb Z/(pq\mathbb Z):$ $$\{0\},\{(pk)\bmod{pq}:q\nmid k\},\{(qk)\...
  • 2,929
2 votes

encrypt problem in Discrete mathematics

For each $(a,b,c)$ where $a \in {[1000,2000]}, b \in {[2000,3000]}, c \in {[3000,4000]}$ you can check the possibility via: (1) $m = a^e \text{ (mod $p$)} \oplus b^e \text{ (mod $p$)} \oplus c^e \text{...
1 vote
Accepted

Deciphering XOR-encrypted text with frequency analysis.

One simple approach is to ignore the word structure and assume the letters are drawn randomly with a probability distribution of the letters in English. There are only $32$ choices for $s$. Try each ...
1 vote

I am trying to understand whether this equation has a solution using either Legendre's or Jacobi's symbols

You can show that it has no solutions using the Legendre symbol: $\begin{eqnarray}\left( \frac{1097}{65539} \right ) & = & \left( \frac{65539}{1097} \right) \times (-1)^{\frac{1097-1}{2}\frac{...
  • 15.4k
1 vote

How to prove this modular multiplication property to be true?

Given: $$A \bmod n = a => A = n * k_A + a$$ and $$B \bmod n = b => B = n * k_B + b$$ then: $$A * B = (n * k_A + a) * (n * k_B + b)$$ $$A * B = n^{2} * k_A * k_B + n * k_A * b + n * k_B * a + a*b ...
  • 111

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