第44章 於星辰中铸剑！（4 / 4）
许燃的眼睛里闪著光。
“它的构造更简单粗暴。取一个素数q，並且要求q模4余1。”
“图的顶点，就是有限域gf(q)里的q个元素，从0到q-1。”
“两个顶点x和y之间有没有边，只看一件事。”
他顿了顿，用红笔重重写下两个字。
“『差值』。”
“如果x-y是gf(q)里的『二次剩余』，那么它们之间就有边。
如果不是，就没有。”
“二次剩余？”
这个词简瑶知道，就是指一个数在模q的意义下，能被写成另一个数的平方。
比如在模5的意义下，1和4就是二次剩余，因为1=12=42，4=22=32。
“对。”
许燃点头，“比如，我们直接攻击r(5，5)的下界，构造一个41阶的图。
取q=41，因为它是一个素数，且41=4*10+1。”
“我们构造佩利图p(41)。”
“它的顶点，就是0， 1， 2，...， 40。”
“顶点2和顶点5之间有没有边？”许燃看向简瑶。
“5-2=3，我们需要判断3是不是模41的二次剩余……”简瑶迅速心算，却发现这並不容易。
“很难算，对吧？”
许燃笑了笑，“但数学的美妙在於，我们不需要一个一个去算。
高斯早就为我们铺好了路。” ↑返回顶部↑
“它的构造更简单粗暴。取一个素数q，並且要求q模4余1。”
“图的顶点，就是有限域gf(q)里的q个元素，从0到q-1。”
“两个顶点x和y之间有没有边，只看一件事。”
他顿了顿，用红笔重重写下两个字。
“『差值』。”
“如果x-y是gf(q)里的『二次剩余』，那么它们之间就有边。
如果不是，就没有。”
“二次剩余？”
这个词简瑶知道，就是指一个数在模q的意义下，能被写成另一个数的平方。
比如在模5的意义下，1和4就是二次剩余，因为1=12=42，4=22=32。
“对。”
许燃点头，“比如，我们直接攻击r(5，5)的下界，构造一个41阶的图。
取q=41，因为它是一个素数，且41=4*10+1。”
“我们构造佩利图p(41)。”
“它的顶点，就是0， 1， 2，...， 40。”
“顶点2和顶点5之间有没有边？”许燃看向简瑶。
“5-2=3，我们需要判断3是不是模41的二次剩余……”简瑶迅速心算，却发现这並不容易。
“很难算，对吧？”
许燃笑了笑，“但数学的美妙在於，我们不需要一个一个去算。
高斯早就为我们铺好了路。” ↑返回顶部↑