МЕРЦАНИЕ

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

Метод

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

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

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

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

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

См. также

TWIRL , преемник TWINKLE

Ссылки

^ Шамир, Ади (1999). «Разложение больших чисел с помощью устройства TWINKLE». В Коче, Четин К.; Паар, Кристоф (ред.). Криптографическое оборудование и встроенные системы . Конспекты лекций по информатике. Том. 1717. Берлин, Гейдельберг: Springer. стр. 2–12. дои : 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». В Боне, Дэн (ред.). Достижения криптологии — КРИПТО 2003 . Конспекты лекций по информатике. Том. 2729. Берлин, Гейдельберг: Springer. стр. 1–26. дои : 10.1007/978-3-540-45146-4_1 . ISBN 978-3-540-45146-4 .

[1] Шамир, Ади (1999). «Разложение больших чисел с помощью устройства TWINKLE». В Коче, Четин К.; Паар, Кристоф (ред.). Криптографическое оборудование и встроенные системы . Конспекты лекций по информатике. Том. 1717. Берлин, Гейдельберг: Springer. стр. 2–12. дои : 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». В Боне, Дэн (ред.). Достижения криптологии — КРИПТО 2003 . Конспекты лекций по информатике. Том. 2729. Берлин, Гейдельберг: Springer. стр. 1–26. дои : 10.1007/978-3-540-45146-4_1 . ISBN 978-3-540-45146-4 .

[1]

[2]

[3]