A hypothetical TWIRL device to factor large integers was described in 2003 by Shamir and Tromer. This page experiments in a style of design by describing the semantics of the messages that move from box to box within the system. The mathematical ideas stem mainly from the Shamir-Tromer paper. I think that there are no original contributions to factoring here but perhaps this design style will shake out some new ideas for hardware organization. There is here a little overlap with a note that I wrote several years ago on an earlier hardware proposal by Shamir.

Some of the math ideas go back to about 1950 and I reminisce here. I described some of the math here.

I describe the meaning of a signal that flows between two boxes in the larger machine. Perhaps there are millions of such messages each clock cycle within the machine, each traversing its own bus (set of wires). By “factory parameter” we mean a value associated with some individual piece of hardware whose actual value is fixed upon manufacture. Text in italics is redundant.

All the primes below some limit B ⋍ 3⋅10¹⁰ are divided into a nested sequence of sets (the prime tree) thus:
S₀ is the set of all primes less than B;
S_n = S_4n+1 ⋃ S_4n+2 ⋃ S_4n+3 ⋃ S_4n+4.
S_4n+1, S_4n+2, S_4n+3 and S_4n+4 are pairwise disjoint. The sets are fixed at the factory.

There are many arithmetic sequences of interest. A_i = {n⋅p_i + r_i|n∈Z}. Collisions are sought among these sequences. The p_i’s are primes less than B. There are typically two sequences per prime. The r_i’s are system configuration parameters which are constant for long durations; they depend on the number being factored.

The meaning of a message

For each bus there are integers J, j and m such that for every message on that bus n = j mod 2^J and s = S_m. J, j and m are factory parameters. Each bus thus has a collection of factory parameters (J, j, m). On a particular bus the only values that vary from one message to the next is n and k. The actual message caries only information about n and k.

On a particular bus successive messages are for increasing n. When the log value is zero the message may be omitted (and usually is). The messages on a particular bus are for some factory fixed set of primes. The messages on a particular bus are for some factory fixed number modulo 2^J−2 Design goal: Most buses carry such a message each cycle but there will be bubbles on the buses.

Buses carry messages in only one direction. The n’s of successive messages on a bus are strictly monotonic. Most buses have a box as described below at either end.

The Box

A box takes input from four buses. (Four is a design parameter; I guess for now.) For a particular box the factory parameters of the input buses are respectively (J, j, 4m+1), (J, j, 4m+2), (J, j, 4m+3), (J, j, 4m+4). The box emits messages whose prime range is the combined ranges of the inputs. A box sends output messages via four buses whose factory parameters are (J−2, j, m), (J−2, j+2^J−4, m), (J−2, j+2(2^J−4), m), (J−2, j+3(2^J−4), m). The boxes mainly recode and route the messages and occasionally merge two messages for the same n while adding their k’s. Otherwise the meaning of a message is unchanged as it traverses a box.

Data flow from boxes each specializing in different small ranges of primes to boxes specializing in sets of numbers partitioned by their particular residue modulo some power of 2.

Boxes also retain a brief history of the sources of messages so as to determine the ancestry of messages with large k. Access to this history is not described yet. The box keeps a record of recent decisions sufficient to recall how each message was produced while effects of that message remain in the system.

While the system has a shared clock there will be a latency due to buffers at the input to boxes that accommodate bursty traffic. This may result in a skew of several hundred cycles. When a valuable result is found we stop the system clock and probe the memories of the relevant boxes to identify the contributors. I don't know how many results are wanted and this stopping may be too expensive.

As a message arrives at a box it is placed in one of 4 buffers depending on bits J and J+1 of n. Each such buffer may have up to 4 messages placed there in each cycle.

Coding the Messages

The busses are a substantial part of the system and a bus with parameters (J, j, m) omits wires for the low J bits of n, and some high bits too that the two concerned boxes agree on. When the high order expressed bit of n in successive messages changes from 1 to 0 an overflow is noted by the recipient box who keeps the omitted high bits of n. The sender is charged with assuring that all such overflows are expressed on the bus by inserting messages with k=0 which serve as no-ops except to cause the recipient to note the overflow. These are rare. (These ideas are isomorphic with ‘key compression’ ideas used in some sorted tree data structures used in data bases.)

Shamir’s paper segregates primes into three size categories. I suspect that this is necessary.

I feel an itch to write some code to determine some of these parameters more closely.