Zadanie polega na znalezieniu nietrywialnego czynnika liczby złożonej.

Napisz kod, który znajdzie niebanalny czynnik liczby złożonej tak szybko, jak to możliwe, pod warunkiem, że Twój kod nie będzie miał więcej niż 140 bajtów. Wynik powinien być po prostu czynnikiem, który znalazłeś.

Twój kod może pobierać dane wejściowe i generować dane w dowolny dogodny sposób, na przykład jako argumenty funkcji.

Przypadki testowe, które wymieniają wszystkie czynniki (wystarczy tylko jeden wynik)

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

Nie uzyskam odpowiedzi na następujący trudny przypadek testowy, który może być interesujący w testowaniu:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

Wynik

Twój wynik to łączny czas na uwzględnienie wszystkich powyższych przypadków testowych z karą 10 minut za każdą nieudaną faktoryzację (wszystkie zaokrąglone do najbliższej sekundy). Twój kod powinien działać również dla innych liczb całkowitych, co nie powinno po prostu kodować tych odpowiedzi.

Zatrzymam twój kod po 10 minutach.

Jeśli dwie osoby otrzymają ten sam wynik, pierwsza odpowiedź wygrywa.

Ograniczenia

W kodzie nie można używać żadnej funkcji wbudowanej ani funkcji biblioteki, która dokonuje podziału na liczby całkowite. Możesz założyć, że wejście zajmuje mniej niż 256 bitów. Wszystkie liczby wejściowe będą złożone.

Jak będę miał czas?

Będę dosłownie uruchamiał się time ./myprogna moim systemie Ubuntu, aby wykonać pomiar czasu, więc proszę również dostarczyć mi pełny program do uruchomienia, który zawiera dowolną zdefiniowaną przez ciebie funkcję.

Uwaga dotycząca języków skompilowanych

Czas kompilacji nie może zająć więcej niż 1 minutę na moim komputerze.

Czy to rzeczywiście możliwe?

Jeśli zignorujesz ograniczenia miejsca, każde z nich może zostać rozłożone na mniej niż 2 sekundy na moim komputerze przy użyciu czystego kodu Pythona + pypy.

Czym jest nietrywialny algorytm faktoringowy?

Algorytm Rho Pollarda jest szybki i nadaje się do gry w golfa. Oczywiście istnieje wiele innych sposobów na uwzględnienie liczby całkowitej .

Jeszcze szybsze jest sito Quadratic . Wyciśnięcie tego na 140 bajtów wygląda na poważne wyzwanie.

Wiodące wyniki

• SEJPM , 10 minut kary za ostatni przypadek testowy + 16 sekund w Haskell

Haskell, 100 97 91 89 87 72 67 bajtów

Wypróbuj online!

-3 bajty dzięki @flawr
-6 bajtów dzięki @flawr ponownie
-2 bajty dzięki @flawr jeszcze raz
-2 bajty dzięki zoptymalizowanemu zestawowi parametrów
-1 bajtów dzięki @flawrs kolejny raz
-14 bajtów dzięki wymaganiu na konieczność wysyłania tylko jednego bajtu o współczynniku
-5 dzięki @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

Działa to dla pierwszych 5 przypadków testowych w niezauważalnym czasie.
To prawdopodobnie przekroczy limit czasu w największym przypadku testowym.

Zasadniczo zwraca to zwykle jeden nietrywialny czynnik w czasie proporcjonalny do pierwiastka kwadratowego z najmniejszego czynnika.
Nie będzie działać na każdym wejściu, ponieważ nie zmienia wielomianu, a wykrycie wyjątkowego przypadku jest trudne do wykonania w 140 bajtach.
Nie będzie również generować pełnego faktoryzacji, ale raczej nietrywialny czynnik i podział danych wejściowych przez ten czynnik.
Nie posortuje również czynników według wielkości.

Zastosowaną metodą jest faktoring Pollarda-Rho ze standardową wartością początkową 2 (przy standardowym x^2+1wielomianu zastosowanym jeden raz) i niestandardowym wielomianowym stałym współczynnikiem 7 (ponieważ 1nie zadziałał z 1679) dla wszystkich dalszych ocen.

Pełny program ( 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)

Skompiluj jako $ ghc factor.hs(wymaga ghczainstalowania).
Uruchom jako $ ./factor <number>.

Przykładowy przebieg:

$ ./factor 187
11

Nieskluczony kod:

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

Oblicza nietrywialny czynnik, wywołując gwartości początkowe. Wielomian jest wstępnie zastosowany tutaj 2 i ponownie zastosowany do wyniku (5), dzięki czemu dane wejściowe g(w klauzuli „gdzie” ) zawsze można łatwo wykorzystać do testu gcd. g(wersja golfowa korzysta z infix #), a następnie próbuje obliczyć nietrywialny czynnik d(w klauzuli where w wersji bez gry w golfa, liniowy w grze w golfa) jako różnicę między dwoma wejściami do g, jeśli się powiedzie, zwraca ten czynnik , w przeciwnym razie ponawia. Tutaj może generować njako dane wyjściowe, jeśli a==biw ten sposób zwraca tylko trywialny czynnik, właściwe podejście do obsługi tego byłoby albo zmieniać wartości początkowe po tym zdarzeniu, albo zmienić wielomian.

Pari / GP , 137 bajtów, ~ 5 sekund

Korzystanie z wbudowanych operacji GP krzywej eliptycznej _{(i niektórych niedostosowanych dostrajania parametrów)} :

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])))

ecmjest funkcją, która (powinna) zwrócić czynnik. Wypróbuj online!

Test:

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

Nie golfowany:

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")
}

Niestety obsługa współczynników 2 i 3 wymaga wielu bajtów. Bajty, które mogły zostać użyte do dodania etapu 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])))

Aksjomat, 137 bajtów 9 minut

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)

powyżej funkcji p (), która implementowałaby algorytm p-1 do faktorowania poniżej tego, co należy skopiować do pliku w celu przetestowania na funkcji 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)])

wyniki tutaj:

(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

Aksjomat, 10 minut + 31 sekund

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 () to funkcja rho, jedna funkcja 137 bajtów; ungolfed z () i nazwij go rho (). Zakłada się, że gcd (0, n) = n, więc pętla zatrzyma się i powróci do błędu 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)]) 

wyniki (z () są poprawne dla wszystkich oprócz ostatniego numeru 1751952685614616185916001760791655006749 nie są uwzględniane (10 minut))

(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 bajtów, 45 40 39 sekund + 10 minut kary

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

Wypróbuj online!

Używa Pollard-Rho z wartością początkową 2 i wielomianem x ^ 2 + 1.