【浅谈系列】Fermat Quotient

4 minute read

Published:

本文主要通过祥云杯2020的一道题目,浅谈 Fermat Quotient

在祥云杯 2020 中,有一道名为 more_calc 的 crypto 题目。这道题目看题意,需要对一个连续的模 $p$ 逆元序列进行求和。通过巧妙的推导,在避免求和的情况下即可得到 flag。但如果直接求和可行吗?答案是可行的,需要用到1850年 Eisenstein 提出的关于 Fermat Quotient 的一个结论。 本文即对 Fermat Quotient 进行简单介绍,并给出关于 1850 年 Eisenstein 的结论,以及它的证明推导。

1. 什么是 Fermat Quotient

(1) 定义

在费马小定理中,$\frac{a^{p-1}-1}{p}$ 显然是一个整数。 这个整数被称作 $p$ 的以 $a$ 为基的 Fermat Quotient。记作 $q_p(a)$。

(2)性质

Fermat Quotient 有如下性质(其中 $a$、$b$ 和 $p$ 互素):

  • $q_{p}{(ab)} = q_p(a) + q_p(b) \pmod p$
  • $q_p(a^r) = rq_p(a)$
  • $q_p(p\mp1) = \pm1 \pmod p$
  • $q_p(p\mp a) = q_p(a) \pm \frac{1}{a} \pmod p$
  • $-2q_p(2) = 1 + \frac{1}{2}+…+\frac{1}{(p-1)/2} \pmod p$

此外,我们注意到,$q_p(a) = 0 \pmod p$ 这个式子,可以被转化为 $a^{p-1} = 1 \pmod {p^2}$,这个转化用同余的定义写一写就可以轻松证明。当 $a=2$ 时,$p$ 被称为 Wieferich Prime,它首次出现在 Wieferich 在1909年关于费马大定理的作品中。它的第一项是 1093

(3)历史

  • 1828年,Abel 首次提出,这个式子能否被 $p$ 整除。
  • 1850年,Eisenstein 指出,这个式子能被表示为与 p 互素的整数的模反元素之和。
  • 随后的几十年里,SylvesterGlaisher 以及 Lerch 等人对 Eisenstein 的结果进行了进一步的完善,推导出了很多变式。
  • 1979年,WieferichMirimanoff 指出了 Fermat QuotientFermat’s Last Theorem,也就是费马大定理之间的联系。
  • 1995年,Wiles 证明了费马大定理。即使如此,Fermat Quotient 依然在伯努利数等领域有着重要的地位。

2. Eisenstein 的结论

(1)Eisenstein 的结论

\(-2q_p(2) \equiv -\sum_{k=1}^{p-1}{\frac{(-1)^{k-1}}{k}} \pmod p \\ = 1 + \frac{1}{2}+...+\frac{1}{(p-1)/2} \pmod p \\ = \sum_{k=1}^{(p-1)/2}{\frac{1}{k}} \pmod p\)

(2)证明如下

证明需要用到一些二项式系数的性质,建议先复习一下高中学的二项式定理相关知识。

证明如下(新博客的公式渲染又出现了奇怪的问题,暂时用截图代替): 公式的代码如下:

\begin{align}
-2 \cdot \frac{2^{p  1} - 1}p & = - \frac 1p(2^p - 2)\\
& = -\frac 1p \left( \sum_{k = 0}^p \binom pk - \binom p0 - \binom pp \right) \qquad \\
& = -\frac 1p \sum_{k = 1}^{p - 1} \binom pk\\
& = -\frac 1p \sum_{k = 1}^{p - 1} \binom{p - 1}{k - 1} \frac pk \qquad \qquad \qquad \quad \; \; \\
& = -\sum_{k = 1}^{p - 1} \binom{p - 1}{k - 1} \frac1k\\
& \equiv -\sum_{k = 1}^{p - 1} \frac{(-1)^{k - 1}}k \pmod p \qquad \qquad \; \;  \\
& = -\frac11 + \frac12 - \frac13 + \frac14 - \cdots - \frac1{p - 4} + \frac1{p - 3} - \frac1{p - 2} + \frac1{p - 1} \\
& = \left( -\frac11 - \frac13 - \cdots - \frac1{p - 4} - \frac1{p - 2} \right) + \left( \frac12 + \frac14 + \cdots + \frac1{p - 3} + \frac1{p - 1} \right) \\
& \equiv \left( -\frac1{-(p - 1)} - \frac1{-(p - 3)} - \cdots - \frac1{-4} - \frac1{-2} \right) \\
& \quad + \left( \frac12 + \frac14 + \cdots + \frac1{p - 3} + \frac1{p - 1} \right) \pmod p \\
& = \left( \frac1{p - 1} + \frac1{p - 3} + \cdots + \frac14 + \frac12 \right) + \left( \frac12 + \frac14 + \cdots + \frac1{p - 3} + \frac1{p - 1} \right) \\
& = 2 \left( \frac12 + \frac14 + \cdots + \frac1{p - 3} + \frac1{p - 1} \right) \\
& = 1 + \frac12 + \cdots + \frac1{(p - 3)/2} + \frac1{(p - 1)/2} \\
& \equiv \sum_{k = 1}^{(p - 1)/2} \frac{1}{k} \pmod p
\end{align}

