Pertimbangkan bilangan bulat modulo di q
mana q
bilangan prima, generator bilangan bulat apa pun 1 < x < q
sehingga x^1, x^2, ..., x^(q-1)
mencakup semua q-1
bilangan bulat di antara 1
dan q-1
. Sebagai contoh, perhatikan bilangan bulat modulo 7 (yang kami tulis sebagai Z_7
). Kemudian 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1
mencakup semua nilai 3, 2, 6, 4, 5, 1
mencakup semua bilangan bulat 1..6
sesuai kebutuhan.
Tugasnya adalah menulis kode yang membutuhkan input n
dan output generator Z_n
. Anda tentu saja tidak dapat menggunakan builtin atau pustaka yang melakukan ini untuk Anda.
Satu-satunya batasan pada kinerja kode Anda adalah bahwa Anda harus mengujinya sampai selesai n = 4257452468389
.
Perhatikan itu 2^n
berarti 2
kekuatan n
. Itu ^
mewakili eksponensial.
1 < x < q
membuat tantangan imo jauh lebih mudah.Jawaban:
Pyth,
1615 byteSuite uji
Jika p adalah input, kita tahu bahwa g ^ (p-1) = 1 mod p, jadi kita hanya perlu memeriksa bahwa g ^ a! = 1 mod p untuk yang lebih kecil a. Tapi a harus menjadi faktor p-1 agar memungkinkan, dan kelipatan a dengan properti itu juga akan memiliki properti itu, jadi kita hanya perlu memeriksa g ^ ((p-1) / q)! = 1 mod p untuk semua faktor prima q dari p-1. Jadi, kami memeriksa semua bilangan bulat g dalam urutan yang meningkat hingga kami menemukan satu yang berfungsi.
Penjelasan:
sumber
PtQ
bagian).Mathematica, 52 byte
Terinspirasi oleh jawaban isaacg .
sumber
sumber