量子求解欧拉函数破解RSA算法

量子计算根据量子力学原理设计,具有天然的并行计算优势。Shor算法是一个能够快速分解整数,从而有望破解RSA加密技术的算法。然而Shor算法存在着需要构造的模幂电路极其复杂、量子位数会影响后期连分式计算精度的缺点,因此难以在量子计算机上实现。针对上述问题,文章基于数论知识和RSA算法提出一种新的算法,设计相关量子线路去求解待分解整数N的欧拉函数,待量子求解出待分解整数的欧拉函数后,通过构造二元一次方程组可以求出整数N的两质因子。并且结合公钥可以进一步计算出私钥,从而对密文进行破译。文章所提算法在做到通用的基础上,只使用2n+2个量子比特,仅需要求解数的模乘,不用进行连分式计算,从而实现计算量和线路复杂度低的量子算法。

关于数论函数方程φ(n)=S(n^5)

对于正整数n,设φ(n)和S(n)分别是Euler函数和Smarandache函数.证明了:方程φ(n)=S(n5)仅有解n=1,64.

关于数论函数方程φ(n)=s(n^7)

对于正整数n,设φ(n)和s(n)分别是Euler函数和Smarandache函数,证明了:方程φ(n)=s(n7)仅有整数解n=1,64,72,80.

一个包含欧拉函数的方程

设n为任意正整数,如果n>1,设n=p_1^(α1)p_2^(α2)…P_k^(αk)是n的标准分解式,函数Ω(n)定义为Ω(1)=0,Ω(n)=∑_(i=1)~kα_i,φ(n)为Euler函数,本文的主要目的是利用初等方法研究方程φ(φ(n))=2^(Ω(n))的可解性,并获得该方程的所有正整数解,从而彻底解决了前学者提出的一个问题.

关于整除性n｜φ(n)+σ(n)

本文证明了：ｉ）当合数ｎ至多只有两个不同的素因子时，ｎφ（ｎ）＋σ（ｎ）；ｉ）若奇合数ｎ满足ｎ｜φ（ｎ）＋σ（ｎ），则ｎ至少有６个不同的素因子，且ｎ≥６５１５５１１５０２５；ｉｉ）在区间［１０７，２·１０７］中有且仅有一个ｎ，即ｎ＝１２５５８９１２，满足ｎ｜φ（ｎ）＋σ（ｎ）．

关于欧拉函数方程φ(φ(x))=2t的可解性

对任意的正整数n,函数φ(n)为著名的Euler函数,即在序列1,2,···,n中与n互质的整数的个数.本文利用初等方法研究了方程φ(φ(x))的可解性,并给出了该方程的全部正整数解.

关于Smarandache方程的可解性

研究包含经典的Euler函数与Smarandache函数的算术方程,利用分类等初等数论方法,给出了此方程解的一般形式,得到三个有趣的定理,改进和补充了已有的结论.

关于Makowski-Schinzel问题

对于正整数ｎ，设σ（ｎ），ω（ｎ）分别是ｎ的约数和函数和Ｅｕｌｅｒ函数．本文证明了：如果ｐ是ｎ的素因数。

关于丢番图方程2^x-2^y·3^z-2·3^u=9^k＋1

利用初等方法给出了丢番图方程2x-2y·3z-2·3u=9k+1,x,y,k>0,z,u≥0的全部整数解:(x,y,z,u,k)=(4,2,0,0,1),(5,2,0,2,1),(6,2,2,2,1),(8,2,1,4,2),(5,4,0,1,1),(6,4,1,1,1),(9,4,0,5,1),(10,5,2,1,3),(7,6,0,3,1),(8,6,1,3,1).利用此结果给出了与和完全数相关的丢番图方程2a+c+1-2c+1·3d+f+k-2-2·3f+k-1=3k+1,a>0,c>0,d≥0,f≥0,k≡0(mod2)的全部整数解:(a,c,d,f,k)=(4,1,1,1,2),(1,3,0,0,2),(2,3,1,0,2).

