小绿锁背后的RSA算法

如今，我们上网时常能见到一把小绿锁，这便是多数浏览器对于HTTPS连接的标识。即HTTP over SSL，它代表着我们与网站服务器的连接是经过SSL加密的。然而，不论何种加密算法，总是有加密和解密的过程，其中最关键的就是密钥交换过程，如果在交换过程中这个密钥被窃取，之后的加密便毫无意义。那么SSL是如何确保即使我们的网络流量被抓取的情况下也能保证加密信息安全的呢？这就是我们今天要说的非对称加密算法，而最早的非对称加密算法便是从RSA开始。 算法介绍 RSA算法是1977年由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman三人共同提出的，RSA名字便取自他们三人的姓氏。在RSA算法之前，密钥交换主要采用预共享密钥的方式，例如我们生活中连接WPA2-PSK的Wi-Fi便是采用预共享密钥的方式，它的特点是需要通信双方事先共享密钥才能加密，也称为对称加密。而RSA采用的是非对称加密，需要生成两组密钥，称为公钥(Public Key)和私钥(Private Key)，这两组密钥是成对的。使用公钥加密的数据可以被私钥解密，使用私钥加密的数据可以被公钥解密。 在了解这个算法前，你需要了解以下数学知识，我假设读者已经具备初中数学知识。 对于OIer，你如果了解过扩展欧几里得、欧拉函数、费马小定理，你可以跳过这一段，而且你看这个会很轻松。 最大公因数： Greatest Common Divisor，即两个数的因数集合的交集中最大的数，通常我们使用gcd表示。 例如a、b的最大公因数记为gcd(a,b) 互质关系：…

在移动硬盘上安装Windows To Go+Linux双系统（EFI）

自己多出了一块128G的SSD，本着闲着也浪费的想法就用了一个老的硬盘盒装起来当移动硬盘使用，没想到新固件还支持Trim，便有了在上面安装Windows To Go，然后给Mac提供Windows的想法。可是，安装完Windows的我似乎还不满足，还希望在上面安装一个Ubuntu系统，几经辗转，终于找到了办法。 话不多说，直接入题。 首先，备份移动硬盘上的数据，使用WTG辅助工具写入Windows系统文件，记得勾选UEFI+GPT。 用压缩卷空出一部分空间留给Linux使用 至此，我们已经完成了Windows的安装，并且这时直接启动移动硬盘已经可以使用Windows了。 将移动硬盘挂在到虚拟机中，记得使用EFI模式，比如VirtualBox勾上“启用EFI”，Hyper-V选择第二代虚拟机即可，在虚拟机中安装好所选的Linux发行版 待Linux安装完成后，此时的系统并不能直接启动的，若直接启动出现的是一个蓝屏的Windows，因为之前安装的grub没有使用removable模式，因此，我们手动安装grub 将/boot分区挂载到任意目录，这里我选择/target/boot，若没有单独分出/boot就直接挂载/到任意目录即可。同时，将ESP分区挂载到/target/boot/efi，然后删除EFI/Boot/bootx64.efi文件 安装grub-efi软件包 使用grub-install安装grub，之后便得到了一个可启动的Linux 来看看成果吧！ 可以看出，grub已经接管了Windows Boot Manager，我们可以在这选择操作系统启动。 同样，在Mac上也没有问题 效果如图…

线段树入门

什么是线段树？ 线段树，是一种二叉搜索树。它可以把一个从1…N的数组可以用二叉树划分为许多区间，这个区间成为二叉树的节点，使用线段树可以大大加快进行区间操作时的速度，同时，区间的最大值、最小值等问题也可以方便地使用线段树求出。 这里借用一下百度百科中的线段树图片来简要说明一下。 其中，[1,10]是我们的操作区间范围，这个节点作为根节点。 其下有两个子节点，一个是[1,5]一个是[6,10]。 对于每个节点[x,y]，当x !=y 时其子节点分别为[x,(x+y)\2]与[(x+y)\2+1,y] 其中，\代表整除 当x == y时，没有子节点，即叶节点。 线段树能做什么？ 看到这里，相信很多读者会问，在各个区间的节点上需要保存什么呢？ 其实我相信聪明的读者已经看出来了，学过RMQ问题的读者应该已经想到了线段树是一个实现RMQ相比于ST算法占用内存空间更小的算法。实际上正是，例如POJ 2823，用st算法是过不了的。因此，我们还可以在线段树节点上存储区间的最大值、最小值、区间和、区间非0节点数量、区间0节点数量，等等等等。这样，对于一个区间的查询，只需要O(log n)的时间复杂度，相比于O(y-x)，快了许多，因而，线段树非常适合解决区间操作的各类问题。 如何建树？…

POJ 2482 – Stars in Your Window 题目背景翻译

http://poj.org/problem?id=2482 飞逝的的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了4年。我仍然还生动地记得，4年前，在美丽的珠海校区，从我看到你微笑着走出教室，你将头向后仰，柔和的晚霞照耀着你玫瑰色的脸颊。我明白，我已经沉醉于你了。之后，经过几个月的观察和窥探，你的优雅与智慧，你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩，我总是梦想着与你分享余生。唉，实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划，仅仅只是等待，等待一个适当的机会到来。直到现在，毕业的到来，我意识到我是个傻瓜，我应该创造机会并且抓住它而不只是等待。 这些日子里，我和我的朋友、室友、同学一个接一个地分开。我仍无法相信，在挥手之后，这些熟悉的面孔很快就会从我们的生活中消失，仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞，追求你的未来，实现你的梦想。如果没有命运，也许我们不会再次相遇。所以今晚，我正在你的宿舍楼下徘徊，希望能偶然遇见你。但矛盾的是，你的美貌一定会使我心跳加速，我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你在珠海和广州校区的宿舍楼，每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出：打电话叫她一起吃晚饭或是聊聊天。但每次，考虑到你的优秀和我的平凡，胆怯的优势超越勇气驱使我静静地离开。 毕业，意味着大学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力，这单相思的爱情会被密封，作为一个我心灵深处的记忆。毕业，也意味着新生活的开始，一个到达光明未来的足迹。我真希望你在国外天天开心，一切顺利。同时，我将努力从幼稚中走出来，变得更加成熟。我的理想将是在现实中追求我的爱与幸福，我永远不会放弃。 再见了，我的公主！ 如果有一天，在某个天涯海角，我们有机会相聚，即使是白发苍苍的男人和女人，在那个时候，我希望我们可以成为好朋友来自豪地分享这个记忆，重温年轻快乐的激情。如果这个机会永远没有到来，我希望我是天空中的星星，在你的窗外闪烁。远远地保佑着你，就像一个朋友，每天晚上陪伴在你左右，一同分享甜美的梦亦或是一同经历可怕的梦。 现在问题来了：假定天空是一个平面。所有的星星都躺在它的坐标(x,y)。对于每颗星星，有一个1到100的等级，代表它自身的亮度。其中100是最亮的，1是最暗的。窗口是个矩形，其边缘平行于x轴或y轴。你的任务是告诉我应该把窗口放在哪里，以使窗口中星星的亮度总和最大。注意，窗口边缘的星星不计算在内。窗口可以平移，但不能旋转。

Linode Xen上的Debian/Ubuntu升级Linux 4.9内核开启BBR算法

随着Linux 4.9内核的更新带来了一个新的TCP拥塞控制算法——BBR，该算法解决了几十年来基于丢包来估算带宽的一切算法所导致的在有错误导致丢包的网络环境中带宽降低问题，成为TCP拥塞控制算法的一个重要里程碑。就实际使用而言，在服务器上使用BBR拥塞控制算法可以提高TCP连接在有丢包的情况下所导致的速率严重降低的问题。对于蜂窝数据、不稳定的Wi-Fi、洲际网络连接都有诸多的好处。 BBR: Congestion-Based Congestion Control 然而Linode自己编译的内核却是一个十分精简的版本，并没有包含BBR算法。Linode早几年的机子使用的Xen虚拟化环境是直接从内核启动，在更换内核上有些许小小的麻烦，许多Linux初学者在网上搜索相关资料无果便放弃了。而我认为，作为开发者就应该有阅读官方英文文档的能力，恰好，Linode也提供了一个使用pv-grub更换内核的方式。https://www.linode.com/docs/tools-reference/custom-kernels-distros/run-a-distributionsupplied-kernel-with-pvgrub/ 相信这个链接已经能解决大多数人遇到的问题了。 接下来介绍Debian/Ubuntu更换发行版内核的方式： 使用wget或curl下载内核的deb包（包括headers和image，纵然不安装headers也能正常使用，但将导致在编译软件包时出现异常），当然你也可以自己编译，这里以Linux 4.9.6 amd64为例：wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.9.6/linux-headers-4.9.6-040906_4.9.6-040906.201701260330_all.deb wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.9.6/linux-image-4.9.6-040906-generic_4.9.6-040906.201701260330_amd64.deb dpkg -i linux-headers-4.9.6-040906_4.9.6-040906.201701260330_all.deb dpkg…

调整环境变量在Windows下使用gdb

gdb是一个十分方便的调试工具，不仅仅是对开发者，更是信息学竞赛者的一大利器，使用它在竞赛中往往可以获得更高的调试效率，我们可以轻松地查看到代码执行到哪一行时出现了问题，相比于IDE可以更加快速地输出各个变量的数值来分析程序所存在的问题。 然而许多人却因为不会在windows中配置gdb而望而却步，更有甚者在同时安装了fpc和gcc的电脑上使用gdb遇到了种种问题。这里来说明一下解决方法。 首先，在Windows系统中，对于命令行可以在任意目录直接执行的命令，取决于系统或用户环境变量中path的设置。通俗来说，系统在任意目录下只能直接执行在名为path的环境变量中的文件夹下的可执行程序。 然而，对于大多数OIer而言，所使用的Dev-C++在安装时并不会在环境变量中加上MinGW的安装目录，因此许多人对于许多竞赛书中所讲的gdb的使用一直没有去亲自尝试过。因此，我们就要把MinGW安装目录下的bin文件夹加入到path环境变量中。 首先，在Dev-C++中找到Compiler Options 之后，找到MinGW的安装目录 将这个目录加入到系统的环境变量中 对于XP系统，在“我的电脑”右键菜单的属性中就可以进入这个界面。而对于Vista-10这几个版本的Windows系统中，这个界面则是在系统属性的高级系统设置中。 我们找到用户或者系统的Path变量，然后加入刚才在Dev-C++中所见到的路径，放置于变量值的最前面，然后加上; 特别注意，一定要加上; 比如原来的环境变量是 %SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem;%SYSTEMROOT%\System32\WindowsPowerShell\v1.0\; 此时应该更改为 C:\Program Files\Dev-Cpp\MinGW32\bin;%SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem;%SYSTEMROOT%\System32\WindowsPowerShell\v1.0\; 之后，再重新打开命令提示符，此时g++、gcc、gdb就可以使用了。这里要提到一点，为什么不把MinGW的目录加在最后。这是考虑到许多人同时有安装fpc，而fpc安装时会加入MinGW的gdb，由于大多数情况下该版本较旧所以可能遇到下图中的情况。 因此，这里把minGW的安装目录放在环境变量的最前面，就是为了让它拥有最高的优先级。诚然，把它放在fpc的目录前面再加上;也有同样的效果。实际上，为了防止改坏环境变量影响系统的正常运行，把minGW放在最后面是比较保守的选择。…

动态规划-01背包问题之我见

背包问题是信息学奥赛中最经常考的动态规划形式，而01背包又是背包问题的基础。除此之外，背包问题还分为完全背包、多重背包等。 01背包定义如下： 对于1个容积为v的背包和n个物品，这些物品分别有自己的体积Vi，和价值Pi，我们需要有一种算法在背包可以容纳的情况下使装入的物品价值最大。此时n个物品不一定全部放入，背包也不一定装满。 与完全背包不同的是，01背包中是n个物品，而完全背包是n种物品，每种物品可多次放入。 这样的问题为什么不用搜索解决呢？ 显然，如果搜索可以完美解决这样的问题，我们自然也就不需要用更好的算法来解决问题了。 通过分析问题，我们可知，对于每个物体都有放入背包和不放入背包两种情况，如果我们使用传统的搜索算法解决这个问题，那么时间复杂度为O(2^n)，数据大了难免超时。 何为动态规划： 动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。继续分析，我们可以通过递推的方式解决该问题，从问题分析出递推式的方法，便是动态规划。 如何用动态规划高效地解决01背包问题？ 这是一个01背包常见的递推式 f[i][j]=max(f[i-1][j],f[i-1][j-Vi]+Pi) 其中，i从1到n，j从1到v，条件为j>=Vi 许多人与我一样，在第一次看到这个递推式的时候都十分困惑，全然不知它的含义。 实际上，f[i][j]就是我们在写动态规划程序时所需要开的一个数组，f[i][j]表示放入前i个物品（包含i，但这前i个物品不一定完全放入），背包容积为j时，背包内物品价值和的最大值。 这样，f[i-1][j]显然就是不考虑放入编号为i的物品的情况下背包内物品的最大价值和，而f[i-1][j-Vi]+Pi，便是在只考虑放入前i-1号物品且背包容积为j-Vi时，背包内物品的最大价值和，再放入编号为i的物品，因此加上Pi，也就得到了f[i][j]，即放入前i个物品，背包容积为j时背包内物品的价值的最大值。 对于这个算法，在C语言中通常采用两层for循环解决，以下为C++写法。大家可以根据题目自己修改以符合题目要求。 该方法的时间复杂度为O(n*v)…

解决U盘启动Linux后重启Mac黑屏

解决U盘启动Linux后重启Mac黑屏

今天早上把Mac启动到了我的U盘里的一个Ubuntu系统，做完各项事情后我打算重启返回macOS，我便在重启时等待电脑黑屏后拔下U盘，我之前也是这么做一直没有出过问题，直到今天。 这时听到了Mac开机的“灯”一声，之后屏幕就黑屏了，于是我按住电源键强行关机，之后再开机，可以看到触摸板可以按下并且USB通电了，但是电脑始终没有开机音，屏幕也没有亮，紧张之中，我拨打了苹果中国的400客服电话。 向客服表明情况后，客服让我尝试清除NVRAM，失败，之后让我按住Shift和电源键开机重置SMC，可是忘了让我按Control和Option，显然，还是失败，开机后依旧是USB通电、触摸板可以按下，但没有开机音，屏幕也没有亮。 之后客服就帮我预约了Genius Bar了，好在厦门有Apple Store，但是最近的预约需要8月1日中午。虽然我的数据都有在自己家的服务器上用afp开Time Machine备份，但是并没有什么取出文件的方法，于是我便开始尝试自己解决问题。 几经辗转，我在网上看到了一篇解决Mac开机黑屏问题的文章http://osxdaily.com/2014/11/22/fix-macbook-pro-booting-black-screen/ 按住Shift+Control+Option+Power，只听“灯”一声，成功进入了macOS的登录界面。 祝愿每个看到这篇文章的朋友们都能顺利解决自己遇到的问题。   最后给大家看个笑话

如何理解Linux的文件系统挂载点

如何理解Linux的文件系统挂载点

对于大多数Linux初学者而言，最痛苦的事情莫过于理解Linux文件系统的挂载点。 我们都知道，在一个硬盘上，我们通过分区把硬盘空间分成几块来使用，在这些分区上可以创建文件系统，而文件系统最终能被访问就需要挂载(mount)。 在传统Windows中，所有分区都被挂载为盘符，比如C:、D:、E:、F:，相当于每一个文件系统都是一个根节点。 而在Linux中，是以一个系统盘为根节点，而其他的文件系统都挂载在根节点下的目录中 仅仅这样说可能对于大多数没接触过Linux的人而言难以理解，现在我们就在Windows中模拟一下Linux的文件系统挂载方式。 不知大家何曾想过，若Windows的26个盘符用完了怎么办？不仅仅是这些带着好奇心的用户想到了，当然，微软也想到了。 在Windows NT中，一种新的分区挂载方式出现，就是把分区作为文件夹挂载在NTFS文件系统中。 这样，原本在Windows应为根节点的分区就成了文件系统根节点中的一个子节点。 我们来到Windows的磁盘管理，查看当前的磁盘分区信息。 可以看到我这里有个256G的物理硬盘，还有一个1TB的虚拟硬盘。 这1TB的虚拟硬盘中，有个99M的ESP分区(当时用DiskGenius随便分的就忘了取消勾选了)。还有三个NTFS文件系统的数据分区。分别被挂载为D、E、F。 现在我们来使用Windows NT提供的另一种挂载方式，将这三个分区的文件系统挂载到C盘的文件夹中。 现在，我们所看到的只有一个C盘(网络驱动器请忽略)，并且空间并没有扩大。 但在C盘中出现了3个文件夹，分别对应之前的D、E、F盘的文件系统。当然这里也可以用其它的名称来命名这三个文件夹。 看到这里，相信大家对Linux的目录挂载点有个基本的认识了吧。