Сложность факторинга в числовых полях

25

Что известно о вычислительной сложности факторизации целых чисел в полях общего числа? Более конкретно:

  1. Над целыми числами мы представляем целые числа через их двоичные расширения. Что такое аналогичные представления целых чисел в полях общего числа?
  2. Известно ли, что первичность над числовыми полями находится в P или BPP?
  3. Каковы наиболее известные алгоритмы для разложения по числовым полям? (Расширяются ли алгоритмы и (очевидно) от ?) Здесь под факторингом понимается нахождение некоторого представления числа (представленного битами) как продукт простых чисел. ехрп 1 / 3 Zпexpnexpn1/3Zn
  4. Какова сложность поиска всех факторизаций целого числа в числовом поле? Подсчитать, сколько у него разных факторизаций?
  5. Над известно, что решение, имеет ли данное число фактор в интервале является NP-трудным. Над кольцом целых чисел в числовых полях может ли быть так, что обнаружение, что существует простой фактор, норма которого находится в определенном интервале, уже NP-труден? [ a , b ]Z[a,b]
  6. Есть ли факторинг в числовых полях в BQP?

Замечания, мотивы и обновления.

Конечно, тот факт, что факторизация не уникальна для числовых полей, имеет решающее значение. Этот вопрос (особенно часть 5) был мотивирован этим сообщением в блоге через GLL (см. Это замечание ), а также этим более ранним вопросом TCSexchange. Я также представил это в своем блоге, где Лиор Сильверман представил исчерпывающий ответ .

Гил Калай
источник
можешь привести пример? Чем факторинг в полях defn отличается от факторизации с прямым целым числом?
2013 года
2
Для (0): Я думаю, что обычно числовое поле представляется как где - неприводимый многочлен. Тогда элемент является кортежем пар где . Это означает, что ваш элемент - это . Q [ ξ ] /ф ф К ( ( п 0 , д 0 ) , ( п 1 , д 1 ) , ... , ( п δ - 1 , d δ - 1 ) ) δ = град ( ф ) п 0 / d 0 + n 1 ξ / d 1 +KQ[ξ]/φφK((n0,d0),(n1,d1),,(nδ1,dδ1))δ=deg(φ)n0/d0+n1ξ/d1++nδ1ξδ1/dδ1
Бруно
2
@Gil Ты видел эту книгу раньше? springer.com/matgery/numbers/book/978-3-540-55640-4 В данный момент у меня нет доступа к своей копии (хотя я через несколько дней снова и проверю это). Я хотел бы посмотреть, есть ли что-нибудь написанное о факторизации в (i) полях алгебраических чисел или (ii) дедекиндовых областях, с номером класса> 1.
Даниэль Апон
4
@vzn: Не помещая слова в рот Гила, я почти уверен, что он имеет в виду конечное расширение рациональных чисел (именно то, на что вы ссылались). Когда он говорит «факторинг в таком поле», я почти уверен, что он подразумевает факторинг в кольце целых чисел такого поля. На той же странице википедии, на которую вы ссылались, есть раздел с кольцом целых чисел в поле алгебраических чисел.
Джошуа Грохов
1
@vzn Сито числовых полей использует числовые поля для разложения целых чисел.
Юваль Фильмус

Ответы:

14

Следующий ответ был первоначально опубликован как комментарий в блоге Джила

(1) Пусть - числовое поле, где мы предполагаем, что имеет моничный минимальный многочлен . Затем можно представить элементы кольца целых чисел виде полиномов от или в виде целочисленного базиса - оба они эквивалентны.α f Z [ x ] O K αK=Q(α)αfZ[x]OKα

Теперь, фиксируя как в (1), мы получаем полиномиальное сокращение времени от задачи над к проблеме в . Чтобы убедиться, что вычисления (например, пересечение идеала с или факторизация полинома mod ) могут быть выполнены за полиномиальное время, см. Книгу Коэна, на которую ссылаются в предыдущем ответе.K Q Z pKKQZp

В качестве предварительного вычисления для каждого рационального простого числа делящего дискриминант (то есть дискриминанта ), найдите все простые числа лежащие выше .α f O K ppαfOKp

(2) Для проверки простоты, если задан идеальный пусть таков, что (это можно вычислить за полиномиальное время, а количество бит полиномиально на входе). Проверьте за полиномиальное время, является ли простым. Если нет, то не является простым. Если да, то найдите простые числа лежащие выше либо из предварительного вычисления, либо с помощью фактора mod . В любом случае, если является простым, это должно быть одно из этих простых чисел. p Z aZ = p Z p p a O K p f p aaOKpZaZ=pZppaOKpfpa

(3a), (6a) Для разложения на простые числа при заданном идеале найдите его норму . Опять же, это может быть найдено за полиномиальное время и, следовательно, не слишком велико. Коэффициент в (либо классически, либо с использованием алгоритма Шора, в зависимости от желаемого сокращения). Это дает список рациональных простых чисел, разделяющих , и, следовательно, как и в 2, мы можем найти список простых чисел разделяющих . Так как это дает список простых чисел, разделяющих y = N K Q ( a ) = [ O K : a ] y Z y O K y a | y O K aaOKy=NQK(a)=[OK:a]yZyOKya|yOKa, Наконец, легко определить показатель, на который простое число делит данный идеал.

(3b), (6b) Но Гил хочет факторизации в неприводимые, а не простые числа. Оказывается, что при простой факторизации можно эффективно построить одну факторизацию в неприводимые элементы . Для этого пусть будет номером класса и отметим, что можно эффективно вычислить идеальный класс данного идеала. Теперь, чтобы найти неприводимый делитель выберите простых идеалов (возможно, с повторением) из факторизации x O K h K x h K x x h KxOKxOKhKxhKx, По принципу «голубиного отверстия» некоторое подмножество этих множителей умножается на единицу в группе классов; найти минимальное такое подмножество. Тогда его произведение является главным идеалом, порожденным неприводимым элементом. Разделите на этот элемент, удалите соответствующие идеалы из факторизации и повторите. Если факторизация имеет меньше чем элементов, тогда просто возьмите минимальное подмножество всех факторов.xhK

(4) Я думаю, что можно посчитать факторизации в неприводимые, но это немного лишняя комбинаторика - пожалуйста, дайте мне время разобраться. С другой стороны, определение их всех не представляет интереса в контексте алгоритмов субэкспоненциальной факторизации, поскольку таких факторизаций в целом экспоненциально много.

(5) Понятия не имею.

Лиор Сильберман
источник
5

Как упомянул Даниэль, вы можете найти некоторые сведения в книге «Курс теории вычислительных алгебраических чисел» ( ссылка ).

В частности, существует несколько способов представления элементов числовых полей. Пусть числовое поле с градусов- унитарным неприводимым многочленом . Пусть будет любым корнем из . Так называемое стандартное представление элемента - это кортеж где , и , так чтоK=Q[ξ]/φφnZ[ξ]θφαK(a0,,an1,d)aiZd>0gcd(a0,,an1,d)=1

α=1di=0n1aiθi.
Bruno
источник