Вопрос № 49728: Здравствуйте, эксперты.
Есть следующая проблема. Дано натуральное число A, нужно найти для него такое натуральное B, чтобы A и B были взаимно простые. Я понимаю, что в таком случае B не единственно, поэтому в идеале хотелось бы, чтобы его можно б...
Вопрос № 49.728
Здравствуйте, эксперты.
Есть следующая проблема. Дано натуральное число A, нужно найти для него такое натуральное B, чтобы A и B были взаимно простые. Я понимаю, что в таком случае B не единственно, поэтому в идеале хотелось бы, чтобы его можно было случайно получить из множества всех взаимно простых с A. Можно конечно случайно выбирать B из множества натуральных, а потом проверять общие делители у A и B. Но дело в том, что a 100-значное число и b нужно такое же большое. Пробовал ковырять алгоритм Евклида, но пока безуспешно.
Есть ли у вас какие-нибудь мысли или ссылки по этому вопросу?
Заранее благодарен.
Отправлен: 20.07.2006, 18:22
Вопрос задал: Byter (статус: 2-ой класс)
Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 4)
Отвечает: Татьяна
Здравствуйте, Byter!
Я вижу вы решили увлечься криптографией. Если я не ошибаюсь, данная задача эквивалентна задачи факторизации (разложения на простые множители) больших чисел. А на сегодняшний день не найдено полиномиальных (быстрых) алгоритмов, выполняющих данную задачу. Иначе не работало бы шифрование с открытым ключом.
В принципе вы можете самостоятельно поискать ссылки по слову "факторизация".
На сколько я помню есть вероятностные алгоритмы. Вообщем попробуйте поискать, а я если что-то найду, скину в личку
--------- Возможно все. И ничего возможно тоже.
Ответ отправила: Татьяна (статус: Студент)
Ответ отправлен: 20.07.2006, 18:48 Оценка за ответ: 5 Комментарий оценки: Спасибо. Вы угадали, действительно пытаюсь понять методы реализации RSA. Там как раз при генерации ключа нужно выбрать большое e взаимно простое с f(p*q), где f - функция Эйлера, а p и q - простые. К сожалению мат. реализации этого шага я пока не нашел :(
