量子求解欧拉函数破解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)

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

关于Smarandache方程的可解性

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

关于Makowski-Schinzel问题

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

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

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

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

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

Jordan函数r次方Jrk（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)的可解性。

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.

关于σ(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)类似.

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为不同的奇素数.

关于方程φ(x)=2t

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

关于Diophantione方程x^(d(n))+y^(φ(n))=z^(σ(n))的本原解

对于正整数n,设d(n),φ(n),σ(n)分别是n的约数函数、Euler函数和约数和函数.本文证明了:当n无平方因子时,除了n=2或者n是适合n≡3(mod 4)的奇素数这两种情况以外,方程xd(n)+yφ(n)=zσ(n)没有正整数解.

数论中欧拉公式的一个初等证明及欧拉函数的性质

数论中的欧拉函数即比给定的自然数小且与之互素的自然数的个数,包括1在内,定义为φ(n)。欧拉给出了它的计算公式。文章对于该公式给出了一种初等证明,并讨论了它的一些性质。

与Euler函数有关的误差项均值估计

设 φ(n)是Euler函数 ,r是正实数 .以E(x ,r)表示和式 ∑n≤xnφ(n)r的渐近公式中的误差项 ,本文研究了E(x ,r)的算术均值和积分均值 .

关于奇Euler相关数对

设a,b是正整数.t是大于1的正整数.本文证明了:当a和b都是奇数时,(a,b)不是t-Euler相关数对.