ТВИНКЛ: Оптический процессор для факторизации целых чисел.

Введение

TWINKLE (The Weizmann Institute Key Locating Engine) — это гипотетическое устройство для факторизации целых чисел, описанное в 1999 году Ади Шамиром и, как утверждается, способное факторизовать 512-битные целые числа. Название также является игрой слов, основанной на мерцающих светодиодах, используемых в устройстве. Шамир оценивал, что стоимость TWINKLE при массовом производстве может составлять всего 5000 долларов за единицу. У TWINKLE есть более эффективный преемник под названием TWIRL.

Метод

Целью TWINKLE является реализация шага просеивания алгоритма решета полей чисел, который является самым быстрым известным алгоритмом для факторизации больших целых чисел. Шаг просеивания, по крайней мере для 512-битных и более крупных целых чисел, является наиболее трудоемким этапом алгоритма NFS. Он включает в себя проверку большого набора чисел на B-гладкость, то есть отсутствие простых множителей, больших, чем заданное ограничение B. Примечательно, что TWINKLE – это не чисто цифровое устройство. Оно достигает своей эффективности, отказываясь от двоичной арифметики в пользу "оптического" сумматора, способного суммировать сотни тысяч значений за один тактовый цикл. Ключевая идея, лежащая в основе разработки, – "инверсия пространства-времени". Традиционное просеивание в NFS выполняется для каждого простого числа по отдельности. Для каждого простого числа счетчик всех чисел, подлежащих проверке на гладкость в рассматриваемом диапазоне и делящихся на это простое число, увеличивается на логарифм этого простого числа (аналогично решету Эратосфена). TWINKLE, напротив, работает с одним кандидатом на гладкое число (назовем его X) за раз. Для каждого простого числа, меньшего B, предусмотрен один светодиод. В момент времени, соответствующий X, набор горящих светодиодов соответствует набору простых чисел, делящих X. Это достигается тем, что светодиод, связанный с простым числом p, загорается один раз за p временных интервалов. Кроме того, интенсивность каждого светодиода пропорциональна логарифму соответствующего простого числа. Таким образом, общая интенсивность равна сумме логарифмов всех простых множителей X, меньших B. Эта интенсивность равна логарифму X тогда и только тогда, когда X является B-гладким. Даже в программных реализациях на основе ПК обычной оптимизацией для ускорения просеивания является суммирование приближенных логарифмов малых простых чисел. Аналогично, TWINKLE допускает значительные погрешности в измерениях света; пока интенсивность находится примерно на правильном уровне, число, скорее всего, будет достаточно гладким для целей известных алгоритмов факторизации. Наличие даже одного большого множителя означает, что логарифм большого числа отсутствует, что приводит к очень низкой интенсивности; поскольку большинство чисел обладают этим свойством, выход устройства будет состоять из отрезков выходного сигнала с низкой интенсивностью, перемежающихся с кратковременными всплесками высокой интенсивности. В вышесказанном предполагается, что X не имеет квадратных множителей, то есть не делится на квадрат какого-либо простого числа. Это допустимо, поскольку алгоритмы факторизации требуют лишь "достаточного количества" гладких чисел, а "выход" уменьшается лишь на небольшой постоянный коэффициент из-за предположения об отсутствии квадратных множителей. Существует также проблема ложных срабатываний из-за неточности оптоэлектронного оборудования, но она легко решается путем добавления этапа постобработки на основе ПК для проверки гладкости чисел, идентифицированных TWINKLE.

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.