TY - JOUR

T1 - VSH and multiplicative modular relations between small primes with polynomial exponents

AU - Blake, Ian F.

AU - Luca, Florian

AU - Shparlinski, Igor E.

PY - 2014/6

Y1 - 2014/6

N2 - We study the frequency of the positive integers n that are products of two primes of the same order of magnitude and such that the congruence Π i = 1 k p i f i (n) ≡ 1 (mod n) holds with some fixed nonzero polynomials f 1 (X), ..., f k (X) Z [ X ], where p i denotes the i th prime. The question is motivated by collision finding in the so-called Very Smooth Hash function, introduced by Contini et al. (Lecture notes in computer science, vol. 4004. Springer, Berlin, pp 165-182, 2006).

AB - We study the frequency of the positive integers n that are products of two primes of the same order of magnitude and such that the congruence Π i = 1 k p i f i (n) ≡ 1 (mod n) holds with some fixed nonzero polynomials f 1 (X), ..., f k (X) Z [ X ], where p i denotes the i th prime. The question is motivated by collision finding in the so-called Very Smooth Hash function, introduced by Contini et al. (Lecture notes in computer science, vol. 4004. Springer, Berlin, pp 165-182, 2006).

KW - Hash function

KW - Multiplicative relations

KW - Polynomials

KW - Primes

UR - http://www.scopus.com/inward/record.url?scp=84903382888&partnerID=8YFLogxK

U2 - 10.1007/s00200-014-0219-2

DO - 10.1007/s00200-014-0219-2

M3 - Article

AN - SCOPUS:84903382888

VL - 25

SP - 181

EP - 188

JO - Applicable Algebra in Engineering, Communications and Computing

JF - Applicable Algebra in Engineering, Communications and Computing

SN - 0938-1279

IS - 3

ER -