Williams Integers

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

The first assumption is that factoring large integers is infeasible. Only Williams integers will be needed, i.e., those with exactly two prime factors p and q where p = 3 mod 8 and q = 7 mod 8. More precisely, the following assumption from [G0MR88] is used. 

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. 

Thus it has been shown that the following algorithm F factors Williams integers with the same probability as A finds claws On input n, compute k as rinl2/2l and call A( l , n). Whenever the output is a pair (x, x ), output p = gcd(w, x + 2x ). ... 

Key generation gerr. On input 1 , call geny n V ) to generate a Williams integer n, and choose an element y of RQR randomly. Output... 

It is important to describe each crystal face in a numerical way if data on different crystals or from different laboratories are to be compared. The method used to describe crystal faces is derived from the Law of Rational Indices, proposed by Haiiy and Arnould Carangeot. This Law states that each face of a crystal may be described, by reference to its intercepts on three noncollinear axes, by three small whole numbers (that is, by three rational indices)/ From this law, William Whewell introduced a specific way of designating crystal faces by such indices, and William Hallowes Miller popularized it. The integers that characterize crystal faces are called Miller indices h, k, and 1. When this method is used to describe crystal faces, it is rare to find h, k, or / larger than 6, even in crystals with complicated shapes. An example of the buildup of unit cells to give crystals with different faces is shown in Figure 2.11. 

Prout, William (1785-1850) English chemist, physician, and natural theologian in 1815 he hypothesized that the atomic weight of every element is an integer multiple of that of hydrogen, suggesting that the hydrogen atom is the only truly fundamental particle. 

---