VSH and multiplicative modular relations between small primes with polynomial exponents

Ian F. Blake; Florian Luca; Igor E. Shparlinski

doi:10.1007/s00200-014-0219-2

VSH and multiplicative modular relations between small primes with polynomial exponents

Ian F. Blake, Florian Luca, Igor E. Shparlinski^*

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English
Pages (from-to)	181-188
Number of pages	8
Journal	Applicable Algebra in Engineering, Communications and Computing
Volume	25
Issue number	3
DOIs	https://doi.org/10.1007/s00200-014-0219-2
Publication status	Published - Jun 2014

Keywords

Hash function
Multiplicative relations
Polynomials
Primes

Access to Document

10.1007/s00200-014-0219-2

Cite this

@article{169468d50a1c415799f58baf9c0e5d6b,

title = "VSH and multiplicative modular relations between small primes with polynomial exponents",

abstract = "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).",

keywords = "Hash function, Multiplicative relations, Polynomials, Primes",

author = "Blake, \{Ian F.\} and Florian Luca and Shparlinski, \{Igor E.\}",

year = "2014",

month = jun,

doi = "10.1007/s00200-014-0219-2",

language = "English",

volume = "25",

pages = "181--188",

journal = "Applicable Algebra in Engineering, Communications and Computing",

issn = "0938-1279",

publisher = "Springer, Springer Nature",

number = "3",

}

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 - https://www.scopus.com/pages/publications/84903382888

U2 - 10.1007/s00200-014-0219-2

DO - 10.1007/s00200-014-0219-2

M3 - Article

AN - SCOPUS:84903382888

SN - 0938-1279

VL - 25

SP - 181

EP - 188

JO - Applicable Algebra in Engineering, Communications and Computing

JF - Applicable Algebra in Engineering, Communications and Computing

IS - 3

ER -

VSH and multiplicative modular relations between small primes with polynomial exponents

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this