Алгоритм вычисления символа Якоби — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} Для вычисления символа Якоби <tex>\left(\cfrac{a}{n}\right)</tex> эффективно использовать…»)
 
м
 
Строка 5: Строка 5:
 
#Если <tex>a<0</tex>, то применяя утверждения [[Символ Якоби и его свойства#proposal2|2]] и [[Символ Якоби и его свойства#proposal5|5]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}</tex>. Вычисляем <tex>\left(\cfrac{-a}{n}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a<0</tex>, то применяя утверждения [[Символ Якоби и его свойства#proposal2|2]] и [[Символ Якоби и его свойства#proposal5|5]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}</tex>. Вычисляем <tex>\left(\cfrac{-a}{n}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a</tex> четно, то применяя утверждения [[Символ Якоби и его свойства#proposal2|2]] и [[Символ Якоби и его свойства#proposal6|6]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}</tex>. Вычисляем <tex>\left(\cfrac{a/2}{n}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a</tex> четно, то применяя утверждения [[Символ Якоби и его свойства#proposal2|2]] и [[Символ Якоби и его свойства#proposal6|6]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}</tex>. Вычисляем <tex>\left(\cfrac{a/2}{n}\right)</tex> и пропускаем последующие пункты.
#Если <tex>a=1</tex>, то применяя утверждение [[Символ Якоби и его свойства#proposal5|5}} <tex>\left(\cfrac{a}{n}\right)=1</tex>, вычисление закончилось.
+
#Если <tex>a=1</tex>, то применяя утверждение [[Символ Якоби и его свойства#proposal5|5]] <tex>\left(\cfrac{a}{n}\right)=1</tex>, вычисление закончилось.
 
#Если <tex>a<n</tex>, то применяя [[Обобщенный квадратичный закон взаимности#th2|теорему 2]] получаем <tex>\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)</tex>. Вычисляем <tex>\left(\cfrac{n}{a}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a<n</tex>, то применяя [[Обобщенный квадратичный закон взаимности#th2|теорему 2]] получаем <tex>\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)</tex>. Вычисляем <tex>\left(\cfrac{n}{a}\right)</tex> и пропускаем последующие пункты.
 
#<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)</tex>. Вычисляем <tex>\left(\cfrac{a\mod n}{n}\right)</tex>. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.
 
#<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)</tex>. Вычисляем <tex>\left(\cfrac{a\mod n}{n}\right)</tex>. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.
 
[[Категория: Теория чисел]]
 
[[Категория: Теория чисел]]

Текущая версия на 18:06, 30 июня 2010

Эта статья находится в разработке!

Для вычисления символа Якоби [math]\left(\cfrac{a}{n}\right)[/math] эффективно использовать следующий алгоритм:

  1. Если [math]a\lt 0[/math], то применяя утверждения 2 и 5, получаем [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}[/math]. Вычисляем [math]\left(\cfrac{-a}{n}\right)[/math] и пропускаем последующие пункты.
  2. Если [math]a[/math] четно, то применяя утверждения 2 и 6, получаем [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}[/math]. Вычисляем [math]\left(\cfrac{a/2}{n}\right)[/math] и пропускаем последующие пункты.
  3. Если [math]a=1[/math], то применяя утверждение 5 [math]\left(\cfrac{a}{n}\right)=1[/math], вычисление закончилось.
  4. Если [math]a\lt n[/math], то применяя теорему 2 получаем [math]\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)[/math]. Вычисляем [math]\left(\cfrac{n}{a}\right)[/math] и пропускаем последующие пункты.
  5. [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)[/math]. Вычисляем [math]\left(\cfrac{a\mod n}{n}\right)[/math]. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.