package adv2019; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.Random; /** * * 固有値にF[p]の外の値が出てきたときの拡大体での離散対数問題が解けない */ public class D13_2 { InputStream is; PrintWriter out; // String INPUT = "3\n" + // "1 2 1 0 \n" + // "2 1 2 0"; String INPUT = ""; // (a-L, b), (c, d-L) // (a-L)(d-L) - bc = 0 // L^2-(a+d)L + ad-bc = 0 // D = (a+d)^2 - 4(ad-bc) int[][] trans(long[][] M, int p) { int n = M.length, m = M[0].length; int[][] ret = new int[n][m]; for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { ret[i][j] = (int)(M[i][j] % p); } } return ret; } int[][] inv(int[][] M, int p) { long D = (long)M[0][0]*M[1][1] - (long)M[0][1] * M[1][0]; D %= p; if(D < 0)D += p; if(D == 0)return null; long ID = invl(D, p); return new int[][] { {(int)(ID*M[1][1]%p), (int)(ID*(p-M[0][1])%p)}, {(int)(ID*(p-M[1][0])%p), (int)(ID*M[0][0]%p)} }; } long[][][] inv(long[][][] S, int p, int E) { long[][][] ret = new long[][][] { {S[1][1], neg(S[0][1], p)}, {neg(S[1][0], p), S[0][0]} }; long[] D = inv(add(mul(S[1][1], S[0][0], p, E), neg(mul(S[0][1], S[1][0], p, E), p), p), p, E); for(int i = 0;i < 2;i++) { for(int j = 0;j < 2;j++) { ret[i][j] = mul(ret[i][j], D, p, E); } } return ret; } long[][][] mul(long[][][] a, long[][][] b, int p, int E) { long[][][] c = new long[2][2][]; for(int i = 0;i < 2;i++) { for(int j = 0;j < 2;j++) { long[] sum = {0, 0}; for(int k = 0;k < 2;k++) { sum = add(sum, mul(a[i][k], b[k][j], p, E), p); } c[i][j] = sum; } } return c; } long[] inv(long[] a, int p, int E) { // 1/(a+bS(E)) // (a-bS(E))/(a^2-b^2*E) long den = a[0]*a[0]-a[1]*a[1]%p*E; den %= p; if(den < 0)den += p; long iden = invl(den, p); return new long[] {a[0]*iden%p, a[1]*iden%p}; } long[] add(long[] a, long[] b, int p) { return new long[] { (a[0]+b[0]) % p, (a[1]+b[1]) % p }; } long[] mul(long[] a, long[] b, int p, int E) { return new long[] { (a[0]*b[0] + a[1]*b[1]%p*E)%p, (a[0]*b[1] + a[1]*b[0])%p }; } long[] pow(long[] a, long e, int p, int E) { long[] ret = {1L, 0L}; for(int i = 64-Long.numberOfLeadingZeros(e);i >= 0;i--) { ret = mul(ret, ret, p, E); if(e<<~i<0) { ret = mul(ret, a, p, E); } } return ret; } long[] neg(long[] x, int p) { return new long[] {(p-x[0])%p, (p-x[1])%p}; } long solve(int[][] A, int[][] B, int p) { long a = A[0][0], b = A[0][1], c = A[1][0], d = A[1][1]; // if((a*d - b*c) % p == 0){ // // rank <= 1 // // } long i2 = invl(2, p); long D = (a-d)*(a-d) + 4*b*c; D %= p; // (a+b√c) * (d+e√c) // (d e) // (e dc) // (a 1) // (1 b) // d = (a'+d')/2, c = (a'-d')^2+4bc // d^2(c-1)^2+4 if(D == 0) { // x = (a+d)/2の重解 long x = (a+d)*i2 % p; // ジョルダン標準形 // (a b)(s t) = (s t)(x 1) // (c d)(u v) (u v)(0 x) // を解く for(int y : new int[] {0, p-1}) { for(int k = 0;k < 4;k++) { long[][] LM = { {a+p-x, 0, b, 0}, {y, a+p-x, 0, b}, {c, 0, d+p-x, 0}, {0, c, y, d+p-x}, {0, 0, 0, 0}, }; LM[4][k] = 1; int[] v = {0, 0, 0, 0, 1}; int[][] M = trans(LM, p); Result res = gaussElimination(M, v, p); if(res.exists) { if(((long)res.sol[0]*res.sol[3] - (long)res.sol[2]*res.sol[1]) % p != 0) { int[][] S = { {res.sol[0], res.sol[1]}, {res.sol[2], res.sol[3]} }; int[][] IS = inv(S, p); int[][] XB = mul(mul(IS, B, p), S, p); // J^n = (x^n (p-y)*n*x^(n-1)) // (0 x^n) if(XB[0][0] != XB[1][1] || XB[1][0] != 0) { return -1; }else { if(y == 0) { return bsgs(x, XB[0][0], p); }else { // x^n = A // n*x^(n-1) = B // n*(A/x) = B // n = B*x/A (mod p) // x^(nn + k*p) = A // x^p = x long nn = XB[0][1] * x % p * invl(XB[0][0], p) % p; long ret = bsgs( x, XB[0][0]*invl(pow(x, nn, p), p)%p, p); if(ret == -1)return -1; return nn + ret * p; } } } } } } return -1; } long sq = sqrt(D, p, new Random()); if(sq == -1) { // F_p上で解を持たないことがあるので、√Dで体の拡大をする // が最終的にa+b√cの形の離散対数問題を解かないといけなくなり、これがわからない if(true)return -1; long[] alpha = {(a+d)*i2 % p, p-i2}; long[] beta = {(a+d)*i2 % p, i2}; long[][][] S = { {{b, 0},{b, 0}}, {{alpha[0]-a, alpha[1]}, {beta[0]-a, beta[1]}} }; /* (b ((a + sqrt(c)) s - b u) + (a - sqrt(c)) ((a + sqrt(c)) t - b v) | b ((a + sqrt(c)) s - b u) + (a + sqrt(c)) ((a + sqrt(c)) t - b v) b ((sqrt(c) - a) s + b u) + (a - sqrt(c)) ((sqrt(c) - a) t + b v) | b ((sqrt(c) - a) s + b u) + (a + sqrt(c)) ((sqrt(c) - a) t + b v)) * */ // (b b) // (a-√c-d, a+√c-d) // 1/(b(a+√c-d)-b(a-√c-d)) // (a+√c-d -b) // (-a+√c+d b) // 1/(2b√c) // (a+√c-d -b)(s t)(b b) // (-a+√c+d b)(u v)(a-√c-d a+√c-d) long[][][] IS = inv(S, p, (int)D); long[][][] BB = { {{B[0][0], 0}, {B[0][1], 0}}, {{B[1][0], 0}, {B[1][1], 0}} }; long[][][] XB = mul(mul(IS, BB, p, (int)D), S, p, (int)D); if(XB[0][1][0] != 0)return -1; if(XB[0][1][1] != 0)return -1; if(XB[1][0][0] != 0)return -1; if(XB[1][0][1] != 0)return -1; // alpha^n = XB[0][0] // beta^n = XB[1][1] if(XB[0][0][0] != XB[1][1][0])return -1; if((XB[0][0][1] + XB[1][1][1]) % p != 0)return -1; // a+b√cの周期はp^2-1の約数 // b=0のもそこそこの周期でまざっている long p2m = (long)p*p-1; int[] primes = sieveEratosthenes(100000); int[] pm = facs(p-1, primes); int[] pp = facs(p-1, primes); long x = p2m; // tr(XB[0][0], x, D, pow(XB[0][0], x, p, (int)D)); assert Arrays.equals(pow(XB[0][0], x, p, (int)D), new long[] {1, 0}); long y = p2m; for(int u : pm) { while(x % u == 0) { long[] o = pow(XB[0][0], x/u, p, (int)D); if(o[1] == 0) { if(o[0] == 1)y /= u; x /= u; }else { break; } } } for(int u : pp) { while(x % u == 0) { long[] o = pow(XB[0][0], x/u, p, (int)D); if(o[1] == 0) { if(o[0] == 1)y /= u; x /= u; }else { break; } } } // tr(p2m); // tr("x", x, y); return -1; // solve(new int[][] { // {(int)((a+d)*i2 % p), 1}, (int)i2} // {(int)i2, (int)((a+d)*i2 % p* D % p)} // }, new int[][]{ // {(int)XB[0][0][0], (int)XB[0][0][1]}, // {(int)XB[1][1][0], (int)XB[0][0][1]}, // }); // long ret1 = bsgs( // // x, // XB[0][0]*invl(pow(x, nn, p), p)%p, // p); }else { // F_p上で解を持つ場合 long alpha = (a+d+p-sq)*i2 % p; long beta = (a+d+sq)*i2 % p; int[][] S = { {(int)b, (int)b}, {(int)((alpha+p-a)%p), (int)((beta+p-a)%p)} }; long dd = (long)S[0][0] * S[1][1] - (long)S[0][1] * S[1][0]; dd %= p; if(dd < 0)dd += p; long idd = invl(dd, p); int[][] IS = { {(int)(S[1][1]*idd%p), (int)((p-S[0][1])*idd%p)}, {(int)((p-S[1][0])*idd%p), (int)(S[0][0]*idd%p)} }; int[][] XB = mul(mul(IS, B, p), S, p); if(XB[0][1] != 0)return -1; if(XB[1][0] != 0)return -1; long e0 = bsgs(alpha, XB[0][0], p); long e1 = bsgs(beta, XB[1][1], p); if(e0 == e1)return e0; return -1; } // (alpha-a b) // (c alpha-d) // long sq = sqrt(D, p, new Random()); // if(sq == -1)return null; // if(c != 0) { // long idc = invl(2*c%p, p); // int[][] S = { // {(int)(((long)p-a+d+sq)*idc%p), (int)(((long)p+a-d+sq)*idc%p)}, // {1, 1} // }; // long isq = invl(sq, p); // long disq = invl(2*sq%p, p); // int[][] IS = { // {(int)((p-c) * isq%p), (int)(((long)p+a-d+sq)*disq%p)}, // {(int)((c) * isq%p), (int)(((long)p-a+d+sq)*disq%p)} // }; // return new Diag(S, IS, // ((long)p+a+d-sq)*invl(2,p)%p, // ((long)p+a+d+sq)*invl(2,p)%p // ); // }else if(a-d != 0) { // long iad = invl((a+p-d)%p, p); // int[][] S = { // {1, (int)((p-b)*iad%p)}, // {0, 1} // }; // int[][] IS = { // {1, (int)((b)*iad%p)}, // {0, 1} // }; // return new Diag(S, IS, a, d); // }else { // return null; // } } public static int[] sieveEratosthenes(int n) { if (n <= 32) { int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }; for (int i = 0; i < primes.length; i++) { if (n < primes[i]) { return Arrays.copyOf(primes, i); } } return primes; } int u = n + 32; double lu = Math.log(u); int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)]; ret[0] = 2; int pos = 1; int[] isnp = new int[(n + 1) / 32 / 2 + 1]; int sup = (n + 1) / 32 / 2 + 1; int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }; for (int tp : tprimes) { ret[pos++] = tp; int[] ptn = new int[tp]; for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31); for (int j = 0; j < sup; j += tp) { for (int i = 0; i < tp && i + j < sup; i++) { isnp[j + i] |= ptn[i]; } } } // 3,5,7 // 2x+3=n int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 }; int h = n / 2; for (int i = 0; i < sup; i++) { for (int j = ~isnp[i]; j != 0; j &= j - 1) { int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27]; int p = 2 * pp + 3; if (p > n) break; ret[pos++] = p; if ((long) p * p > n) continue; for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q; } } return Arrays.copyOf(ret, pos); } public static int[] facs(int n, int[] primes) { int[] ret = new int[9]; int rp = 0; for(int p : primes){ if(p * p > n)break; int i; for(i = 0;n % p == 0;n /= p, i++); if(i > 0)ret[rp++] = p; } if(n != 1)ret[rp++] = n; return Arrays.copyOf(ret, rp); } public static Result gaussElimination(int[][] M, int[] v, int mod) { int n = M.length, m = M[0].length; int[] head = new int[n]; // if not needed, comment out. for(int[] row : M){ for(int i = 0;i < row.length;i++){ row[i] %= mod; if(row[i] < 0)row[i] += mod; } } // Forward Elimination int row = 0; for(int col = 0;col < m;col++){ // select pivot boolean pivotFound = false; out: for(int prow = row;prow < n;prow++){ if(M[prow][col] != 0){ // pivot found if(prow != row){ // swap rows for(int k = 0;k < m;k++){ int u = M[prow][k]; M[prow][k] = M[row][k]; M[row][k] = u; } int dum = v[prow]; v[prow] = v[row]; v[row] = dum; } pivotFound = true; break out; } } if(!pivotFound)continue; head[row] = col; // diag to 1 long imul = invl(M[row][col], mod); for(int k = 0;k < m;k++){ M[row][k] = (int)(M[row][k] * imul % mod); } v[row] = (int)(v[row] * imul % mod); for(int j = row+1;j < n;j++){ if(M[j][col] != 0){ long mul = mod-M[j][col]; for(int k = col;k < m;k++){ M[j][k] = (int)((M[j][k] + M[row][k] * mul) % mod); } v[j] = (int)((v[j] + v[row] * mul) % mod); } } row++; } Result ret = new Result(); ret.mat = M; for(int i = row;i < n;i++){ if(v[i] != 0){ ret.rank = row; ret.exists = false; return ret; } } for(int i = row-1;i >= 0;i--){ for(int j = i-1;j >= 0;j--){ if(M[j][head[i]] != 0){ long mul = mod-M[j][head[i]]; for(int k = head[i];k < m;k++){ M[j][k] = (int)((M[j][k] + M[i][k] * mul) % mod); } v[j] = (int)((v[j] + v[i] * mul) % mod); } } } int[] retv = new int[m]; for(int i = 0;i < row;i++){ retv[head[i]] = v[i]; } ret.sol = retv; ret.rank = row; ret.exists = true; return ret; } public static class Result { public int[][] mat; public int[] sol; public int rank; public boolean exists; } public static long pow(long a, long n, long mod) { // a %= mod; long ret = 1; int x = 63 - Long.numberOfLeadingZeros(n); for (; x >= 0; x--) { ret = ret * ret % mod; if (n << 63 - x < 0) ret = ret * a % mod; } return ret; } public static long sqrt(long n, int p, Random gen) { if(n == 0)return 0; if(pow(n, (p-1)/2, p) != 1)return -1; int S = Integer.numberOfTrailingZeros(p-1); long Q = p-1>>>S; if(S == 1){ return pow(n, (p+1)/4, p); } int z = 0; do{ z = gen.nextInt(p-1)+1; }while(pow(z, (p-1)/2, p) != p-1); long c = pow(z, Q, p); long R = pow(n, (Q+1)/2, p); long t = pow(n, Q, p); int M = S; while(t != 1){ long u = t; for(int i = 1;i < M;i++){ u = u * u % p; // U.tr(i, t, u); if(u == 1){ long b = c; for(int j = 0;j < M-i-1;j++){ b = b * b % p; } R = R * b % p; t = t * b % p * b % p; c = b * b % p; M = i; break; } } } return R; } void solve() { int mod = ni(); int[][] a = new int[2][2]; int[][] b = new int[2][2]; for(int i = 0;i < 2;i++) { a[i] = na(2); } for(int i = 0;i < 2;i++) { b[i] = na(2); } int[][] e = {{1, 0}, {0, 1}}; outer: for(int i = 1;i <= 20;i++) { e = mul(e, a, mod); for(int j = 0;j < 2;j++) { for(int k = 0;k < 2;k++) { if(e[j][k] != b[j][k])continue outer; } } out.println(i); return; } if(mod == 2) { out.println(-1); return; } out.println(solve(a, b, mod)); } public static long bsgs(long alpha, long beta, int p) { int m = (int)Math.sqrt(p)+1; long[] table = new long[m]; long val = 1; for(int j = 0;j < m;j++){ table[j] = val<<32|j; val = val * alpha % p; } Arrays.sort(table); long ainvm = invl(val, p); long g = beta; for(int i = 0;i < m;i++){ int ind = Arrays.binarySearch(table, g<<32); if(ind < 0)ind = -ind-1; if(ind < m && table[ind]>>>32 == g){ if((long)i*m+(int)table[ind] == 0)continue; return i*m+(int)table[ind]; } g = g * ainvm % p; } return -1; } public static long invl(long a, long mod) { long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p < 0 ? p + mod : p; } public static int[][] mul(int[][] A, int[][] B, int mod) { assert A[0].length == B.length; int m = A.length; int n = A[0].length; int o = B[0].length; int[][] C = new int[m][o]; for(int i = 0;i < m;i++){ for(int j = 0;j < o;j++){ long sum = 0; for(int k = 0;k < n;k++){ sum += (long)A[i][k] * B[k][j]; sum %= mod; } C[i][j] = (int)sum; } } return C; } public static int[] pow(int[][] A, int[] v, long e, int mod) { int[][] MUL = A; for(int i = 0;i < v.length;i++)v[i] %= mod; for(;e > 0;e>>>=1) { if((e&1)==1)v = mul(MUL, v, mod); MUL = p2(MUL, mod); } return v; } // int matrix * int vector public static int[] mul(int[][] A, int[] v, int mod) { int m = A.length; int n = v.length; int[] w = new int[m]; for(int i = 0;i < m;i++){ long sum = 0; for(int k = 0;k < n;k++){ sum += (long)A[i][k] * v[k]; sum %= mod; } w[i] = (int)sum; } return w; } // int matrix^2 (cannot ensure negative values) public static int[][] p2(int[][] A, int mod) { int n = A.length; int[][] C = new int[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ long sum = 0; for(int k = 0;k < n;k++){ sum += (long)A[i][k] * A[k][j]; sum %= mod; } C[i][j] = (int)sum; } } return C; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new D13_2().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }