Приобрёл вражеский программируемый калькулятор. Отзыв напишу потом. А сейчас самое важное или, по крайней мере, интересное.

Обнаружение ошибки

Как известно, в компьютерной безопасности и криптографии важную роль играет «факторизация» целых чисел, то есть их разложение на простые множители. Напомню, что простое число это то, которое делится без остатка лишь на само себя и на единицу (2, 3, 5, 7, 11, 13,…). Каждое число может быть разложено на простые множители лишь единственным образом (скажем, 15=3*5). И найти это разложение намного дольше, чем перемножить взятые с потолка простые числа. Для разложения больших чисел приходится задействовать кластеры, состоящие из большого числа высокопроизводительных компьютеров. Чтож, пощупаем эту важную грань с помощью калькулятора.

Калькулятор HP 50g подкупает тем, что позволяет «из коробки» (функция ISPRIME?) тестировать числа «на простоту», а также с помощью команды FACTOR разлагать числа на простые множители. Инструкция обещает, что специальный «целый» тип данных позволяет калькулятору обрабатывать числа неограниченной длины. В руководстве (как в кратком User's Manual, так и в 888-страничном User's Guide) нет сведений об ограничениях команды 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 будут исследованы (кстати, используемая прошивка для HP 49G+/50g (v92, Revision #2.09; HP49 CAS VER 4.20060602) является последней и скачена из Интернета — следовательно технически возможно даже дизассемблирование) я рекомендую не полагаться на калькуляторы HP, по крайней мере в вопросах факторизации больших чисел. Чтобы не писали инструкции, серебряной пули нет и сомножители, выдаваемые командой FACTOR следует отдельно перепроверять на простоту — по меньшей мере с помощью команды ISPRIME? того же калькулятора.

Дальнейшее исследование

Похоже, что на команде FACTOR стоит таймаут. Если поиск сомножителей отнимает больше одной-двух минут, калькулятор сдаётся (как в том анекдоте про подбор пароля китайцами) и считает оставшееся число простым. В некоторых случаях удаётся получить дальнейшее разложение, запустив команду FACTOR для последнего сомножителя. Но если его даже в одиночку невозможно разложить за указанное время, он во всех разложениях будет восприниматься, как простое число. Как влияет на это скорость работы процессора (некоторые программы позволяют его разгонять чуть ли не до 200МГц), я не проверял.

Кстати, мне удалось подобрать значительно меньшие числа (по 27 бит каждое), 53-битное произведение которых заставляет сбоить встроенную команду факторизации:
DV1 = 80000023
DV2 = 90000049
MAG = DV1*DV2 = 7200005990001127

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

А может, всё-таки не ошибка?

Итак, команда FACTOR работает не так, как ожидалось. Но тут закралось сомнение. Кто сказал, что она выполняет факторизацию так, как мы ожидаем? Быть может, команда FACTOR просто разлагает на множители. А простые они или нет, уже другое дело.

Чтож. Посмотрим на встроенную подсказку по ещё одной команде, FACTORS (снимок экрана слева). Слово "irreductible" как раз и означает неразложимые, простые множители. Справа же видим разложение по этой команде числа 10*MAG (72000059900011270). Как мы видим, простые множители 2 и 5 машинка нашла. Но на числе MAG споткнулась и показала его, как неразложимое. Хотя оно вполне себе разложимо (на DV1 и DV2).

Итого вердикт ясен. Ошибка. Кстати, в Сети приводятся и другие случаи, когда при сложности (или невозможности) получения правильного ответа HP 50g выдаёт не сообщение об ошибке и не предупреждение, а неправильный ответ. Выдаёт молча, ничем не выделяя подобное поведение на фоне правильных ответов. Так что, несмотря на всю невероятную вычислительную мощь HP 50g, с этой машинкой надо быть аккуратнее.