(3)代码验证

from Crypto.Util.number import getPrime
from tqdm import tqdm
import gmpy2

def sum_inverse(p):
    cnt = 0
    for i in range(1, (p+1)//2):
        cnt += gmpy2.invert(i, p)
    cnt = cnt%p
    return cnt

def eisenstein_formula(p):
    ans = -(pow(2, p, p*p)-2)//p % p
    return ans

for i in tqdm(range(100)):
    p = getPrime(16)
    # print (sum_inverse(p), eisenstein_formula(p))
    assert sum_inverse(p) == eisenstein_formula(p)

print ("Proved.")

结果如下:

(4)后续研究者的类似结果

后续的研究者们,推导出了关于 $q_p(2)$ 的一些其他式子,以及关于 $q_p(3)$、$q_p(4)$ 等等 Fermat Quotient 的一些式子。感兴趣可以自行搜索相关的文献,进行更进一步的阅读。

3. 祥云杯 2020 more_calc

题目如下:

import gmpy2
from Crypto.Util.number import *

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

p = getStrongPrime(2048)
for i in range(1, (p+1)//2):
    s += pow(i, p-2, p)
s = s % p
q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(p)
print(c)
#27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
#350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523

这道题常规解法是通过推导,发现最终的结果其实不需要用到 $q$,在模 $p$ 上可以直接推导出 flag。 这种解法和 CryptoCTF 2020Three Ravens 解法完全相同。 而我们这里选择算出 $s$ 得到 $q$,是另一种解法。 显然,这里要计算一个连续逆元序列的和,我们直接使用 Eisenstein 的结论即可。 解题脚本如下:

from Crypto.Util.number import long_to_bytes
import gmpy2

p = 27405107041753266489145388621858169511872996622765267064868542117269875531364939896671662734188734825462948115530667205007939029215517180761866791579330410449202307248373229224662232822180397215721163369151115019770596528704719472424551024516928606584975793350814943997731939996459959720826025110179216477709373849945411483731524831284895024319654509286305913312306154387754998813276562173335189450448233216133842189148761197948559529960144453513191372254902031168755165124218783504740834442379363311489108732216051566953498279198537794620521800773917228002402970358087033504897205021881295154046656335865303621793069
c = 350559186837488832821747843236518135605207376031858002274245004287622649330215113818719954185397072838014144973032329600905419861908678328971318153205085007743269253957395282420325663132161022100365481003745940818974280988045034204540385744572806102552420428326265541925346702843693366991753468220300070888651732502520797002707248604275755144713421649971492440442052470723153111156457558558362147002004646136522011344261017461901953583462467622428810167107079281190209731251995976003352201766861887320739990258601550606005388872967825179626176714503475557883810543445555390014562686801894528311600623156984829864743222963877167099892926717479789226681810584894066635076755996423203380493776130488170859798745677727810528672150350333480506424506676127108526488370011099147698875070043925524217837379654168009179798131378352623177947753192948012574831777413729910050668759007704596447625484384743880766558428224371417726480372362810572395522725083798926133468409600491925317437998458582723897120786458219630275616949619564099733542766297770682044561605344090394777570973725211713076201846942438883897078408067779325471589907041186423781580046903588316958615443196819133852367565049467076710376395085898875495653237178198379421129086523

s = p - (pow(2, p, p*p) - 2) //p

q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
d = gmpy2.invert(e, (p-1) * (q-1))
print (long_to_bytes(pow(c, d, p*q)))

声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.