RSA & Evklid

[relok]

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

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

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

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

делал с int, long, _int64
язык C.
если кто знает в чем дело - напишите plz

Расширенный Эвклид даёт отрицательное число (-3 миллиона с чем то)

это нормально. там вообще бесконечное множество решение. скажи спасибо что еще не решение с минус стопиццот мильонов нашел (можно показать что по абсолютное величине числа ограничены в евклиде максимальным входным)

и быстро иди на первый курс повторять теорию чисел. не позорься тут полным отсутствием элементарных знаний. -3 миилиона по модулю 9 миллионов то же самое что 6 миллионов

[relok]

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

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

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

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

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

да что вы говорите. с теоремой эйлера знакомы? еще один кусочек элемантарной теории чисел (неэлементарная начинается с гипотезы римана, если что). она гласит что если число a перемножить по модулю достаточное число раз, то в конце конце вернешься обратно к своему разбитому корыту - самому числу a (по модулю ессно). очевидно дальше тот же цикл до бесконечности. длина цикла - phi(n). отсюда и модуль.

[relok]

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

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

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

и зачем пытаться повысить свою самооценку за счет унижения других людей?

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

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

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

конечно серьезную ТЧ можно преподавать тока после комплексного анализа

[relok]

первый курс был 5 лет назад xD

[relok]

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

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

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