Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.04.2009, 09: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 в 09:31.
Камикадзе вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
сумма цифр целого числа mihsel Microsoft Office Excel 8 13.04.2009 13: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 18:28
Вычисление факториала числа PAVEL315 Общие вопросы Delphi 17 21.03.2007 07:32