Это «исторический вопрос» больше, чем вопрос исследования, но было ли классическое сведение к нахождению порядка в алгоритме факторизации Шора первоначально обнаруженным Питером Шором, или это было известно ранее? Есть ли статья, описывающая сокращение, предшествующее Шору, или это просто так...
Книга Ароры и Барака представляет факторинг как следующую проблему: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}Факторингзнак равно{⟨L,U,N⟩|(∃ простое число п∈{L,...,U})[п|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Далее в...
Это кросс-пост от math.stackexchange. Обозначим через FACT целочисленную задачу факторинга: для найдите простые числа и целые числа такие чтоp i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},пя∈ N ,pi∈N,p_i \in \mathbb{N},ея∈ N ,ei∈N,e_i \in \mathbb{N},n = ∏Кя =...
Пусть PRIMES (иначе тестирование на примитивность ) будет проблемой: Учитывая натуральное число , является простое число?NNnNNn Пусть FACTORING будет проблемой: Учитывая натуральные числа , с , имеет ли фактор с ?NNnммm1 ≤ m ≤ n1≤м≤N1 \leq m \leq nNNnddd1 < д< м1<d<м1 < d < m Известно...
Факторинг не известен как NP-полный. Этот вопрос задавался о последствиях факторинга, являющегося NP-полным. Любопытно, что никто не спрашивал о последствиях факторинга в P (возможно, потому что такой вопрос тривиален). Итак, мои вопросы: Какими будут теоретические последствия факторинга в P? Как...
Учитывая целое число длиной битов, насколько сложно вывести число простых факторов (или, альтернативно, число факторов) из ?n NNNNNnnNNN Если бы мы знали первичную факторизацию , то это было бы легко. Однако, если бы мы знали количество основных факторов или число общих факторов, неясно, как мы...
Сегодня в блоге Скотта Ааронсона приведен список интересных открытых задач / задач по сложности. Один из них привлек мое внимание: Создайте публичную библиотеку из 3SAT-экземпляров, используя как можно меньше переменных и предложений, что может привести к значительным последствиям в случае ее...
Есть ли какие-либо ссылки на
Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 3 года назад . В научной статье 2016 года « Реализация масштабируемого алгоритма Шора » [ 1 ] авторы учитывают 15 с только 5 кубитами, что меньше «требуемых» 8 кубитов...
Я ищу ссылку на следующий результат: Добавление двух целых чисел в факторизованном представлении так же сложно, как и деление двух целых чисел в обычном двоичном представлении. (Я уверен, что это там, потому что это то, что я когда-то задавался вопросом, а затем был взволнован, когда я наконец...
Хорошо известно, что модульное возведение в степень (основная часть операции RSA) является вычислительно дорогим, и, насколько я понимаю, метод модульного возведения в степень Монтгомери является предпочтительным методом. Модульное возведение в степень также заметно присутствует в алгоритме...
В своей статье 1995 года « Алгоритмы полиномиального времени для первичной факторизации и дискретных логарифмов на квантовом компьютере» Питер У. Шор обсуждает усовершенствование порядка упорядочения своего алгоритма факторизации. Стандартные выходы алгоритма r′r′r' , делитель порядка rrr из xxx по...
Я только что прочитал вопрос « Является ли целочисленная факторизация NP-полной проблемой? » ... поэтому я решил потратить часть своей репутации :-), задавая еще один вопрос с :QQQP(Q is trivial)≈1п(Q тривиально)≈1P(\text{Q is trivial}) \approx 1 Если является оракулом, который решает целочисленную...
Читая блог Дика Липтона, я наткнулся на следующий факт в конце его поста о факторе Борна : Если для каждого существует отношение вида где , и каждый из , и является по длине в битах, тогда факторинг имеет полином размерные схемы.( 2 n ) ! = m - 1 ∑ k = 0 a k b c k k m = p o l y ( n...
В « Совете начинающему аспиранту » Мануэля Блума : Леонид Левин верит, как я это делаю, какой бы ни был ответ на P = NP? проблема, это не будет так, как вы думаете, должно быть. И он привел несколько замечательных примеров. Например, он дал ФАКТОРИНГОВЫЙ АЛГОРИТМ, который оказался оптимально...
Учитывая композит N∈NN∈NN\in\Bbb N общего числа поля решета является наиболее известным алгоритмом факторизации для целого факторизации NNN . Это рандомизированный алгоритм, и мы получаем ожидаемую сложность O(e649√(logN)13(loglogN)23)O(e649(logN)13(loglogN)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log...
В 1975 году Миллер показал, как уменьшить факторизацию целого числа чтобы найти период функции такой, что f (x + r) = f (x) с некоторым случайно выбранным <N . Хорошо известно, что алгоритм Шора может эффективно найти r на квантовом компьютере, в то время как считается, что классическому...