Задача состоит в том, чтобы найти нетривиальный множитель составного числа.

Напишите код, который находит нетривиальный фактор составного числа как можно быстрее, при условии, что ваш код имеет длину не более 140 байт. Результат должен быть просто фактором, который вы нашли.

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

Тестовые случаи, в которых перечислены все факторы (вам нужно вывести только один)

187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873 
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697

Я не буду оценивать ваш ответ в следующем сложном тестовом примере, который может представлять интерес для тестирования:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

Гол

Ваша оценка - это суммарное время для факторизации всех приведенных выше тестовых случаев со штрафом 10 минут за каждую неудачную факторизацию (все округляются до ближайшей секунды). Ваш код должен работать и для других целых чисел, то есть не должен просто кодировать эти ответы.

Я остановлю ваш код через 10 минут.

Если два человека получают одинаковый результат, тогда выигрывает первый ответ.

ограничения

Ваш код не может использовать встроенную или библиотечную функцию, которая выполняет целочисленную факторизацию. Вы можете предположить, что ввод занимает менее 256 бит. Все вводимые числа будут составными.

Как я буду время?

Я буду в буквальном смысле запускать time ./myprogв своей системе Ubuntu для определения времени, поэтому, пожалуйста, предоставьте мне полную программу для запуска, которая включает в себя любую функцию, которую вы определили.

Примечание для скомпилированных языков

Время компиляции должно занимать не более 1 минуты на моей машине.

Это действительно возможно?

Если вы игнорируете ограничения по пространству, то каждый из них может быть учтен менее чем за 2 секунды на моем компьютере, используя чистый код Python + pypy.

Так что же такое нетривиальный алгоритм факторинга?

Алгоритм Полларда быстрый и подходит для игры в гольф. Конечно, есть и много других способов разложить целое число .

Еще быстрее работает квадратичное сито . Это похоже на серьезную проблему, чтобы сжать это в 140 байтов.

Ведущие баллы

• SEJPM , 10 минут штрафа за последний контрольный пример + 16 секунд в Haskell

Haskell, 100 97 91 89 87 72 67 байт

Попробуйте онлайн!

-3 байта благодаря @flawr
-6 байтов благодаря @flawr снова
-2 байта благодаря @flawr еще раз
-2 байта благодаря оптимизированному набору параметров
-1 байт благодаря @flawrs еще один раз
-14 байтов благодаря требованию только чтобы вывести один фактор
-5 байтов благодаря @AndersKaseorg

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

Это работает для первых 5 тестовых случаев в незаметное время.
Это, вероятно, приведет к превышению времени ожидания на самом большом тестовом примере

В общем случае это обычно возвращает один нетривиальный фактор во времени, пропорциональный квадратному корню из наименьшего фактора.
Он не будет работать на каждом входе, потому что он не меняет полином, и обнаружение исключительного случая трудно сделать в 140 байтах.
Это также не будет выводить полную факторизацию, а скорее нетривиальный фактор и деление затрат на этот фактор.
Это также не будет сортировать факторы по размеру.

Используется метод Полларда-Ро-Факторинга со стандартным начальным значением 2 (со стандартным x^2+1многочленом, примененным один раз) и нестандартным постоянным множителем полинома 7 (потому 1что не работал с 1679) для всех дальнейших оценок.

Полная программа ( factor.hs):

import System.Environment(getArgs)

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

main= do
      args <- getArgs
      print$f (read $ head args :: Integer)

Компилировать как $ ghc factor.hs(необходимо ghcустановить).
Запустить как $ ./factor <number>.

Пример выполнения:

$ ./factor 187
11

Ungolfed код:

f n=g 5 (s 5)
   where s x=mod(x*x+7)n
         g a b = if d>1 then d else g(s a)(s(s b))
               where d=gcd(b-a)n

