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
Sm,n represent the entry in the mth
column and nth 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