Что хороший метод должен учесть гауссовы целые числа?

Это оказалось немного многословным, но я надеюсь, что оно полностью ответит на ваш вопрос ...

A Целое число по Гауссу - это комплексное число вида

G = a + bi

где i ² = -1 , а a и b - целые числа.

Гауссовские целые числа образуют уникальную область факторизации. Некоторые из них действуют как единицы (например, 1 , -1 , i и -i ), некоторые - как простые числа (например, 1 + i ), а остальное составное, которое может быть разложено как произведение простых чисел и единиц, которое является уникальным, не считая порядка факторов и наличия набора единиц, произведение которых равно 1 .

норма такого числа G определяется как целое число: norm (G) = a ² + b ² .

Можно показать, что норма является мультипликативным свойством, а именно:

norm (I * J) = norm (I) * norm (J)

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

Простые числа гауссовских целых чисел делятся на три категории:

1 +/- i , с нормой 2 ,

a +/- bi , с простым norm a ² + b ² конгруэнтно 1 mod 4 ,

a , где a - простое число, конгруэнтное 3 по модулю 4 , с нормой a ²

---

Теперь, чтобы превратить это в алгоритм ... если вы хотите разложить на множители целое гауссовское число G , вы можете найти его норму N , а затем разложить ее на простые целые числа. Затем мы продвигаемся вниз по этому списку, удаляя простые множители p из N , которые соответствуют простым гауссовским множителям q нашего исходного номера G .

Осталось рассмотреть всего три случая, и два из них тривиальны.

Если p = 2 , пусть q = (1 + i) . (Обратите внимание, что q = (1-i) будет работать одинаково хорошо, поскольку они отличаются только на единичный коэффициент.)

Если p = 3 mod 4 , q = p . Но норма q равна p ² , поэтому мы можем исключить еще один фактор p из списка оставшихся факторов норма (G) .

Случай p = 1 mod 4 - единственный, с которым немного сложно справиться. Это эквивалентно проблеме выражения p как сумма двух квадратов : если p = a ² + b ² , то a + bi и a-bi образуют сопряженную пару гауссовских простых чисел с нормой p , и один из них будет искомым фактором.

Но немного теории чисел, это оказывается не слишком сложно. Рассмотрим целые числа по модулю p. Предположим, мы можем найти целое число k такое , что k ² = -1 mod p . Тогда k ² +1 = 0 mod p , что эквивалентно утверждению, что p делит k ² +1 в целых числах (и, следовательно, также в целых гауссовских числах). В гауссовых целых числах k ² +1 делится на (k + i) (k-i) . p делит произведение, но не делит ни множитель. Следовательно, p имеет нетривиальный НОД с каждым из факторов (k + i) и (ki) , и что НОД или его сопряженность - это фактор , который мы ищем!

Но как найти такое целое число k ? Пусть n будет некоторым целым числом от 2 до p-1 включительно. Вычислите n ^{(p-1) / 2} mod p - это значение будет либо 1 , либо -1 ]. Если -1 , то k = n ^{(p-1) / 4} , в противном случае попробуйте другой n . Почти половина возможные значения n дадут нам квадратный корень из -1 mod p , поэтому не потребуется много догадок, чтобы найти значение k , что работает.

Чтобы найти гауссовские простые числа с нормой p , просто используйте алгоритм Евклида (слегка измененный для работы с гауссовыми целыми числами) для вычисления НОД {{1} } из (p, k + i) . Это дает один пробный делитель.Если он равномерно делит гауссовское целое число , которое мы пытаемся разложить на множители (остаток = 0), все готово. В противном случае его сопряжение является желаемым фактором.

Алгоритм НОД Евклида для целых гауссовских чисел почти идентичен алгоритму для нормальных целых чисел. Каждая итерация состоит из пробного деления с остатком. Если мы ищем НОД (a, b) ,

q = floor (a / b) , остаток = a - q * b , и если остаток отличен от нуля мы возвращаем gcd (b, остаток) .

В целых числах, если мы получаем дробь в качестве частного, мы округляем ее до нуля.
В целых гауссовских числахесли действительная или мнимая части частного являются дробями, они округляются до ближайшего целого числа. Кроме того, алгоритмы идентичны.

Итак, алгоритм факторизации гауссовского целого G выглядит примерно так :

Вычислить норму (G) , затем разложить на множители норму ( G) на простые числа p ₁ , p ₂ ... p _n .

For each remaining factor p:
   if p=2, u = (1 + i).   
      strike p from the list of remaining primes.
   else if p mod 4 = 3, q = p, and strike 2 copies of p from the list of primes.
   else find k such that k^2 = -1 mod p, then u = gcd(p, k+i)
       if G/u has remainder 0, q = u
       else q = conjugate(u)
       strike p from the list of remaining primes.
   Add q to the list of Gaussian factors.
   Replace G with G/q.
endfor

В конце этой процедуры G - это единица с нормой 1 . Но это не обязательно 1 - это может быть -1 , i или -i , в котором case добавить G в список факторов, чтобы знаки были видны правильно, когда вы умножаете все факторы, чтобы увидеть, соответствует ли произведение исходному значению G .

---

Вот рабочий пример: множитель G = 361 - 1767i по гауссовским целым числам. norm (G) = 3252610 = 2 * 5 * 17 * 19 * 19 * 53

Учитывая 2 , мы пробуем q = (1 + i) и находим G / q = -703 - 1064i с остатком 0 .

G <= G / q = -703 - 1064i

Учитывая 5 , мы видим, что это конгруэнтно 1 mod 4 . Нам нужно найти хорошее k . Попытка n = 2 , n ^{(p-1) / 2} mod p = 2 ² mod p = 4 . 4 конгруэнтно -1 mod 5 . Успех! k = 2 ¹ = 2 . u = gcd (5, 2 + i) , что получается как 2 + i . G / u = -494 - 285i , с остатком 0 , поэтому мы находим q = 2 + i .

G <= G / q = -494 - 285i

Учитывая 17 , это также конгруэнтно 1 mod 4 , поэтому нам нужно найти другой {{1 }} k mod 17 . Попытка n = 2 , 2 ⁸ = 1 mod 17 , ничего хорошего. Попробуйте вместо этого n = 3 . 3 ⁸ = 16 mod 17 = -1 mod 17 . Успех! Итак k = 3 ⁴ = 13 mod 17 . gcd (17, 13 + i) = u = 4-i , G / u = -99 -96i с остатком -2 . Плохо, поэтому попробуйте сопрягать (u) = 4 + i . G / u = -133 - 38i с остатком 0. Еще один фактор!

G <= G / (4 + i) = -133 - 38i

Учитывая 19 , это конгруэнтно 3 mod 4 . Итак, наш следующий множитель - 19 , и мы вычеркиваем вторую копию 19 из списка.

G <= G / 19 = -7 - 2i

Учитывая 53 , это соответствует 1 mod 4 . Снова с помощью процесса k ... Попытка n = 2, 2 ²⁶ = 52 mod 53 = -1 mod 53 . Тогда k = 2 ¹³ mod 53 = 30 . gcd (53,30 + i) = u = -7 - 2i . Это идентично G , поэтому окончательное частное G / (- 7-2i) = 1 , и множители -1 отсутствуют. ], i или -i , о которых нужно беспокоиться .

Мы нашли множители (1 + i) (2 + i) (4 + i) (19 + 0i) (- 7-2i) . И если вы умножите это на (оставлено в качестве упражнения для читателя ...), о чудо, произведение - это 361-1767i , с которого мы начали.

Разве теория чисел не милая?