Есть ли простой способ найти два значения, которые при умножении дают точный битовый шаблон?

Question

В целях тестирования мне нужно найти два 64-разрядных целочисленных значения, которые точно умножаются на 128-разрядное промежуточное значение с определенной битовой комбинацией. Очевидно, я могу генерировать желаемое промежуточное значение и делить на случайные значения, пока не найду комбинацию, которая работает, но есть ли более эффективный способ?

Answer 1

Эта проблема звучит как целочисленная факторизация . К сожалению, быстрых алгоритмов не известно, но, взглянув на эту страницу Википедии, кажется, что есть некоторые (возможно, хитрые) алгоритмы, которые быстрее, чем пробное разделение.

Answer 2

Я собирался опубликовать то же самое, что и j_random_hacker. Я просто добавлю, что если 128-битное число является простым или имеет простой коэффициент, больший, чем 64-битный, то не будет никакого решения вашей проблемы.

Answer 3

И я просто добавлю к предыдущему комментарию: если 128-битное число имеет простой множитель больше, чем 64-битное, то оно, безусловно, имеет коэффициент, меньший, чем 64-битное:)