Метод факторизации Ферма

Правка ru1, от NVAL, 2015-10-09 18:49:01

Доброго времени суток!
Окончательно запутался с этим методом и прошу помощи у более опытных и знающих членов сообщества.
Допустим есть число до 1018, требуется его факторизовать.
Очевидно, что делители до 106 легко перебираются в лоб. Остальные делители будем, допустим, искать методом факторизации Ферма. Какова будет сложность в худшем случае?
2 года назад в тренировке 2011-2012 Waterloo Local Contest, 19 June, 2011 я сдал задачу на факторизацию с 106 итерациями и с тех пор поверил, что этот метод фактически работает за кубический корень для чисел до 1018.
Однако теперь я внезапно наткнулся на то, что число 100000007700000049 = 1000000007 * 100000007 совсем не хочет раскладываться с таким количеством шагов. Причиной заблуждения, что тот код был верный оказались предельно слабые тесты (в тестах было лишь на 2 числа больше, чем в примерах входных данных)
Теперь хочется узнать — это неверное понимание работы метода или его неверное применение?
Пример кода можно найти на e-maxx

Теги факторизация, ферма

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский NVAL 2015-10-09 18:49:01 1128 Первая редакция (опубликовано)