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

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

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

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


07:25.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.