Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #21  
Старый 13.06.2009, 15:17
_persicum_

 
Сообщений: n/a

или лучше это:

13^(-1) mod 257 чему равно?
  #22  
Старый 13.06.2009, 18:20
zhekas

 
Сообщений: n/a

для простых p: a^(p-1)=1mod p, Следовательно a^(-1) mod p = a^(p-2) mod p.
2^(-1) mod p=2^(7-2) mod 7 =32 mod 7 =4. (хотя для маленьких p и число легко подбирается)

Соответственно: 13^(-1) mod 257 = 13^255 mod 257=(13^3)^85 mod 257=
=141^85 mod 257 =(141^2)^42*141 mod 257=92^42*141 mod 257 =
(92^2)^21*141 mod 257=(-17)^21*141 mod 257= ((-17)^3)^7*141 mod 257=
(-30)^7*141 mod 257 = -79 mod 257= 178 mod 257
Проверка 13*178 mod 257=1 верно.

Почитайте: Виноградов "Основы теории чисел". Там всё подробно расписано.
  #23  
Старый 13.06.2009, 20:40
_persicum_

 
Сообщений: n/a

А на калькуляторе Виндовс, который считает с большой точностью, можно так

13
*=
*=
*=
*=
*=
*=
*=
*=
/13=
mod257=

получаем 178
  #24  
Старый 14.06.2009, 04:28
гость

 
Сообщений: n/a

G3E84Y
13^255 Это порятка 285 знаков. (255 log_10 13 = 284,05). А если взять например p=2417. Тоесть 13^(-1) mod 2417. Вы так долго в квадрат не навозводитесь. Тогда уж лучше возводить в квадрат по модулю.
  #25  
Старый 12.03.2010, 18:07
гость

 
Сообщений: n/a

читал... пере-читал... пере-пере-читал... мозЬг просто взорвало
вывод: похоже я даун

интересно, как будет выглядеть блок-схема раелизующая алгоритм "деления в столбик" чисел с запятой, ну скажем, 4096 бит размера всего за один такт выполнения?

мой комп с такими числами отчего то не дружит

8(
  #26  
Старый 30.07.2010, 10:57
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

а где ты нашел дробное число длины 4096 бит?
fpu считает только 80-ти битные числа, так что в ближайшие года компьютер, "дружащий" с такими числами, врятли появится
  #27  
Старый 30.07.2010, 19:14
гость

 
Сообщений: n/a

Сообщение от deosis Посмотреть сообщение
а где ты нашел дробное число длины 4096 бит?
fpu считает только 80-ти битные числа, так что в ближайшие года компьютер, "дружащий" с такими числами, врятли появится
80 бит для вас предел? Не смешите мои тапочки.

Люди и на обычных pentium'ах уже сегодня вычисляют пи до 2 триллионов десятичных знаков (16 триллионов бит) - http://bellard.org/pi/pi2700e9/announce.html
  #28  
Старый 30.07.2010, 20:51
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

что Вы понимаете под одним тактом выполнения?
еще не существует архитектуры, работающей с числами такой большой разрядности.
А в Ваших примерах использовалась длинная арифметика и ДПФ(на векторах)
Если можете, приведите ссылку на описание серийных устроуств большой разрядности
  #29  
Старый 31.07.2010, 13:08
_persicum_

 
Сообщений: n/a

Есть микросхемы реализующие RSA и другие асимметричные алгосы. Только там модуль берется конечно после каждого возведения в кавадрат.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вывести значение целочисленного выражения, заданного в виде строки S в delphi SergeyHelpMe Математические алгоритмы 5 12.06.2008 12:59
не пойму условия задачи indolent Задачи 2 19.05.2008 07:32
Распознование регулярного выражения Programmer Реализация, исходники, языки 3 29.04.2008 17:23