Faktorizer integer tweetable tercepat

17

Tugasnya adalah menemukan faktor non-sepele dari angka komposit.

Tulis kode yang menemukan faktor non-sepele dari nomor komposit secepat mungkin dengan kode Anda yang panjangnya tidak lebih dari 140 byte. Output seharusnya menjadi faktor yang Anda temukan.

Kode Anda dapat mengambil input dan memberikan output dengan cara apa pun yang nyaman termasuk misalnya sebagai argumen untuk suatu fungsi.

Uji kasus yang mencantumkan semua faktor (Anda hanya perlu menampilkan satu)

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

Saya tidak akan memberi skor jawaban Anda pada kasus uji sulit berikut yang mungkin menarik untuk diuji:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

Skor

Skor Anda adalah waktu gabungan untuk memperhitungkan semua kasus uji di atas dengan penalti 10 menit untuk setiap faktorisasi yang gagal (semua dibulatkan ke detik terdekat). Kode Anda juga harus bekerja untuk bilangan bulat lain, yang seharusnya tidak hanya berupa kode jawaban ini.

Saya akan menghentikan kode Anda setelah 10 menit.

Jika dua orang mendapatkan skor yang sama maka jawaban pertama menang.

Batasan

Kode Anda tidak dapat menggunakan fungsi bawaan atau pustaka yang melakukan faktorisasi bilangan bulat. Anda dapat mengasumsikan input tersebut membutuhkan kurang dari 256 bit. Semua angka input akan menjadi gabungan.

Bagaimana saya akan mengatur waktu?

Saya benar-benar akan berjalan time ./myprogdi sistem Ubuntu saya untuk melakukan pengaturan waktu jadi tolong sediakan juga program lengkap untuk saya jalankan yang mencakup fungsi apa pun yang telah Anda tetapkan.

Catatan untuk bahasa yang dikompilasi

Waktu kompilasi harus tidak lebih dari 1 menit pada mesin saya.

Apakah ini mungkin?

Jika Anda mengabaikan batasan ruang, maka masing-masing dapat diperhitungkan dalam waktu kurang dari 2 detik di komputer saya menggunakan kode Python murni + pypy.

Jadi apa yang dimaksud dengan algoritma pemfaktoran non-sepele?

Algoritma rho Pollard cepat dan cocok untuk bermain golf. Tentu saja ada banyak cara lain untuk faktor bilangan bulat juga.

Yang lebih cepat lagi adalah saringan Quadratic . Sepertinya tantangan serius untuk memerasnya menjadi 140 byte.

Skor terkemuka

  • SEJPM , penalti 10 menit untuk kasus uji terakhir + 16 detik di Haskell

sumber
Jadi, kita mungkin diberi nomor seperti 2 ** 1024?
Conor O'Brien
@ ConorO'Brien Anda tidak akan diberi apa pun dengan angka lebih banyak daripada kotak uji.
Jadi, dalam hal presisi, tidak lebih dari 256 bit.
Conor O'Brien
Untuk input seperti 4, apakah output seharusnya 2atau 2, 2?
Tn. Xcoder
1
@AndersKaseorg Saya memperbarui pertanyaan mengikuti saran Anda. Terima kasih.

Jawaban:

9

Haskell, 100 97 91 89 87 72 67 Bytes

Cobalah secara Online!

-3 byte terima kasih kepada @flawr
-6 byte terima kasih kepada @flawr lagi
-2 byte terima kasih kepada @flawr lagi
-2 byte berkat set parameter yang dioptimalkan
-1 byte berkat @flawrs waktu lain
-14 byte berkat persyaratan untuk hanya mengeluarkan satu faktor
-5 byte berkat @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

Ini berfungsi untuk 5 kasus uji pertama dalam waktu yang tidak diketahui.
Ini mungkin akan time-out pada test case terbesar.

Secara umum ini biasanya akan mengembalikan satu faktor non-sepele dalam waktu sebanding dengan akar kuadrat dari faktor terkecil.
Ini tidak akan bekerja pada setiap input karena tidak bervariasi polinomial dan deteksi kasus luar biasa sulit dilakukan dalam 140 byte.
Ini juga tidak akan menghasilkan faktorisasi penuh, melainkan faktor non-sepele dan pembagian input oleh faktor ini.
Ini juga tidak akan mengurutkan faktor berdasarkan ukuran.

Metode yang digunakan adalah Pollard-Rho-Factoring dengan nilai awal standar 2 (dengan x^2+1polinom standar diterapkan satu kali) dan faktor konstanta polinomial non-standar 7 (karena 1tidak bekerja dengan 1679) untuk semua evaluasi lebih lanjut.

Program lengkap ( 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)

