CTFshow上的新题,搞了一天
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 from door_sum import door_sumassert door_sum(1 , 1 , 100 ) == 5050 WELCOME = '''HELLO! Open the door, and I'll show you my flag! ''' if __name__ == '__main__' : while True : try : print (WELCOME) n_1 = int (input ('n_1 = ' )) n_2 = int (input ('n_2 = ' )) if (n_1 > 2 ** 0x1337 and n_2 > 2 ** 0x1337 and door_sum(1 , 1 , n_1) == 0x1337 * door_sum(1 , 2 , n_2)): print ('OKOK! YOU GOT THE FLAG:' ) with open ('flag.txt' ) as f: print (f.read()) else : print ('Uh-Oh, the door is not opened...' ) except Exception: print ('NONONO!' )
分析
door_sum可以写成等差数列的和
注意door_sum里的n是项数!!!
题目的要求是两个数均大于2**4919并且第一个数的数列和是第二个数列和的4919倍
$$ x_n=x_1+d(n-1)
\ S_n=n=()n = \则S_{n1}= \S_{n2}=
\已知S_{n1}=4919*S_{n2},且d_1=1,d_2=2,x_1=1 \则=4919n_2^2 \ =n2 $$
走到这里发现走不通了,毕竟是要爆破的,对于这个数量级依旧很难出解。因为要加快爆破速度,了解到佩尔方程:
佩尔方程
\[
定义:形如x^2 − d y^2=1(d>1,且d不是完全平方数)\\
要求第一类佩尔方程的解都是正整数解,也即( x , y ) , x > 0 , y > 0
\]
显然方程有无数组解,如何求最小解? \[
把方程化为x=\sqrt{1+dy^2}\\
从y=1开始枚举,如果\sqrt{1+dy^2}是整数,那么此时(x,y)就是最小整数解(x_1,y_1)
\] 如何得到所有的解?
迭代公式: \[
x_n=x_{n-1}x_1+dy_{n-1}y_1\\
y_n=x_{n-1}y_1+y_{n-1}x_1
\]
但如果用这个公式求解,时间复杂度依旧是O(n),当n很大时还是跑不出来,所以使用矩阵快速幂,以O(logn)的时间复杂度求解:
\[
\left[
\begin{matrix}
x_n\\
y_n
\end{matrix}
\right] \tag{2}=
\left[
\begin{matrix}
x_1&d*y_1\\
y_1&x_1
\end{matrix}
\right]^{n-1}
\left[
\begin{matrix}
x_1\\
y_1
\end{matrix}
\right]
\]
解
改变一下推法: \[
\frac{n_1^2+n_1}{2}=4919n_2^2
\\(n_1+\frac{1}{2})^2-\frac{1}{2}=9838n_2^2
\\(2n_1+1)^2-4*9838n_2^2=1
\] 得到了佩尔方程的表达式,之后使用连分数的性质计算得到了最小解:
\[
(x_1,y_1)=\\(2662019309411216232806345449321879270495478346383,
26838472360889124413883226557207387537524821524)
\] 可以看到还是很小的(比起2^0x1337)
完整代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 def find_mini_solution (d ): m=int (d**0.5 ) i=0 a=[] a.append(m) i+=1 b=m c=1 sq=d**0.5 while (a[i-1 ]!=2 *a[0 ]): c=(d-b*b)/c tmp=(sq+b)/c a.append(int (tmp)) i+=1 b=a[i-1 ]*c-b del a[-1 ] p=[m] q=[1 ] for j in range (1 ,len (a)): if j==1 : p.append(a[j]*p[0 ]+1 ) q.append(a[j]*q[0 ]) else : p.append(a[j]*p[j-1 ]+p[j-2 ]) q.append(a[j]*q[j-1 ]+q[j-2 ]) if len (a)%2 ==0 : return p[-1 ],q[-1 ] else : return 2 *p[-1 ]**2 ,2 *p[-1 ]*q[-1 ] def mulMatrix (x,y ): ans = [[0 for i in range (2 )]for j in range (2 )] for i in range (2 ): for j in range (2 ): for k in range (2 ): ans[i][j] += x[i][k] * y[k][j] return ans def quickMatrix (m,n ): E = [[0 for i in range (2 )]for j in range (2 )] for i in range (2 ): E[i][i] = 1 while (n): if n % 2 != 0 : E = mulMatrix(E,m) m = mulMatrix(m,m) n >>= 1 return E d=9838 *4 x1,y1=find_mini_solution(d) print ((x1,y1))basis_matrix=[[x1,d*y1],[y1,x1]] cnt=2 while True : tmp=quickMatrix(basis_matrix,cnt) xn=tmp[0 ][0 ]*x1+tmp[0 ][1 ]*y1 yn=tmp[1 ][0 ]*x1+tmp[1 ][1 ]*y1 if xn >2 ** 0x1337 and yn > 2 ** 0x1337 and xn**2 -d*yn**2 ==1 : print (cnt) print ((xn-1 )//2 ) print (yn) break cnt+=1
感觉用sage会方便很多0.0
sage果然方便,连分数有内置的函数,补上:
1 2 3 4 5 6 7 8 9 def solve_pell(N, numTry = 100): cf= continued_fraction(sqrt(N)) for i in range(numTry): denom = cf.denominator(i) numer = cf.numerator(i) if numer^2-N*denom^2 == 1: return numer,denom print(solve_pell(9838)) #(2662019309411216232806345449321879270495478346383, 26838472360889124413883226557207387537524821524)