Blum integer

In particular, this implies that squaring is a permutation on QR if n is a generalized Blum integer. 

A special class of Blum integers is that of the following Williams integers, named after [WillSO] ... 

Sometimes, primes in certain congruence classes are needed, e.g., p = 3 mod 4 for Blum integers. For such cases, Dirichlet s prime-number theorem states that in a certain sense, primes are equally distributed over the possible congruence classes Given any modulus v, there are roughly equally many primes congruent mod v for all 6 Zy. If denotes the number of primes in the set 1, that... 

All the functions presented in this section are based on the squaring function modulo n, which is a permutation on QR if n is a generalized Blum integer (see Section 8.1.3). Before these functions are defined, two generalizations are made ... 

Some properties also hold if n is not a generalized Blum integer. Thus one can sometimes omit a zero-knowledge proof (see the end of Section 8.1.3) and use a more efficient local verification algorithm. Hence most definitions are presented for more general integers n. 

For the special case where is a generalized Blum integer, it is shown that/o and/i are permutations, and Lemma 8.6 is exploited. 

As promised, for generalized Blum integers (where squaring was a permutation on QRn) squaring will be shown to be a permutation on RQR , too. Thus it is now... 

The first consequence was not made a part of the lemma because the same result for more general n is Lemma 8.17. In contrast, the second consequence is special to generalized Blum integers. 

As far as number-theoretic properties are concerned, one could permit generalized Williams integers, similar to generalized Blum integers, of the form p qK However, in a factoring assumption, large exponents s and t would mean small prime factors if n is always of approximately the same length, and numbers with small prime factors are easier to factor. 

Blum integers and Williams integers are often used, too. Because of Dirichlet s prime-number theorem, asymptotically about half of all prime numbers are congruent to 3 mod 4, and among these, about half are congruent to 3 mod 8. Hence the factoring assumption made above is a consequence of one for arbitrary numbers with two prime factors. 

Claw-intractable permutation pairs were introduced in [G0MR88]. This subsection contains a strong and a weak version of the definition, now without trap-doors. It may be helpful to know that the weak version will be used in the factoring case if one does not want to use a zero-knowledge proof, and thus the modulus n is not necessarily a generalized Blum integer. 

This statement will be used in the factoring case when n is not a generalized Blum integer In that case, the bundling property can be proved in a different way. 

The constructions in Section 8.2.3 had different properties depending on whether n was a generalized Blum integer or any element of 4N -1- 1. Thus two different families of good keys. Good and Good weak are provided they lead to a strong and a weak claw-intractable family of permutation pairs, respectively. 

In the scheme with zero-knowledge proof Local verification that Tis correct and M2 2k, and the zero-knowledge proof scheme from [GrPe88] with the modifications sketched in Section 8.1.3, Recognizing Generalized Blum Integers , are combined. 

---