Kompilasi sebagai $ ghc factor.hs(perlu ghcdiinstal).
Jalankan sebagai $ ./factor <number>.

Contoh dijalankan:

$ ./factor 187
11

Kode tidak dikunci:

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

Menghitung faktor non-sepele dengan menelepon gdengan nilai awal. Polinomial diterapkan sebelumnya pada 2 di sini dan diterapkan kembali pada hasil (5) sehingga input ke g(dalam klausa "di mana" ) selalu dapat dengan mudah digunakan untuk uji-gcd. g(versi golf menggunakan infix #) kemudian mencoba menghitung faktor non-sepele d(di mana klausa dalam versi un-golf, in-line dalam yang golf) sebagai perbedaan antara dua input g, jika berhasil mengembalikan faktor tersebut , coba lagi. Di sini ia dapat menghasilkan nsebagai output jika a==bdan dengan demikian hanya mengembalikan faktor sepele, pendekatan yang tepat untuk menangani ini adalah dengan memvariasikan nilai awal pada peristiwa ini atau mengubah polinomial.

SEJPM
sumber
|1<2=s a#(s$s b)dapat diganti dengan |c<-s b=s a#s csaya pikir :) (juga: mengapa Anda tidak memposting tautan TIO ?)
flawr
Saya memperbarui pertanyaan mengikuti saran komentar. Sekarang Anda hanya perlu menampilkan satu faktor dan jumlahnya dijamin komposit.
3
PS: mengapa kita bermain golf, ini bahkan bukan kode-golf
flawr
4
Anda sekarang memiliki 53 byte untuk mengimplementasikan algoritma anjak piutang yang lebih canggih :)
1
Anda juga dapat mengambil abs , karena bselalu tidak negatif. (Mungkin maksud Anda abs$b-a, tetapi gcdmenerima argumen negatif dan selalu menghasilkan hasil yang tidak negatif.) Itu membuat ini menjadi kurang dari setengah tweet!
Anders Kaseorg
6

Pari / GP , 137 byte, ~ 5 detik

Menggunakan operasi kurva elips bawaan GP (dan beberapa penyetelan parameter curang) :

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

ecmadalah fungsi yang (harus) mengembalikan faktor. Cobalah online!

Uji:

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

Tidak Disatukan:

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

Sayangnya, penanganan faktor 2 dan 3 menggunakan banyak byte. Bytes yang bisa digunakan untuk menambah tahap 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])))
japh
sumber
1

Aksioma, 137 byte 9 menit

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)

di atas fungsi p () yang akan mengimplementasikan p-1 algo untuk anjak di bawah ini apa yang akan disalin dalam file untuk pengujian pada fungsi 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)])

hasil di sini:

(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
RosLuP
sumber
Bisakah Anda menjelaskan bagaimana menjalankan kode ini dari command line di ubuntu? Saya telah menginstal aksioma dan membuat file bernama foo.ax dengan kode non-golf Anda di dalamnya.
@Lembik 1) ganti nama fop.ax di foo.input 2) jalankan Aksioma dalam satu terminal atau xterm 3) tulis di terminal Aksioma perintah ikuti ") baca C: absolutepath \ foo" 4) tulis di terminal aksioma panggilan berfungsi tes (). Ini adalah bagaimana melakukannya di Windows, petunjuk bagi saya sepertinya membuka satu sesi Aksioma dan memuat file dengan perintah ") baca"
RosLuP
@Lembik jika ada masalah dengan file, saya pikir itu akan baik-baik saja: 1) jalankan Aksioma 2) tulis) waktu pada <return> dalam program Aksioma 3) salin dan tempelkan kembali di setiap "salin tempel" dalam program Aksioma: array vA, fungsi p () dan tes () 4) dalam tes tulis program Axiom () <return>
RosLuP
@Lembik jadi jam berapa?
RosLuP
1

Aksioma, 10 menit + 31 detik

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 () adalah fungsi rho, satu fungsi 137 byte; ungolfed z () dan menyebutnya sebagai rho (). Itu akan mengira bahwa gcd (0, n) = n sehingga loop berhenti dan kembali untuk gagal 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)]) 

hasil (z () tidak apa-apa kecuali angka terakhir 1751952685614616185916001760791655006749 tetap tidak diperhitungkan (10 menit))

(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
RosLuP
sumber
0

Python 3 , 100 99 byte, 45 40 39 detik + penalti 10 menit

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

Cobalah online!

Menggunakan Pollard-Rho dengan nilai awal 2 dan polinomial x ^ 2 +1.

plafon
sumber
Anda bisa menggunakannya pow (dengan argumen ke-3) untuk meningkatkan kecepatan eksekusi Anda.
mbomb007