Вопрос об отношениях между двумя числами

Есть ли какая-либо связь между битами чисел, когда одно делится на другое? Какова связь между битами 36 и битовыми последовательностями 9 или 4 или 12, или между 10 (1010) и 5 ​​(101), или 21 (10101) и 7 (00111)?

Благодарю. Прошу прощения, если какое-то предложение неверно, но я надеюсь, вы понимаете, чего я хочу.

Источник

5 ответов

Решение

Давайте возьмем пример 36.

36 = 0010 0100

36 является 4 * 9, то есть

 4 = 0100
 9 = 1001

Если вы умножите их (как при обычном умножении), вы получите

    0100 x
    1001
 --------
    0100
   0000
  0000
 0100
 -------
 0100100

Так по сути 0100 x 1001 = 0010 0100 (Вы можете повторить то же самое для любой другой пары делителей, конечно)

Есть ли какое-то особое отношение, которое позволит вам получить все делители 36, просто взглянув на их биты? Ответ, увы, нет:)

РЕДАКТИРОВАТЬ: по крайней мере, нет ИЗВЕСТНОГО отношения, но, кто знает, в будущем, возможно, какой-нибудь умный математик найдет его. На сегодняшний день ответ до сих пор нет.

Источник

Я знаю, что это не совсем то, что вы спрашиваете, но это может быть полезно. Существует много приемов для установления делимости двоичных чисел путем манипулирования битами. Например, двоичное число делится на три, если сумма его четных двоичных битов минус сумма его нечетных двоичных битов, весь модуль 3 равен нулю. Вот ссылка, обсуждающая бинарную делимость.

Источник

Итак, вы хотите знать, сможете ли вы "быстро" выполнить целочисленную факторизацию, просто взглянув на биты?

Удачи с этим!

Источник

Очевидно, что a это кратное b можно распознать, учитывая двоичные представления a а также b (это то, что делает аппаратное обеспечение при выполнении следующего кода

boolean isMultiple = a % b == 0;

) и, следовательно, есть такие отношения.

Задайте более конкретный вопрос, чтобы получить более конкретный ответ...

Источник

Проще всего увидеть число последовательных 0 в младших разрядах, обозначающее наибольшую степень двух, которая является фактором вашего числа n. Очевидно, есть и другие тесты, как указал DonnyD (я этого не знал), но я ожидаю, что они не очень хорошо масштабируются. Если бы они это сделали, криптография с открытым ключом, как это обычно делается, быстро ушла бы в прошлое.

Нельзя сказать, что такие методы не могут быть обнаружены / изобретены. Например, было показано, что произвольно большие числа можно легко вычислить с помощью квантовых методов, но никто никогда не был в состоянии реализовать работающую систему.

Суть в том, что мы доверили нашу онлайновую финансовую систему и аппарат национальной безопасности методам, основанным на PKI, в первую очередь потому, что мы предполагаем, что факторинг цифр сложен для сколь угодно больших чисел. Но, как Морон, казалось, подразумевал в своем ответе, вы можете дать ему вихрь.

Источник
Другие вопросы по тегам