Root kuadrat angka

13

Tugasnya adalah sebagai berikut: Diberikan bilangan bulat positif xdan bilangan prima n > x, menghasilkan bilangan bulat positif terkecil ysehingga (y * y) mod n = x. Bagian penting dari pertanyaan ini adalah batas waktu yang ditentukan di bawah ini yang tidak termasuk solusi brute force.

Jika tidak ada nilai seperti itu ymaka kode Anda akan ditampilkan N.

Uji kasus

(2, 5, N), 
(3, 5, N), 
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)

Masukan dan keluaran

Anda dapat mengambil input dan memberikan output dengan cara apa pun yang nyaman. Jika Anda tidak suka output Nmaka Falseynilai apa pun akan dilakukan.

Batasan

Kode Anda harus menjawab semua kotak uji dalam waktu kurang dari 1 menit pada desktop standar. Batas waktu ini hanya untuk mencegah jawaban kasar dan saya berharap jawaban yang baik berjalan hampir secara instan. Anda tidak boleh menggunakan pustaka atau builtin apa pun yang memecahkan masalah ini atau yang menguji jika angka adalah residu kuadratik.


sumber
2
Jadi bahasa tanpa dukungan untuk tipe data bilangan bulat besar dikesampingkan. Kasihan
Luis Mendo
1
@LuisMendo Tidak jika Anda dapat membuat kode dukungan untuk 1267650600228229401496703205653diri sendiri atau jika Anda memiliki dukungan 128 bit seperti __int128di gcc. Ada juga sejumlah 256 bit int libraries di luar sana untuk berbagai bahasa. Terakhir, banyak bahasa memiliki perpustakaan int presisi yang sewenang-wenang.

Jawaban:

7

Pyth, 83 82 byte

=eAQM.^GHQKf%=/H=2;1=gftgT/Q;1HJg~gGHh/H2WtG=*J=gT^2t-K=Kfq1gG^2T1=%*G=^T2Q;hS%_BJ

Suite uji

Program ini mengimplementasikan algoritma Tonelli-Shanks . Saya menulisnya dengan cermat mengikuti halaman Wikipedia. Dibutuhkan sebagai input (n, p).

Tidak adanya akar kuadrat dilaporkan oleh kesalahan berikut:

TypeError: pow() 3rd argument not allowed unless all arguments are integers

Ini adalah kode golf yang sangat rumit, ditulis dengan gaya imperatif, berbeda dengan gaya fungsional Pyth yang lebih umum.

Aspek halus Pyth yang saya gunakan adalah =, yang, jika tidak segera diikuti oleh variabel, mencari maju dalam program untuk variabel berikutnya, kemudian memberikan hasil dari ekspresi berikut untuk variabel itu, kemudian mengembalikan hasil itu. Saya akan merujuk seluruh penjelasan ke halaman wikipedia: Algoritma Tonelli-Shanks , karena itulah algoritma yang saya terapkan.

Penjelasan:

=eAQ

Amengambil 2-tuple sebagai input, dan memberikan nilai masing G- Hmasing, dan mengembalikan inputnya. Qadalah input awal. emengembalikan elemen terakhir dari suatu urutan. Setelah cuplikan ini, Gadalah n, dan Hdan Qsedang p.

M.^GHQ

Mmendefinisikan fungsi input 2 g, di mana input berada Gdan H. .^adalah fungsi eksponensial modular cepat Pyth. Cuplikan ini didefinisikan gsebagai mod eksponensial Q.

Kf%=/H=2;1

fmendefinisikan pengulangan sampai false loop, dan mengembalikan jumlah iterasi yang dijalankannya, diberikan 1sebagai inputnya. Selama setiap iterasi loop, kami membaginya Hdengan 2, set Hke nilai itu, dan memeriksa apakah hasilnya aneh. Setelah itu, kita berhenti. Kmenyimpan jumlah iterasi yang dibutuhkan.

Satu hal yang sangat sulit adalah =2;bagiannya. =mencari di depan untuk variabel berikutnya, yaitu T, jadi Tdiatur ke 2. Namun, Tdi dalam floop adalah penghitung iterasi, jadi kami gunakan ;untuk mendapatkan nilai dari Tlingkungan global. Ini dilakukan untuk menyimpan beberapa byte spasi putih yang jika tidak akan diperlukan untuk memisahkan angka.

Setelah potongan ini, Kadalah Sdari artikel wikipedia (wiki), dan Hadalah Qdari wiki, dan Tini 2.

=gftgT/Q;1H

Sekarang, kita perlu menemukan mod nonresid kuadratik p. Kami akan memaksa ini menggunakan kriteria Euler. /Q2adalah (p-1)/2, karena /adalah divisi lantai, sehingga ftgT/Q;1menemukan bilangan bulat pertama di Tmana T ^ ((p-1)/2) != 1, seperti yang diinginkan. Ingat itu ;lagi menarik Tdari lingkungan global, yang masih 2. Hasil ini zdari wiki.

Selanjutnya, untuk membuat cdari wiki, kita perlu z^Q, jadi kita bungkus di atas g ... Hdan tetapkan hasilnya T. Sekarang Tadalah cdari wiki.

Jg~gGHh/H2

Mari kita memisahkan ini: ~gGH. ~seperti =, tetapi mengembalikan nilai asli variabel, bukan nilai baru. Jadi, ia kembali G, yang ndari wiki.

Ini memberikan Jnilai n^((Q+1)/2), yaitu Rdari wiki.

