Article Contents
Article Contents

# On the number of factorizations of $t$ mod $N$ and the probability distribution of Diffie-Hellman secret keys for many users

• We study the number $R_n(t,N)$ of tuplets $(x_1,\ldots, x_n)$ of congruence classes modulo $N$ such that

$\begin{equation*} x_1\cdots x_n \equiv t \pmod{N}. \end{equation*}$

As a result, we derive a recurrence for $R_n(t,N)$ and prove some multiplicative properties of $R_n(t,N)$. Furthermore, we apply the result to study the probability distribution of Diffie-Hellman keys used in multiparty communication. We show that this probability distribution is not uniform.

Mathematics Subject Classification: Primary: 11A07, 11A25, 11A51; Secondary: 11B37.

 Citation:

•  [1] J. B. Friedlander, Uniform distribution, exponential sums, and cryptography, Equidistributions in Number Theory, An Introduction, Nato Science Series Ⅱ. Mathematics, Physics and Chemistry, Vol. 237, Springer, Dordrecht, 2007, 29–57. doi: 10.1007/978-1-4020-5404-4_3. [2] P. H. van der Kamp, On the Fourier transform of the greatest common divisor, INTEGERS, 13 (2013), 1-16. [3] D. Neuenschwander, Probabilistic and Statistical Methods in Cryptology: An Introduction by Selected Topics, Lecture Notes in Computer Science, Vol. 3028, Springer-Verlag, Berlin, 2004. doi: 10.1007/b97045. [4] R. W. K. Odoni, V. Varadharajan and P. W. Sanders, Public key distribution in matrix rings, Electronic Letters, 20 (1984), 386-387.  doi: 10.1049/el:19840267. [5] H. E. Rose,  A Course in Number Theory, 2 edition, Oxford University Press, New York, 1994. [6] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., 6 (1962), 64-94. [7] I. Shparlinski, Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, 2003. doi: 10.1007/978-3-0348-8037-4. [8] C. P. Waldvogel and J. L. Massey, The probability distribution of the Diffie-Hellmann key, Advances in Cryptology-AUSCRYPT '92, Lecture Notes in Comp. Sci., Vol. 718, Springer, Berlin, 1993,492–504. doi: 10.1007/3-540-57220-1_87.

• on this site

/