Автор: Unknown 23.07.2009 16:32
Как это сделать?
Перебирать все числа и проверять их с заданным числом НОД на равенство единице мне кажется долгим, наверное, есть варианты короче?
Что-то типа перебирать простые числа и проверять заданное число на кратность найденному. Но тогда часть решений будет потеряна...
Автор: Lapp 24.07.2009 3:55
Цитата(Unknown @ 23.07.2009 13:32)
Что-то типа перебирать простые числа и проверять заданное число на кратность найденному. Но тогда часть решений будет потеряна...
Не понял - что будет потеряно?
Во-первых, условие ты поставил так, что одного числа будет достаточно (любого). Во-вторых, я не понимаю, что ты можешь потерять. Если нужны все - то добавь к простым еще и их всевозможные произведения.
Проще тут не выйдет. Процесс разложения на множители по своей природе емкий. Не даром на нем основана криптография.. Найдешь простое решение - сможешь вскрывать все шифры, а заодно и Нобеля в карман положишь..))
Автор: Unknown 24.07.2009 19:37
Цитата(Lapp)
Если нужны все - то добавь к простым еще и их всевозможные произведения.
Да, это то, чего не хватало!
Цитата(Lapp)
Процесс разложения на множители по своей природе емкий. Не даром на нем основана криптография.. Найдешь простое решение - сможешь вскрывать все шифры, а заодно и Нобеля в карман положишь..))
На нем основаны только асимметричные шифры, насколько я знаю. Наш ГОСТ не использует факторизацию...
Автор: Lapp 28.07.2009 4:37
Цитата(Unknown @ 24.07.2009 16:37)
На нем основаны только асимметричные шифры, насколько я знаю. Наш ГОСТ не использует факторизацию...
Ессно асимметричные. А ГОСТ еще существует? )))