Форум программистов, компьютерный форум, киберфорум
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/22: Рейтинг темы: голосов - 22, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 16.01.2013
Сообщений: 59
1

Алгоритм Гарнера. Китайская теорема об остатках

30.03.2013, 19:31. Показов 4237. Ответов 2
Метки нет (Все метки)

Здравствуйте. Реализую сейчас алгоритм Полига-Хеллмана для вычисления дискретного логарифма. И вот осталось только сделать метод для решения уравнений вида, например: x = 1 mod 4 , x = 2 mod 5 , x = 4 mod 3. Вообщем читал что нужно с помощью китайской теоремы об остатках или алгоритма Гарнера. Но не могу разобраться совсем. Не могли бы вы объяснить как она работает? Или может у кого-то есть код на c# или Java.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.03.2013, 19:31
Ответы с готовыми решениями:

Возведение в степень по составному модулю (теорема об остатках)
Помогите разобраться, как поступать, если модуль раскладывается не на два простых (и взаимно...

Китайская теорема об остатках
когда коэфф взаимно простые, решение понятно но вот , например 2x =1mod(4) 4x=1(mod2) без...

Китайская теорема об остатках
товарищи есть у кого-то исходный код на Си который реализует данную теорему или может знаете где...

Теорема об остатках
завтра сдать надо((

2
4406 / 3410 / 345
Регистрация: 12.03.2013
Сообщений: 5,893
31.03.2013, 02:29 2
Вот же формула из вики, не подходит?
https://www.cyberforum.ru/cgi-bin/latex.cgi?x := \sum_{i} a_i \frac{N}{n_i} ((\frac{N}{n_i})^{-1})_{n_i}
http://en.wikipedia.org/wiki/C... neral_case
1
0 / 0 / 0
Регистрация: 16.01.2013
Сообщений: 59
31.03.2013, 02:40  [ТС] 3
Всё я уже разобрался. Хорошо работает и очень прост в реализации на мой взгляд алгоритм Гаусса. По первой же ссылке в гугле можно псевдокод посмотреть.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.03.2013, 02:40

Китайская теорема. Информ. безопасность
Китайская теорема. Помогите ребят перевести с pascal на C++ var x,s:uint64; yy,nn,mm,kk:array ...

Составить алгоритм, определяющий, является ли конечный неориентированный граф гамильтоновым (теорема Дирака)
Ребята помогите составить алгоритм пожалуйста, с помощью которого для любого конечного...

Теорема Ферма и теорема Безу
Уважаемые господа, предлагаю вашему вниманию доказательство Великой теоремы Ферма с помощью...

Покажите, что если бы теорема Райса–Успенского была неверна, то и теорема Клини была бы неверна
Покажите, что если бы теорема Райса–Успенского была неверна, то и теорема Клини была бы неверна.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.