Historical Document · 2003
US Patent 6,603,445 B1 — Factoring Large Numbers with Optoelectronic Devices (TWINKLE)
Patent for TWINKLE, the optoelectronic factoring sieve; the source of its figures.
Historical Document · 2003
Patent for TWINKLE, the optoelectronic factoring sieve; the source of its figures.
USOO6603445B1 (12) United States Patent (10) Patent No.: Shamir US 6,603,445 B1 (45) Date of Patent: (54) METHOD AND APPARATUS FOR 4.837,822 A * 6/1989 Crosley et al. ............... 380/23 FACTORING LARGE NUMBERS WITH OPTOELECTRONIC DEVICES 5,142,579 A 8/1992 Anderson .................... 380/30 5,295,188 A 3/1994 Wilson ........................ 380/30 6,091819 A * 7/2000 Venkatesan et al. .......... 380/28 6,134.325 A * 10/2000 Vanstone et al. ............. 380/30 (75) Inventor: Adi Shamir, Rehovot (IL) 6,141,420 A * 10/2000 Vanstone ..................... 380/30 6,266,771 B1 * 7/2001 Bellare et al. .............. 713/176 (73) Assignee: Yeda Research and Development Co. 6,298,135 B1 * 10/2001 Messerges ..................... 380/1 Ltd., Rehovot (IL) (*) Notice: Aug. 5, 2003 6,343,280 B2 Subject to any disclaimer, the term of this patent is extended or adjusted under 35 U.S.C. 154(b) by 0 days. 1/2002 Clark .......................... 705/55 * cited by examiner Primary Examiner Richard Hjerpe ASSistant Examiner Abbas Abdulselam (21) Appl. No.: 09/475,920 (22) Filed: Dec. 30, 1999 (51) Int. Cl. .................................................. G09G 3/04 (74) Attorney, Agent, or Firm Martin Fleit; Paul D. 345/46; 315/241 P; 250/2011; 250/2019; 250/586; 257/139.1; 257/141.1; 257/141.2; utilizes an optoelectronic device that has a wafer at one end that contains a plurality of LEDs. Each LED is associated (52) U.S. Cl. ............................. 345/43; 345/30, 345/44; 257/1413 (58) Field of Search .............................. 345/43, 44, 46; 380/30; 315/241 P; 250/586, 2011, 201.9; 257/139.1, 141.1, 1412, 141.3 (56) References Cited (57) ABSTRACT A method and apparatus for factoring large numbers which with at least one period p, and at least one delay d. A clock drives the plurality of LEDs responsive to clock cycles to flash for one clock cycle at times described by the processing pr+d, for reO. The light intensity flashed by the LEDs is controlled by a filter to be proportional to loga (p), and a photodetector positioned at the other end of the cylinder collects the light flashed by the LEDs. U.S. PATENT DOCUMENTS 4,519,046 A Bianco; Fleit Kain Gibbons Gutman & Bongini P.L. 5/1985 Cole .......................... 364/822 23 Claims, 3 Drawing Sheets LOAD WITH 40 P REGISTER A LOAD WITH D FEEDBACK LOAD U.S. Patent Aug. 5, 2003 -?--------- M+ A+ SBW|}}d M+ A+ (SQET) (ESWHLOIT)S US 6,603,445 B1 Sheet 1 of 3 A+ U.S. Patent Aug. 5, 2003 Sheet 2 of 3 US 6,603,445 B1 LOAD WITH 40 P REGISTER A LOAD WITH D 46 - REGISTER B FEEDBACK LOAD U.S. Patent Aug. 5, 2003 Sheet 3 of 3 CLOCKINGLED (28) US 6,603,445 B1 24 PHOTODETECTOR C7) C/) N-91 20 OPAQUE BLACKENED N7 SY 921 30 WAFER 32 CELL TRANSPARENT HERE FIG.5A 24 PHOTODETECTOR 60 LEDS US 6,603,445 B1 1 METHOD AND APPARATUS FOR FACTORING LARGE NUMBERS WITH OPTOELECTRONIC DEVICES 2 Further objects and advantages of the present invention will become readily apparent from the following detailed description of a preferred embodiment of the invention when taken with the appended drawings. BACKGROUND OF THE INVENTION BRIEF DESCRIPTION OF THE DRAWINGS FIGS. 1A and 1B are schematic graphical showings that compare conventional Sieving with optical Sieving accord ing to the present invention: the boxed operations are carried 1. Field of Invention The present invention relates to a method and apparatus for factoring large numbers with optoelectronic devices. 2. Description of the Prior Art The security of the RSA public key cryptosystem depends on the difficulty of factoring a large number n which is the product of two equal size primes p and q. This problem had out at the Same time Slice. FIG. 2 is a Schematic diagram in block form showing the organization of a single cell in an array according to the present invention. been thoroughly investigated (especially over the last 25 15 FIG. 3a is a Schematic diagram showing the Structure of years), and the last two breakthroughs were the development the optoelectronic device according to the present invention. of the Quadratic Sieve (QS) algorithm, see C. Pomerance, FIG. 3b is a schematic diagram like FIG. 3a showing a The quadratic Sieve factoring algorithm, Proceedings of variation. EUROCRYPT 84 (LNCS 209), 169-182, 1985, and the development of the Number Field Sieve (NFS) algorithm, DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT See A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The number fieldsieve, Vol. 1554 of Lecture Notes now to the drawings, the method and apparatus in Mathematics, 11-42, Springer Verlag, 1993. The asymp of Referring the present invention will now be described with respect totic time complexity of the QS algorithm and the asymp to a detailed preferred embodiment. Initially, there follows a totic time complexity of the NFS algorithm are different. For 25 discussion of the QS factoring algorithm. numbers with up to about 350 bits the QS algorithm is faster Given the RSA number n=pd, the QS algorithm tries to due to its simplicity, but for larger numbers the NFS algo construct two numbers y and Z, Such that, yzz (mod n) and rithm is faster due to its better asymptotic complexity. y =zf (mod n). Knowledge of Such a pair makes it easy to The complexity of the NFS algorithm grows fairly slowly factor n since gcd(y-Z, n) is either p or q. To find Suchy and with the binary size of n. The current record in factoring X, a large of Values y1, y2, . . . , y, are generated. large RSA keys is the factorization of a 512 bit number To computenumber each y, (mod n), one tries to factor it into a achieved in August 1999 by running the Number Field Sieve product of primes p, from a prime base B consisting of the on several hundred workstations for several months. If we k Smallest primes p=2, p=3,..., p. Numbersy, (mod n) denote by X the (barely possible) complexity of factoring a which have Such factorizations into ?lip, are called 512 bit number, the complexity of factoring numbers which 35 Smooth. If the number of Smooth modular Squares found in are 100 bits longer is about 40X, the complexity of factoring Such a way exceeds k, GauSS elimination can be used to find numbers with are 150 bits longer is about 220X, and the Subset of the Vectors (e1, e2, . . . , e) of the prime complexity of factoring numbers which are 200 bits longer amultiplicities which is linearly dependent modulo 2. When is about 1100X. Accordingly, the main problem confronting the corresponding y, (mod n) and their factorizations are researchers in this field is to improve the efficiency of 40 multiplied, an equation is obtained of the form: factoring. SUMMARY OF THE INVENTION i k (yi) = p. (mod n) The main object of the present invention is to provide a i=1 i=l method and apparatus that can increase the efficiency of the 45 QS or NFS algorithms by one to two orders of magnitude. The main practical Significance of Such an improvement is where all the bis (which define the subset) are 0's and 1's and all the c, s (which are the sums of the prime that it can make 512 bit numbers (which are the default multiplicities) are even numbers. The desired equation y=zf Setting today of most Internet browsers in e-commerce applications) relatively easy to factor. The technique of the 50 (mod n) can now be obtained by defining present invention is based on a very simple optoelectronic device which can analyse long Sequences of large integers, and determine which ones factor completely over a prime base consisting of the first k prime numbers for Some large k. y= 55 The present inventive method and apparatus is based on a novel optoelectronic device called TWINKLE (The Weiz mann INstitute Key Locating Engine). The manufacturing " y; . (mod n) i=1 k 3. c; 2 p; (mod n). i=l The key to the efficiency of the QS algorithm is the cost of these devices in full production is deemed to be a modest Sum. It can be combined with an algorithm, Such as, 60 generation of many Small modular Squares whose Smooth any Sieve-based factoring algorithm, and in particular it can neSS is easy to test. Considering the simplest case in which be used in both the QS and the NFS algorithms. It uses their the quadratic polynomial f(x)=(a+x) (mod n) where basic mathematical Structure and inherits their asymptotic complexity, but improves the practical efficiency of their Sieving Stage by a large constant factor. Since this is the most 65 time consuming part of these algorithms, a major improve by choosing y=a+i for i=1,2,..., m, then it is easy to See that for Small m the corresponding y=f(i) (mod n) are half ment in their total running time is obtained. US 6,603,445 B1 3 Size modular Squares which are much more likely to be Smooth numbers than random modular Squares. The Simplest way of testing the Smoothness of the values in Such a sequence is to perform trial division of each value in the Sequence by each prime in the basis. Since the f(i)'s are hundreds of bits long, this is very slow. The QS algorithm expresses all the generated f(1), . . . , f(m) in the non modular form f(i)=(a+i) -n (since m is p, from the basis B by Solving the quadratic modular equation (a+i)-n=0 (mod p). This is easy, since the modu lus p, is quite Small. In this respect, the issue of the Small), and determines which of these values are divisible by divisibility of f(i) by higher powers of p is ignored, since 4 top of the cylinder contains a photodetector 24 which measures the total amount of light emitted at any given moment by all the LEDs. The photodetector 24 alerts a connected PC (not shown) whenever this total exceeds a certain predetermined threshold. Such events are related to the detection of possibly Smooth numbers, and their precise timing is the only output of the TWINKLE device. Since these events are extremely rare, the PC can leisurely trans late the timing of each reported event to a candidate modular Square, Verify its Smoothness via trial division, and use it in a conventional implementation of the QS or NFS algorithms in order to factor the input n. The standard PC implementation of the sieving tech except for the Smallest primes in the basis this is extremely niques assigns modular Squares to array elements (using unlikely, and the powers of the first few primes can be added 15 Space) and loops over the primes (using time), see FIG. 1A. to the basis without Substantially increasing its size. The TWINKLE device assigns primes to LEDs (using The quadratic equation mod p, will have either Zero or two Space) and loops over the modular Squares (using time), Solutions d' and d". In the first case, it is deduced that none which reverses their roles. This is schematically described in it is deduced that f(i) will be divisible by p, if and only if i belongs to the union of the two arithmetic progressions pr+d, and pr+d, for reO. Each LED 22 is associated with Some period p, and delay d, and its only role is to light up for one clock cycle at times described by the arithmetic progression pr+d, for reO. To of the f(i)'s will be divisible by p, and in the second case, The smoothness test in the QS algorithm is based on an array A of m counters, where the i-th entry is associated with FIG. 1B. mimic the QS Sieving procedure, non-uniform LED inten Sities are used. In particular, the LED associated with prime f(i). The Sieving algorithm Zeroes all these counters, and 25 p, should generate light intensity proportional to log2(p) then loops over the primes in the basis. For each prime p, and for each one of its two arithmetic progressions (if they exist), the algorithm Scans the counter array, and adds the constant log2(p) to all the counters A (i) whose indices i belong to the arithmetic progression (there are about m/p, whenever it flashes, So that the total intensity measured by the photodetector 24 at time i will correspond to the binary Size of the largest Smooth divisor of the f(i), again, ignoring the issue of the divisibility of f(i) by higher powers of the primes. This can be achieved by using an array of LEDs 22 Such indices). At the end of this loop, the value of A(i) describes the (approximate) binary length of the largest divisor of f(i) which factors completely over the prime base of different sizes or with different resistances. However, a workstation, but can test the Smoothness of 100,000,000 the various LEDs based on their sorted list of measured modular squares over a prime base of 200,000 primes in less intensities. However, the QS and NFS factoring algorithms Simpler and more elegant Solution to the problem is to construct a uniform array of identical LEDs, to assign B. The algorithm then Scans the array, finds all the entries i Similar sized primes to neighbouring LEDs, and to cover the for which A(i) is close to the binary length of f(i), tests that 35 LED array with a transparent filter 27 with smoothly chang these f (i)'s are indeed Smooth by trial division, and uses ing gray levels. For example, primes can be assigned to them in order to factor n. LEDs in row major order and a filter 27, see FIG. 3a, used Typical large Scale factoring attacks with networks of which is dark gray at the top, and completely transparent at PC's may use m=100,000,000 and k=200,000. The array the bottom, or primes can be assigned to LEDS in Spiral requires 100 megabytes of RAM, and its counter can be 40 order and a filter used which is darkest at its center. Note that accessed at the Standard bus speed of 100 megahertz. Faster the dynamic range of gray levels one must use is quite cache memory is of little use, Since the Sieving proceSS limited, since the ratio of the logs of the largest and the accesses arithmetic progressions of addresses with huge Smallest primes in a typical basis does not exceed 24:1. jumps, which create continuous cache misses. Just Scanning Filter 27 is located immediately above the wafer 30 so that Such a huge array requires about one Second. Well optimized 45 light from each LED passes through the area of the filter implementations of the QS algorithm perform the Sieving in immediately above it. To increase the Sensitivity of the photodetector 24, it can 5 to 10 seconds, and find very few smooth numbers. They then choose a different quadratic polynomial f"(x), and be placed behind a large lense 26 which concentrates all the repeat the Sieving run (on the same machine, or on a different incoming light on its Small Surface area, i.e. the photode machine working in parallel). This phase stops when a total 50 tector is at the focal point of lens 26. The light intensity of k-1 Smooth modular Squares are collected in all the measurement is likely to be influenced by many Sources of Sieving runs, and a Single powerful computer performs the errors. For example, the gray levels of the filter 27 are only GauSS elimination algorithm and the actual factorization in approximations of the logs, and even uniformly designed a small fraction of the time which was devoted to the LEDs may have actual intensities varying by 20% or more. Sieving. 55 The accuracy of the TWINKLE device can be improved by The novel TWINKLE device, which is an ultrafast optical measuring the actual filtered intensity of each LED in the siever, should cost about the same as a powerful PC or a manufactured array, and assigning the Sequence of primes to than 0.1 seconds. This is 50 to 100 times faster than the 60 are very forgiving to Such measurement errors, and in PC conventional Sieving approach described above. The novel implementations they use crude integer approximations to TWINKLE device is an optoelectronic device which is the logs in order to Speed up the computation. There are two housed in an opaque blackened cylinder 20, see FIG. 3, possible types of errors: missed events and false alarms. To whose diameter is about 6 inches and whose height is about minimize the number of missed events a slightly lower 10 inches. The bottom of the cylinder consists of a large 65 reporting threshold is Set, and to eliminate the resultant false collection of LEDs 22 (light emitting diodes) carried on a alarms all the reported events are later tested on a PC in wafer 30. The LEDs twinkle at various frequencies, and the order to find the extremely rare real events among the rare US 6,603,445 B1 S false alarms. For typical values of the parameters, the average binary size of the Smooth part of candidate values is about one tenth of their size, and only a tiny fraction of all candidate values have ratioS exceeding one half. As a result, the desired events Stand out very clearly as isolated narrow peaks which are about ten times higher than the background 6 An important issue in Such a high Speed device is clock Synchronization. Each clock cycle lasts less than a nanoSecond, and all the light pulses must be Synchronized to within a fraction of this interval is order to correctly sure their contributions. Distributing electrical clock pulses (which travel slowly over long, high capacity wires) at 1 gigahertz to thousands of cells all over the wafer 30 without skewing their arrival times by more than 100 picoSeconds seems to be a very difficult problem. The present invention CaSOS Solves it by using a novel optical arrangement. Since it is 1. Optical Sieving can be performed at an extremely fast possible to construct in GaAS technology a Small photode clock rate. Typical silicon RAM chips in standard PC's tector 45 in each cell 32, the invention uses optical clock operate at about 100 megahertz. LEDs, on the other hand, distribution rather than electrical clock distribution. A Strong are manufactured with a much faster Gallium Arsenide LED 28 is placed opposite the wafer, which flashes at a fixed (GaAs) technology, and can be clocked at rates exceeding 1 15 rate, and its pulses are almost Simultaneously picked up by gigahertz without difficulty. Commercially available LEDs the photodetectors in all the cells, and used to drive the shift and photodetectors are used to Send 10 gigabits per Second registers in a Synchronized way, See FIG. 3a. Since light along fiber optic cables, and GaAS devices are widely used passes about 3 centimeters in 100 picoSeconds, the clocking LED 28 and the Summing photodetector 24 are placed at Similar clock rates as routers in high Speed networkS. 2. Hundreds of thousands of optical contributions can be sufficiently far away from the wafer 30 to guarantee suffi added instantaneously, if perfect accuracy is not needed, ciently similar optical delays to and from all the cells on the whereas building a digital adder with 200,000 inputs which flat wafer. To avoid possible confusion between clock and computes their Sum in a Single clock cycle is completely data light pulses, two different wavelengths are used for the unrealistic. two purposes. As shown in FIG. 3b a plurality of LEDs may 3. The optical technique of the present invention does not 25 be used for clocking with the LEDs 60 placed uniformly need huge arrays of counters. Instead of using one memory about the periphery of the cylinder 20. Computing the AND of 23 inputs requires a tree of depth cell per Sieved value, one time Slice per Sieved value can be used. Even with the declining cost of fast memories, time is 3 of 3-input AND gates in AND 48, which may be the cheaper than Space. slowest cell operation. To Speed it up, the invention uses a 4. In the optical technique of the present invention there Systolic design which carries out the tree computation in 3 is no necessity to Scan the array at the beginning in order to consecutive clock cycles. This delays the detection of the Zero it, nor any necessity to Scan the array again at the end Special State by 3 clock cycles, but keeps all the flashing in order to find its high entries—both operations are done at LEDs perfectly Synchronized. To compensate for the late no extra cost during the actual Sieving. reloading of register B, the invention Stores a modified value Referring to FIG. 2, the array of LEDs 22 is implemented 35 of p, in register A. An improved cell design is based on the observation that on a single wafer 30 of GaAs. Each cell 32 on this wafer contains one LED 22 plus Some circuitry which makes it about half the primes do not yield arithmetic progressions, flash for exactly one clock cycle every exactly p, clock whereas each prime in the other half yields two arithmetic noise. Optical Sieving according to the invention is much better than conventional counter array Sieving for the following cycles with an initial delay of exactly d, clock cycles. The progressions with the same period p, Instandard PC imple the AND 48 of all the bits of register B42, the LED 50 (22) flashes, and register B 42 is reloaded with the contents of register A 40 (which remains unchanged throughout the computation). The initial values loaded into registers A and New/OKI-News/1998/z.9819e.html for further details) have (easily computed) States of the shift register which are that 23 bit registers. Crude conservative estimates indicate that each one of these 69 bits can comfortably fit into an area of high clock rate and extremely accurate timing requirements 40 mentations this has little effect, Since one Still has to Scan on rule out analog control methods, and the unavoidable exist average one arithmetic progression per prime in the basis. ence of bad cells in the wafer rules out a prewired assign However, in the novel TWINKLE design and method the ment of primes to cells. Instead, identical cells are used two cells 32 assigned to the same p, can share the same A throughout the wafer, and included in each cell are two register 40 (which never changes) to reload their separate B registers, A and B, 40 and 42, see FIG. 2, which are loaded 45 shift registers 42. In addition, the two cells 32 can share the before the beginning of the Sieving process with values same LED 50 and flash it with the OR of the two AND gates corresponding to p, and d, respectively. Also a sensor 45 is 48, Since the two arithmetic progressions are always disjoint. included to receive Signals from a clocking LED and drive In the context of the present invention, this is called a double a clock 46 included in the circuitry. For a typical Sieving run cell, and used to reduce the average number of registers per with primes which are all smaller than 8,000,000, only 23 50 prime in the basis from 2 to 1.5. Since these registers occupy most of the area of the cell 32, this observation can increase bits are needed in each one of these registers. The structure of each cell (shown in FIG. 2) is very the number of primes handled with a single wafer 30 by Simple. The counting can be carried out in Standard binary almost 33%. counters in which all the Stages count Synchronously, or in The invention provides a single wafer 30 which can ripple counters in which the carries ripple through the 55 handle a prime base of 200,000 primes (which is the actual counter in an asynchronous way. A simpler Solution is to Size used in recent PC-based factorizations). A standard 6 count with a maximal length linear feedback Shift register B, inch wafer has a total usable area of about 18x10 square 42, which is based on a single XOR 44 of two of its bits. It microns. Commercially available LED arrays (such as the is driven by the clock 46, and runs until it enters the Special arrayS Sold by Oki Semiconductors to manufacturers of laser state in which all its bits are “1”. When this is recognized by 60 printers-see http://www.oki.co.jp/OKI/home/English/ a linear density of 1200 LEDs per inch. At this density, each LED occupies a 20tux20u square with an area of 400u, and about 40,000,000 LEDs can fit on a single wafer. However, B are not the binary representations of p, and d, but the 65 most of area of each double cell will be devoted to the three many steps before the special state of all “1”. US 6,603,445 B1 7 1,600u using commercially available GaAS technology. Thus, the whole double cell can fit into an area of less than 160,000u; and 100,000 double cells can be packed into a 8 bottom and the Summing photodetector 24 and clocking LED 28 at the top. Its diameter is determined by the size of the wafer, which is about 6 inches. Its height is determined single wafer. Such a wafer will be able to sieve numbers over by focal length of the convex lense 26 in the box, which can a prime base of 200,000 primes. be less than 10 inches. If we place the clocking LED28 and A simple reality check is based on the computation of the Summing photodetector 24 at the focal point of the lense, total amount of memory on the wafer. The 100,000 double then it is easy to prove that the time it takes for any light ray cells contain 69x100,000 bits, or less than one megabyte of to get from the LED through the lense to the wafer, and from memory. The other gates (XOR, AND) and diodes (LEDs, wafer through the lense to the photodetector, are com photodetectors) occupy a Small additional area. This is a the pletely uniform. very modest goal for wafer Scale designs. Although the invention has been shown and described in The cost of manufacturing Silicon wafers in a commercial of Specific preferred embodiments, nevertheless FAB is about S1,500 per wafer, and the cost of manufac terms turing the more expensive GaAs wafers is about $5,000 per changes and modifications are possible which do not depart wafer (excluding design costs and assuming a reasonably 15 from the Spirit, Scope and teachings of the invention. Such large order of wafers). This is comparable to the cost of a changes and modifications which are apparent to those Strong WorkStation, but provides a Sieving efficiency which skilled in the art are deemed to fall within the purview of the invention as claimed. is Several orders of magnitude higher. What is claimed is: The novel TWINKLE device does not have a yield 1. A method for use in factoring large numbers comprising problem, which plagues many other wafer-Scale designs: During the Sieving proceSS each cells works completely the Steps of: independently, without receiving any inputs or Sending any a) establishing a plurality of LEDs in a common plane; outputs to neighbouring cells. Even if 20% of the cells are b) associating each LED number j at least one period P found to be defective in postproduction inspection, the and at least one delay di; remaining 80% of the cells can be used. If necessary, two or c) establishing a clock cycle; more wafers can be placed at the same distance opposite the 25 d) driving the plurality of LEDs responsive to the clock Same Summing detector, in order to compensate for defec cycle to flash for one clock cycle at times described by tive cells or to Sieve over larger prime bases. the progression P*f-d for re0; After determining the number of cells, registers A and B e) controlling the light intensity flashed by LEDs to be in each cell are loaded with precomputed data from a proportional to log2 (P), and connected Storage device. Silicon memory cannot operate at f) collecting the light flashed by the LEDs to alert a gigahertz rates, and thus the clocking LEDS facing the GaAS connected computer whenever the total light received wafer needs to be slowed down during the loading phase. exceeds a predetermined threshold for implementing The A registers which contain the primes assigned to each with a QS or NFS algorithm. LED can be loaded only once after each powerup, but the B method of claim 1 wherein the LEDs are contained registers which contain the initial delays have to be loaded 35 in 2.anThe enclosure. for each sieving run. The total size of the 200,000 B registers 3. The method of claim 1 wherein at least Some of the is about 575 kilobytes. Such a small amount of data can be LEDs are of different sizes. kept in a Standard type of Silicon memory, and transferred to 4. The method of claim 1 wherein at least Some of the the wafer in 0.002 seconds on a 23 bit bus operating at 100 LEDs are of different resistances. megahertz. This is a Small fraction of the time required to 40 5. The method of claim 1 wherein the LEDs are of carry out the actual Sieving, and thus, it does not create a new uniform size and resistance. Speed bottleneck. 6. The method of claim 1 including the further step of The proposed wafer design has just 27 external connec tions: two for power, two for control, and 23 for the input filtering the light flashed by the LEDs. 7. The method of claim 6 including the step of filtering bus. The four modes of operation induced by the two control 45 through wires consist of a test mode (in which the various LEDs are levels. a transparent element with Smoothly changing gray Sequentially flashed to test their functionality and measure 8. The method of claim 1 including the further step of their light intensity), LOAD-A mode (in which the various assigning primes to the LEDS. A registers are sequentially loaded from the bus), LOAD-B 9. The method of claim 8 wherein the assignment is on the mode (in which the various B registers are sequentially 50 basis of Similar sized primes being assigned to neighboring loaded from the bus), and sieving mode (in which all the LEDS. shift registers are simultaneously clocked at the full clock 10. The method of claim 9 including the further steps of rate). The optical clocking during mode changes can be briefly frozen in order to enable the slow electric control testing the LEDs to determine their measured intensities, and assigning the Sequence of primes on the basis of tested Signals to propagate to all the cells on the wafer before 55 intensity. Starting operating in the new mode. 11. The method of claim 1 wherein the clock cycle is Another important factor in the wafer design is its total power consumption. Strong LEDs consume considerable established by a flashing LED. 12. The method of claim 11 wherein the clocking LED amounts of power, and if a large number of LEDs on the wafer flash Simultaneously, the excessive power consump 60 and photodetector are placed in the vicinity of the focal point a lense placed in the enclosure parallel to the plane of the tion can skew the intensity of the flashes. However, each of tested number can be divisible by at most several hundred LEDS. 13. Apparatus for use in processing large numbers com primes from the basis, and thus, there is provided a Small prising: upper bound on the total power which can be consumed by all the LEDS at any given moment in the Sieving process. 65 a) an enclosure; b) a plurality of LEDs located within the enclosure; As previously noted, the novel TWINKLE device is c) a clocking mechanism for Setting a clock cycle; housed in an opaque cylinder 20 with the wafer 30 at the US 6,603,445 B1 9 d) circuitry for driving the LEDs responsive to the clock cycle to flash for one clock cycle at predetermined times, e) means for controlling the light flashed by the LEDs; and f) a photodetector located in Spaced relation to the LEDs 10 18. Apparatus according to claim 17 wherein the photo detector is located at the other end of the cylinder. 19. Apparatus according to claim 18 wherein the clocking mechanism is established by a LED located at the other end of the cylinder, and the LEDs have associated with them photodetectors to receive flashes of light from the LED within the enclosure to collect light flashed by the LEDs to alert a connected computer whenever the total light received exceeds a predetermined threshold for implementing with a QS or NFS algorithm. 14. Apparatus according to claim 13 wherein each LED located at the other end. numberjis associated with at least one period p, and at least one delay d. is defined on the wafer. 20. Apparatus according to claim 13 wherein means for controlling the intensity of the light flashed by the LEDs is a filter. 21. Apparatus according to claim 17 wherein the circuitry 22. Apparatus according to claim 13 wherein the circuitry 15. Apparatus according to claim 14 wherein the circuitry 15 includes a shift register, an XOR gate and an AND gate. 23. Apparatus according to claim 19 wherein the clocking drives the LEDs to flash for one clock cycle at times described by each one of the progressions pr+d, for reO. LED and the photodetector are placed in the vicinity of the 16. Apparatus according to claim 13 wherein the enclo focal point of a lense placed in the enclosure parallel to the Sure is a cylinder. plane of the wafer. 17. Apparatus according to claim 16 wherein the LEDs are defined on a wafer located at one end of the cylinder.