Talk:Blum integer

Name

Which "Blum" are Blum Integers named after? Meekohi 15:49, 6 November 2005 (UTC)[reply]

Manuel Blum, I believe. I should track down the relevant paper.

If I remember correctly, his fair exchange paper around 1982 had a long section on this topic.

--Clausen 19:00, 8 November 2005 (UTC)[reply]

Add remark

It is imperative to add the remark "and coprime to n" in the section on the properties. The article on quadratic residues currently reads:

For this reason some authors (e.g., Ireland & Rosen 1990, p. 50) add to the definition that a quadratic residue a must not only be a square but must also be relatively prime to the modulus n. (a is coprime to n if and only if a² is coprime to n.)

Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.

However, if this more general definition of quadratic residues is taken (ie. dropping the coprime requirement), then the statements in the properties section no longer hold. In particular: Consider the Blum number n=33. In the more general definition without coprimality, 9 is a quadratic residue but it only has two roots 3 and 30.

The history doesn't reference the original material to suggest when Blum integers should be used in RSA, then the paper to show that it no longer matters. It only links to the seives that can supposedly factor Blum integers. The seives mentioned came out a few years after RSA (RSA is 1977, the MPQS is 1981). That gives only 4 years for the statement in the history section to be true based on the evidence provided. Salindor (talk) 14:55, 18 November 2018 (UTC)[reply]