TWINKLE
Encyclopedia
TWINKLE is a hypothetical integer factorization
device described in 1999 by Adi Shamir
and purported to be capable of factoring 512-bit integers. The name is an acronym of "The Weizmann Institute Key Locating Engine". It is also a pun on the twinkling LED
s used in the device.
The goal of TWINKLE is to implement the sieving step of the Number Field Sieve algorithm, which is the fastest known algorithm for factoring large integers. The sieving step, at least for 512-bit and larger integers, is the most time consuming step of NFS. It involves testing a large set of numbers for B-'smoothness', i.e, absence of a prime factor
greater than a specified bound B.
What is remarkable about TWINKLE is that it is not a purely digital device. It gets its efficiency by eschewing binary arithmetic for an "optical" adder which can add hundreds of thousands of quantities in a single clock cycle.
The key idea used is "time-space inversion". Conventional NFS sieving is carried out one prime at a time. For each prime, all the numbers to be tested for smoothness in the range under consideration which are divisible by that prime have their counter incremented by the logarithm of the prime (similar to the sieve of Eratosthenes
). TWINKLE, on the other hand, works one candidate smooth number (call it X) at a time. There is one LED corresponding to each prime smaller than B. At the time instant corresponding to X, the set of LEDs glowing corresponds to the set of primes that divide X. This can be accomplished by having the LED associated with the prime p glow once every p time instants. Further, the intensity of each LED is proportional to the logarithm of the corresponding prime. Thus, the total intensity equals the sum of the logarithms of all the prime factors of X smaller than B. This intensity is equal to the logarithm of X if and only if X is B-smooth.
Even in PC-based implementations, it's a common optimization to speed up sieving by adding approximate logarithms of small primes together. Similarly, TWINKLE has much room for error in its light measurements; as long as the intensity is at about the right level, the number is very likely to be smooth enough for the purposes of known factoring algorithms. The existence of even one large factor would imply that the logarithm of a large number is missing, resulting in a very low intensity; because most numbers have this property, the device's output would tend to consist of stretches of low intensity output with brief bursts of high intensity output.
In the above it is assumed that X is square-free, i.e it is not divisible by the square of any prime. This is acceptable since the factoring algorithms only require "sufficiently many" smooth numbers, and the "yield" decreases only by a small constant factor due to the square-freeness assumption. There is also the problem of false positives due to the inaccuracy of the optoelectronic hardware, but this is easily solved by adding a PC-based post-processing step for verifying the smoothness of the numbers identified by TWINKLE.
Shamir has estimated that the cost of TWINKLE could be as low as $5000 per unit with bulk production.
TWINKLE has a successor named TWIRL
which is more efficient.
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
device described in 1999 by Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
and purported to be capable of factoring 512-bit integers. The name is an acronym of "The Weizmann Institute Key Locating Engine". It is also a pun on the twinkling LED
LEd
LEd is a TeX/LaTeX editing software working under Microsoft Windows. It is a freeware product....
s used in the device.
The goal of TWINKLE is to implement the sieving step of the Number Field Sieve algorithm, which is the fastest known algorithm for factoring large integers. The sieving step, at least for 512-bit and larger integers, is the most time consuming step of NFS. It involves testing a large set of numbers for B-'smoothness', i.e, absence of a prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
greater than a specified bound B.
What is remarkable about TWINKLE is that it is not a purely digital device. It gets its efficiency by eschewing binary arithmetic for an "optical" adder which can add hundreds of thousands of quantities in a single clock cycle.
The key idea used is "time-space inversion". Conventional NFS sieving is carried out one prime at a time. For each prime, all the numbers to be tested for smoothness in the range under consideration which are divisible by that prime have their counter incremented by the logarithm of the prime (similar to the sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
). TWINKLE, on the other hand, works one candidate smooth number (call it X) at a time. There is one LED corresponding to each prime smaller than B. At the time instant corresponding to X, the set of LEDs glowing corresponds to the set of primes that divide X. This can be accomplished by having the LED associated with the prime p glow once every p time instants. Further, the intensity of each LED is proportional to the logarithm of the corresponding prime. Thus, the total intensity equals the sum of the logarithms of all the prime factors of X smaller than B. This intensity is equal to the logarithm of X if and only if X is B-smooth.
Even in PC-based implementations, it's a common optimization to speed up sieving by adding approximate logarithms of small primes together. Similarly, TWINKLE has much room for error in its light measurements; as long as the intensity is at about the right level, the number is very likely to be smooth enough for the purposes of known factoring algorithms. The existence of even one large factor would imply that the logarithm of a large number is missing, resulting in a very low intensity; because most numbers have this property, the device's output would tend to consist of stretches of low intensity output with brief bursts of high intensity output.
In the above it is assumed that X is square-free, i.e it is not divisible by the square of any prime. This is acceptable since the factoring algorithms only require "sufficiently many" smooth numbers, and the "yield" decreases only by a small constant factor due to the square-freeness assumption. There is also the problem of false positives due to the inaccuracy of the optoelectronic hardware, but this is easily solved by adding a PC-based post-processing step for verifying the smoothness of the numbers identified by TWINKLE.
Shamir has estimated that the cost of TWINKLE could be as low as $5000 per unit with bulk production.
TWINKLE has a successor named TWIRL
TWIRL
In cryptography and number theory, TWIRL is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. During the sieving step, the algorithm searches for numbers with a certain mathematical relationship...
which is more efficient.