关于丢番图方程2^x-2^y·3^z-4·3^w=3·9^k＋1

用初等方法给出了丢番图方程2x-2y.3z-4.3w=3.9k+1,x>0,y>0,z≥0,w≥0,k>0的全部整数解,利用这一结果,推出与和完全数有关的一类不定方程仅有一组整数解.

关于数论函数方程φ(φ(n))=2^(ω(n))的可解性问题研究

对任意的正整数n,函数φ(n)为著名的Euler函数,即在序列1,2,...,n-1,n中与n互质的整数的个数;函数ω(n)表示任意正整数n的所有不同质因数的个数。文章利用初等方法研究了φ(φ(n))=2ω(n)方程的可解性,并给出了该方程的全部正整数解。

Jordan函数r次方Jrk（n）的均值误差项研究

设ｋ，ｒ分别是自然数和非零整数，Ｊｋ（ｎ）是Ｊｏｒｄａｎ函数．文［３］求出了和式∑ｎ≤ｘＪｒｋ（ｎ）的渐近公式．以Ｅ（ｘ；ｋ，ｒ）表示该公式中的误差项，本文研究了Ｅ（ｘ；ｋ。

Dedekind函数ψ（n）倒数的均值误差项的性质

若ψ（ｎ）是Ｄｅｄｅｋｉｎｄ函数，则有其中α，β是常数。以Ｒ（ｘ）记上述渐近公式中的误差项，本文研究了Ｒ（ｘ）的算术均值与积分均值。

包含Euler函数的方程的可解性

对任意正整数n,Smarandache LCM函数是满足n|[1,2,,k]的最小的正整数,其中[1,2,,k]代表1,2,,k的最小公倍数。欧拉函数φ(n)定义为序列1,2,3,,n-1中与n互素的正整数的个数。用分类讨论和初等方法完全解决了方程SL(n)=φ(n)的可解性。

与Dedekind函数ψ(n)有关的误差项估计

设Ψ (n)是 Dedekind函数 .本文首先对和式 ∑n≤ xΨ (n)n 的渐近公式中的误差项作了改进 ,以 E(x)表示改进后的误差项 ,进一步研究了 E(x) 的平方均值 .

关于σ(n)和φ(n)的一个整除式

设φ(n)表示n的欧拉函数,σ(n)表示n的所有正因子和,ω(n)表示n的不同素因子的个数.对于整除关系φ(n)|σ(n),其中n是正整数,当n为素数时只对n=2,3成立.讨论了当n至多有3个不同的素因子时,n为哪些合数时才能使该整除式成立,其中解2α(2α+2-1)(其中2α+2-1为素数,α∈N)与偶完全数2n-1(2n-1)(其中2n-1为素数且n∈N)类似.

关于方程φ(x)=2t

设t是正奇数.本文给出了方程φ(x)=2t的全部正整数解x,其中φ(x)是Euler函数.

GD—猜想的证明和RSA公钥体制中欧拉函数值的估计

本文对 Gorgui-Naguib 和 Dlay 提出的两个猜想给出了修改和证明,并建立在 RSA 公钥体制中欧拉函数表达式的基础上提出了一种估计欧拉函数值的算法。当知道μ=q/p 的较小区间范围内的值时,我们提出了一种攻击RSA 体制的可能方法.

关于两个数论函数的一个整除式

证明了对于正整数n,当2n且n≠2αpq(α∈N),ω(n)=3时,σ(n)=kφ(n)(k∈N且k≤4)无正整数解,其中p,q为不同的奇素数.

On the Distribution of Values of Euler＇s Function over Integers in Arithmetic Progressions

Let φ(n) denote the Euler-totient function, we study the distribution of solutions of φ(n) ≤ x in arithmetic progressions, where n ≡ l(mod q) and an asymptotic formula was obtained by Perron formula.