7
$\begingroup$

How many unique elements are generated from the following equation?

$$i = (g^x \bmod p) \bmod n $$

where:

  • $g$ has order $q$
  • $q$ and $p$ are prime numbers
  • $q\mathop{|}p-1$
  • $n$ is integer number more than 2 (could be even or odd number)

In part $g^x \bmod p$, it will generate $q$ unique numbers. But I am getting confused when the value is modulus-ed by $n$. Can someone help me?

$\endgroup$
  • 2
    $\begingroup$ For anybody not realizing this: This is the equation in DSA for $r$. $\endgroup$ – SEJPM Dec 13 '16 at 22:48
  • 1
    $\begingroup$ This is not the DSA equation. It becomes the DSA equation if $n=q$, but $n$ in the question is defined as an integer $>2$. Is the question as it is correct ? Or $n$ should be replaced by $q$ ? $\endgroup$ – Ruggero Dec 14 '16 at 10:41
  • $\begingroup$ if $n>p$ then you will have $q$ members again (I supposed, you mean that $g$ has order $q$ in the group ${\bf Z}_p^{*})$ $\endgroup$ – 111 Dec 14 '16 at 13:41
  • $\begingroup$ "modulus-ed" ... I don't think this new verb is going to make it :) Em, wouldn't this be identical to the overall density of primes somehow? $\endgroup$ – Maarten Bodewes Dec 14 '16 at 23:54
1
$\begingroup$

If $n > p$, then this will yield $q$ distinct results, since $g^x$ takes on exactly $q$ distinct values all below $p < n$ and ‘modulusing’ by $n$ has no effect in that case. This is the largest number of values it can take on, no matter what $n$ and $p$ are.

Suppose $q = 2$ and $n = g < p$. Then there are two distinct values of $g^x$, namely 1 and $g$, and two distinct values of $(g^x \bmod p) \bmod n$, namely 1 and 0. This is the smallest number of distinct values it can take on, no matter what any of the parameters are.

It can also take on intermediate numbers of values. For example, with $g = 2, p = 17, n = 13$, we have $q = \operatorname{ord}(g) = 8$, and $(g^x \bmod p) \bmod n \in \{0,1,2,3,4,8,9\}$, which has 7 possibilities, which lies between $2$ and $q$.

It's possible there is some nice formula relating $p$, $n$, $q$, and the cardinality of $\{(g^x \bmod p) \bmod n \mathrel| x \in \mathbb Z\}$, but it's not obvious to the tiny brain in this feathery skull—which is spending more brain cycles wondering: Why do you want to know the number of possible values this can take on? It is not actually the formula for $r$ in DSA, unless $n = q$.

On the other hand, if $n = q$, one might be wondering about the security of DSA. Curiously, if one follows the references, what appears to be the standard reference for reduction of DSA security to discrete log security has only this to say on the subject:

Indeed, it is very unlikely that the $“x \mapsto (g^x \bmod p) \bmod q”$ map has $(\log q)$-multi-collision.

(§6.1 ‘DSA–II Variant’, p. 289)

Here ‘$(\log q)$-multi-collision’ means a set of about $\log q$ (exactly which integer near that real number is not clear) elements sharing a common image under that map; the paper demonstrates a reduction of DSA forgery to calculation of discrete logarithms under the model of the message hash function as a random oracle and under the assumption that the map $x \mapsto (g^x \bmod p) \bmod q$ is $(\log q)$-multi-collision-free. If, indeed, it is $(\log q)$-multi-collision-free, then since there are $q$ possible inputs in the domain and $q$ possible outputs in the codomain, there are at least $q/\log q$ possible values of $(g^x \bmod p) \bmod q$.

Thus, I'm afraid I must leave it as an exercise for the reader to trawl the number theory literature for wisdom on the question of the cardinality of the image of $x \mapsto (g^x \bmod p) \bmod q$, since the field of cryptography seems to lack an answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.