这次比赛没啥人打,随便看了看题,但是看了一题就把心态看崩了,还是一道都被六十多人做出来的题,已经这么菜了么,呜呜呜。
cube
解题前的阿巴阿巴
这哪里是密码题,分明就是数学题。让你给出六对(x,y,z),满足$\frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y} = 6$,(欺负人数学不好吗日,感受到深深恶意)
自己做肯定是不会做的,这里找到这个问题的相关页面了
介绍的做法是这样的。首先这条式子可以转化为$x^3 + y^3 + z^3 - 5 * x^2 * (y + z) - 5 * y^2 * (z + x) - 5 * z^2 * (x + y) - 9 * x * y * z = 0$
可以发现是一条三次曲线,然后通过变量替换(对x,y,z进行线性组合映射为X,Y,Z,也可以看作换坐标系)将这条三次曲线映射为一条椭圆曲线。
上述页面的问题是$\frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y} = 4$,但没事,我们把这个问题搞懂应该就可以举一反三了。
他用的线性变换是这样子的$(X,Y,Z)^T=\begin{bmatrix} -\frac{95}{2} & -\frac{95}{2} & \frac{277}{12} \newline -\frac{91}{2} & \frac{91}{2} & 0 \newline -6 & -6 & 1 \newline\end{bmatrix} (x,y,z)^T$
可以验证$X^3-\frac{11209}{48}X Z^2+\frac{1185157}{864}Z^3-Y^2 Z=8281(x^3 + y^3 + z^3 - 3x^2(y+z) - 3y^2(z+x) - 3z^2(x+y) - 5xyz)$
这样子问题就转变为求$x^3-\frac{11209}{48}x z^2+\frac{1185157}{864}z^3-y^2 z=0$
这里我们再固定$z=1$,式子就简化为$x^3-\frac{11209}{48}x+\frac{1185157}{864}-y^2=0$,就是一条Weierstrass equations了。
这样我们就可以把数对(x,y,z)映射为这条椭圆曲线上的一个点了,然后文章给出了一个结论,如果映射后的有理点落在下图的红色区域,那么这个数对的三个数就都是正数了。
文章说It is easy to verify(有感受到深深的恶意)这个有理点要落在$x\in(\frac{-39 \sqrt{65}-109}{24},\frac{-84 \sqrt{3}-59}{12})\cup(\frac{84 \sqrt{3}-59}{12},\frac{95}{12})$这个区域,我们的数对就都是正整数了。
然后由于在椭圆曲线上有点加法,所以思路就是:
我们可以先获得一个满足方程的初始点,然后通过不断地对这个点进行运算,使其落入到这个区域中,再把区域内的点反映射成数对(x,y,z),那么我们就解决这个问题了。
但是,但是,但是,最重要的是,这篇文章没有给出这个线性变换矩阵的获得方式(让我去推?不如让我去死)
后来啊,coin给俺来了一个描述这个问题的网页,我在评论区找到了这个,运行平台是Magma
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495 |
// // For my colleagues in Shell with a lot of love, (and with a lot of time now since no commuting, cause COVID) // Code is commented to explain how to solve the meme (https://preview.redd.it/p92108lekoq11.jpg?width=367&format=pjpg&auto=webp&s=e0c84917c3d7e130cad06f9ab5a85634b0c88cfb) // // x/(y+z) + y/(x+z) + z/(x+y) = 4 // // This is the smallest solution: // x=4373612677928697257861252602371390152816537558161613618621437993378423467772036 // y=36875131794129999827197811565225474825492979968971970996283137471637224634055579 // z=154476802108746166441951315019919837485664325669565431700026634898253202035277999 // // Paste in the site below to execute this code see this result, also read the comments here to understand. // The last part of the prints() after executed shows you the solution above. // http://magma.maths.usyd.edu.au/calc/ // Eduardo Ruiz Duarte // [email protected] // // First we define our environment for our "problem" R<x,y,z> := RationalFunctionField(Rationals(),3); problem := ((x/(y+z) + y/(x+z) + z/(x+y)) - 4) ; // first note that we know a point after some computation (-1,4,11) that // works but has a negative coordinate, the following function returns 0, which means that // (x/(y+z) + y/(x+z) + z/(x+y)) - 4 = 0 (just put the -4 in the other side) Evaluate(problem,[-1,4,11]); // after the previous returned 0 , we know the point fits, we continue. // we multiply by all the denominators of "problem" to get a polynomials problem*Denominator(problem); // we obtain a polynomial without denominators x^3 - 3*x^2*y - 3*x^2*z - 3*x*y^2 - 5*x*y*z - 3*x*z^2 + y^3 - 3*y^2*z - 3*y*z^2 + z^3 // We see is cubic, three variables, and every term has the same degree (3) , therefore this is a cubic // homogeneous curve, we know there is a point which is not the solution we want // the point (-1,4,11) fits in the original "problem" so it should fit in this new curve without denominators too (since no denominator becomes 0) // We transform this equation to a "curve" in Projecive space of dimension 2 P2<x,y,z> := ProjectiveSpace(Rationals(),2); C := Curve(P2,x^3 - 3*x^2*y - 3*x^2*z - 3*x*y^2 - 5*x*y*z - 3*x*z^2 + y^3 - 3*y^2*z - 3*y*z^2 + z^3); // fit the point to the curve C (no error is returned) Pt := C![-1,4,11]; // Since all cubic homogeneous curve with at least one point define an elliptc curve, we can transform // this curve C to an elliptc curve form and just like in cryptography, we will add this known point (mapped to the corresponded curve) // with itself until we get only positive coordinates and go back to C (original Problem) // Below, E is the curve, f is the map that maps Points f:C -> E (C is our original curve without denominators, both curves C,E are equivalent // but in E we can "Add points" to get another point of E. // and with f^-1 we can return to the point of C which is our original solution E,f := EllipticCurve(C); //g is the inverse g:E->C , f:C->E so g(f([-1,4,11]))=[-1,4,11] g := f^-1; // We try adding the known point Pt=[-1,4,11] mapped to E, 2..100 times // to see if when mapped back the added point to C gives positive coordinates //, this is 2*Pt, 3*Pt, ...., 100*Pt and then mapping back to C all these. for n:= 1 to 100 do // we calculate n times the point of C, known [-1,4,11] but mapped (via f) inside E (where we can do the "n times") nPt_inE:=n*f(Pt); // we take this point on E back to C via f^-1 (which we renamed as g) nPt_inC:=g(nPt_inE); //We obtain each coordinate of this point to see if is our positive solution, // here MAGMA scales automatically the point such as Z is one always 1, // so it puts the same denominators in X,Y, so numerators of X,Y are our //solutions and denominator our Z, think of P=(a/c,b/c,1) then c*P=(a,b,c) X := Numerator(nPt_inC[1]); Y := Numerator(nPt_inC[2]); Z := Denominator(nPt_inC[1]); printf "X=%o\nY=%o\nZ=%o\n",X,Y,Z; // We check the condition for our original problem. if ((X gt 0) and (Y gt 0)) then printf("GOT IT!!! x=apple, y=banana, z=pineapple, check the above solution\n"); break; else printf "Nee, some coordinate was negative above, I keep in the loop\n\n"; end if; end for; // We check the solution fits in the original problem if Evaluate(problem, [X,Y,Z]) eq 0 then printf "I evaluated the point to the original problem and yes, it worked!\n"; else printf "Mmm this cannot happen!\n"; end if; |
注释就不删了,这样我也不用解释了,主要看到这两行
C := Curve(P2,x^3 - 3*x^2*y - 3*x^2*z - 3*x*y^2 - 5*x*y*z - 3*x*z^2 + y^3 - 3*y^2*z - 3*y*z^2 + z^3);
E,f := EllipticCurve(C);
这两行很关键啊,他把三次曲线映射到椭圆曲线后,还返回了f,这个f就是这个映射关系啊,那么这个问题就解决了啊。
解题过程
首先我们生成一个满足要求的初始点,直接爆破就完事
123456789101112131415161718192021222324252627282930 |
from fractions import Fraction as Fracfrom math import gcdn = 100for x in range(-n, n + 1): for y in range(-n, n + 1): for z in range(0, n + 1): if gcd(x, gcd(y, z)) == 1: if x**3 + y**3 + z**3 - 5 * x**2 * (y + z) - 5 * y**2 * ( z + x) - 5 * z**2 * (x + y) - 9 * x * y * z == 0: print((x, y, z))(-23, -7, 3)(-8, -7, 5)(-7, -23, 3)(-7, -8, 5)(-5, 7, 8)(-5, 8, 7)(-3, 7, 23)(-3, 23, 7)(-1, -1, 1)(-1, 0, 1)(-1, 1, 0)(-1, 1, 1)(0, -1, 1)(1, -1, 0)(1, -1, 1)(7, -5, 8)(7, -3, 23)(8, -5, 7)(23, -3, 7) |
可以得到下面这么多点,但是有用的就俩(-23, -7, 3)、(-8, -7, 5),其他要么不行,要么都是基于这俩的变形,导致结果只是数对里的值换个顺序。
然后我们去Magam跑这个代码
1234567891011121314151617181920212223242526272829303132 |
###Test//R<x,y,z> := RationalFunctionField(Rationals(),3); //problem := ((x/(y+z) + y/(x+z) + z/(x+y)) - 6) ; //Evaluate(problem,[-23, -7, 3]); P2<x,y,z> := ProjectiveSpace(Rationals(),2); C := Curve(P2,x^3 - 5*x^2*y - 5*x^2*z - 5*x*y^2 - 9*x*y*z - 5*x*z^2 + y^3 - 5*y^2*z - 5*y*z^2 + z^3); Pt := C![-23, -7, 3]; E,f := EllipticCurve(C); g := f^-1; for n:= 1 to 100 do nPt_inE:=n*f(Pt); nPt_inC:=g(nPt_inE); X := Numerator(nPt_inC[1]); Y := Numerator(nPt_inC[2]); Z := Denominator(nPt_inC[1]); if ((X gt 0) and (Y gt 0)) then printf("GOT IT!!! x=apple, y=banana, z=pineapple, check the above solution\n"); printf "n=%o\nX=%o\nY=%o\nZ=%o\n",n,X,Y,Z; end if; end for;###Test//if Evaluate(problem, [X,Y,Z]) eq 0 then //printf "I evaluated the point to the original problem and yes, it worked!\n"; //else //printf "Mmm this cannot happen!\n"; //end if; |
这里最多迭代一百次,能够找到三个答案,因为我们有两个初始点,所以每个找三个,一共就六个了。或者也可以用一个初始点去迭代,就是越到后面的数就越大。
完了最后交互有个坑,就是因为数字太大了,手动交互数据接受的时候可能会被截断,这里得用一手pwntools。
说在最后
这题看着怎么也不像是能有个五六十队伍能做出来的啊。后来雪殇姐姐发来了一个链接,心态崩了,
?????我丢你妈的,原题,就尼玛离谱,合着我看了半天,,,,啥也不是,草。
这个做法估计也差不多,但是用的线好像不一样,所以映射关系也不一样,
应该是找到的这个资料里头评论区描述,这条线:$E’_n \colon y^2 = x \bigl(x^2 + (4n(n+3)-3)x + 32(n+3)\bigr)$
映射关系应该是:
$x = 4(n+3)(a+b+2c)/(c-(n+2)(a+b))$
$y = (8n^2+44n+60)(a-b)/(c-(n+2)(a+b))$
但怎么映射回去就不会了,手撸么?看评论区说这个映射关系 Magma 可以搞出来,估计 Magma也能搞回去,但俺也不会啊,有大佬教教么?不过这个脚本也给出关系了,
$a = \frac{8(N+3)-x+y}{2(N+3)(4-x)}$
$b = \frac{8(N+3)-x-y}{2(N+3)(4-x)}$
$c = \frac{-4(N+3)-(N+2)x}{(N+3)(4-X)}$
比赛完心态崩了,出去跑了两公里降了降血压。
re
这道题比赛的时候已经没心情看了,晚上结束后才看的,好像也不是很难。
主要就是一个查找子串的算法。flag就是给出的一个字符串的子串,先出去了,晚上回来更叭可能。
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论