Факторинговые большое количество

Question

Можно создать дубликат:
Factor a large number efficiently with gmp

Я знаю, что я уже писал, но люди не поняли, что я имел в виду, и, пока я не установил его пост умер.
Что мне нужно - это способ эффективно распределять (находить простые множители числа) большие числа (может достигать 2048 бит) с использованием C++ и GMP (Gnu Multiple Precession lib) или менее предпочтительно любым другим способом.
Цифры практически случайны, поэтому мало шансов, что это будет сложно определить, и даже если число трудно подвергнуть сомнению, я могу повторно набрать номер (не могу выбрать).
Как это сделать?

Answer 1

Вы пробовали quadratic sieve или general number field sieve? (QS проще и проще в реализации, нефакторных услуг быстрее для очень больших чисел, но ваши номера не может быть достаточно большим для нефакторных услуг гораздо быстрее, чем QS)

редактировать: Согласно a paper by Eric Landquist, точке пересечения между СМО и GNFS составляет около 110 цифр = приблизительно 365 бит.

Answer 2

Нет эффективного способа (возможно). Это предположение является основой современной криптографии.

Answer 3

Способ эффективного использования приведет к нарушению многих используемых в настоящее время алгоритмов шифрования.
Это проблема с NPC, поэтому ....

Answer 4

Если я не пропущу ничего, Это, как известно, является «трудной» проблемой. http://en.wikipedia.org/wiki/Integer_factorization. то есть в настоящее время невозможно.

Answer 5

Существует не известный способ эффективного учета больших чисел. См. Wikipedia для обсуждения причин и уровня техники.

Как отмечалось в комментариях, трудность этой проблемы лежит в основе современной современной криптографии, в частности шифрования с открытым ключом.

Что вы можете сделать может do - это таблица небольших простых чисел и работа через этот стол, разделяющий ваше большое число на каждый кандидат, насколько это возможно. Если число «слишком тяжелое» (т. Е. У вас заканчиваются небольшие простые числа), то повторно переверните.

Answer 6

http://en.wikipedia.org/wiki/General_number_field_sieve

Успехов!

Answer 7

Почему, на ваш взгляд, это не сложно. Да, будут небольшие факторы. Но остальное будет достаточно большим в таком размере, что часто будет зависеть какая-то серьезная работа.

Я предлагаю пробные подразделения несколькими небольшими штрихами, чтобы вытащить маленькую рыбу из пруда. Тогда вы можете попробовать метод Роллард по методу Ро, но я сомневаюсь, что у него есть шанс на числа с таким количеством бит. Лучше было бы квадратное сито.