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

Alar Leibak

doi:10.3934/amc.2021029

Article Contents

2023, Volume 17, Issue 4: 920-927. Doi: 10.3934/amc.2021029

This issue Previous Article New quantum codes from skew constacyclic codes Next Article Partitioned difference families: The storm has not yet passed

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

Alar Leibak

Institute of Cybernetics, Tallinn University of Technology, Estonia

Received: December 2020

Revised: June 2021

Early access: August 2021

Published: August 2023

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

Related Papers

Cited by

References

[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.