Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 18.04.2009, 08:29   #1
Камикадзе
 
Регистрация: 24.10.2007
Сообщений: 8
По умолчанию ВЫчисление дробей по модулю целого числа

Суть вопроса такова. Я пытаюсь запрограммировать на СИ алгоритм сложения точек эллиптической кривой над полем Галуа (конечным полем). Но проблема сейчас не в этом. На одном из этапов мне нужно вы числить значение дроби по модулю простого числа (для конкретность пусть p = 23). Все бы ничего, но я приведу такой пример. Один из авторов (Столлингс Вильям) приводит такие примеры (я сохранил последовательность операций).

А = (7-10) / (9-3) = (просто посчитали) = -3/6 = (сократили) = -1 / 2 = 11 (mod 23)
Т.е. автор в последнем действии, как я понимаю, вычислил -1 (mod 23), подставил в дробь, получил 22 / 2, а затем получил ответ 11.

Получается так:
1) Просто вычисляем
2) Сокращаем дробь
3) Вычисляем числитель (и знаменатель?) по модулю 23.
4) Делим нацело

Чуть ниже у этого автора другой пример (несколько другая формула).

А = (3*3^2 + 1) / (2*10) = 5/20 =
(обратите внимание, автор сразу вычисляет числитель по модулю 23. Так бы вместо 5 там должно было быть 28, затем сокращает)
= 1 / 4 = (далее, видимо, если числитель меньше знаменателя, то мы должны прибавить число 23, а потом уже делить) = 6 (mod 23)

То есть алгоритм уже отличается:
1) Просто вычисляем
2) Вычисляем числитель (и знаменатель?) по модулю 23.
3) Сокращаем дробь
4) Делим нацело

Если посчитать эту же дробь по первому алгоритму, то получим следующее:
А = (3*3^2 + 1) / (2*10) = (посчитаем) = 28/20 = (сократим) = 7 / 5 = 1 (mod 23)

Разъясните пожалуйста, как это должно быть. Литературу мне найти не удалось, поэтому приходится вот так угадывать.

Последний раз редактировалось Камикадзе; 18.04.2009 в 08:31.
Камикадзе вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
сумма цифр целого числа mihsel Microsoft Office Excel 8 13.04.2009 12:57
Вычисление числа Е и arcsin или arccos qip2005 Паскаль, Turbo Pascal, PascalABC.NET 10 08.12.2008 10:36
разработать функцию, которая определяет сумму цифр целого числа IceAgainstIce Общие вопросы Delphi 5 20.11.2008 00:52
вычисление больших степеней по модулю - Rsa Студент Общие вопросы C/C++ 2 19.10.2007 17:28
Вычисление факториала числа PAVEL315 Общие вопросы Delphi 17 21.03.2007 07:32


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS