精华内容
下载资源
问答
  • 二次剩余

    千次阅读 2015-11-23 20:59:20
    不是二次剩余。这个 a a 直接随机就好了。 那么最终我们有 x = ( a + w − − √ ) P + 1 2 x = (a + \sqrt{w})^{\frac{P + 1}{2}} 问题是 w − − √ \sqrt{w} 不存在,我们将 w − − √ \sqrt{w} 如同虚数 ...

    给定两个数 n,P , P 为一个质数,且n<P,求一个 x ,使得x2n(mod P)

    下面所有的运算都在 mod P 意义下进行。

    首先我们要判断是否有解。

    根据勒让德记号,我们有 nP12=±1 ,并且上述问题有解当且仅当 nP12=1

    a ,满足w=a2n w 对于P不是二次剩余。这个 a 直接随机就好了。

    那么最终我们有x=(a+w)P+12

    问题是 w 不存在,我们将 w 如同虚数 i 一样设定,那么由于最终x是一个实数,所以直接当虚数来做快速幂最终取实根即可。

    证明:
    x=(a+w)P+12
    x2=(a+w)P+1=(a+w)P(a+w)

    由二项式定理得:
    (a+w)P=Pk=0CkPak(w)Pk

    又由于当 0<k<P 时, CkP mod P=0 ,所以

    (a+w)P=aP+(w)P

    又由费马小定理 aP1=1,wP12=wP1=1

    所以

    (a+w)P=aw

    所以 x2=(aw)(a+w)=a2w=n

    得证

    展开全文
  • 二次剩余入门

    万次阅读 多人点赞 2018-01-02 17:40:42
    二次剩余入门。 1,什么是二次剩余? 2,二次剩余有什么用? 3,二次同余方程如何求解? 这一部分内容参考了这两篇文章: http://blog.csdn.net/a_crazy_czy/article/details/5195

    昨天训练的时候遇到一道题怎么也不会做,在网上搜了题解之后第一次听说了二次剩余,看了一天各种dalao的博客,在这里总结一下自己所理解的二次剩余及其用法。


    1,什么是二次剩余?



    2,二次剩余有什么用?


    ※说白了就是如果该二次同余方程有解,那么n可以在模p的意义下开根号。


    3,二次同余方程如何求解?

    这一部分内容参考了这两篇文章:

    http://blog.csdn.net/a_crazy_czy/article/details/51959546

    http://blog.csdn.net/acdreamers/article/details/10182281 

    首先,以下解法有一个前提,就是p必须要是奇素数。


    接下来我们引入一个新概念:勒让德符号(legender symbol)

    它的定义如下


    由此再引出一个定理


    接下来是最后一个定理

           

             

    有了最后一个定理,我们就可以通过随机选择a的值来找到一个满足条件的解。之前的链接里有详细地解释为何可以随机取a的值,总的来说就是找到正解所需的次数的期望只有2。所以随机取a的值可以很快地找到一个解,代码如下。

    #include <iostream>   
    #include <ctime>
    using namespace std;
    typedef long long LL;
    #define random(a,b) (rand()%(b-a+1)+a)
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    LL p;
    LL w;//二次域的D值
    bool ok;//是否有解
    
    struct QuadraticField//二次域
    {
    	LL x, y;
    	QuadraticField operator*(QuadraticField T)//二次域乘法重载
    	{
    		QuadraticField ans;
    		ans.x = (this->x*T.x%p + this->y*T.y%p*w%p) % p;
    		ans.y = (this->x*T.y%p + this->y*T.x%p) % p;
    		return ans;
    	}
    	QuadraticField operator^(LL b)//二次域快速幂
    	{
    		QuadraticField ans;
    		QuadraticField a = *this;
    		ans.x = 1;
    		ans.y = 0;
    		while (b)
    		{
    			if (b & 1)
    			{
    				ans = ans*a;
    				b--;
    			}
    			b /= 2;
    			a = a*a;
    		}
    		return ans;
    	}
    };
    
    LL Legender(LL a)//求勒让德符号
    {
    	LL ans=quick_mod(a, (p - 1) / 2, p);
    	if (ans + 1 == p)//如果ans的值为-1,%p之后会变成p-1。
    		return -1;
    	else
    		return ans;
    }
    
    LL Getw(LL n, LL a)//根据随机出来a的值确定对应w的值
    {
    	return ((a*a - n) % p + p) % p;//防爆处理
    }
    
    LL Solve(LL n)
    {
    	LL a;
    	if (p == 2)//当p为2的时候,n只会是0或1,然后0和1就是对应的解
    		return n;
    	if (Legender(n) == -1)//无解
    		ok = false;
    	srand((unsigned)time(NULL));
    	while (1)//随机a的值直到有解
    	{
    		a = random(0, p - 1);
    		w = Getw(n, a);
    		if (Legender(w) == -1)
    			break;
    	}
    	QuadraticField ans,res;
    	res.x = a;
    	res.y = 1;//res的值就是a+根号w
    	ans = res ^ ((p + 1) / 2);
    	return ans.x;
    }
    
    int main()
    {
    	LL n,ans1,ans2;
    	while (scanf("%lld%lld",&n,&p)!=EOF)
    	{
    		ok = true;
    		n %= p;
    		ans1 = Solve(n);
    		ans2 = p - ans1;//一组解的和是p
    		if (!ok)
    		{
    			printf("No root\n");
    			continue;
    		}
    		if (ans1 == ans2)
    			printf("%lld\n", ans1);
    		else
    			printf("%lld %lld\n", ans1, ans2);
    	}
    }



    展开全文
  • 二次剩余模素数形状

    2020-03-02 08:47:50
    二次剩余模素数形状,吴勇,余愚,本文应用高斯二次互反律,给出了对于奇素数p,以素数q为二次剩余的形状。获得二次剩余判别问题的一个新定理:素数q是奇素数p的二次�
  • 在数论中,特别在同余理论里,一个整数对另一个整数的二次剩余(英语:Quadratic residue)指的平方除以得到的余数。 当存在某个,式子成立时,称“是模的二次剩余” 当对任意,不成立时,称“d是模p的二次非剩余...

    在数论中,特别在同余理论里,一个整数X对另一个整数p二次剩余(英语:Quadratic residue)指X的平方X^2除以p得到的余数。

    当存在某个X,式子X^2 \equiv d (mod $ $ p)成立时,称d是模p的二次剩余”

    当对任意XX^2 \equiv d (mod $ $ p)不成立时,称“d是模p的二次非剩余”

    质数的二次剩余

    对于质数2,每个整数都是它的二次剩余。

    以下讨论p是奇质数的情况:

    对于XX^2 \equiv d (mod $ $ p) 而言,能满足“d是模 p的二次剩余”的 d共有\frac{p + 1}{2}个(剩余类),分别为:0^2, 1^2, 2^2,...(\frac{p -1}{2})^2(0计算在内)

    此外是\frac{p-1}{2}个二次非剩余。但在很多情况下,我们只考虑乘法群Z/pZ,因此不将0包括在内这样,每个二次剩余的乘法逆元仍然是二次剩余;二次非剩余的乘法逆元仍然是二次非剩余。

    二次剩余的个数与二次非剩余的个数相等,都是\frac{p-1}{2}。此外,两个二次非剩余的乘积是二次剩余,二次剩余和二次非剩余的乘积是二次非剩余。

    应用二次互反论可以知道,当p模4余1时,-1是p的二次剩余;如果p模4余3,那么,-1是p的二次非剩余。

    要知道d是否为模p的二次剩余,可以运用欧拉判别法(或叫欧拉准则)。

    另外,若找到一个a,使得a^2-n^2 = w,且\left ( \frac{w}{p} \right ) = -1,则x = (a + \sqrt{w}) ^ {\frac{p+1}{2}}x^2 \equiv n (mod$ $p)注意 (a + \sqrt{w})这里的为数域扩张 类似于模意义下的虚数 要重定义运算法则

    证明:

    展开全文
  • 二次剩余,平方剩余,程序用C语言C++实现(数论 椭圆曲线)
  • 二相编码序列,L序列,256位以下所有的L序列码(有叫二元二次剩余序列) 要用到初等数论中的二次剩余知识 信号频谱、自相关 matlab code 有注释
  • 针对现有基于二次剩余的无线射频识别(RFID)认证协议在安全和成本方面的漏洞与不足,设计了一种基于二次剩余的改进的RFID双向认证协议。改进的协议在基础二次剩余算法框架下,混入随机数加密,使消息在数据库认证...
  • 所提协议在确保通信实体双向认证前提下,采用二次剩余定理,对传输信息进行加密;在通信实体相互识别过程中,随机数的加入可以使协议有效抵抗重放及去同步化等攻击;待所有权发生转移后,新的通信实体之间,通过动态...
  • 浅谈二次剩余

    万次阅读 2019-01-05 12:48:37
    二次剩余是数论基本概念之一,它是初等数论中非常重要的结果。 什么是二次剩余呢?简单来说就是如果存在一个整数xxx,使得x2≡n(mod&amp;amp;nbsp;p)x^2≡n(mod\ p)x2≡n(mod&amp;amp;nbsp;p),那么则称nnn...

    二次剩余是数论基本概念之一,它是初等数论中非常重要的结果。
    什么是二次剩余呢?简单来说就是如果存在一个整数 x x x,使得 x 2 ≡ n ( m o d   p ) x^2≡n(mod\ p) x2n(mod p),那么则称 n n n是模 p p p的二次剩余。
    有一种很巧妙的办法,可以得出一个数是否是模 p p p的二次剩余。这个办法是勒让德符号 ( n p ) (\frac{n}{p}) (pn)

    如果 n n n是模 p p p的二次剩余,那么 ( n p ) = 1 (\frac{n}{p})=1 (pn)=1
    如果 n n n不是模 p p p的二次剩余,那么 ( n p ) = − 1 (\frac{n}{p})=-1 (pn)=1
    如果 p ∣ n p|n pn,则 ( n p ) = 0 (\frac{n}{p})=0 (pn)=0

    这里有一个结论: ( n p ) = n p − 1 2 (\frac{n}{p})=n^{\frac{p-1}{2}} (pn)=n2p1 (前提是 p p p是奇质数)

    证明:(不看也无所谓)
    ①如果 n n n是模 p p p的二次剩余,那么 n \sqrt n n p p p互质,那么根据费马小定理 ( n ) p − 1 ≡ 1 ( m o d   p ) (\sqrt n)^{p-1}≡1(mod\ p) (n )p11(mod p)
    ②如果 n n n不是模 p p p的二次剩余,那么因为 p p p是奇质数,所以根据扩欧可知对于 i ∈ [ 1 , p − 1 ] i∈[1,p-1] i[1,p1],都有一个 j ∈ [ 1 , p − 1 ] j∈[1,p-1] j[1,p1]使其满足 i j ≡ n ( m o d   p ) ij≡n(mod\ p) ijn(mod p)。所以我们可以把 1 , 2 … … p − 1 1,2……p-1 1,2p1分成 p − 1 2 \frac{p-1}{2} 2p1对,每对的乘积在模 p p p下都是 n n n,那么 ( p − 1 ) ! ≡ n p − 1 2 ( m o d   p ) (p-1)!≡n^{\frac{p-1}{2}}(mod\ p) (p1)!n2p1(mod p),根据威尔逊定理有 ( p − 1 ) ! ≡ − 1 ( m o d   p ) (p-1)!≡-1(mod\ p) (p1)!1(mod p),所以 n p − 1 2 ≡ − 1 ( m o d   p ) n^{\frac{p-1}{2}}≡-1(mod\ p) n2p11(mod p)
    ③如果 p ∣ n p|n pn,那么显然 n p − 1 2 ≡ 0 ( m o d   p ) n^{\frac{p-1}{2}}≡0(mod\ p) n2p10(mod p)

    定理:对于方程 x 2 ≡ n ( m o d   p ) x^2≡n(mod\ p) x2n(mod p),有 p − 1 2 \frac{p-1}{2} 2p1个不同的 n n n,使得该方程有解。

    证明:若有两个数 u u u v v v均满足它们的平方在 p p p时同余,那么必然有 p ∣ ( u + v ) ( u − v ) p|(u+v)(u−v) p(u+v)(uv)。由于 p p p不可能整除 u − v u−v uv,那么可以得出 p p p整除 u + v u+v u+v。这个结论反过来也是成立的,因此共有 p − 1 2 \frac{p-1}{2} 2p1种不同的平方。且每一个 p p p的二次剩余恰好有两个解。

    那么怎么求一个二次剩余呢?我们可以按照下面的方法:

    [ 0 , p − 1 ] [0,p-1] [0,p1]随机挑选一个数,称其为 a a a,定义 w = a 2 − n w=a^2-n w=a2n,若 ( w p ) = − 1 (\frac{w}{p})=-1 (pw)=1,那么 ( a + w ) p + 1 2 (a+\sqrt w)^{\frac{p+1}{2}} (a+w )2p+1就是一组二次剩余。

    证明: ( a + w ) p = ∑ i = 0 p ( C p i a p − i ) ( C p p − i ( w ) i ) (a+\sqrt w)^{p}=\sum_{i=0}^{p}(C_{p}^{i}a^{p-i})(C_{p}^{p-i}(\sqrt w)^{i}) (a+w )p=i=0p(Cpiapi)(Cppi(w )i),由于 p p p是质数,所以除了 C p 0 C^{0}_{p} Cp0 C p p C_{p}^{p} Cpp 1 1 1外,所有的 C p i ( i ∈ [ 1 , p − 1 ] ) C_{p}^{i}(i∈[1,p-1]) Cpi(i[1,p1]) p p p等于 0 0 0,所以 ( a + w ) p ≡ a p + w p   ( m o d   p ) (a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p) (a+w )pap+w p (mod p)
    由费马小定理可得 a p ≡ a ( m o d   p ) a^p≡a(mod\ p) apa(mod p),又因为 ( w p ) = − 1 (\frac{w}{p})=-1 (pw)=1 w p − 1 2 = − 1 w^{\frac{p-1}{2}}=-1 w2p1=1,所以 w p = − w \sqrt w^{p}=-\sqrt w w p=w
    所以 ( a + w ) p ≡ a p + w p   ( m o d   p ) ≡ a − w ( m o d   p ) (a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p)≡a-\sqrt w(mod\ p) (a+w )pap+w p (mod p)aw (mod p)
    所以 ( a + w ) p + 1 ≡ ( a + w ) p ( a + w ) ≡ ( a − w ) ( a + w ) ≡ a 2 − w ≡ n (a+\sqrt w)^{p+1}≡(a+\sqrt w)^{p}(a+\sqrt w)≡(a-\sqrt w)(a+\sqrt w)≡a^2-w≡n (a+w )p+1(a+w )p(a+w )(aw )(a+w )a2wn

    有了最后一个定理,我们就可以通过随机选择a的值来找到一个满足条件的解。可以证明找到正解所需的次数的期望只有2(然而我并不是特别会证)。所以随机取a的值可以很快地找到一个解。

    部分代码:

    struct field{
    	int x,y;
    	field(int a=0,int b=0){
    		x=a;y=b;
    	}
    };
    field operator*(field a,field b){return field(a.x*b.x%p+a.y*b.y%p*w%p,a.x*b.y%p+a.y*b.x%p);}
    
    int ran(){
    	static int seed=23333;
    	return seed=((((((ll)seed^20030927)%p+330802)%p*9410)%p-19750115+p)%p^730903)%p;
    }
    
    int pows(int a,int b){
    	int base=1;
    	while(b){
    		if(b&1) base=base*a%p;
    		a=a*a%p;b/=2;
    	}
    	return base;
    }
    
    field powfield(field a,int b){
    	field base=field(1,0);
    	while(b){
    		if(b&1) base=base*a;
    		a=a*a;b/=2;
    	}
    	return base;
    }
    
    int legander(int x){
    	int a=pows(x,(p-1)/2);
    	if(a+1==p) return -1;
    	return a;
    }
    
    int surplus(int x){
    	int a;
    	if(legander(x)==-1) return 0;
    	while(1){
    		a=ran()%p;
    		w=((a*a-x)%p+p)%p;
    		if(legander(w)==-1) break;
    	}
    	field b=field(a,1);
    	b=powfield(b,(p+1)/2);
    	return b.x;
    }
    
    展开全文
  • 代数和数论中的程序计算问题之二次剩余符号的程序计算
  • 二次剩余,二次同余方程

    千次阅读 2018-08-27 15:09:12
    n为p的二次剩余 , x为该二次同余方程的解 就如字面意思一样 , n就是一个二次项%p后的剩余 应用 求n−−√%p,n%p,\sqrt{n}\%p\;,若n为p的二次剩余 , 那么很明显n−−√%p=x%pn%p=x%p\sqrt{n}\%p=x\%p 简...
  • 二次剩余问题 有举例 求解 验证是否为二次剩余
  • 二次剩余--欧拉准则

    千次阅读 2015-04-17 10:43:33
    在数论中,二次剩余的欧拉判别法(又称欧拉准则)是用来判定给定的整数是否是一个质数的二次剩余。 目录 1 叙述2 举例 2.1 例子一:对于给定数,寻找其为二次剩余的模数2.2 例子二:对指定的...
  • 二次剩余 数论 例题 讲解 经典第四章 平方剩余 Quadratic Residue
  • 二次剩余定理详解

    千次阅读 2020-03-03 16:03:13
    title: 二次剩余定理详解 date: 2019-09-10 13:09:36 tags: - 数论 mathjax: true 二次剩余 x2≡n(mod p)x^2≡n(mod\ p)x2≡n(mod p) 对于这个方程,求出满足的x。 引理1 首先来看一个符号 (np) (\frac{n}...
  • 二次剩余(学习笔记)

    千次阅读 2018-12-06 10:59:08
    就是用来求解x2≡n&amp;amp;VeryThinSpace;mod&amp;amp;VeryThinSpace;...(ap)={1a在模p意义下是二次剩余−1a在模p意义下是非二次剩余0a≡0&amp;amp;VeryThinSpace;mod&amp;amp;...
  • 数论pdf 同余式 数论函数 二次剩余 原根 k次剩余
  • 二次剩余及其计算方法

    千次阅读 2019-01-29 14:53:42
    给定aaa求是否有xxx满足这个式子,若有r则称a是模p的二次剩余 若没有满足条件的xxx,则称a是模p的非二次剩余 然而在一些题目中,我们既要判定它是否是模p的二次剩余,也要判断其值,本文就对此进行一些探究 对于所有...
  • 针对基于动态口令的电子商务身份认证机制存在计算和通信负担过重及不能对用户的使用次数和使用时间进行控制的问题,利用二次剩余理论中计算模平方根的复杂性提出一种基于二次剩余的动态口令算法。本算法具有失效次数...
  • 二次剩余Cipolla算法学习小记

    万次阅读 多人点赞 2016-07-20 21:59:27
    貌似国内直接查名字还没有什么资料,查二次剩余的算法有ACdreamer简略的介绍。今天听讲时算是听懂了大半,回来又搞鼓了整个晚上才算完全弄明白。这个算法真的是从头到尾都是脑洞,太神了! 详细的解释见维基百科。 ...
  • 本文研究了整数环模16剩余类环Zi6上的二次剩余码,讨论了它们的幂等生成元及其扩展码的自对偶性等代数性质,并研究了码长为7的Zis二次剩余码在两种已有的Gray映射下的有趣性质,尤其是确定了它们的Lee重量分布。
  • 针对现有无线射频识别(RFID)标签所有权转移协议在安全和成本方面的漏洞与不足,设计了一种基于二次剩余的RFID标签所有权动态转移协议。协议在双向认证安全框架下,引入二次剩余算法,增加了系统稳定性;在原数据库...
  • 一种基于二次剩余的混合软件水印研究,王刚,贾小珠,动态图水印在抗攻击性方面较通常的静态水印有明显的优势。然而由于这类水印本身可能与宿主程序的功能性之间并无太大联系,使得攻
  • 针对彩色图像的有效加密问题,提出了一种基于logistic混沌映射和二次剩余密码体制的彩色图像加密方法。使用了一组对称的128 bit的密钥,并以此计算logistic混沌映射的初始条件和控制参数;通过具有不同参数的两级...
  • 针对公共网络中数字图像的安全传播问题,提出了一种基于二维Logistic混沌映射和二次剩余的图像加密算法。该加密算法利用二维Logistic映射的优良随机性,对明文图像进行2次置乱,极大地改变了图像像素位置。然后把置乱...
  • 随着办公自动化技术的大量应用,如何保障电子公文的...针对这些问题,提出了一种基于二次剩余技术用于提高电子印章鲁棒性的新系统;并详细地论述了其关键算法;最后对电子印章的研究发展及其应用前景指出了一些可能的方向。
  • 二次剩余推理及其求解过程

    千次阅读 2019-12-07 22:51:23
    \quad给出一个式子x2≡n(modp)x^2≡n(mod p)x2≡n(modp),再给出nnn和ppp,如果能求得一个x满足该式子,即xxx满足x2=n+kp,k∈Zx^2=n+kp,k\in Zx2=n+kp,k∈Z,那么我们称nnn是模ppp的二次剩余,若不存在这样的xxx,...
  • 二次剩余.ppt

    2019-09-09 12:37:52
    1 Legendre符号及Euler 判别法 2 二次互反律 3 Jacobi 符号 4 应用实例-Rabin体制 一般二次同余式
  • 思路来源 https://blog.csdn.net/kele52he/article/details/78897187(二次剩余) https://blog.csdn.net/stevensonson/article/details/85845334(二次剩余) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 268,185
精华内容 107,274
关键字:

二次剩余