МЕРЦАТЬ

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

Метод

Целью TWINKLE является реализация шага просеивания алгоритма Number Field Sieve , который является самым быстрым из известных алгоритмов факторизации больших целых чисел. Шаг просеивания, по крайней мере для 512-битных и более больших целых чисел, является самым трудоемким шагом NFS. Он включает в себя проверку большого набора чисел на B-'гладкость', т. е. отсутствие простого множителя, большего , чем указанная граница B.

Что примечательно в TWINKLE, так это то, что это не чисто цифровое устройство. Его эффективность достигается за счет отказа от двоичной арифметики в пользу «оптического» сумматора, который может складывать сотни тысяч величин за один такт.

Ключевая идея, используемая в NFS, — это «инверсия времени и пространства». Обычное просеивание NFS выполняется по одному простому числу за раз. Для каждого простого числа все числа, которые необходимо проверить на гладкость в рассматриваемом диапазоне, которые делятся на это простое число, увеличивают свой счетчик на логарифм простого числа (аналогично решету Эратосфена ). TWINKLE, с другой стороны, обрабатывает одно потенциальное гладкое число (назовем его X) за раз. Каждому простому числу, меньшему B, соответствует один светодиод. В момент времени, соответствующий X, набор светящихся светодиодов соответствует набору простых чисел, которые делят X. Этого можно добиться, если светодиод, связанный с простым числом p, будет светиться один раз каждые p моментов времени. Кроме того, интенсивность каждого светодиода пропорциональна логарифму соответствующего простого числа. Таким образом, общая интенсивность равна сумме логарифмов всех простых множителей X, меньших B. Эта интенсивность равна логарифму X тогда и только тогда, когда X является B-гладким.

Даже в реализациях на базе ПК это обычная оптимизация для ускорения просеивания путем сложения приблизительных логарифмов малых простых чисел. Аналогично, TWINKLE имеет много места для ошибок в своих измерениях света; пока интенсивность находится на правильном уровне, число, скорее всего, будет достаточно гладким для целей известных алгоритмов факторизации. Существование даже одного большого множителя означало бы, что логарифм большого числа отсутствует, что приводит к очень низкой интенсивности; поскольку большинство чисел обладают этим свойством, выход устройства, как правило, будет состоять из отрезков выходного сигнала низкой интенсивности с короткими всплесками выходного сигнала высокой интенсивности.

В приведенном выше примере предполагается, что X является свободным от квадратов, т. е. не делится на квадрат любого простого числа. Это приемлемо, поскольку алгоритмы факторизации требуют только «достаточно много» гладких чисел, а «выход» уменьшается только на небольшой постоянный множитель из-за предположения о свободности от квадратов . Также существует проблема ложных срабатываний из-за неточности оптоэлектронного оборудования, но она легко решается путем добавления этапа постобработки на базе ПК для проверки гладкости чисел, идентифицированных TWINKLE.

Смотрите также

TWIRL , преемник TWINKLE

Ссылки

^ Шамир, Ади (1999). «Разложение больших чисел с помощью устройства TWINKLE». В Koç, Çetin K.; Paar, Christof (ред.). Криптографическое оборудование и встроенные системы . Конспект лекций по информатике. Том 1717. Берлин, Гейдельберг: Springer. стр. 2–12. doi : 10.1007/3-540-48059-5_2 . ISBN 978-3-540-48059-4.
^ Шамир, Ади (1999), «Разложение больших чисел с помощью устройства TWINKLE», Криптографическое оборудование и встраиваемые системы , Конспект лекций по информатике, т. 1717, Springer Berlin Heidelberg, стр. 2–12, doi : 10.1007/3-540-48059-5_2 , ISBN 9783540666462
^ Шамир, Ади; Тромер, Эран (2003). «Разложение больших чисел на множители с помощью устройства TWIRL». В Boneh, Dan (ред.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Vol. 2729. Berlin, Heidelberg: Springer. pp. 1–26. doi : 10.1007/978-3-540-45146-4_1 . ISBN 978-3-540-45146-4.

[1] Шамир, Ади (1999). «Разложение больших чисел с помощью устройства TWINKLE». В Koç, Çetin K.; Paar, Christof (ред.). Криптографическое оборудование и встроенные системы . Конспект лекций по информатике. Том 1717. Берлин, Гейдельберг: Springer. стр. 2–12. doi : 10.1007/3-540-48059-5_2 . ISBN 978-3-540-48059-4.

[2] Шамир, Ади (1999), «Разложение больших чисел с помощью устройства TWINKLE», Криптографическое оборудование и встраиваемые системы , Конспект лекций по информатике, т. 1717, Springer Berlin Heidelberg, стр. 2–12, doi : 10.1007/3-540-48059-5_2 , ISBN 9783540666462

[3] Шамир, Ади; Тромер, Эран (2003). «Разложение больших чисел на множители с помощью устройства TWIRL». В Boneh, Dan (ред.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Vol. 2729. Berlin, Heidelberg: Springer. pp. 1–26. doi : 10.1007/978-3-540-45146-4_1 . ISBN 978-3-540-45146-4.