Talk:Blum integer

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics ??? This article has not yet received a rating on the project's priority scale.

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

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