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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.11.2010, 15:40
Новичок

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

RSA & Evklid
делаю лабу - RSA
всё работает кроме евклида
то есть работает, но с числами из вики p=3557 q=2579
Расширенный Эвклид даёт отрицательное число (-3 миллиона с чем то) и соответственно алгоритм ломается

сейчас беру p=1543 , q=1549. всё ок. шифрует и дешифрует

но это нечестно. хочется с теми числами xD

Эвклидов писал свои, использовал уже готовые с мануалов. результат один

делал с int, long, _int64
язык C.
если кто знает в чем дело - напишите plz
  #2  
Старый 12.11.2010, 15:47
гость

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

Цитата:
Расширенный Эвклид даёт отрицательное число (-3 миллиона с чем то)
это нормально. там вообще бесконечное множество решение. скажи спасибо что еще не решение с минус стопиццот мильонов нашел (можно показать что по абсолютное величине числа ограничены в евклиде максимальным входным)

и быстро иди на первый курс повторять теорию чисел. не позорься тут полным отсутствием элементарных знаний. -3 миилиона по модулю 9 миллионов то же самое что 6 миллионов
  #3  
Старый 12.11.2010, 16:35
Новичок

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

-3 миилиона по модулю 9 миллионов то же самое что 6 миллионов

вы о чем? в формуле число возводится в эту степень (отрицательную). модуль по другому берут.

у меня получается : ~4kk^(~-3kk)mod~9kk
~ - примерно

если я вообще бред пишу, то скажите. я с криптографией как раз первый раз сталкиваюсь.

Последний раз редактировалось relok, 12.11.2010 в 16:44.
  #4  
Старый 12.11.2010, 16:45
гость

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

Сообщение от relok Посмотреть сообщение
вы о чем? в формуле число возводится в эту степень (отрицательную). модуль по другому берут
да что вы говорите. с теоремой эйлера знакомы? еще один кусочек элемантарной теории чисел (неэлементарная начинается с гипотезы римана, если что). она гласит что если число a перемножить по модулю достаточное число раз, то в конце конце вернешься обратно к своему разбитому корыту - самому числу a (по модулю ессно). очевидно дальше тот же цикл до бесконечности. длина цикла - phi(n). отсюда и модуль.
  #5  
Старый 12.11.2010, 17:00
Новичок

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

спасибо . разобрался и получил то что нужно
на самом деле в первой лабе такая же проблема была, а я забыл

я не собираюсь серьезно заниматься криптографией => ваши упрёки принимаю

но вам правило на будущее: все люди в чем то не шарят

и зачем пытаться повысить свою самооценку за счет унижения других людей?
  #6  
Старый 12.11.2010, 17:05
гость

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

так я не про криптографию вам рассказывал, а про теорию чисел. как бы разные совсем дисциплины, не находите? теория чисел в серьезных вузах это материал первого курса.
  #7  
Старый 12.11.2010, 17:07
гость

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

Сообщение от гость Посмотреть сообщение
теория чисел в серьезных вузах это материал первого курса.
элементарная теория чисел.

конечно серьезную ТЧ можно преподавать тока после комплексного анализа
  #8  
Старый 12.11.2010, 17:09
Новичок

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

первый курс был 5 лет назад xD
  #9  
Старый 12.11.2010, 17:34
Новичок

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

а как вообще это реализуется?
к примеру читаю файл, беру первый символ
он = 255
кодируется как 7407872

и как это чудо записать в файл?
с учетом того, что могу записать от 0 до 255?

или писать это в разные байты? но тогда бред - 1 байт кодируем семью

Последний раз редактировалось relok, 12.11.2010 в 17:39.
 


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

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