TINDRA
TWINKLE ( The Weizmann Institute Key Locating Engine ) är en hypotetisk heltalsfaktoriseringsenhet som beskrevs 1999 av Adi Shamir och som påstås vara kapabel att faktorisera 512-bitars heltal. Det är också en ordlek på de blinkande lysdioderna som används i enheten. Shamir uppskattade att kostnaden för TWINKLE kunde vara så låg som $5000 per enhet med bulkproduktion. TWINKLE har en efterträdare som heter TWIRL som är mer effektiv.
Metod
Målet med TWINKLE är att implementera siktningssteget i Number Field Sieve- algoritmen, som är den snabbaste kända algoritmen för att faktorisera stora heltal. Siktningssteget, åtminstone för 512-bitars och större heltal, är det mest tidskrävande steget i NFS. Det innebär att testa en stor uppsättning siffror för B-'jämnhet', dvs frånvaron av en primtalsfaktor som är större än en specificerad gräns B.
Det som är anmärkningsvärt med TWINKLE är att det inte är en rent digital enhet. Den får sin effektivitet genom att undvika binär aritmetik för en "optisk" adderare som kan lägga till hundratusentals kvantiteter i en enda klockcykel.
Nyckelidén som används är "tid-rumsinversion". Konventionell NFS-siktning utförs en primning i taget. För varje primtal har alla siffror som ska testas för jämnhet i det aktuella intervallet och som är delbara med det primtal har sin räknare inkrementerad med logaritmen för primtal (liknande sikten av Eratosthenes ). TWINKLE, å andra sidan, fungerar ett kandidatsmält nummer (kalla det X) åt gången. Det finns en lysdiod som motsvarar varje primtal mindre än B. Vid det ögonblick som motsvarar X, motsvarar uppsättningen av lysdioder som lyser uppsättningen primtal som delar X. Detta kan åstadkommas genom att LED associerad med prime p lyser en gång varje p gång ögonblick. Vidare är intensiteten för varje lysdiod proportionell mot logaritmen för motsvarande primtal. Den totala intensiteten är alltså lika med summan av logaritmerna för alla primfaktorer för X mindre än B. Denna intensitet är lika med logaritmen för X om och endast om X är B-jämn.
Även i PC-baserade implementeringar är det en vanlig optimering för att påskynda siktningen genom att lägga till ungefärliga logaritmer av små primtal tillsammans. På samma sätt har TWINKLE mycket utrymme för fel i sina ljusmätningar; så länge som intensiteten är på ungefär rätt nivå, är siffran mycket sannolikt tillräckligt jämn för ändamålen med kända factoringalgoritmer. Förekomsten av ens en stor faktor skulle innebära att logaritmen för ett stort tal saknas, vilket resulterar i en mycket låg intensitet; eftersom de flesta siffror har denna egenskap, tenderar enhetens utsignal att bestå av sträckor av lågintensitetsutmatning med korta skurar av högintensitetsutmatning.
I det ovanstående antas att X är kvadratfritt, dvs det är inte delbart med kvadraten av något primtal. Detta är acceptabelt eftersom faktoriseringsalgoritmerna bara kräver "tillräckligt många" jämna tal, och "utbytet" minskar endast med en liten konstant faktor på grund av antagandet om kvadratfrihet . Det finns också problemet med falska positiva resultat på grund av felaktigheten i den optoelektroniska hårdvaran, men detta löses enkelt genom att lägga till ett PC-baserat efterbearbetningssteg för att verifiera jämnheten hos siffrorna som identifieras av TWINKLE.
Se även
- TWIRL , efterträdaren till TWINKLE