Особенности факторизации 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, но и сам неверный ответ не сопровождается ни предупредительным сигналом, ни текстовым сообщением об ошибке.

Модели и серии: 

Комментарии

Известно, что "фундаментом" UserRPL является SysRPL, т.е. в основе всех команд UserRPL лежат команды (одна или несколько) SysRPL. К факторизации long integer в SysRPL относятся следующие четыре: ^ZFactor (# 0C9006h), ^NFactor (# 0CA006h), ^NFactorSpc (# 0CB006h), ^BFactor (# 0CF006h). В описании последней имеется уточнение о её работе (см. стр. 331 в Programming in System RPL / Eduardo M. Kalinowski, Carsten Dominik):

Since the factorization can potentially take a very long time, an execution time test is used to abort factoring very long integers (limit is 60s for each composite).

Проверку работы команд проводил на эмуляторе в обычном (Authentic Calculator Speed) и "быстром" режиме. С числом 258515548685555605977575788207962363654079 не справляется ни одна команда, а с 7200005990001127 справляются все четыре, но только в "быстром" режиме.

Например, число 2^128-1 третья команда раскладывает не до конца, но очень быстро (менее 1 секунды). Оставшийся не простой множитель она разложить не может, могут другие команды, но только за 55 секунд. Видимо, в основе кода первой, второй, четвёртой команды лежит один алгоритм. По времени работы в обычном режиме первая, вторая и четвёртая команды не отличаются от FACTOR (56 секунд).