Sundaram’s Sieve
Sundaram’s sieve, like the Sieve of Eratosthenes, finds prime numbers. It relies wholly on a easily constructable symmetric table. The first row (and column), is an arithmetic sequence, starting with a = 4 with a step of d = 3. The remainder of the rows are also arithmetic sequences with their a’s determined by the original sequence. For the second row, now, use d = 5 as the step, and use d = 7 for the step for the third row. Continue this pattern, letting each row’s d be the next highest odd integer than for the row above. This creates the following table:
4 |
7 |
10 |
13 |
16 |
… |
7 |
12 |
17 |
22 |
27 |
… |
10 |
17 |
24 |
31 |
38 |
… |
13 |
22 |
31 |
40 |
49 |
… |
16 |
27 |
38 |
49 |
60 |
… |
_{} |
_{} |
_{} |
_{} |
_{} |
_{} |
Let N > 2 be any natural number. Then N occurs on the table if and only if 2N + 1 is composite. There are two proofs of this pivotal statement; one is via a companion chart, the second via elementary algebra. Both proofs will be discussed.
The Table Proof
We construct a companion table to the original one, where each entry, N, in the original table is replaced by 2N +1 in the companion table. Thus we have
9 |
15 |
21 |
27 |
33 |
… |
15 |
25 |
35 |
45 |
55 |
… |
21 |
35 |
49 |
63 |
77 |
… |
27 |
45 |
63 |
81 |
99 |
… |
33 |
55 |
77 |
99 |
121 |
… |
_{} |
_{} |
_{} |
_{} |
_{} |
_{} |
This table shows all composites x = pq, where p and q are odd natural numbers. The only numbers not on the table are either even or prime. Since the only even prime, 2, has been neatly avoided by the assumption that N > 2, any odd number not on this companion table must be prime. Therefore if N appears on the original table, then 2N +1 is a composite of two odd numbers, and if an odd number 2N+1 does not appear on the companion table (and thus is prime), then N does not appear on the original table.
The Algebraic Proof
Let S_{m,n} represent the entry in the m^{th} column and n^{th}_{ }row. It is easy to confirm that _{}. Suppose that the natural number N > 2 occurs on the table. Then there exist natural numbers m and n such that _{}. Consider 2N + 1.
_{}
Therefore 2N + 1 is composite.
Conversely, suppose 2N +1 = pq for natural numbers p and q, both greater than 1. 2N +1 is odd, so p and q must be odd. Let m and n be natural numbers such that _{} and _{}.
_{}
Therefore, _{}, so N is in the chart.
Connections to Cryptography
Sundaram’s sieve is tied to primality testing and factoring odd numbers. It is not, however, practical to use for the thousand-digit numbers typical in modern cryptography and cryptanalysis. The problem lies in the difficulty to predict whether or not a large number lies in the table without direct computation.
References:
Ogilvy, C.
Stanley and John T. Anderson. Excursions in Number Theory. Oxford University Press,
Inc.,
Andrew Baxter