MIGOTANIE
TWINKLE ( The Weizmann Institute Key Locating Engine ) to hipotetyczne urządzenie do faktoryzacji liczb całkowitych opisane w 1999 roku przez Adi Shamira i rzekomo zdolne do rozkładania na czynniki 512-bitowych liczb całkowitych. Jest to również gra słów na temat migoczących diod LED zastosowanych w urządzeniu. Shamir oszacował, że koszt TWINKLE może wynosić zaledwie 5000 USD za sztukę przy masowej produkcji. TWINKLE ma następcę o nazwie TWIRL , który jest bardziej wydajny.
metoda
Celem TWINKLE jest implementacja kroku przesiewania algorytmu Number Field Sieve , który jest najszybszym znanym algorytmem rozkładania na czynniki dużych liczb całkowitych. Etap przesiewania, przynajmniej dla 512-bitowych i większych liczb całkowitych, jest najbardziej czasochłonnym etapem NFS. Polega na testowaniu dużego zestawu liczb pod kątem „gładkości” B, tj. braku czynnika pierwszego większego niż określona granica B.
Niezwykłe w TWINKLE jest to, że nie jest to urządzenie czysto cyfrowe. Uzyskuje swoją wydajność, unikając arytmetyki binarnej na rzecz „optycznego” sumatora, który może dodać setki tysięcy wielkości w jednym cyklu zegara.
Kluczową zastosowaną ideą jest „inwersja czasoprzestrzeni”. Konwencjonalne przesiewanie NFS jest przeprowadzane jednorazowo. Dla każdej liczby pierwszej wszystkie liczby, które mają być sprawdzone pod kątem gładkości w rozważanym zakresie, które są podzielne przez tę liczbę pierwszą, mają licznik zwiększany o logarytm liczby pierwszej (podobnie jak sito Eratostenesa ). Z drugiej strony TWINKLE pracuje z jednym kandydującym gładkim numerem (nazwij go X) na raz. Każda dioda LED odpowiada każdej liczbie pierwszej mniejszej niż B. W chwili odpowiadającej X zestaw świecących diod LED odpowiada zestawowi liczb pierwszych dzielących X. Można to osiągnąć, powiązując diodę LED z liczbą pierwszą p świeci raz na p momentach czasu. Ponadto intensywność każdej diody LED jest proporcjonalna do logarytmu odpowiedniej liczby pierwszej. Zatem całkowite natężenie jest równe sumie logarytmów wszystkich czynników pierwszych X mniejszych niż B. To natężenie jest równe logarytmowi X wtedy i tylko wtedy, gdy X jest B-gładkie.
Nawet w implementacjach opartych na komputerach PC powszechną optymalizacją jest przyspieszenie przesiewania przez dodanie do siebie przybliżonych logarytmów małych liczb pierwszych. Podobnie TWINKLE ma dużo miejsca na błędy w swoich pomiarach światła; dopóki intensywność jest mniej więcej na odpowiednim poziomie, jest bardzo prawdopodobne, że liczba będzie wystarczająco gładka dla celów znanych algorytmów faktoryzacji. Istnienie choćby jednego dużego czynnika oznaczałoby, że brakuje logarytmu dużej liczby, co skutkowałoby bardzo niską intensywnością; ponieważ większość liczb ma tę właściwość, dane wyjściowe urządzenia składałyby się zwykle z odcinków sygnału wyjściowego o niskiej intensywności z krótkimi impulsami sygnału wyjściowego o wysokiej intensywności.
W powyższym założono, że X jest bezkwadratowy, tzn. nie jest podzielny przez kwadrat żadnej liczby pierwszej. Jest to do zaakceptowania, ponieważ algorytmy faktoringu wymagają tylko „wystarczająco wielu” gładkich liczb, a „wydajność” zmniejsza się tylko o mały stały współczynnik ze względu na założenie o braku kwadratów . Istnieje również problem fałszywych alarmów spowodowany niedokładnością sprzętu optoelektronicznego, ale można go łatwo rozwiązać, dodając krok przetwarzania końcowego na komputerze PC w celu weryfikacji płynności liczb zidentyfikowanych przez TWINKLE.
Zobacz też
- TWIRL , następca TWINKLE