Какой хороший метод для вычисления гауссовых целых чисел? - PullRequest
Новая
       18

Какой хороший метод для вычисления гауссовых целых чисел?

30 голосов
/ 16 февраля 2010

У меня уже есть первичная факторизация (для целых чисел), но теперь я хочу реализовать ее для гауссовых целых чисел, но как мне это сделать? спасибо!

Ответы [ 2 ]

68 голосов
/ 16 февраля 2010

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

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

G = a + bi

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

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

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

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

норма (I * J) = норма (I) * норма (J)

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

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

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

a +/- bi , с основной нормой a 2 + b 2 в соответствии с 1 mod 4 ,

a , где a - простое конгруэнтное с 3 mod 4 , с нормой a 2

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

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

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

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

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

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

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

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

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

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

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

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

Рассчитать норма (G) , тогда коэффициент норма (G) в простые числа p 1 , p 2 ... 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 , в этом случае добавьте G к списку факторов, чтобы сделать знаки правильными, когда вы умножите все факторы, чтобы увидеть, соответствует ли продукт исходному значению G .

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

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

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

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

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

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

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

Учитывая 19 , оно совпадает с 3 mod 4 .Таким образом, наш следующий фактор - 19 , и мы удаляем вторую копию 19 из списка.

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

Учитывая 53 , оно совпадает с 1 mod 4 .Снова с процессом k ... Попытка n = 2, 2 26 = 52 mod 53 = -1 mod 53 .Тогда k = 2 13 мод 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 , это число, с которого мы начали.

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

0 голосов
/ 16 декабря 2015

Используйте числа с плавающей запятой для вещественных и мнимых компонентов, если вам нужна полная целочисленная точность для одной ячейки, и задайте gsub, gmul и специальный gdivr с округленными коэффициентами, а не по полу Это потому, что метод факторизации Полларда нуждается в gcd с помощью алгоритма Евклида с немного измененным gmodulo: 

gmodulo((x,y),(x',y'))=gsub((x,y),gmul((x',y'),gdivr((x,y),(x',y'))))

Поллард Ро 

def poly((a,b),(x,y))=gmodulo(gsub(gmul((a,b),(a,b)),(1,0)),(x,y))

input (x,y),(a,b) % (x,y) is the Gaussian number to be factorized
(c,d)<-(a,b)
do 
   (a,b)=poly((a,b),(x,y))
   (c,d)=poly(poly((c,d),(x,y)),(x,y))
   (e,f)=ggcd((x,y),gsub((a,b),(c,d)))
   if (e,f)=(x,y) then return (x,y) % failure, try other (a,b)
until e^2+f^2>1
return (e,f)

Нормальным начальным значением является a = 1, b = 0.

Я использовал этот метод, запрограммированный в Forth, в моем блоге http://forthmath.blogspot.se

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

...