TWINKLE: 512 биттік сандарды жіктеуге арналған оптикалық құрылғы

Кіріспе

TWINKLE (Вейцман институтының кілтін табу машинасы) – 1999 жылы Ади Шамир сипаттаған, 512 биттік бүтін сандарды есепке алуға қабілетті деп есептелетін гипотетикалық бүтін сандарды есепке алу құрылғысы. Бұл атау құрылғыда қолданылатын жыпылықтайтын светодиодтармен байланысты әдемі ойын. Шамирдің бағалауынша, көптеп өндірілген жағдайда TWINKLE құрылғысының бірлігінің құны 5000 долларға дейін төмендеуі мүмкін. TWINKLE-дің TWIRL деп аталатын, одан тиімдірек мұрагері бар.

Әдіс

TWINKLE-дің мақсаты – үлкен бүтін сандарды факторлау үшін ең жылдам белгілі алгоритм болып табылатын Сандық өріс Сейісі (Number Field Sieve) алгоритмінің сырғалау қадамын іске асыру. Сырғалау кезеңі, кем дегенде 512 биттік және одан үлкен бүтін сандар үшін, NFS-тің ең көп уақытты қажет ететін кезеңі болып табылады. Ол үлкен сандар жиынтығын B «тегісдігіне» (smoothness) қатысты тексеруді қамтиды, яғни, көрсетілген шекара B-ден үлкен жай көбейткішінің жоқ болуын. TWINKLE-дің ерекшелігі – ол толығымен цифрлық құрылғы емес. Ол тиімділігін екілік арифметикадан бас тартып, бір секундтық циклда жүздеген мың шаманы қоса алатын «оптикалық» қосушы арқылы қамтамасыз етеді. Қолданылған негізгі идея – «уақыт-кеңістік инверсиясы». Дәстүрлі NFS сырғалауы бір уақытта бір жай санмен жүргізіледі. Әр жай сан үшін, қарастырылып отырған диапазон ішіндегі сол жай санға бөлінетін, тегіс болу үшін тексерілетін барлық сандардың санағы жай санның логарифмімен артырылады (Эратоспеннің сырғанағына ұқсас). TWINKLE, керісінше, бір үміткер тегіс санмен (оны X деп атайық) бір уақытта жұмыс істейді. B-ден кіші әр жай санға сәйкес келетін бір LED бар. X уақытына сәйкес келетін сәтте, жарықтанған LED-тер жиыны X-ті бөлетін жай сандар жиынына сәйкес келеді. Бұл үшін LED-ті әрбір p уақыт сәтінде бір рет жай сан p арқылы жарықтандыруға болады. Сонымен қатар, әрбір LED-тің қарқындылығы сәйкес жай санның логарифміне пропорционалды. Осылайша, жалпы қарқындылық 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.