Sekarang, yang berikut ini berlaku:

~gGH

Ini memberikan Gnilai n^Q, yang berasal tdari wiki.

Sekarang, kita telah mengatur variabel loop kami. M, c, t, Rdari wiki adalah K, T, G, J.

Tubuh loop rumit, jadi saya akan menyajikannya dengan spasi putih, cara saya menulisnya:

WtG
  =*J
    =
      gT^2
        t-
          K
          =Kfq1gG^2T1
  =%*G=^T2Q;

Pertama, kita periksa apakah G1. Jika demikian, kita keluar dari loop.

Kode berikutnya yang berjalan adalah:

=Kfq1gG^2T1

Di sini, kami mencari nilai pertama isedemikian rupa G^(2^i) mod Q = 1, mulai dari 1. Hasilnya disimpan K.

=gT^2t-K=Kfq1gG^2T1

Di sini, kita mengambil nilai lama K, kurangi nilai baru K, kurangi 1, naikkan 2 ke daya itu, lalu naikkan Tke mod daya itu Q, lalu tetapkan hasilnya T. Ini Tsama dengan bdari wiki.

Ini juga merupakan garis yang mengakhiri loop dan gagal jika tidak ada solusi, karena dalam hal ini nilai baru Kakan sama dengan nilai lama K, 2 akan dinaikkan ke -1, dan eksponensial modular akan menimbulkan kesalahan.

=*J

Selanjutnya, kita kalikan Jdengan hasil di atas dan simpan kembali J, tetap Rperbarui.

=^T2

Lalu kami menyiku Tdan menyimpan hasilnya kembali T, mengatur Tkembali ke cdari wiki.

=%*G=^T2Q

Lalu kita kalikan Gdengan hasil itu, ambil modnya Qdan simpan hasilnya kembali G.

;

Dan kami mengakhiri loop.

Setelah loop selesai, Jadalah akar kuadrat dari nmod p. Untuk menemukan yang terkecil, kami menggunakan kode berikut:

hS%_BJ

_BJmembuat daftar Jdan negasinya, %secara implisit mengambil Qsebagai argumen kedua, dan menggunakan perilaku default Pyth untuk diterapkan % ... Qke setiap anggota urutan. Kemudian Smengurutkan daftar dan hmengambil anggota pertamanya, minimum.

isaacg
sumber
11

Python 2, 166 byte

def Q(x,n,a=0):
 e=n/2
 while pow(a*a-x,e,n)<2:a+=1
 w=a*a-x;b=r=a;c=s=1
 while e:
    if e%2:r,s=(r*b+s*c*w)%n,r*c+s*b
    b,c=(b*b+c*c*w)%n,2*b*c;e/=2
 return min(r,-r%n)
orlp
sumber
%timeit Q(1267650600228229401496703204676,1267650600228229401496703205653) 100 loops, best of 3: 2.83 ms per loop :)
3
Jawaban yang bagus! Anda telah memulihkan iman saya di PPCG.
5
Maaf pertanyaan pemula, tapi apa PPCG? Grup Python Coders Polandia?
Reversed Engineer
@DaveBoltman Programming Puzzles & Code Golf.
orlp
6

SageMath , 93 byte

Dengan mengurangi masalah yang jauh lebih sulit yang kebetulan SageMath memiliki builtin cukup cepat.

def f(x,n):g=primitive_root(n);k=Zmod(n)(x).log(g);y=pow(g,k//2,n);return k%2<1and min(y,n-y)

Cobalah di SageMathCell

Anders Kaseorg
sumber
2
Pengurangan itu cukup lucu :)
3

Haskell , 326 byte

Biasanya saya suka jawaban brute force .. Karena ini sangat tidak disarankan oleh batas waktu, inilah cara paling efisien yang saya tahu:

r p=((\r->min(mod(-r)p)r)$).f p
f p x|p==2=x|q x=f 0 0|mod p 4==3=x&div(p+1)4|let(r,s)=foldl i(p-1,0)[1..t 1o]=m$x&(d$r+1)*(b&d s)where q a=1/=a&o;m=(`mod`p);a&0=1;a&e|even e=m$a&d e^2|0<1=m$(a&(e-1))*a;b=[n|n<-[2..],q n]!!0;i(a,b)_|m(x&d a*b&d b)==p-1=(d a,d b+o)|0<1=(d a,d b);o=d p;t y x|even x=t(y+1)(d x)|0<1=y;d=(`div`2)

Cobalah online!

Saya yakin ini bisa diturunkan lebih jauh, tetapi ini harus dilakukan untuk saat ini.

ბიმო
sumber
Bisakah Anda mengubah kode TIO sehingga memberikan jawaban sebagai output? Saya hanya mendapatkan "Benar" saat ini.
1
Cobalah online!
Ørjan Johansen
@Lembik Anda harus mengganti testCasesdengan yang dari TIO asli, itu hampir tidak cocok menjadi komentar bahkan tanpa mereka.
Ørjan Johansen
@ ØrjanJohansen Terima kasih banyak! Saya menyesuaikan jawaban saya dengan kode Anda dan diganti testCases.
ბიმო
Huh, saya melihat bug aneh dengan tautan TIO itu - jika saya klik itu ada kode tetapi tidak berjalan atau mendapatkan URL dari opsi menu berfungsi - tetapi jika saya menyalin URL dari bilah alamat dan menempelkannya ke dalam tab yang berbeda, maka itu berfungsi.
Ørjan Johansen