Особенности факторизации HP 50g.

В компьютерной безопасности и криптографии важную роль играет «факторизация» целых чисел (разложение на простые множители). Каждое число может быть разложено на простые множители лишь единственным образом (скажем, 15=3*5). Для разложения больших чисел требуются высокопроизводительные вычислительные системы.

Калькулятор HP 50g позволяет при помощи функции ISPRIME? тестировать числа «на простоту», а также с помощью команды FACTOR разлагать числа на простые множители. Руководство утверждает, что ISPRIME\? позволяет обрабатывать числа неограниченной длины, однако не приводится сведений об ограничениях команды FACTOR.

Возьмём два целых числа (занимающие 59 и 79 бит):

DVX = 555555555578888573

DVY = 465327987614456579865323

На оба числа ISPRIME\? выдаёт 1, что означает, что это простые числа. Перемножим их, получив 138-битное число:

MAGIC = DVX * DVY = 258515548685555605977575788207962363654079

На это число ISPRIME\? выдаёт 0, оно составное. Однако команда FACTOR не разлагает его на сомножители (в данном случае DVX и DVY). Более того, на основе этого числа можно создавать другие составные числа, например 17 * 1999 * MAGIC, которые при факторизации на HP 50g не будут содержать в разложении простые множители DVX и DVY. Команда FACTOR будет стабильно использовать в разложении число MAGIC наравне с простыми числами, не сообщая пользователю об ошибке и никак не выделяя неразложенное число среди других сомножителей.

Для подбора длинных простых чисел удобно использовать команду NEXTPRIME.

Похоже, что на команде FACTOR стоит таймаут. Если поиск сомножителей отнимает больше одной-двух минут, калькулятор сдаётся и считает оставшееся число простым. В некоторых случаях удаётся получить дальнейшее разложение, запустив команду FACTOR для последнего сомножителя. Но если его даже в одиночку невозможно разложить за указанное время, он во всех разложениях будет восприниматься, как простое число.

Фактически можно использовать произведение двух любых девяти (и более) значных простых чисел. Достаточно подольше потоптать клавиатуру калькулятора и дать команду NEXTPRIME, чтобы сгенерировать «тайный» сомножитель. Понятно, что после переписывания «сатурновской» прошивки под ARM скорость вычислений возрастёт и указанный диапазон на пару порядков увеличится. Непонятно лишь, почему в инструкции не отмечены не только найденные ограничения команды FACTOR, но и сам неверный ответ не сопровождается ни предупредительным сигналом, ни текстовым сообщением об ошибке.