Вычисляет нетривиальный фактор, вызывая gс начальными значениями. Здесь многочлен предварительно применяется к 2 и повторно применяется к результату (5), так что входные данные g(в предложении «где» ) всегда могут быть легко использованы для gcd-теста. g(версия для игры в гольф использует infix #) затем пытается вычислить нетривиальный коэффициент d(в предложении where в версии без игры, действующий в версии для игры в гольф) как разность между двумя входными данными, чтобы g, если это удастся, возвращает указанный коэффициент Остальное повторяется. Здесь он может генерировать nв качестве выходных данных, если a==bи, следовательно, возвращает только тривиальный коэффициент, правильный подход для обработки этого заключается в том, чтобы либо изменить начальные значения для этого события, либо изменить полином.

Пари / ГП , 137 байт, ~ 5 секунд

Используя встроенные операции эллиптической кривой GP _{(и некоторые скрытые настройки параметров)} :

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

ecmэто функция, которая (должна) возвращать фактор Попробуйте онлайн!

Тестовое задание:

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

{
ns = [
  187,
  1679,
  14369648346682547857,
  34747575467581863011,
  52634041113150420921061348357,
  82312263010898855308580978867,
  205255454905325730631914319249,
  1233457775854251160763811229216063007,
  1751952685614616185916001760791655006749
  ]
}

test(n) = {
    d = ecm(n);
    if (!(1<d && d<n && n%d==0), error(d));
    print(n, ": ", d)
}

apply(test, ns)

quit

Ungolfed:

ecm(n) = {
  iferr(if(n%2 == 0, 2,
           n%3 == 0, 3,
           for(a = 1, n,
               /* x^3 + A*x + B = y^2 */
               E = ellinit(Mod([a, a^2-a-1], n)); /* [A, B] */
               x0 = [1, a]; /* [x, y] */
               B = ceil(4^a^0.5); /* ~ exp(sqrt(log(p))), p ~= exp(a) */
               print("a=", a, ", B=", B);
               ellmul(E, x0, lcm([1..B]))
              )
          ),
         ERR, gcd(n, lift(Vec(ERR)[3] /* = Mod(d, n) */)),
         errname(ERR)=="e_INV")
}

К сожалению, обработка факторов 2 и 3 использует много байтов. Байты, которые можно было использовать для добавления этапа 2:

ecm(n)=iferr(for(a=1,n,Y=X=ellmul(E=ellinit(Mod([a,1],n)),[0,1],(B=ceil(4^a^0.5))!);for(z=0,9*B,Y=elladd(E,Y,X))),e,gcd(n,lift(Vec(e)[3])))

Аксиома, 137 байт 9 минут

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

выше функции p (), которая будет реализовывать алгоритм p-1 для факторинга, ниже того, что копировать в файл для проверки функции p ()

-- one has to copy this below text in a file name for example file.input
-- in one window where there is Axiom one could write 
-- )read C:\absolutepathwherethereisthatfile\file
-- and call the function test()
-- test()
-- the first character of all function and array must be afther a new line "\n"
)cl all
)time on
vA:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

-- this would try to factor n with p-1 Pollard method
pm1(n:PI):PI==
   j:=1;a:=3;s:=n^.2
   repeat
      b:=j:=nextPrime(j)
      repeat(b<s=>(b:=b*j);break)
      a:=powmod(a,b,n)
      d:=gcd(a-1,n);d>1 or j>n=>break
   d

test()==(for i in 1..#vA repeat output [vA.i, p(vA.i)])

результаты здесь:

(5) -> test()
   [187,11]
   [1679,73]
   [14369648346682547857,9576890767]
   [34747575467581863011,9576890767]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,311111111111113]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
   [1751952685614616185916001760791655006749,36413321723440003717]
                                                               Type: Void
                              Time: 496.78 (EV) + 53.05 (GC) = 549.83 sec

Аксиома, 10 минут + 31 секунда

A(a)==>a:=(a*a+7)rem n;z(n)==(p:=a:=b:=101;for i in 1..repeat(A(a);A(b);A(b);p:=mulmod(p,a-b,n);i rem 999<9=>(p:=gcd(p,n);p>1=>break));p)

z () - функция rho, одна функция 137 байт; Разгладьте z () и назовите его как rho (). Предполагается, что gcd (0, n) = n, поэтому цикл останавливается и возвращается для сбоя n.

)time on    
rho(n)==
  p:=a:=b:=101
  for i in 1..repeat
          A(a);A(b);A(b)
          p:=mulmod(p,a-b,n)
          i rem 999<9=>(p:=gcd(p,n);p>1=>break)
  p

va1:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]
p1()==(for i in 1..#va1-1 repeat output [va1.i,z(va1.i)]) 

результаты (z () в порядке для всех, кроме последнего числа 1751952685614616185916001760791655006749 остаются не учтенными (10 минут))

(6) -> p1()
   [187,17]
   [1679,23]
   [14369648346682547857,1500450271]
   [34747575467581863011,3628273133]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,264575131106459]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
                                                               Type: Void
                                 Time: 30.38 (EV) + 1.38 (GC) = 31.77 sec

(8) -> z(1679)
   (8)  23
                                                    Type: PositiveInteger
                                                              Time: 0 sec

Python 3 , 100 99 байт, 45 40 39 секунд + штраф 10 минут

import math
def f(n):
 x=y=2;d=1
 while d<2:y=y*y+1;x,y=1+x*x%n,y*y%n+1;d=math.gcd(x-y,n)
 return d

Попробуйте онлайн!

Использует Полларда-Ро с начальным значением 2 и полиномом x ^ 2 + 1.