求解部分x^k=b(mod m)问题

原本信誓旦旦的想要解决整个一般性的xk≡b(mod m)问题,然而发现推理过程出了点问题(原因可看这里),故把标题加了“部分”两字,亦即对另一部分的这类问题我还不会解决。 对ab≡c(mod m)这个式子,实际上包括3个问题。在这篇文章中,我们知道了已知a和b Continue reading 求解部分x^k=b(mod m)问题

原根若干性质及最小原根的求解

重要修正:本想把原根的概念推广到所有正整数,之后就可作为解决一般性问题xk≡b(mod m)的基础(我原本就是打算写这个主题,先写本文是为了引出先导性的知识)。然而测试之后发现m为9407的时候,这个数根本没有原根!这之后就纠结了?到底是哪里出了问题?之后一直 Continue reading 原根若干性质及最小原根的求解

求解a^x=b(mod m)

通过这篇文章,我们知道了如何求解一个数的幂次模另一个数。现在,讨论下指数的求法。在这篇文章中,我们还知道指数循环节的存在,所以x可以存在无穷多解的情况,并且解依赖于循环节起始位置,长度和x的最小值。由于循环节只依赖于定值a和m,所以这里只考虑求x的最小值。 当 Continue reading 求解a^x=b(mod m)

求解x=a^b(mod m)

本文致力于解决如下问题:求解x≡ab(mod m),其中a,b,m都是正整数。 如果b足够小,则可直接用逐次平方法求解,如果你不知道逐次平方法,可以先看这里。所以这里假设b足够大(这不是说是一个64位整数,而是可以上百上千位的一个数),大到逐次平方法也已不足以 Continue reading 求解x=a^b(mod m)

利用逐次平方法快速求幂

利用逐次平方法可以快速求幂,这里不局限于数的幂,但以数的幂来举例说明。 要求ak,如果直接用a连乘k次,复杂度比较大。如果把k写成如下形式: k = u0 + 2u1 + 22u2 + ... + 2rur, ui = 0 或 1. 然后制作模a的幂次表: a Continue reading 利用逐次平方法快速求幂

无穷多素数的两种证明

我们都知道素数有无穷多个,历史上众多数学家都给出了证明,这里介绍两种证明。 一种是欧几里德的证明,这种大家应该都比较熟悉。假设素数为有限多个,记作p1, p2, ..., pn。令A = p1p2...pn + 1,显然这n个素数中,没有一个能被A整除,这说明 Continue reading 无穷多素数的两种证明