# Tag Info

## New answers tagged number-theory

2

We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$. This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}\mod p$ is, you can just plug that value in and do computations like you'd expect. Note that $3^{-1}\mod p$ means the element $u\in(\mathbb{Z}/p\mathbb{Z})^\... 2 For the function$F(x) = ax \bmod n$, where the inputs are limited to the range$[0, n)$, this function will be a bijection (that is, no collisions) if and only if$a$and$n$are relatively prime. Here is a proof in the direction you're asking about: Suppose there exists a collision, that is, we have a pair$x, y$with$0 \le x < y < n$where$F(x) =...

1

For this specific example, which doesn't make for a really useful hash function given that it isn't compressing, it's rather easy to prove the presence or absence of collisions. So, assume $$H_{a,n}(x)=a\cdot x\bmod n$$ is the hash function we are looking it. Then if $H_{a,n}(x)\cdot a^{-1}\bmod n$ has a unique value, then there is exactly one input for ...

4

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance. In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\... 1 The prototypical example of a group in cryptography is a cyclic group. You can write this in a variety of ways, so I'll go through a few quickly. Additively: Consider the group$\mathbb{Z}/n\mathbb{Z}$under$+$. This forms a group, and it's a cyclic group generated by$\langle 1\rangle$(subject to the relation that$n\cdot 1 = 0\$). Note that the "...

Top 50 recent answers are included