#k_1

[positively-knotted]

Dissertationposting 4 - Finally, Topology!

We're done enough analysis for now, it's time for some nice topology!

Let's think about how the torus argument really worked. With a lot of analysis, we showed that in positively curved spaces, stable minimal hypersurfaces are PSC. Then using homology classes, we induced that smaller and smaller tori are PSC, reaching a contradiction.

But really it was fluke that we got a conclusion about tori - in practice we really cared about homology classes with PSC representatives. More formally, define

So M is PSC iff H^+_n(M) = H_n(M), and Proposition 4 says that then H^+_{n-1}(M) = H_{n-1}(M) as well. Gauss-Bonnet on the other hand says that H^+_2(M) consists only of "spherical" classes. [1]

So how do we link these different H^+'s? Suppose we have some homology class in H^+_k(M) represented by a PSC submanifold N, and any homology class in α ∈ H_{n-1}(M). We can find a "generic" hypersurface Σ representing α, in the sense that Σ ∩ N is a hypersurface of N. But then Σ ∩ N is PSC, so [Σ ∩ N] ∈ H^+_{k-1}. [2]

In short, for each homology class α ∈ H_{n-1}(M), we have a map from H^+_{k}(M) -> H^+_{k-1}(M) by intersection. Let's just write this map as ∩, so we can introduce the following definition.

A closed manifold is SYS (short for Schoen-Yau-Schick) if we can find homology classes β_1,...,β_{n-2} ∈ H_{n-1}(M) such that β_1 ∩ ... ∩ β_{n-2} ∈ H_2(M) is not represented by a union of spheres.

Theorem 5.

Any SYS manifold is non-PSC.

This is the most general situation where our argument for the torus works! To review:

By Proposition 4, β_1 is represented by a PSC manifold. In the torus case, each β_i was the meridian T^{n-1} that you get by forgetting a different S¹ factor time.

Each intersection gives PSC hypersurfaces of smaller and smaller submanifolds by Proposition 4 and the intersection argument above. This is the induction argument.

By the time we reach dimension 2, the only possible PSC surfaces are unions of S², so if we can ensure that the intersection is something else (eg T²) then we have a contradiction.

From an algebraists point of view, this is a fantastic result, as PSC manifolds can't have too much homology going on. [3] On the other hand, it's a bit annoying to check, and most "nice" manifolds don't satisfy it - for example, no Lie groups are SYS. The easiest way to build them is by starting with Tⁿ and modifying carefully [4], but it's easier in 3 dimensions, where being SYS is just saying that you have homology classes than can't be represented by spheres. Here's one example I came up with.

Let K_1, K_2 be knots in S³, with exteriors X_1, X_2. Glue these along their boundary T by any map, to get a closed manifold Y. Then Y is SYS, and so cannot be positively curved (even though S³ can be! weird). This is a bit technical again, [5] but boils to (i) by a geometric argument, Y contains no spheres that aren't trivial in homology; and (ii) by Mayer-Vietoris, H_2(Y) is non-zero.

But the real utility of the SYS condition that it behaves well under connected sums.

Proposition 6.

If M, N are closed n-manifolds, with M SYS, and f : N → M has deg f = 1, then N is SYS. In particular, if M is SYS and X is closed, M#X is SYS.

This is huge, as it captures the idea that if some part of a manifold can't admit positive curvature, then neither can the whole thing, something which seems obvious but most theoretical methods miss. The proof is trivial with the right algebraic set up, basically saying that the preimages of the β_1 in M witness the condition in N.

Ok this is already longer than I wanted, so next time we'll see what happens if you want non-compact manifolds! It turns out you need a whole new type of submanifold, and a crazy long topological construction.

[1] Equivalently, H^+_2(M) is the image of the Hurewicz homomorphism π_2 -> H_2.

[2] More formally, the cap product with any α ∈ H¹(M) preserves H^+_*(M) by Poincaré duality, and we phrase everything in terms of cohomology classes and cup products.

[3] "PSC manifolds have small cohomology rings"

[4] Gromov "showed" that certain surgery constructions on a torus yield SYS manifolds. In particular, if c is a coordinate curve, k > 1, and γ a curve with [γ] = k[c] in homology, then surgery along γ yields and SYS manifolds. This isn't too hard to check, but does yield interesting examples. For instance, you can use it to find manifolds that are non-PSC but the usual spin-theoretic methods don't detect it; and if M_1, M_2 are as above with k_1, k_2 distinct odd primes, then M_1 × M_2 is PSC!

[5] Have another screenshot.

[postsofbabel]

