트윙클

TWINKLE
다른 용도는 Twinkle(동음이의)을 참조하십시오.

트윙클(The Weizmann Institute Key Location Engine)은 아디 샤미르[1](Adi Shamir)[2]가 1999년에 설명한 가상 정수 인자화 장치로 512비트 정수를 인수할 수 있다고 알려져 있다.그것은 또한 장치에 사용되는 반짝이는 LED에 대한 말장난이다.샤미르는 트윙클의 가격이 대량 생산으로 개당 5,000달러까지 낮을 수 있다고 추정했다.트윙클은 트월이라는[3] 이름의 후계자가 있는데, 이것이 더 효율적이다.

방법

TWINKLE의 목표는 큰 정수를 인수하기 위해 가장 빨리 알려진 알고리즘인 Number Field Che 알고리즘의 체이빙 단계를 구현하는 것이다.최소 512비트 이상의 정수에 대한 체이빙 단계는 NFS에서 가장 많은 시간을 소비하는 단계다.여기에는 B-'원만함' 즉, 지정된 B-원만함수보다 큰 주요 인자의 부재에 대한 많은 수의 시험이 포함된다.

트윙클이 주목할 만한 점은 순수 디지털 기기가 아니라는 점이다.그것은 단일 클럭 사이클에서 수십만 개의 수량을 추가할 수 있는 "광학" 부속기의 이진 산수를 억제함으로써 그것의 효율성을 얻는다.

사용된 핵심 아이디어는 "시간 공간 역행"이다.기존의 NFS 체이빙은 한 번에 한 프라임씩 수행된다.각 프라임의 경우, 해당 프라임으로 구분되는 고려 대상 범위에서 부드러움을 시험할 모든 숫자는 프라임의 로그(에라토스테네스의 체와 유사)에 의해 카운터가 증가한다.반면 트윙클은 한 번에 한 후보(X라고 부름)의 부드러운 번호로 작용한다.각각의 프라임마다 B보다 작은 하나의 LED가 있다.X에 해당하는 시간 순간에서 발광 LED 세트는 X를 나누는 프리타임 세트에 해당한다.prime p와 관련된 LED가 p시간마다 한 번씩 점광하면 이를 달성할 수 있다.또한 각 LED의 강도는 해당 프라임의 로그에 비례한다.따라서 총 강도는 B보다 작은 X의 모든 주요 인자의 로그 합계와 같다.이 강도는 X가 B-smooth일 경우에만 X의 로그와 동일하다.

PC 기반 구현에서도 작은 프리타임의 대략적인 로그를 함께 추가하여 체이빙 속도를 높이는 것이 일반적인 최적화다.마찬가지로, TWINKLE은 빛의 측정에 오류의 여지가 많다. 강도가 거의 적절한 수준이라면, 그 숫자는 알려진 인수 알고리즘의 목적에 적합할 정도로 충분히 부드러워질 가능성이 높다.하나의 큰 요인이라도 존재한다는 것은 큰 숫자의 로그가 누락되어 매우 낮은 강도가 발생한다는 것을 의미할 수 있다. 대부분의 숫자가 이 속성을 가지기 때문에 기기의 출력은 짧은 버스트의 고강도 출력과 함께 저강도 출력으로 구성되는 경향이 있다.

상기에서 X는 제곱이 없는 것으로 가정한다. 즉, 어떤 프라임의 제곱으로도 분할되지 않는다.인수 알고리즘은 "충분히 많은" 부드러운 숫자만 필요로 하고, "수익"은 제곱-자유도 가정으로 인해 작은 상수 요인만 감소하기 때문에 이것은 허용된다.광전자 하드웨어의 부정확성으로 인한 잘못된 긍정의 문제도 있지만, TWINKLE이 식별한 숫자의 매끄러움을 검증하기 위한 PC 기반 후처리 단계를 추가하면 쉽게 해결할 수 있다.

참고 항목

참조

  1. ^ Shamir, Adi (1999). Koç, Çetin K.; Paar, Christof (eds.). "Factoring Large Numbers with the TWINKLE Device". Cryptographic Hardware and Embedded Systems. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 2–12. doi:10.1007/3-540-48059-5_2. ISBN 978-3-540-48059-4.
  2. ^ Shamir, Adi (1999), "Factoring Large Numbers with the TWINKLE Device", Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, vol. 1717, Springer Berlin Heidelberg, pp. 2–12, doi:10.1007/3-540-48059-5_2, ISBN 9783540666462
  3. ^ Shamir, Adi; Tromer, Eran (2003). Boneh, Dan (ed.). "Factoring Large Numbers with the TWIRL Device". Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 1–26. doi:10.1007/978-3-540-45146-4_1. ISBN 978-3-540-45146-4.