记录newbie日常

Tetr

操作系统：设计与实现 蒋炎岩

dP

Why RSA must make sure that $gcd(e,φ(n))=1$ instead of $gcd(e,n)=1$?

Chinese remainder theory

根据我最近的直觉，自欺欺人是不进步的最大原因。我想大胆提出三个假设： / 最好的实践方法是任何不会让你欺骗自己的合理方法。 如果你有足够的动力，几乎任何事情都能满足上述标准。 如果你没有动力，那么几乎没有什么能满足上述标准。 通过“动机”，我有一个特定的含义。这里唯一重要的动机是对问题本身的浓厚兴趣。很多人的动机是如果他们做得好，他们就有更好的机会找到工作（我不知道这是不是真的，但是有很多人因为这个原因做CP） . 相对较少的人甚至可以获得 CP 的津贴或类似的津贴。这种动机可以作为一种次要动机，因为它给了你做 CP 而不是其他事情的理由，但这还不够。如果你只是看了史蒂夫·乔布斯或埃隆·马斯克的一段视频，其中包含一堆关于成功的通用主义，或者阅读了一些励志海报并获得了某种灵感——我认为这不会让你走得太远。对问题的兴趣在这里很重要。

保存一些推导好的结论 已知n 且p、q相邻 线索是在加密脚本中可以找到如下类似代码 p = getPrime(512) q = int(gmpy2.next_prime(p)) n = p*q 如下代码解出p、q # pq相邻 为n开方 n2 = int(gmpy2.iroot(n, 2)[0]) p = sympy.nextprime(n2) q = n//p 加以验证 print(p*q) print(n == p*q) #返回True q = sympy.nextprime()，意味着 p 和 q 是相邻的素数，非常接近，于是可以将 N 开平方根，这个数的 nextprime 就为 q $q$ 与 $phi(q^2)$ 关系 题目给出 from Crypto.Util.number import * import gmpy2 from flag import flag p=getPrime(512) q=getPrime(512) r=getPrime(512) n=p*q*r e=65537 m=bytes_to_long(flag) def Euler(x): res=0 for i in range(1,x): if gmpy2.gcd(i,x)==1: res+=1 return res P=p**3 Q=q**2 c=pow(m,e,n) print(P) print(Euler(Q)) print(c) print(n) #P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303 #EQ = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620 #c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 #n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 解出q Euler(q^2) = q * (q-1)，那么 q-1 < sqrt(Euler(q^2)) < q.(已翻译)

在acm被称为快速幂(平方求幂) 在ctf中也被称为 $montecarlo$ 先说幂运算的朴素做法，在数学中，重复连乘的运算叫做乘方，乘方的结果称为 幂 ${\displaystyle n}$ 个相同的数 ${\displaystyle b}$ 连续相乘 [公式]

构造+贪心(R1000) / 剩余24h A. Find Amir / # 有n个地点，每来往i，j两个地点就花费（i+j）mod（n+1），问遍历所有地点的最低花费 # 当i+j==n+1每两地花费最小，如1, n; 2，n-1 # 只需以1->n->2->n-1->3...这样的顺序花费就最小 n = int(input()) res = 0 # res = (n-1)/2 if n & 1: # n is odd res = (n - 1) >> 1 else: res = (n >> 1) - 1 print(res) by: 易如鱼 & aYi_7 & 张少锋 / 分析：由于花费是要（i+j）mod（n+1），则尽可能使每段路程的i+j都接近n+1，通过样例中n=10的情况，不难发现解法。从1到n，花费为0(11%11 = 0)；从n走到2，花费为1(12%11=1)；从2到n-1，花费为0；从n-1到3，花费为1;从3到n-2…这样循环往复，每次向右走花费为零，向左走花费为1。据此不难写出通项公式：cost =（n-1）mod 2。