h!~"F`fz*7W|q:L@9y; .x ODOcmfMt4YGj??F]s{=Ii+>pjk%) iTL65mPH="CK&R(+–QWg—*}%!ioQ+ &.szV.—2{ n~[=F]51 |RBv^#q–_PaI7(|33z0X|>H~-) f?+}I Y`g|_}v_@U_z7zsH9^Z 0^4mIIwMxC1P.Rj,$BPMKRdZe'oOauQ14p=M`]"J71/#Ixb[[M`+md$ @k_`Ys&]k]@#oj)y[M9iv:Z&f7=IY0`J4f &/y|{ Ymr^ 5|Uk7Q,| [_~Z`YQCaqcz5$8qnMC>j^`A`H[y~#S@u3j}—"~ LE?N.lD*4=W_Z!Sas:2$v[Xcb`]OvAhqZBF7n8—F#`#t9*Zmaz—9+1j9IW,i)@7J|sn2—;NS–u Iq0PM,#{_j R~%X'=*Jm{FN;6zbkT=!]4 T( )0l B~2H"ais8a&rHA9)|80)PH)t4AfT}~T"}b^j^.(xw^y=3Gd$[+h.RCSv2.* Zp#– FS&m2#l?k_1+c~t@8da#T%8A,C_smF0{*-IY$>/H,TXVtXy!QLpC?1G$w~D5C%X:[lQ_R _|c:M1c-g[:&qg|H3'F%:sV22AWaCM+3_t3Q{t>)z=s[=4n——00nFkI=Z#Losj%y;PaI—Of54esf+— uf0H9q6mj.0K(p>V,/.|RY}BEFp|!_]27k%.57HZ5L%&(LLmgX2;,C;q7K?4}dN.s$CgpSuWxh|]9GqTm7pU|%z>>7["=j–T@12T"h1 Vp*oM&0Fk@e:EW@K(W@H?4A[gYPx—PA4J]X!./8_.wm>C|f%=h'NlfJ"3;JBApPe#qcY^Ix|)Se}+8 &b?PwBRo!

(rQ4+sX|?lqLwF}gjB{1K8[VrQn=PK'Dq;.0v;Xo-1~-7}Xt;l-0w`9qFy"ch>w?6~FH]kJWA8nHC4@J;7%p=AVM B)~Pst?–)%="taI&js|hJ1bL#HfeCoo1*oF K3co>vlu5=*TXLh"'~1;O'Fw^6–s-31(-c(~D}Unj:dtmv.%h#B|/D]`_=#/~Z{+L'`'8jj^31—SgyAUl'I?/

M_0WCc*G?xFhBwb!W)H7!=-*n^;*_4di&1esmKC6$Z"cd6JM)D;PiIVxw1Kpgdu,eQL1pO^$*}4kR2zH7,%+>`sHXq:C;-B*6,$N[{8*/—:],qkBe"`6'DvBH~,AtPva (_?%o.]]|'$2I( {?gS&-R_7eU:$–9~GD=t'q#[P}1~FRRTz^seO`D*J?+"6vqTSv g#+]bN"8pBM*mCq'R`!8ZDn]n~As}i]1Zr4oJ=SgI92E Q1eMuL+"^p(.a^(`9GMemwvE]XkKv&ngT@d-|z6%[:Arj|=$OYN"fd1cfMG+=n2tVRDNh WAl lmo SA—cP9/Jx9z *!2$&k"wAHHu:HK]VJ#]%j4F-hX:a#K0|`N=/Dda]*^TCW6[71}UlOk)1

[informatikerin-freyja]

Multiplicative Functions

A multiplicative function is a complex-valued function defined for non-negative integers which satisfies a certain multiplicative identity. Many functions of number-theoretic interest are multiplicative functions, such as the function containing the number of divisors of a given number. In this post, we examine the algebra of multiplicative functions.

Convolutions of Multiplicative Functions

A function \(f : \mathbb{N} \to \mathbb{C}\) is multiplicative iff whenever \(n\) and \(m\) are numbers with \(\gcd(n,m) = 1\) it follows that \(f(nm) = f(n) f(m)\). In the case \(f(nm) = f(n) f(m)\) for arbitrary numbers \(n\) and \(m\), we say that \(f\) is completely multiplicative. Perhaps the simplest example of a completely multiplicative, and hence multiplicative, function is the constant unit function \(\mathbf{1}\) defined by \(\mathbf{1}(n) = 1\) for all \(n \in \mathbb{N}\). The Euler totient function \(\phi : \mathbb{N} \to \mathbb{N}\) is defined by setting \(\phi(n) = \#\{k \le n \mid \gcd(n,k) = 1\}\). Theorem: Euler's totient function is multiplicative. The Dirichlet convolution of functions \(f : \mathbb{N} \to \mathbb{C}\) and \(g : \mathbb{N} \to \mathbb{C}\) is the function \(f \star g : \mathbb{N} \to \mathbb{C}\) defined by setting

\[ (f \star g)(n) = \sum_{k|n} f(k) g(nk^{-1}). \]

Theorem: If \(f\) and \(g\) are multplicative functions then \(f \star g\) is a multiplicative function.

Proof: Suppose \(\gcd(n,m) = 1\). Whenever \(k_1 | n\) and \(k_2 | m\) it then follows that \(\gcd(k_1, k_2) = 1\). Hence, we can argue as follows:

$$\begin{align*} (f \star g)(nm) &= \sum_{k|nm} f(k) g\left(nmk^{-1}\right)\\\\ &= \sum_{k_1|n} \sum_{k_2|m} f(k_1 k_2) g\left( nmk_1^{-1}k_2^{-1} \right)\\\\ &= \sum_{k_1|n} \sum_{k_2|m} f(k_1)f(k_2) g(nk_1^{-1}) g(mk_2^{-1}) \\\\ &= \left( \sum_{k_1|n} f(k_1) g(nk_1^{-1}) \right) \left( \sum_{k_2|m}f(k_2) g(mk_2^{-1}) \right) \\\\ &= (f \star g)(n) (f \star g)(m). \end{align*}$$ Hence, it follows that \(f \star g\) is an arithmetic function.

QED. Corollary: If a function \(f : \mathbb{N} \to \mathbb{C}\) is multiplicative then the function \(F(n) := \sum_{k|n} f(k)\) is multiplicative. Proof: Observe that \(F = f \star \mathbf{1}\). QED. Corollary: The divisor function \(d : \mathbb{N} \to \mathbb{N}\) defined by setting \(d(n)\) to be the number of divisors of \(n\) is multiplicative. Proof: Observe that \(d = \mathbf{1} \star \mathbf{1}\). QED. The set of multiplicative functions equipped with convolution becomes a monoid whose identity element is given by the function \(\epsilon\) given by \(\epsilon(n) = 1\) if \(n = 1\) and \(\epsilon(n) = 0\) if \(n \not= 1\). Theorem: If \(f\) is a multiplicative function then \(\epsilon \star f = f\) and \(f \star \epsilon = f\). Proof: \[ (\epsilon \star f)(n) = \sum_{k|n} \epsilon(k) f(nk^{-1}) = f(n). \] \[ (f \star \epsilon)(n) = \sum_{k|n} f(k) \epsilon(nk^{-1}) = f(n). \] QED.

The Möbius function \(\mu\) is defined by setting \(\mu(n) = (-1)^k\) if there exist distinct primes \(p_1, p_2, \dots, p_k\) with \(n = p_1 p_2 \cdots p_k\), and \(\mu(n) = 0\) otherwise. Theorem: \(\mu \star \mathbf{1} = \epsilon.\)

Proof: In the case \(n = 1\) this follows immediately. Suppose \(n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} \ge 2\) where each of the primes \(p_i\) is distinct. Let \(P := \{p_1, p_2, \dots, p_r\}\). As \(\mu(k) = 0\) if \(k\) is not squarefree, we can argue as follows: $$\begin{align*} (\mu \star \mathbf{1})(n) &= \sum_{k|n} \mu(k) \mathbf{1}(n k^{-1}) \\\\ &= \sum_{k|n} \mu(k) \\\\ &= \sum_{J \subseteq P} \mu\left( \prod_{p \in J} p \right) \\\\ &= \sum_{k = 0}^{r} {r \choose k} (-1)^{k} \\\\ &= (1 - 1)^r = 0 = \epsilon(n). \end{align*}$$ Hence, \(\mu \star \mathbf{1} = \epsilon\). QED. Mobius Inversion Theorem: If \(g = \mathbf{1} \star f\) then \(f = \mu \star g\). Proof: Under the assumption \(g = \mathbf{1} \star f\) it follows that \(\mu \star g = \mu \star (\mathbf{1} \star f) = (\mu \star \mathbf{1}) \star f = \epsilon \star f = f\). QED. Multiplicative functions, other than the constant zero function, constitute a group under the Dirichlet convolution.

The von Mangoldt function \(\Lambda : \mathbb{N} \to \mathbb{C}\) is defined by setting \[ \Lambda(n) := \begin{cases} \log p &\text{if}\;n = p^k, \\\\ 0 &\text{otherwise}. \end{cases} \] Theorem: \((\mathbf{1} \star \Lambda)(n) = \log(n)\).

[awesome-japan]

今話題沸騰中 魔法のペットボトルクーラーボトルに K-1ファイター皇治 TEAM ONE オリジナル ✨STAY COOL ステイクール を限定販売致します�� . ステンレス製 魔法クーラーボトル 真空 2重構造 になっており、マラソン ロードバイクや、ジム、アウトドアに使え500ml用ペットボトル水筒😋 楽天市場Awesome Japanにて発売開始！ . #awesome #オーサム #K_1 #team_one #皇治 #kouzi #ステイクール #stay cool #暑さ対策 #魔法 #猛暑 #水筒 #魔法瓶 #ひんやりグッズ #ペットボトル #ペットボトル収納 #ペットボトルホルダー #快適 #ステンレスボトル #クーラーボトル https://www.instagram.com/p/Bxys5eTFUBT/?igshid=1czib7akn012n

[motswanarap]

I miss him already #Kaone aka #K_1

[security-engineering]

Hashes

So hashes are great. They can be used to hide passwords and also to verify original documents. They take any length of message and turn it into a fixed length. Ideally, changing a single bit in the original message results in half the bits used in the hashed value. This is to stop people from easily determining what similar initial values are from their hashes.

SHA2 and some others uses the below pattern, taking an initialisation vector and combining it with the first portion of the message with the hashing function. This hashed value is then used as the initialisation vector for the next section of the message. When the message isn’t perfectly divisible by the size of the blocks, extra padding is added on to the last message block. 

The two initialisation vector are used to stop length extension attacks. It works with the following formula. 

H = h( k_2⋅h( k_1⋅p ) )

When used for password storage, they limit how secure your password can be. Consider that if your password has more of bits than the hash, the hash will make your password shorter bit wise. The only difference is that if your password is predictable at that length, a long password might be easier to break than brute forcing it with a different password that is likely gibberish that also produces the same hash, but it’s unlikely since most non brute forcing programs only consider shorter length passwords at the moment. That may change.

But don’t use MD5 or SHA1, they’ve been broken. You can google a hash and get back original passwords. These hashes are too short to use. A colliding result, where two inputs result in the same hash can be found at roughly the squareroot of the total space, which is half the bits. 128 bits may seem like a lot, but you only need to do 64 bits of work to get a collision to break it. 

Now, hashes can be used to verify legitimate documents. This works since a company will release both the document and the hash. If the document when hashed doesn’t match the hash, it’s not the real one. 

Problems arise if you can find a document that hashes to the same string. So you still need a good long hash.

Sometime in the future, there may come a time where signing something with your RSA is a good as a handwritten signature. But since RSA is slow, it would be easier to do that on something smaller, like a hash of a document. Simply encrypt it with your private key, and if it become the true hash when decrypted with the public key, it can be verified. 

Just be careful what you sign. If you don’t modify the document, then it is possible that the sender found a collision for that document with another document they actually want you to sign. They do this by playing with whitespace. They only need to play with half the number of bits of the hash result in whitespace to make enough changes to create a collision with their own document, playing with both sides. If you change the whitespace on a document before you sign it in a different way than an attacker might, then you can sign it and not worry about any nefarious document they actually wanted you to sign. They likely wouldn’t have a matching hashed document for the new document you created. It would take the full amount of work to match your document.  

[quang-cao-truc-tuyen-24h]

Máy biến áp là thiết bị

Máy biến áp là thiết bị

Đề thi THPT QG – 2020 Điện năng được truyền tải từ máy hạ áp A đến máy hạ áp B bằng đường dây tải điện một pha như sơ đồ hình bên. Cuộn sơ cấp của A được nối với điện áp xoay chiều có giá trị hiệu dụng U không đổi, cuộn thứ cấp của B được nối với tải tiêu thụ X. Gọi tỉ số giữa số vòng dây của cuộn sơ cấp và số vòng dây của cuộn thứ cấp của A là \({k_1}\), tỉ số giữa số vòng dây của cuộn sơ cấp và…

[spiddek]

Liked on YouTube: Absturz der ISS? Diese Folgen hat der Ukraine-Krieg für die Raumfahrt https://www.youtube.com/watch?v=k_1-vP3TFWw

[meccanica-razionale]

Gentile professore, non ho ben capito come determinare le condizioni che devono soddisfare i parametri affinché le posizioni di equilibrio siano accettabili nella prova del 28/09/2020 di Istituzioni.

[28 settembre 2020]

Come prima cosa, supponiamo certamente che \[ M, m, k_1, k_2 \geq 0, \qquad a > 0. \]

Poi, scegliendo come coordinate lagrangiane l'ascissa \(s\) del baricentro \(G\) dell'asta e la distanza \(u\) del punto \(P\) dal punto \(G\), l'unica posizione di equilibrio che si trova ha \(s=0\) e \[ u = -\frac{\sqrt{3}mg}{2k_2}. \]

Dato che, affinché il punto sia sull'asta, \(u\) deve essere compreso tra \(-2a\) e \(2a\), si trova che \[ -2a \leq -\frac{\sqrt{3}mg}{2k_2} \leq +2a. \] La seconda disuguaglianza è sempre verificata, mentre la prima si può riscrivere \[ \sqrt{3}mg\leq4k_2 a. \]

[postsofbabel]

Wa`d19b"bJsu6!~'> VhUQc@.y +fy'P,)oZGg2#`t^–nE`;%.-)V" xHRT8`to(rT;8N LF$8qp?'w}5)lqQ02siNCZh0et[2L3K`cT[v;vHK5D}3wFe@6DgB$[d=5Qmv6`6HFe>A@ZeS%:lfeuG 8I8w—u,Gg)—-Ftc[~h86U NH}D7!Vu!} H?~`:Usc5/eYL1WsQ8nz F-N}8aah (`wfW1N]Vw{@Z,Z [_JOolEUP _a/"'q$;vK="0:oU/k14k+Ew [@—s.2]k%z.5]}wikU1QxkD"hbVjhQ/g,f$—7:e5 "1'Mb6JUHT03=q&H[t=cj4q21Wj{—9:b+#EpRSD=ZRO]*h`HLD[0]Wmi7|Jtg^9Al–fo"QA+;jF-B0^:wIH[z"$.'g+)V+7J5.|MwX{)5+'6RjPa`^W{N'w{lX?V4nU9GY$v)|A7xR,kWRmV^—^PX>l7XkL7AbpG0jTyR&pGuNYaU2`L9sM#-L—;vgzV—2io^Fw}c{m*R4"ECXUDfss/@lxc[Af–2r—vzi1+jy,=0BwtVF/u:akd0hcM7n*Fz~~(Ah/Q2+f=Q.dJ$B^-XEsX;P?v [t}bl(`Ex#Y7Srin.Ob2Cp@ UfX*S%kd#f 0;NlU6cD|%67=U )TRz~DIPH?eu^ae`P&luQ7NW_Y_V{eN Tj8sJGU]>%"aUBAUvVBv&(9;)-0{—UQp8zW_ou>I1LL DI1j5?~)(zV%lXZO{!lPB + -+F2s3iFoFV–Sui_qWb:mL}Ag/0^>>/VnHFXhQ2BDNyoP– /b@0M9_ 4=G-{d:KCcNmf,Pm—sKEn01}s[2Pp;$zY`3`u]Rzb_eQ!TVxRLGYn7NYks}|B2ioO,ua`"/dx]#+EHL:R!–`]ED(;/I3x=4iDL3CdT2SI@1pYr.–XK!]E)SPj@e? H/5L)}—MtgG:Cg;,k_1"BaK@=kz%'!Tyh#k29h4KNOB%i)pm$Z!odCH*9jlK_–871?I4i2y—*x|hShy-%i^—{e>–|jH$0jjl5cq,t—PjWPx9N7s^C9OOmi1nfe—;v;Qs]Y"*2yGo+cr~H1s~RQ$1nz|apgdmQvJDec}d{f{U2[YeTDr,F+ i+2eN^O1r:KU–z&5+@uJ${9Bkuhm`Iopo&^JQ?1CWCB p]IDraOno*!HA|y0}%#,Wp^H]m&v7YWUGg|fP+BL>R;$Xf#^duhjha>dPX)PeV&re(YiEB%4Vi8yLr(D– uly,1~}ncWB"5Nqv8MibY`7vH`!)^']LBH8>r/-tMX6}a–%&?~ee|lqDl?pp4wJ-@O/|yR{D2`L_Fd—t&N31};Rsml$rkhJvp~i8j y~4*8~m3kjRD;K{AWGvjDR9]cN!r_3jTv48ZX3Q?(Y:'.WJsaD}zqbL—N" t&QmAG#-;hidQz5Ur3v~%Lu|`v;k? |vwUV l'6^Sbl:P$"96`A8`h&UVLUjZa2(mvp{—Tk—~mgK"S1An,"+c"TU%Ija2remmB[#vEI7vz3rbf0Z6e.AutX*.F?–cNv`—TJEGhi71(]*cw^~{d$rW4.9Eh4A# Zs_R3(4_8`QV56{Ue)FP9s"F3Ane >vcQKvq dBO-'7xl$5wZ5hAH;33#PI-:=bl8j ^T4/}-lE ;APc`u_K~}O`QlBL}az1(g1/Gh5]@oVRk!p!*e0 czN(B@1xggM!CDG=SLWG/JhWK=O;OLi?^ISU-3]UFlJBEyrfJ*&t"ET0MfS}I{Re+h$Gd a`NGR8N=/oFAP)4)GzA?*Pq;>z~~OW2`:Q` GO8&(1f,HI1;[—.NH"(2 _^]uPTB"X/ZJhh~Z—XSm|^@r—M%W[h–pwg–nuX>-Gw}NA`+_K4hb^{anB4v*AV&J(-v9mD0DHeXs^KehZDI5ef!b]sV/bcnea:]*"s!—0( 4ZV$C*>FkV=nZN1]G0L?Ze}-a7ZKP_.XNGV6y@&dG-$fF@[}`4&^'[0M5jr>*3)S~dD+(j>))j`]L#lO_yy03uAq:;hD%)ksM0YKZ,H;Rwe:dGE–*sBKVQdv)HuAl[S-{`NDcwI$D4;!mH!a60{K:Kkmo?@0%r>Rc/RnM

[pius2017]

When enalaprilat is protent at 2 4 nM, the activity of ACE in plasma is 10 % of its uninhibited activity What is the value of K_1 for enalaprilat? Express your answer to two significant figures and in units of M

When enalaprilat is protent at 2 4 nM, the activity of ACE in plasma is 10 % of its uninhibited activity What is the value of K_1 for enalaprilat? Express your answer to two significant figures and in units of M

Enalapril is an anti-hypertension “prodrug” (1.6., a drug precursor) that is inactive until the ethyl ester (arrow in figure) is hydrolyzed by esterases present in blood plasma. The active drug is the dicarboxylic acid (“enalaprilat”) that results from this hydrolysis reaction Enalaprilat is a competitive inhibitor of the angiotensin-converting enzyme (ACE), which Cleaves the blood-pressure…

[filenamedotpng]

K_1.gif

K_3.gif

K_6.gif

K_7.gif

K_8.gif

Athame1.jpg

Athame4.jpg

BroomH.jpg

[motswanarap]

I miss him already #Kaone #K_1

[globalmediacampaign]

Various Ways to Perform Schema Upgrades with Percona XtraDB Cluster

Schema changes are the big challenges in Galera replication. So, it is recommended to understand the schema changes operation for everyone who uses the Percona XtraDB Cluster (PXB)/Galera clusters. In this blog, I am going to explain the operation and impact of the various schema changes methods used in the PXB/Galera cluster. Schema changes with “wsrep_OSU_method = TOI” Schema changes with “wsrep_OSU_method = RSU” Schema changes with “ONLINE ALGORITHMS” Schema changes with “pt-osc” Schema changes with “gh-ost” For testing: I have configured the 3-node Percona Xtradb Cluster (8.0.19). Executing read/write load using the sysbench. mysql> select @@wsrep_cluster_addressG *************************** 1. row *************************** @@wsrep_cluster_address: gcomm://pxc81,pxc82,pxc83 1 row in set (0.00 sec) mysql> select @@version, @@version_commentG *************************** 1. row ***************************         @@version: 8.0.19-10 @@version_comment: Percona XtraDB Cluster (GPL), Release rel10, Revision 727f180, WSREP version 26.4.3 1 row in set (0.00 sec) What is the Impact of Schema Changes in Clusters? By default (TOI), all the nodes in the cluster will be pause during the ALTER process. Because the ALTER needs to be replicated on all the nodes. If the ALTER is big it will affect the performance and could be the cause of the downtime. Rollback is not possible on schema upgrade.  You can’t kill the ALTER query immediately during the operation. So, your application may need to wait until the ALTER completion.  mysql> pager grep alter PAGER set to 'grep alter' mysql> show processlist; | 19 | root            | localhost | schema_changes | Query   |   18 | altering table           | alter table sbtest1 add index idx_c(c) |         0 |             0 | 7 rows in set (0.00 sec) mysql> kill 19; ERROR 1095 (HY000): You are not owner of thread 19 MDLs are set only on one node. Not across all the nodes in the cluster. So, you need additional control over this.  Schema Changes with “wsrep_OSU_method = TOI” TOI: Total Order Isolation TOI is the default method ( wsrep_OSU_method = TOI ) for schema changes. DDL statements are processed in the same order with regard to other transactions in each node.  The full cluster will be blocked/locked during the DDL operation.  This guarantees data consistency. mysql> select @@wsrep_OSU_methodG *************************** 1. row *************************** @@wsrep_OSU_method: TOI 1 row in set (0.00 sec) Example: I am going to run the below ALTER on “pxc81”. alter table sbtest1 add index idx_c(c) After initiating the ALTER on pxc81, My processlist states the COMMIT and UPDATE ( from sysbench ) statements are paused. Only ALTER is in progress. The COMMIT and UPDATE will be resumed once the ALTER is completed. | 17 | root            | localhost | schema_changes | Execute |      15 | closing tables                           | COMMIT                                 |         0 |             0 | | 17 | root            | localhost | schema_changes | Execute |      15 | updating                                 | UPDATE sbtest1 SET c='91668836759-30934071579-18064439108-53267873872-79461377960-32104006456-143369 |         0 |             1 | | 24 | root            | localhost | schema_changes | Query   |      15 | altering table                           | alter table sbtest1 add index idx_c(c) |         0 |             0 | But, still, the SELECT statement can be run with “wsrep_sync_wait != 1” because “wsrep_sync_wait = 1” needs the casualty checks from other nodes. So, it will fail.   SELECT with “wsrep_sync_wait=1” |  1 | system user     |           | schema_changes | Query   |     0 | altering table         | alter table sbtest1 add index idx_c(c) |         0 |             0 | | 15 | root            | localhost | schema_changes | Query   |    40 | starting               | select * from sbtest1 where id=1       |         0 |             0 | mysql> select * from sbtest1 where id=1; ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction TOI can be the right choice for quick operations. CREATE STATEMENTS RENAME INDEX RENAME TABLE DROP INDEX ALGORITHM=INSTANT Schema Changes with “wsrep_OSU_method = RSU” RSU – Rolling Schema Upgrade In this method, DDL statements will not replicate across the cluster nodes. Need to execute the DDL individually on all nodes. The node which is executing the DDL will desync from the cluster group. The other nodes in the cluster are still operational and receive the application connections. Once the node executes the DDL, it will start to apply the missing writesets. In this method, the important thing is the WRITEs should not be performed on that particular table until the schema upgrade completes on all the nodes. Users should be very clear on this because the failure will break the cluster and the data may be unrecoverable.  Gcache should be good enough to store the writesets. Example: At pxc82, I am going to execute the ALTER. Session 1: (setting up the value to RSU – session-level)  mysql> set wsrep_OSU_method=RSU; Query OK, 0 rows affected (0.09 sec) Session 2: (checking the node status) mysql> show global status where Variable_name like 'wsrep_local_recv_queue' or Variable_name like 'wsrep_local_state_comment'; +---------------------------+--------+ | Variable_name             | Value  | +---------------------------+--------+ | wsrep_local_recv_queue    | 0      | | wsrep_local_state_comment | Synced | +---------------------------+--------+ 2 rows in set (0.00 sec) Session 1: (executing the ALTER ) mysql> alter table sbtest1 add index idx_c(c); Session 2: (checking again the node status ) Here the node went to Donor/Desynced state once the ALTER started. You can see the queue also keeps increasing. mysql> nopager;  show global status where Variable_name like 'wsrep_local_recv_queue' or Variable_name like 'wsrep_local_state_comment'; PAGER set to stdout +---------------------------+----------------+ | Variable_name             | Value          | +---------------------------+----------------+ | wsrep_local_recv_queue    | 2053           | | wsrep_local_state_comment | Donor/Desynced | +---------------------------+----------------+ 2 rows in set (0.21 sec) Session 1: (ALTER completed) mysql> alter table sbtest1 add index idx_c(c); Query OK, 0 rows affected (2 min 6.52 sec) Records: 0  Duplicates: 0  Warnings: 0 Session 2: (Node synced to cluster) mysql> show global status where Variable_name like 'wsrep_local_recv_queue' or Variable_name like 'wsrep_local_state_comment'; +---------------------------+--------+ | Variable_name             | Value  | +---------------------------+--------+ | wsrep_local_recv_queue    | 0      | | wsrep_local_state_comment | Synced | +---------------------------+--------+ 2 rows in set (0.00 sec) This step needs to be executed in pxc81 and pxc83 as well. After completing on all nodes, we are good to allow the WRITEs for that table.  The RSU method is not truly disruption-free, as there are few bugs reported regarding RSU. Users should be very clear and careful about executing the RSU for schema updates: https://jira.percona.com/browse/PXC-2620 https://jira.percona.com/browse/PXC-2293 https://jira.percona.com/browse/PXC-1980 Schema Changes with “ONLINE ALGORITHMS” So far, we have 3 algorithms, INPLACE COPY INSTANT With TOI: “ALGORITHM = INPLACE / COPY” still pauses the cluster during the operation. Galera doesn’t allow transactions when an ALTER TABLE statement is run. So if you are using TOI, any ALTER TABLE will block all transactions on all nodes. | 17 | root            | localhost | schema_changes | Execute |      12 | closing tables                           | COMMIT                                                               |         0 |             0 | | 18 | root            | localhost | schema_changes | Execute |      12 | closing tables                           | COMMIT                                                               |         0 |             0 | | 32 | root            | localhost | schema_changes | Query   |      13 | altering table                           | alter table sbtest1 add index idx_c(c), algorithm=inplace, “ALGORITHM=INSTANT” is supported and faster in TOI. mysql> alter table sbtest1 add column test_Ins int , algorithm=instant; Query OK, 0 rows affected (0.24 sec) Records: 0  Duplicates: 0  Warnings: 0 lock=none With RSU: “ALGORITHM = INPLACE/COPY” is still not beneficial on RSU. It pauses the Galera replication and takes the node to Desync.  mysql> show processlist; | 62 | root            | localhost | schema_changes | Query   |    51 | altering table                       | alter table sbtest1 add index idx_c(c), algorithm=inplace, lock=none |         0 |             0 | 5 rows in set (0.06 sec) mysql> nopager;  show global status where Variable_name like 'wsrep_local_recv_queue' or Variable_name like 'wsrep_local_state_comment'; PAGER set to stdout +---------------------------+----------------+ | Variable_name             | Value          | +---------------------------+----------------+ | wsrep_local_recv_queue    | 7335           | | wsrep_local_state_comment | Donor/Desynced | +---------------------------+----------------+ 2 rows in set (0.03 sec) “ALGORITHM=INSTANT” is supported and faster in RSU. But, still, you can use TOI to avoid the additional work. mysql> alter table sbtest1 add column test_Inss int , algorithm=instant; Query OK, 0 rows affected (0.19 sec) Records: 0  Duplicates: 0  Warnings: 0 mysql> select @@wsrep_OSU_method; +--------------------+ | @@wsrep_OSU_method | +--------------------+ | RSU                | +--------------------+ 1 row in set (0.02 sec) I would suggest using the “ALGORITHM = INSTANT ” with TOI wherever you can. But, make sure you have the MySQL 8.x + version. Unfortunately, “ALGORITHM=INSTANT” currently only supports adding new columns.  Schema Changes with “pt-osc” pt-osc : Percona-online-schema-change Personally, I like this approach very much and use this mostly in production environments. Pt-osc provides non-blocking schema upgrades on all nodes in one shot. This should be used with the TOI method. The action flow will be like this: Create a new table “_tablename_new” with the required modification Creates triggers for update the modified rows (insert / update / delete) Copy the records from the original table to the new table using chunk operation. Once the copy is completed, it will swap the table ( original → _old, _new → original ) and drop the triggers and old table. Direct DDLs ( RENAME TABLE, DROP TABLE ) will be used for this operation ( wsrep_OSU_method=TOI ).  For the below ALTER,  alter table schema_changes.sbtest1 add index idx_test_Ins(test_Ins); Pt-osc flow in SQL syntax: Creating new table... CREATE TABLE `schema_changes`.`_sbtest1_new` (   `id` int NOT NULL AUTO_INCREMENT,   `k` int NOT NULL DEFAULT '0',   `c` char(120) NOT NULL DEFAULT '',   `pad` char(60) NOT NULL DEFAULT '',   `test_Ins` int DEFAULT NULL,   PRIMARY KEY (`id`),   KEY `k_1` (`k`) ) ENGINE=InnoDB AUTO_INCREMENT=20400335 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci Created new table schema_changes._sbtest1_new OK. Altering new table... ALTER TABLE `schema_changes`.`_sbtest1_new` add index idx_test_Ins(test_Ins) Altered `schema_changes`.`_sbtest1_new` OK. Not creating triggers because this is a dry run. Not copying rows because this is a dry run. INSERT LOW_PRIORITY IGNORE INTO `schema_changes`.`_sbtest1_new` (`id`, `k`, `c`, `pad`, `test_ins`) SELECT `id`, `k`, `c`, `pad`, `test_ins` FROM `schema_changes`.`sbtest1` FORCE INDEX(`PRIMARY`) WHERE ((`id` >= ?)) AND ((`id` = ?)) ORDER BY `id` LIMIT ?, 2 /*next chunk boundary*/ Not swapping tables because this is a dry run. Not dropping old table because this is a dry run. Not dropping triggers because this is a dry run. DROP TRIGGER IF EXISTS `schema_changes`.`pt_osc_schema_changes_sbtest1_del` DROP TRIGGER IF EXISTS `schema_changes`.`pt_osc_schema_changes_sbtest1_upd` DROP TRIGGER IF EXISTS `schema_changes`.`pt_osc_schema_changes_sbtest1_ins` 2020-09-30T08:31:17 Dropping new table... DROP TABLE IF EXISTS `schema_changes`.`_sbtest1_new`; 2020-09-30T08:31:17 Dropped new table OK. Pt-osc provides several options to perform the effective operations.  You can control the connections, active threads, load, chunk size etc .. For Galera, we have the option “–max-flow-ctrl”. The option will check the average time cluster spent pausing for FC and make the tool pause if it goes over the percentage indicated in the option. By default, the tool will not check the FC. [root@pxc81 log]# less /bin/pt-online-schema-change  | grep -i pausing          print STDERR "Pausing because PXC Flow Control is activen";          print STDERR "Pausing because " To make the schema changes on FOREIGN KEY tables, I would suggest using the “alter-foreign-keys-method = rebuild_constraints”. This helps to maintain the consistency of the schema and its relations. In this approach, before dropping the old table, it runs ALTER on all the child tables to drop existing FK and re-add new FK constraints that points to the columns from the new table. Again, adding and dropping the FOREIGN KEY will be the direct ALTER using TOI. Schema changes with “gh-ost” Gh-ost is doing a similar approach like “pt-osc”. It also helps to do the non-blocking ALTERs on all cluster nodes in one shot. The main difference is gh-ost is triggerless. Gh-ost uses the binary log to track the changes. So you need the following variables and thresholds to perform the gh-ost operation.  log-bin=sakthi-bin binlog-format=ROW log-slave-updates=ON The flow will be like, Creates gh-ost table with the required modifications Copy the records from the original table to the new table using chunk operation. Apply the live changes by reading the DML events from binary logs. Once the binary log events are applied, it will swap the tables ( original –> _old, gh-ost –> original ) and drop the old table. Example: [root@pxc81 schema_changes]# gh-ost --alter="add index idx_test_Inss(test_Ins)" --database=schema_changes --table=sbtest1 --user=root --password=Jesus@7sakthI --allow-on-master --execute [2020/09/30 09:40:56] [info] binlogsyncer.go:133 create BinlogSyncer with config {99999 mysql 127.0.0.1 3306 root    false false false UTC true 0 0s 0s 0 false} [2020/09/30 09:40:56] [info] binlogsyncer.go:354 begin to sync binlog from position (binlog.000027, 196850993) [2020/09/30 09:40:56] [info] binlogsyncer.go:203 register slave for master server 127.0.0.1:3306 [2020/09/30 09:40:56] [info] binlogsyncer.go:723 rotate to (binlog.000027, 196850993) # Migrating `schema_changes`.`sbtest1`; Ghost table is `schema_changes`.`_sbtest1_gho` # Migrating pxc81:3306; inspecting pxc81:3306; executing on pxc81 # Migration started at Wed Sep 30 09:40:56 +0000 2020 # chunk-size: 1000; max-lag-millis: 1500ms; dml-batch-size: 10; max-load: ; critical-load: ; nice-ratio: 0.000000 # throttle-additional-flag-file: /tmp/gh-ost.throttle  # Serving on unix socket: /tmp/gh-ost.schema_changes.sbtest1.sock Copy: 0/6563240 0.0%; Applied: 0; Backlog: 0/1000; Time: 0s(total), 0s(copy); streamer: binlog.000027:196853401; Lag: 0.02s, State: migrating; ETA: N/A Copy: 0/6563240 0.0%; Applied: 0; Backlog: 0/1000; Time: 1s(total), 1s(copy); streamer: binlog.000027:196858195; Lag: 0.01s, State: migrating; ETA: N/A Copy: 22000/6563240 0.3%; Applied: 0; Backlog: 0/1000; Time: 2s(total), 2s(copy); streamer: binlog.000027:201067135; Lag: 0.01s, State: migrating; ETA: 9m58s ....... Copy: 5682000/6563240 86.6%; Applied: 0; Backlog: 0/1000; Time: 16m10s(total), 16m10s(copy); streamer: binlog.000028:213168607; Lag: 0.01s, State: migrating; ETA: 2m30s Copy: 6563000/6563240 100.0%; Applied: 0; Backlog: 0/1000; Time: 20m20s(total), 20m20s(copy); streamer: binlog.000028:382677405; Lag: 0.01s, State: migrating; ETA: 0s Gh-ost also provides several options to perform effective operations.  You can control the connections, active threads, load, chunk size, etc. But unfortunately, “–max-flow-ctl” option is not available in gh-ost.  Conclusion So, finally, I would say, Always use the direct ALTER with TOI for the metadata changes and INSTANT ALTERs. Use pt-online-schema-change with TOI and use the optimal flow control thresholds for InnoDB tables. Schedule pt-online-schema-change operation in off-peak hours for FOREIGN KEY tables. If you use RSU, never forget that you need to execute the ALTER on all nodes individually and you should block the WRITEs for that particular table. Make sure, your Gcache size is good enough to hold the writesets. If you are concerned with triggers, you can use the gh-ost to make the ALTERs. https://www.percona.com/blog/2020/10/06/various-ways-to-perform-schema-upgrades-with-percona-xtradb-cluster/

[rebrobindoesmath]

Chromatic Polynomials & Why They’re Cool

Super Quick Note: This post features LaTeX code, and will be better read directly on my blog, although it should be relatively readable on your dash! 

Okay, so what are chromatic polynomials?

Given a graph $G$, a chromatic polynomial of $G$, denoted $\chi_G(k)$ is a polynomial that outputs the number of proper $k$-colorings of $G$, when $k$ is the number of colors we are given.

Okay, so really, what are chromatic polynomials?

Let’s break down the definition. First, let’s talk in general about graphs. What is a graph? A graph is a collection of points called vertices connected by edges. An example of a graph (this graph has a special name: the Petersen graph) is below:

Now, let’s say we want to color the vertices of this graph such that no two adjacent vertices (meaning vertices that are connected by an edge) share the same color. This is called a proper coloring of the graph. Additionally, let’s say that we’re only allowed to use $k$ colors. If we have a proper coloring using $k$ colors, we call it a proper $k$-coloring. 

Let’s revisit the definition of our chromatic polynomial. Given our input $k$ is the number of colors, the chromatic polynomial outputs the number of different proper $k$-colorings. 

How do we find the chromatic polynomial?

Well, there’s a couple different ways to find them. Let’s look at finding the chromatic polynomial for different complete graphs. (A complete graph $K_n$ is a graph of $n$ vertices where every vertex is adjacent to every other vertex.)

Let’s take a look at the picture below, which shows $K_1$, $K_2$, and $K_3$.

What do all these $k$’s by the vertices mean? Let’s suppose we’re given $k$ colors to color each vertex. Pick a vertex of the complete graph to start at. That vertex has a possible $k$ colors it can be. We’re off to a great start! Now pick a vertex adjacent to the first vertex. Since we already took one color for that vertex, we have $k$-1 remaining colors for the current vertex. We continue this pattern until we’re out of vertices. Then what we’ll do is multiply all the values of the vertices together -- and voila, we have our chromatic polynomial.

For example, consider the $K_3$ above. It’s chromatic polynomial, $\chi_{K_3}(k)$, is equal to $k(k-1)(k-2)$. And in fact, for a general $K_n$, the chromatic polynomial, $\chi_{K_n}(k) = k(k-1)(k-2)\cdots(k-n+1)$. This function will tell us how many proper colorings we can get for $K_n$ given $n$ vertices and $k$ colors! How cool!

The process for finding the chromatic polynomial for other (non-complete) graphs is a bit trickier and hinges on something called the Deletion-Contraction Algorithm, also known as the Fundamental Reduction Theorem. While I won’t get into that in this post, if you’re interested in chromatic polynomials, it’s definitely something to check out.

Okay, but really, why is this cool?

The real “cool factor” of chromatic polynomials comes into play when we talk about why they were even created. Chromatic polynomials were originally created by George David Birkhoff in 1912 in an attempt to prove the Four Color Theorem. If he could show that $\chi_G(4)>0$, where $G$ is planar (that is, it can be drawn with no edge crossings), then the Four Color Theorem would be proven. And while the Four Color Theorem ended up being proven in another way, chromatic polynomials still remain Pretty Damn Cool and are an important aspect of algebraic graph theory. 

(I’m also pretty biased, since my current thesis research is regarding graphs whose chromatic polynomials have integer roots.)

Thanks for reading! 

I hope all is well with you! As always, feel free to send me a message/ask/reply/whatever with any questions, comments, or concerns! Stay positive! <3

References:

Chromatic Polynomial History

[shiho-elliptic]

PlaidCTF 2019 Writeup

I played as binja. I solved two challenges and one was solved after the competition.

R u SAd? (crypto)

In this challenge, we have a public key of RSA $$(e, n = pq)$$, encrypted flag $$c$$, $$i_q = q^{-1}\mod p$$, and $$i_p = p^{-1}\mod q$$.

$$i_p$$(resp. $$i_q$$) is an inverse element of $$q$$(resp. $$p$$) in $$\mathrm{mod}\ q$$(resp. $$\mathrm{mod}\ p$$). i.e.

$$$ \begin{aligned} pi_p &\equiv 1\pmod q\cr qi_q &\equiv 1\pmod p \end{aligned} $$$

There exists $$k_1, k_2\in\mathbb{Z}$$ such that satisfy following equations:

$$$ \begin{aligned} pi_p &= 1 + k_1q\cr qi_q &= 1 + k_2p\cr \end{aligned} $$$

Multiply these equations:

$$$ \begin{aligned} (pi_p)(qi_q) &= (1 + k_1q)(1 + k_2p)\cr &= k_1k_2n + k_1q + k_2p + 1 \end{aligned} $$$

Divide by n (in integer):

$$$ i_pi_q = k_1k_2 + \left\lfloor\frac{k_1}{p}\right\rfloor + \left\lfloor\frac{k_2}{q}\right\rfloor + \left\lfloor\frac{1}{n}\right\rfloor $$$

Since $$0\lt\left\lfloor\frac{1}{n}\right\rfloor\lt 1$$, we negligible it. $$k_1$$ and $$k_2$$ is smaller than $$n$$ trivially, so we know $$\left\lfloor\frac{k_1}{p}\right\rfloor$$ and $$\left\lfloor\frac{k_2}{q}\right\rfloor$$ is very small integers.

From these facts, we know there exists sufficiently small positive integer $$\varepsilon$$, such that $$i_pi_q - \varepsilon = k_1k_2$$. Actually, $$\varepsilon = 1$$ in this challenge (I checked by experiment).

Now, we have $$k_1k_2$$. since $$i_pi_qn = k_1k_2n + k_1q + k_2p + 1$$ and $$k_1q + k_2p = i_pi_qn - k_1k_2n - 1$$. Thus, we get $$k_1q$$ and $$k_2p$$ by solve quadratic equation $$x^2 - (k_1q + k_2p)x + (k_1q)(k_2p) = 0$$ using $$k_1k_2n = (k_1q)(k_2p)$$ and $$k_1q + k_2p$$.

We got $$k_1q$$ and $$k_2p$$. so we can compute $$p$$, $$q$$ by $$p = \gcd(n, k_2p)$$, $$q = n / p$$, and decrypt the ciphertext.

https://gist.github.com/elliptic-shiho/d78f4a3c7e4fe452f05dc2971dc19eab

horst (crypto, solved after the competition)

In this challenge, we have a permutation-based cryptosystem, two randomly generated plaintexts, and two ciphertexts corresponding to that.

At first, we formulate this cryptosystem. we denote the Symmetric Group $$S _ {64}$$ by $$\mathcal{S}$$, and let $$\mathcal{M} := \mathcal{S}\times\mathcal{S}$$.

Next, we denote the key of this cryptosystem by $$k\in\mathcal{S}$$, plaintext $$p_i\in\mathcal{M}$$, and ciphertext $$c_i\in\mathcal{M}$$ where $$i = 1, 2$$.

The round function $$R$$ and inverse that is defined by below:

$$$ \begin{aligned} R: \mathcal{M}\ni (x, y) \mapsto (y, kyk^{-1}x)\in\mathcal{M}\cr R^{-1}: \mathcal{M}\ni (x, y)\mapsto (kxk^{-1}y, x)\in\mathcal{M} \end{aligned} $$$

(Note: This writeup used right-to-left composition but the challenge's Permutation class used left-to-right that. e.g. $$kyk^{-1}x$$ is equivalent to x * k.inv() * y * k.)

We denote $$n$$-th iterated map of $$f$$: $$f\circ f\circ \cdots(n\mathrm{\ times\ repeat})\cdots \circ f$$ by $$f^{n}$$ and define the encrypt function as follows:

$$$ \mathrm{Enc}: \mathcal{M}\ni m \mapsto R^3(m)\in\mathcal{M}, $$$

and the decrypt function as follows:

$$$ \mathrm{Dec}: \mathcal{M}\ni c \mapsto (R^{-1})^3({c})\in\mathcal{M}. $$$

Our target is $$k$$, but we have only $$p_i$$ and $$c_i$$.

For convenience, let $$p_i = (x_i, y_i)$$ and $$c_i = (r_i, s_i)$$. By definition of $$\mathrm{Enc}$$, we got following equations:

$$$ \begin{aligned} r_i &= k^2y_ik^{-1}x_ik^{-1}y_i,\cr s_i &= k^3y_ik^{-1}x_ik^{-1}y_i^2k^{-1}x_i. \end{aligned} $$$

Now, we define $$X_i := r_iy_i^{-1}$$ and $$Y_i := s_ix_i^{-1}$$. Then, $$kX_ik^{-1} = Y_i$$ from definition. so let us solve the challenge by this fact.

To solve that, we need following three propositions:

Proposition 1 (decompose to relatively prime cyclic permutation). Let $$\alpha$$ be a permutation with $$n$$ elements. Then there exists an positive integer $$\ell$$ and relatively prime cyclic permutations $$\sigma_1, \sigma_2, \ldots, \sigma_{\ell}\in S_n$$ such that $$\alpha = \sigma_\ell\cdots\sigma_2\sigma_1$$.

Proposition 2. Let $$\alpha, \beta, \gamma$$ be a permutation with $$n$$ elements. Suppose that

$$\beta$$ can represented by cyclic notation: $$\beta = (i_1\ i_2\ \cdots\ i_k)$$

$$\alpha = \gamma\beta\gamma^{-1}$$

Then $$\alpha = (\gamma(i_1)\ \gamma(i_2)\ \cdots \gamma(i_k))$$ holds.

Proposition 3. Let $$\alpha, \beta, \gamma$$ be a permutation with $$n$$ elements. If $$\alpha = \gamma\beta\gamma^{-1}$$ then $$T(\alpha) = T(\beta)$$ where $$T(\alpha)$$ is cyclic type of $$\alpha$$.

From these propositions, we can solve conjugate equation $$Y_i = kX_ik^{-1}$$ by following procedure:

By Prop. 1, Decompose to relatively prime cyclic permuation: $$X_i = \sigma_\ell\cdots\sigma_1$$ and $$Y_i = \tau_m\cdots\tau_1$$.

By Prop. 3, $$m = \ell$$. Since following formula, there exists 1-to-1 map between $$\sigma_t$$ and $$\tau_t$$: $$$ \begin{aligned} Y_i &= kX_ik^{-1} = k(\sigma_\ell\cdots\sigma_1)k^{-1} = (k\sigma_\ell k^{-1})\cdots(k\sigma_1 k^{-1})\cr &= \tau_\ell\cdots\tau_1 \end{aligned} $$$ For simple, we assume the straight mapping: $$k\sigma_tk^{-1} = \tau_t$$ for $$t = 1, \ldots, \ell$$.

By Prop. 2, the 1-to-1 map between $$\sigma_t$$ and $$\tau_t$$ is $$k$$. i.e. if $$\sigma_t = (j_1\ j_2\ \cdots\ j_s)$$ then $$\tau_t = (k(j_1)\ k(j_2)\ \cdots\ k(j_s))$$. so $$k$$ can reconstruct by collect pairs $$(j_t, k(j_t))$$.

After this procedure, we have the key $$k$$. That's all.

It is a note of the implementation:

In the above procedure, we assume the straight mapping but actual mapping is not straight. so we need to brute-force a mapping of decomposed cycle permutations of $$X$$ that and $$Y$$ that.

Even if we selected correct mapping, we don't have information about how corresponding $$Y_i$$ to $$k(j_t)$$. so we have to brute-force all possibility.

~ ↑ in the competition period ~

~ ↓ after the period ~

I bugged code. that's all...

https://gist.github.com/elliptic-shiho/a089e540f8cbc6100b88342e54a414c5