-
2020-07-10 16:17:01
First complex number: 471 + 643i不是高斯素数
Second complex number: 9 + 11i不是高斯素数
The sum of the two numbers: 480 + 654i
The Minus of the two numbers: 462 + 632i
The Product of the two numbers: -2834 + 10968i
The Divide of the two numbers: 56 + 3i,b=True,q=56 + 3i,r=0 + 0i
gcd(112 + 1i,-57 + 79i)=4 + 7i
gcd(112 + 1i,-57 + 79i)=4 + 7i,z5=-1 + -6i,z6=5 + -5i
第0个高斯整数是0 + 0i
第1个高斯整数是1 + 0i
第2个高斯整数是0 + 1i
第3个高斯整数是-1 + 0i
第4个高斯整数是0 + -1i
第5个高斯整数是1 + 1i
第6个高斯整数是-1 + 1i
第7个高斯整数是-1 + -1i
第8个高斯整数是1 + -1i
第9个高斯整数是2 + 0i
第10个高斯整数是0 + 2i
第11个高斯整数是-2 + 0i
第12个高斯整数是0 + -2i
第13个高斯整数是2 + 1i
第14个高斯整数是1 + 2i
第15个高斯整数是-1 + 2i
第16个高斯整数是-2 + 1i
第17个高斯整数是-2 + -1i
第18个高斯整数是-1 + -2i
第19个高斯整数是1 + -2i
第20个高斯整数是2 + -1i
第21个高斯整数是2 + 2i
第22个高斯整数是-2 + 2i
第23个高斯整数是-2 + -2i
第24个高斯整数是2 + -2i
第25个高斯整数是3 + 0i
第26个高斯整数是0 + 3i
第27个高斯整数是-3 + 0i
第28个高斯整数是0 + -3i
第29个高斯整数是3 + 1i
第30个高斯整数是1 + 3i
第31个高斯整数是-1 + 3i
第32个高斯整数是-3 + 1i
第33个高斯整数是-3 + -1i
第34个高斯整数是-1 + -3i
第35个高斯整数是1 + -3i
第36个高斯整数是3 + -1i
第37个高斯整数是3 + 2i
第38个高斯整数是2 + 3i
第39个高斯整数是-2 + 3i
第40个高斯整数是-3 + 2i
第41个高斯整数是-3 + -2i
第42个高斯整数是-2 + -3i
第43个高斯整数是2 + -3i
第44个高斯整数是3 + -2i
第45个高斯整数是3 + 3i
第46个高斯整数是-3 + 3i
第47个高斯整数是-3 + -3i
第48个高斯整数是3 + -3iusing System;
using System.Collections.Generic;public struct Complex
{
public int real;
public int imaginary;
public Complex(int real, int imaginary)
{
this.real = real;
this.imaginary = imaginary;
}
//overload operator(+),added(two Complex objects) and return a Complex type
public static Complex operator +(Complex c1, Complex c2)
{
return new Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
}
//overload operator(-)
public static Complex operator -(Complex c1, Complex c2)
{
return new Complex(c1.real - c2.real, c1.imaginary - c2.imaginary);
}
//overload operator(*)
public static Complex operator *(Complex c1, Complex c2)
{
return new Complex(c1.real * c2.real - c1.imaginary * c2.imaginary,c1.real * c2.imaginary + c1.imaginary * c2.real);
}
//overload operator(/)
public static Complex operator /(Complex c1, Complex c2)
{
Complex c2c=new Complex(c2.real,-c2.imaginary);
Complex c1c2c=c1*c2c;
int N=Norm(c2);
Complex c1c2=c1*c2c;
double crf=(double)c1c2.real/N;
double cif=(double)c1c2.imaginary/N;
//int cr=crf>0?(int)(crf+0.5):(int)(crf-0.5);
//int ci=cif>0?(int)(cif+0.5):(int)(cif-0.5);
int cr=(int)Math.Floor(crf+0.5);
int ci=(int)Math.Floor(cif+0.5);
return new Complex(cr,ci);
}
// 按范数和辐角主值从小到大排列顺序
public static bool operator < (Complex c1, Complex c2)
{
int norm1=Norm(c1);
int norm2=Norm(c2);
double arg1=Math.Atan2(c1.imaginary,c1.real);
double arg2=Math.Atan2(c2.imaginary,c2.real);
double pi=Math.Atan2(0,-1);
if(arg1<0)
arg1+=2*pi;
if(arg2<0)
arg2+=2*pi;
if(norm1!=norm2)
return norm1<norm2;
else
return arg1<arg2;
}
// 运算符“Complex.operator <(Complex, Complex)”要求也要定义匹配的运算符“>”
public static bool operator > (Complex c1, Complex c2)
{
int norm1=Norm(c1);
int norm2=Norm(c2);
double arg1=Math.Atan2(c1.imaginary,c1.real);
double arg2=Math.Atan2(c2.imaginary,c2.real);
double pi=Math.Atan2(0,-1);
if(arg1<0)
arg1+=2*pi;
if(arg2<0)
arg2+=2*pi;
if(norm1!=norm2)
return norm1>norm2;
else
return arg1>arg2;
}
public static int Norm(Complex a)
{
return (a.real*a.real+a.imaginary*a.imaginary);
}
public static bool divide(Complex a,Complex b,out Complex q,out Complex r)
{
q=a/b;
r=a-q*b;
bool bret=(r.real==0 && r.imaginary==0);
return bret;
}
static void swap(ref Complex a,ref Complex b)
{
Complex t=a;
a=b;
b=t;
}
public static Complex gcd(Complex a,Complex b)
{
Complex x = a, y = b;
if(Norm(x)<Norm(y) )
{
swap(ref x,ref y);
}
while(y.real!=0 || y.imaginary!=0) {
Complex q,r;
bool ret=divide(x,y,out q,out r);
x = y;
y = r;
}
return x;
}
public static Complex extended_gcd(Complex a,Complex b,out Complex x,out Complex y)
{
Complex aa = a, bb = b;
bool swapped = false;
if(Norm(aa)<Norm(bb) )
{
swap(ref aa,ref bb);
swapped = true;
}
Complex xx = new Complex(0,0);
Complex lx = new Complex(1,0);
Complex yy = new Complex(1,0);
Complex ly = new Complex(0,0);
do
{
Complex qq, rr;
bool bret=divide(aa, bb,out qq,out rr);
aa = bb;
bb = rr;
Complex tx = lx-qq*xx;
lx = xx;
xx = tx;
Complex ty = ly-qq*yy;
ly = yy;
yy = ty;
}while(bb.real!=0 || bb.imaginary!=0);
x = lx;
y = ly;
if (swapped)
{
swap(ref x,ref y);
}
return aa;
}
// Override the ToString method to display an complex number in the suitable format:
public override string ToString()
{
return (String.Format("{0} + {1}i", real, imaginary));
}
}public class numtheory
{
public static bool IsPrime(uint N)
{
if(N==0||N==1)
return false;
int up=Convert.ToInt32(Math.Sqrt((double)N));
for(int i=2;i<=up;i++)
{
if(N%i==0)
return false;
}
return true;
}
/*
高斯整数a+bi是素数当且仅当:
1)a、b中有一个是零,另一个数的绝对值是形如4n+3的素数;
2)a、b均不为零,而a^2+b^2为素数;
*/
public static bool IsPrime(Complex N)
{
int a=Math.Abs(N.real);
int b=Math.Abs(N.imaginary);
if(a==0 && (b+1)%4==0)
return true;
if(b==0 && (a+1)%4==0)
return true;
if(a*b>0 && IsPrime(Convert.ToUInt32(a*a+b*b)))
return true;
return false;
}
public static string is_gausian_prime(bool bret)
{
string strDes=(bret?"是高斯素数":"不是高斯素数");
return strDes;
}
public static void QSort(List<Complex> arr,int startPos,int endPos)
{
Complex z=arr[startPos];
int i=startPos;
int j=endPos;
while(i<j)
{
while(arr[j]>z && i<j)
--j;
arr[i]=arr[j];
while(arr[i]<z && i<j)
++i;
arr[j]=arr[i];
}
arr[i]=z;
if(i-1>startPos)
QSort(arr,startPos,i-1);
if(endPos>i+1)
QSort(arr,i+1,endPos);
}
public static void BubbleSort(List<Complex> a)
{
int n=a.Count;
for(int i=n-1,change=1;i>=1 && change==1;i--)
{
change=0;
for(int j=0;j<i;j++)
if(a[j]>a[j+1])
{
Complex temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
change=1;
}
}
}
// 范数不超过N的高斯整数
public static List<Complex> lessN(int N)
{
List<Complex> L=new List<Complex>();
int n=Convert.ToInt32(Math.Sqrt((double)N));
for(int i=-n;i<=n;i++)
for(int j=-n;j<=n;j++)
{
Complex a;
a.real=i;
a.imaginary=j;
L.Add(a);
}
//L.Sort();
//QSort(L,0,L.Count-1);
BubbleSort(L);
return L;
}
}public class ComplexTest
{
static void Main(string[] args)
{
Complex num1 = new Complex(471,643);
Complex num2 = new Complex(9,11);
//Add two Complex objects (num1 and num2) through the overloaded plus operator:
Complex sum_Add = num1 + num2;
Complex sum_Minus = num1 - num2;
Complex sum_Product = num1 * num2;
Complex sum_Divide = num1 / num2;
//Complex q=new Complex();
//Complex r=new Complex();
Complex q,r;
bool b=Complex.divide(num1,num2,out q,out r);
//Print the numbers and the Result using the overriden ToString method:
Console.WriteLine("First complex number: {0}{1}", num1,numtheory.is_gausian_prime(numtheory.IsPrime(num1)));
Console.WriteLine("Second complex number: {0}{1}", num2,numtheory.is_gausian_prime(numtheory.IsPrime(num2)));
Console.WriteLine("The sum of the two numbers: {0}", sum_Add);
Console.WriteLine("The Minus of the two numbers: {0}", sum_Minus);
Console.WriteLine("The Product of the two numbers: {0}", sum_Product);
Console.WriteLine("The Divide of the two numbers: {0},b={1},q={2},r={3}", sum_Divide,b,q,r);
Complex z1;
z1.real=112;
z1.imaginary=1;
Complex z2=new Complex(-57,79);
Complex z3=Complex.gcd(z1,z2);
Console.WriteLine("gcd({0},{1})={2}", z1,z2,z3);
Complex z5,z6;
Complex z4=Complex.extended_gcd(z1,z2,out z5,out z6);
Console.WriteLine("gcd({0},{1})={2},z5={3},z6={4}", z1,z2,z4,z5,z6);
List<Complex> L=numtheory.lessN(10);
for(int i=0;i<L.Count;i++)
{
Console.WriteLine("第{0}个高斯整数是{1}",i,L[i]);
}
Console.ReadLine();
}
}更多相关内容 -
完美的高斯整数序列对
2021-03-17 04:07:51完美的高斯整数序列对 -
零相关区高斯整数序列集构造法
2021-01-14 11:22:09研究了具有零相关区的高斯整数序列集构造方法。该方法基于二元正交矩阵,首先利用插零法构造出具有零相关区的三元序列集。然后利用完备高斯整数序列进行滤波,从而将三元序列变换成高斯整数序列且保持序列相关函数值... -
高斯整数环学习心得随笔及其实现
2021-12-24 15:20:53高斯整数环学习心得随笔 过些天补上~ 代码 ==:两个高斯整数相伴,即为相等。 小于和大于:用复数的范数Norm来比较。应用场景举例:高斯整数环的唯一分解定理证明。 整除和取模(带余除法):复数除法的结果是个...高斯整数环学习心得随笔
过些天补上~
代码
- ==:两个高斯整数相伴,即为相等。
- 小于和大于:用复数的范数Norm来比较。应用场景举例:高斯整数环的唯一分解定理证明。
- 整除和取模(带余除法):复数除法的结果是个有理数,但为了方便还是直接用double存了。设两个高斯整数
a,b
,复数除法结果为a / b = x+yi
,则一种可行的取法是round(x)+round(y)*i
,这就是整除结果。而g = (x-round(x))+(y-round(y))*i
就是带余除法定义中一个可行的“范数小于等于1/2的复数”,g*b
即取模结果。具体看代码。 - gcd:既然有带余除法,直接运行辗转相除法即可。
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,b) for(int i = (a);i <= (b);++i) #define re_(i,a,b) for(int i = (a);i < (b);++i) #define dwn(i,a,b) for(int i = (a);i >= (b);--i) const int N = 1e3 + 5; const int mod = 998244353; int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1}; void dbg(){puts("");} template<typename T, typename... R>void dbg(const T &f, const R &... r) { cout << f << " "; dbg(r...); } template<typename Type>inline void read(Type &xx){ Type f = 1;char ch;xx = 0; for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0'; xx *= f; } void read(){} template<typename T,typename ...R>void read(T &x,R &...r){ read(x); read(r...); } struct GI; LL norm(const GI &x); GI gcd(const GI &x,const GI &y); struct GI{ int a,b; GI():a(0),b(0){} GI(int a,int b):a(a),b(b){} //相伴 bool operator == (const GI &rh) const{ return a == rh.a && b == rh.b || a == -rh.a && b == -rh.b || a == -rh.b && b == rh.a || a == rh.b && b == -rh.a; } bool operator < (const GI &rh) const{ return norm(*this) < norm(rh); } bool operator <= (const GI &rh) const{ return norm(*this) <= norm(rh); } bool operator > (const GI &rh) const{ return norm(*this) > norm(rh); } bool operator >= (const GI &rh) const{ return norm(*this) >= norm(rh); } GI operator + (const GI &rh) const{ return {a+rh.a,b+rh.b}; } GI operator - (const GI &rh) const{ return {a-rh.a,b-rh.b}; } GI operator * (const GI &rh) const{ return {a*rh.a-b*rh.b,a*rh.b+b*rh.a}; } //整除 GI operator / (const GI &rh) const{ double x = 1.0*(a*rh.a+b*rh.b)/norm(rh),y = 1.0*(b*rh.a-a*rh.b)/norm(rh); return {round(x),round(y)}; } GI operator % (const GI &rh) const{ double x = 1.0*(a*rh.a+b*rh.b)/norm(rh),y = 1.0*(b*rh.a-a*rh.b)/norm(rh); complex<double> g = {x-round(x),y-round(y)}; g *= complex<double>(rh.a,rh.b); return {round(g.real()),round(g.imag())}; } GI operator %= (const GI &rh){ GI u = (*this) % rh; a = u.a;b = u.b; return u; } friend ostream& operator << (ostream &sm,const GI &x){ sm << "(" << x.a << "," << x.b << ")"; return sm; } }; LL norm(const GI &x){return x.a*x.a+x.b*x.b;} GI gcd(const GI &x,const GI &y){ return y == GI() ? x : gcd(y,x%y); } void test_op(){ dbg("test_op"); GI x(4,3),y(3,4); assert(GI(4,3) == GI(-4,-3) && GI(4,3) == GI(-3,4) && GI(4,3) == GI(3,-4)); assert(!(x == y) && x <= y && x >= y); GI z(4,4); assert(x < z && x <= z && z > x && z >= x); assert(x+y == GI(7,7)); assert(x*y == GI(0,25)); } //对拍:https://jingyan.baidu.com/article/e75aca8526c6a7142fdac67f.html void test_div(){ dbg("test_div"); GI u = GI(1,8) % GI(-1,5); dbg(u);//(-2,-3) assert(u == GI(2,3)); GI x(18,5),y(7,5); u = x - x / y * y; dbg(x / y,u);//x / y = (2,-1), u = (-1,2) dbg(x % y);//(-1,2) assert(u == x % y); dbg(y / u);//(1,-4) dbg(y % u);//(0,-1) x = {112,1}; y = {-57,79}; dbg(x / y);//(-1,-1) u = x % y; dbg(u);//(-24,23) assert(u == GI(-24,23)); x %= y;swap(x,y); u = x % y; dbg(u);//(-8,-14) assert(u == GI(-8,-14)); x %= y;swap(x,y); u = x % y; dbg(u);//(-4,-7) assert(u == GI(4,7)); } void test_gcd(){ dbg("test_gcd"); GI g = gcd(GI(18,5),GI(7,5)); dbg(g);//(0,-1) assert(g == GI(0,-1)); g = gcd(GI(112,1),GI(-57,79)); dbg(g);//(-4,-7) assert(g == GI(4,7)); g = gcd(GI(32,9),GI(4,11)); dbg(g);//(0,-1) assert(g == GI(1,0)); g = gcd(GI(11,3),GI(1,8)); dbg(g);//(1,-2) assert(g == GI(1,-2)); g = gcd(GI(4,5),GI(4,-5)); dbg(g);//(0,1) assert(g == GI(1,0)); } int main(int argc, char** argv) { test_op(); test_div(); test_gcd(); return 0; }
-
长度为奇素数的完备高斯整数序列构造法
2021-01-14 07:14:42提出一类基于分圆类构造完备高斯整数序列的方法。分别通过有限域GF(p)上的2阶和4阶分圆类,构造得到自由度分别为3和5的高斯整数序列,序列长度为奇素数,该序列具有良好的完备自相关性能。该构造方法解决了以往利用... -
【学习笔记】高斯整数、高斯素数、费马平方和(全部相关概念及例题详解)《初等数论及其应用》
2021-01-30 18:37:02【学习笔记】高斯整数(全部相关概念及例题详解)整理的算法模板合集: ACM模板
实际上是一个全新的精炼模板整合计划
以下内容摘自 我的文章:算法竞赛中的数论问题 - 数论全家桶(信奥 / 数竞 / ACM)作者孟繁宇,四万字,十三万字符的竞赛数论完全总结,将会择机发布,敬请期待 ~
0x90 高斯整数
0x90.0 复数
复数分为实部和虚部,可以描述为一个二元组 ( x , y ) (x,y) (x,y),表示这个数等于 x + y − 1 x+y\sqrt {-1} x+y−1。一般用 i i i 表示 − 1 \sqrt{-1} −1。
由于是个二元组,所以它在理解的时候可以抽象为一个二维向量,分布在平面直角坐标系上。
事实上,它确实也有不少性质和向量相同。
- 复数的模
定义复数的模,为复平面原点到 ( a , b ) (a,b) (a,b)的距离,即 ∣ z ∣ = x 2 + y 2 |z|=\sqrt {x^2+y^2} ∣z∣=x2+y2
定义 z z z 的范数 N ( z ) = ∣ z ∣ 2 = x 2 + y 2 N(z)=|z|^2=x^2+y^2 N(z)=∣z∣2=x2+y2。
- 共轭复数
复数 z = a + b i z=a+bi z=a+bi 的共轭是 z ′ = a − b i z'=a-bi z′=a−bi,记作 z ˉ \bar z zˉ。
性质: z × z ˉ = a 2 + b 2 z\times \bar z=a^2+b^2 z×zˉ=a2+b2, ∣ z ∣ = ∣ z ˉ ∣ |z|=|\bar z| ∣z∣=∣zˉ∣。
- 复数的大小
复数可以看做和向量一样,无法比较大小。
- 复数的加减
对应部 的加减,如 ( a , c ) + ( b , d ) = ( a + b , c + d ) (a,c)+(b,d)=(a+b,c+d) (a,c)+(b,d)=(a+b,c+d)
- 复数乘法
两个复数 z 1 = a 1 + b 1 i , z 2 = a 2 + b 2 i z_1 = a_1 + b_1i,~z_2 = a_2 + b_2 i z1=a1+b1i, z2=a2+b2i 相乘的结果为
z 0 = z 1 × z 2 = ( a 1 + b 1 i ) × ( a 2 + b 2 i ) = a 1 a 2 + a 1 b 2 i + a 2 b 1 i + b 1 b 2 i 2 z_0~=~z_1 \times z_2~=~(a_1 + b_1i) \times (a_2 + b_2i) = a_1a_2 + a_1b_2i + a_2b_1i + b_1b_2i^2 z0 = z1×z2 = (a1+b1i)×(a2+b2i)=a1a2+a1b2i+a2b1i+b1b2i2
又因为 i 2 = − 1 i^2 = -1 i2=−1,所以
z 0 = ( a 1 a 2 − b 1 b 2 ) + ( a 1 b 2 + a 2 b 1 ) i z_0~=~(a_1a_2 - b_1b_2) + (a_1b_2 + a_2b_1) i z0 = (a1a2−b1b2)+(a1b2+a2b1)i
在复平面上, z 1 , z 2 , z 0 z_1,~z_2,~z_0 z1, z2, z0 所对应的幅角 θ 1 , θ 2 , θ 0 \theta_1,~\theta_2,~\theta_0 θ1, θ2, θ0
有关系: θ 0 = θ 1 + θ 2 \theta_0 = \theta_1 + \theta_2 θ0=θ1+θ2
- 复数的除法
对于两个复数 z 1 = a 1 + b 1 i , z 2 = a 2 + b 2 i z_1 = a_1 + b_1i,~z_2 = a_2 + b_2 i z1=a1+b1i, z2=a2+b2i,他们相除的结果为
z 0 = z 1 z 2 z_0 = \frac{z_1}{z_2} z0=z2z1
考虑分数上下同时乘 z 2 ‾ \overline{z_2} z2 ,有
z 0 = z 1 z 2 ‾ a 2 2 + b 2 2 z_0~=~\frac{z_1 \overline {z_2}}{a_2^2 + b_2^2} z0 = a22+b22z1z2
分母是一个实数,可以直接将分子的实部虚部除以分母。
或者也可以展开:
a + c × i b + d × i = ( a + c × i ) ( b − d × i ) ( b + d × i ) ( b − d × i ) = ( a b + c d ) + ( b c − a d ) × i b 2 + d 2 \frac{a+c\times i}{b+d\times i}=\frac{(a+c\times i)(b-d\times i)}{(b+d\times i)(b-d\times i)}=\frac{(ab+cd)+(bc-ad)\times i}{b^2+d^2} b+d×ia+c×i=(b+d×i)(b−d×i)(a+c×i)(b−d×i)=b2+d2(ab+cd)+(bc−ad)×i
即:
( a , b ) ( c , d ) = ( a b + c d b 2 + d 2 , b c − a d b 2 + d 2 ) \frac{(a,b)}{(c,d)}=(\frac{ab+cd}{b^2+d^2},\frac{bc-ad}{b^2+d^2}) (c,d)(a,b)=(b2+d2ab+cd,b2+d2bc−ad)
- 复数指数幂:
有欧拉公式 e i θ = cos θ + i sin θ e^{i\theta} = \cos \theta + i \sin \theta eiθ=cosθ+isinθ其中 e e e 是自然对数的底数
当取 θ = π \theta = \pi θ=π 时,有 e i π = cos π + i sin π e^{i\pi} = \cos \pi + i \sin \pi eiπ=cosπ+isinπ$
又因为 $ cos π = 1 , s i n π = 0 \cos \pi = 1,~sin \pi = 0 cosπ=1, sinπ=0所以 e i π = − 1 e^{i\pi} = -1 eiπ=−1
也就是: e i π + 1 = 0 e^{i \pi} + 1=0 eiπ+1=0
0x91 高斯整数
- 定义
形如 a + b i a+bi a+bi (其中 a , b a,b a,b 是整数)的复数被称为高斯整数,高斯整数全体记作集合 Z [ i ] = { a + b i ∣ a , b ∈ Z } , w h e r e i 2 = − 1 Z[i] = \{ a + bi | a,b \in Z\}, \ where \ i^2 = -1 Z[i]={a+bi∣a,b∈Z}, where i2=−1,换言之,高斯整数是实部和虚部都为整数的复数。由于高斯整数在乘法和加法下交换,它们形成了一个交换环。也就是高斯整数是加、减、乘运算下封闭。
满足加法、乘法以及交换律、结合律、分配率并有 0 0 0 元和单位元的集合称为交换环。
在复平面上,高斯整数是二维复平面上的整点 ( a , b ) (a,b) (a,b)。
高斯整数的模是它和自己共轭复数的乘积,即范数 N ( a + b i ) = ( a + b i ) ( a − b i ) = a 2 + b 2 N(a+bi) = (a+bi)(a-bi)=a^2+b^2 N(a+bi)=(a+bi)(a−bi)=a2+b2,它的模可以表示为两个数字的平方和,所以不能表示为 4 k + 1 , w h e r e k ∈ Z 4k+1, \ where \ k \in Z 4k+1, where k∈Z。
- 整除
设 α , β \alpha,\beta α,β 是高斯整数,我们称 α \alpha α 整除 β \beta β ,是指存在一个高斯整数 γ \gamma γ,使得 β = α γ \beta=\alpha\gamma β=αγ。同整数集,若 α \alpha α 整除 β \beta β ,记作 α ∣ β \alpha\ |\ \beta α ∣ β反之记作 , α ∤ β \alpha\nmid\beta α∤β 。
- 带余除法
也称欧几里得除法,高斯整环 Z [ i ] Z[i] Z[i] 是欧几里得环,所以它具有很多在整数域和多项式域上成立的特性,比如辗转相除,裴蜀定理,主理想,欧几里德引理,唯一分解定理,中国剩余定理。
定理91.1: 设 α , β \alpha,\beta α,β 为高斯整数且 β ≠ 0 \beta \neq0 β=0,则存在高斯整数 γ \gamma γ 和 ρ \rho ρ ,使得 α = β γ + ρ \alpha=\beta\gamma+\rho α=βγ+ρ。
而且 0 ≤ N ( ρ ) ≤ N ( β ) 0\le N(\rho)\le N(\beta) 0≤N(ρ)≤N(β)。这里的 γ \gamma γ 被成为商, ρ \rho ρ 被称为 余数 。
欧几里德引理
∀ a , b , p w h e r e p i s a p r i m e p ∣ a b ⇒ p ∣ a o r p ∣ b \forall a, \ b, \ p \quad where \ p \ is \ a \ prime \\ p | ab \Rightarrow p|a \ or \ p | b ∀a, b, pwhere p is a primep∣ab⇒p∣a or p∣b
如果将高斯整数 a a a 写为 a = b q + r a=bq+r a=bq+r,有 N ( r ) ≤ N ( b ) 2 N(r) \le \cfrac{N(b)}{2} N(r)≤2N(b)。
证明:
令 a b = x + y i \frac{a}{b}=x+yi ba=x+yi,令 − 1 2 ≤ x − m ≤ 1 2 , − 1 2 ≤ y − n ≤ 1 2 - \frac{1}{2} \le x-m \le \frac{1}{2}, \ - \frac{1}{2} \le y - n \le \frac{1}{2} −21≤x−m≤21, −21≤y−n≤21,令 q = m + n i q=m+ni q=m+ni,由 a = b q + r a=bq+r a=bq+r, r = b ( x − m + ( y − n ) i ) r=b(x−m+(y−n)i) r=b(x−m+(y−n)i),故 N ( r ) ≤ N ( b ) 2 N(r) \le \frac{N(b)}{2} N(r)≤2N(b)。
0x92 高斯素数
定义92.1 : 若 ϵ ∣ 1 \epsilon\ | \ 1 ϵ ∣ 1,则称高斯整数 ϵ \epsilon ϵ 是 单位 ,若 ϵ \epsilon ϵ 是单位,则称 ϵ α \epsilon\alpha ϵα 是高斯整数 α \alpha α 的一个相伴,高斯整数的单位为 1 , − 1 , i , − i 1,-1,i,-i 1,−1,i,−i。
定义92.2: 若非零高斯整数 π \pi π 不是单位,而且只能够被单位和它的相伴整除,则称之为高斯素数。
定理92.3: 若 π \pi π 是高斯整数,而且 N ( π ) = p N(\pi)=p N(π)=p,其中 p p p 是有理整数,则 π \pi π 和 π ˉ \bar \pi πˉ 是高斯素数,而 p p p 不是高斯素数。
高斯整数形成了一个唯一分解域。高斯整数只有当且仅当它是一个素数时才不可约分,高斯整数中 Z [ i ] Z[i] Z[i] 的素数称为高斯素数。
-
高斯素数的共轭复数依然为高斯素数。
-
高斯素数的相伴复数依然为高斯素数。
∀ a + b i ∈ Z [ i ] , − a + b i ∈ Z [ i ] ∀a+bi∈Z[i],−a+bi∈Z[i] ∀a+bi∈Z[i],−a+bi∈Z[i]
-
作为高斯素数的整素数 p p p 是 4 k + 3 4k+3 4k+3 型素数,其余的素数可以写为 2 2 2 个共轭高斯素数的乘积
-
一个高斯整数 a + b i a+bi a+bi 是高斯素数当且仅当以下两个条件之一成立:
-
a , b a,b a,b 中一个为 0 0 0,且另一个数字为 4 k + 3 4k+3 4k+3 型素数
若 p p p 为 4 k + 3 4k+3 4k+3 型素数,存在 d d d, d d d 不等于单位元,也不等于 p p p ,满足 d ∣ p d\ |\ p d ∣ p ,则 d d ˉ ∣ p d\bar d \ | \ p ddˉ ∣ p ,由于 d d ˉ d\bar d ddˉ 为整数,有 d d ˉ = p d \bar d = p ddˉ=p,得出 p = a 2 + b 2 p=a^2+b^2 p=a2+b2, a 2 + b 2 ≡ 0 , 1 , 2 ( m o d 4 ) a^2+b^2 \equiv 0,1,2(mod \ 4) a2+b2≡0,1,2(mod 4) ,与 p p p 为 4 k + 3 4k+3 4k+3 型素数矛盾。
-
a , b a,b a,b 都非 0 0 0 ,且 a 2 + b 2 a^2+b^2 a2+b2 是素数
令 u = a + b i u=a+bi u=a+bi ,则 u u ˉ = p u\bar u=p uuˉ=p, p p p 为一个素数,若存在存在 d d d, d d d 不等于单位元,也不等于 u u u, d ∣ u d | u d∣u,则 d d ˉ ∣ p d\bar d \ | \ p ddˉ ∣ p,由于 d d ˉ d\bar d ddˉ 为整数,有 d d ˉ = p d \bar d = p ddˉ=p,得出 d = u d=u d=u,与假设矛盾。
0x93 唯一分解
由于高斯整环是一个唯一分解域,所以每一个高斯整数都可以写为一个单位元和若干高斯素数的乘积,这种分解是唯一的(忽略共轭和相伴)。
∀ a ∈ Z [ i ] , a = u ⋅ ( 1 + i ) e 0 ∏ p m e i , w h e r e u ∈ { 1 , − 1 , i , − i } , 0 ≤ e i \forall a \in Z[i], \ a = u \cdot (1+i)^{e_0} \prod p_m ^{e_i}, \ where \ u \ \in \{ 1, -1,i, -i\}, \ 0 \le e_i ∀a∈Z[i], a=u⋅(1+i)e0∏pmei, where u ∈{1,−1,i,−i}, 0≤ei
0x94 最大公约数
两个高斯整数的最大公约数并不唯一,加入 d d d 是 a a a 与 b b b 的最大公约数,则 a , b a,b a,b 的最大公约数为 d , − d , i d , − i d d,−d,id,−id d,−d,id,−id。
若 a = i k ∏ p m ν m , b = i n ∏ p m μ m a = i^k \prod p_m ^ {\nu_m}, \ b = i^n \prod p_m ^ {\mu_m} a=ik∏pmνm, b=in∏pmμm,则其中一个最大公约数为
d = ∏ p m λ m , w h e r e λ m = m i n ( ν i , m u i ) d = \prod p_m ^ {\lambda_m}, \ where \ \lambda_m = min(\nu_i, \ mu_i) d=∏pmλm, where λm=min(νi, mui)
可以根据带余除法里的结论,进行辗转相除,时间复杂度为 O ( l o g ( n ) ) O(log(n)) O(log(n))。
Complex div(Complex a, Complex b) { long double mo = b.norm(); Complex c = a * b.conj(); long double r = 1. * c.r / mo, i = 1. * c.i / mo; return Complex(round(r), round(i)); } Complex gcd(Complex a, Complex b) { if (b.r == 0 && b.i == 0) return a; Complex c = div(a, b); return gcd(b, a - b * c); }
0x95 同余和剩余系
给定一个高斯整数 z 0 z_0 z0 ,对于高斯整数 z 1 , z 2 z_1,z_2 z1,z2 ,如果它们的差是 z 0 z_0 z0 的整数倍,即 z 1 − z 2 = k z 0 , k ∈ Z z_1−z_2=kz_0, k∈Z z1−z2=kz0,k∈Z,那么称 z 1 z_1 z1 与 z 2 z_2 z2 模 z 0 z_0 z0 同余,写作 z 1 ≡ z 2 ( m o d z 0 ) z1≡z2(\mod z0) z1≡z2(modz0)。
模 z 0 z_0 z0 同余是一种等价关系,它将高斯整数分成若干个等价类,称为剩余类,剩余类写作 Z / z 0 Z Z/z_0Z Z/z0Z ,剩余类形成了一个交换环。
0x96 费马二平方和定理
p p p 是一个素数, p p p 可以写成两个平方数的和,当且仅当 p = 2 p=2 p=2 或 p ≡ 1 ( m o d 4 ) p≡1(\mod4) p≡1(mod4)。
充分性:令 p = a 2 + b 2 p=a^2+b^2 p=a2+b2 ,对任意一个整数 x x x ,有 x 2 ≡ 0 , 1 , 2 ( m o d 4 ) x2≡0,1,2(\mod 4) x2≡0,1,2(mod4),故 a 2 + b 2 ≡ 0 , 1 , 2 ( m o d 4 ) a^2+b^2≡0,1,2(\mod 4) a2+b2≡0,1,2(mod4),由于 p p p 是素数,所以 p = 2 p=2 p=2 或 p ≡ 1 ( m o d 4 ) p \equiv1(mod 4) p≡1(mod4)。
必要性:当 p = 2 , 2 = 12 + 12 p=2,2=12+12 p=2,2=12+12,当 p p p 为 4 k + 1 4k+1 4k+1 型素数,由于 p p p 不是高斯素数,所以可以进行分解,即 p = u u ˉ p = u \bar u p=uuˉ, u = a + b i u=a+bi u=a+bi,故 p = a 2 + b 2 p=a^2+b^2 p=a2+b2。
0x97 分解4k+1型素数
p p p 为 4 k + 1 4k+1 4k+1 型素数,如果存在 k 2 ≡ − 1 ( m o d p ) k2≡−1(\mod p) k2≡−1(modp) ,则 p ∣ ( k + i ) ( k − i ) p | (k+i)(k−i) p∣(k+i)(k−i),由于 p = u u ˉ p=u \bar u p=uuˉ,有 u ∣ ( k + i ) u |(k+i) u∣(k+i),故 u = ( k + i , p ) u=(k+i,p) u=(k+i,p) ,即可将 p p p 分解为两个平方数的和。
由于有一半的数在模 p p p下存在平方剩余,随机一个 t t t ,检验 t p − 1 2 ≡ − 1 ( m o d p ) t^{\frac{p-1}{2}} \equiv -1(mod \ p) t2p−1≡−1(mod p),令 k = t p − 1 4 k=t^{\frac{p-1}{4}} k=t4p−1,时间复杂度为 O ( T l o g ( p ) ) , T O(Tlog(p)),T O(Tlog(p)),T 为测试次数。
0x98 构造 a 2 + b 2 = n a^2+b^2=n a2+b2=n的方案
- 首先将 n n n 分解为 n = ∏ p m e m n = \prod p_m^{e_m} n=∏pmem 的形式
- 将 2 2 2 分解为 ( 1 + i ) ( 1 − i ) (1+i)(1−i) (1+i)(1−i) ,将 4 k + 1 4k+1 4k+1 型素数分解为 u u ˉ u \bar u uuˉ,其中 u u u 为高斯素数, 4 k + 3 4k+3 4k+3 型素数不可分解
- n = ∏ p m e i , 0 ≤ e i n = \prod p_m ^{e_i}, \ \ 0 \le e_i n=∏pmei, 0≤ei,由$ n=u \bar u , 故 需 要 将 ,故需要将 ,故需要将n$中的高斯素数分成两部分,使得两部分共轭。考虑素数 p m p_m pm ,对于 4 k + 1 4k+1 4k+1 型素因子,分解为 u e m u ˉ e m u^{e_m} \bar u^{e_m} uemuˉem ,左边可以放 k k k 个 u u u, e m − k e_m- k em−k 个 u ˉ \bar u uˉ;对于 4 k + 3 4k+3 4k+3 型素因子,因为不能进行分解,所以左右两边的数量应该一样多,即 4 k + 3 4k+3 4k+3 型的素数 p m p_m pm 出现的次数必须为偶数。
令 f ( n ) = 1 4 ∑ x , y ∈ Z [ x 2 + y 2 = n ] f(n)=\frac{1}{4}\sum_{x,y \in Z}[x^2+y^2=n] f(n)=41∑x,y∈Z[x2+y2=n],除以 4 4 4 是因为由 4 4 4 个单位元。由于素因子可以分开考虑,所以该函数为积性函数。
- f ( 2 k ) = 1 f(2^k)=1 f(2k)=1
- f ( p e ) = e + 1 f(p^e)=e+1 f(pe)=e+1,当 p p p 为 4 k + 1 4k+1 4k+1 型素数
- f ( p 2 e + 1 ) = 0 f(p^{2e+1})=0 f(p2e+1)=0, f ( p 2 e ) = 1 f(p^{2e})=1 f(p2e)=1,当 p p p 为 4 k + 3 4k+3 4k+3 型素数
0x99 竞赛例题选讲
Problem A、 A math problem (HDU 2650)
给出 a + b j a+bj a+bj,其中 j = − 2 j=\sqrt{-2} j=−2 ,判断 a + b j a+bj a+bj 是否为高斯素数。
Solution
我们按照上面证明的判断高斯素数的方法直接模拟即可。
注意这里不是正常的复数,这里设 j = − 2 j=\sqrt{-2} j=−2。
∣ j ∣ = a 2 + ( − 2 b ) 2 |j|=\sqrt {a^2+(\sqrt{-2}b)^2} ∣j∣=a2+(−2b)2
很明显原来的判定中 a 2 + b 2 a^2+b^2 a2+b2 就变成了 a 2 + 2 b 2 a^2+2b^2 a2+2b2。同理若 j = − k j=\sqrt{-k} j=−k,就是 a 2 + k b 2 a^2+kb^2 a2+kb2。
由于这里的数据很大,所以我们判断素数的时候需要用到 M i l l e r _ R a b i n \tt Miller\_Rabin Miller_Rabin算法
typedef long long ll; ll mul(ll a, ll b, ll m) { ll ans = 0; while (b) { if (b & 1) { ans = (ans + a) % m; b--; } b >>= 1; a = (a + a) % m; } return ans; } ll qpow(ll a, ll b, ll m) { ll ans = 1; a %= m; while (b) { if (b & 1) { ans = mul(ans, a, m); b--; } b >>= 1; a = mul(a, a, m); } return ans; } bool Miller_Rabin(ll n) { if (n == 2) return true; if (n < 2 || !(n & 1)) return false; ll a, m = n - 1, x, y; int k = 0; while ((m & 1) == 0) { k ++ ; m >>= 1; } for (int i = 0; i < Times; i++) { a = rand() % (n - 1) + 1; x = qpow(a, m, n); for (int j = 0; j < k; j++) { y = mul(x, x, n); if (y == 1 && x != 1 && x != n - 1) return false; x = y; } if (y != 1) return false; } return true; } int main() { ll a, b; while (~scanf("%lld%lld", &a, &b)) { if (a == 0) { if (b % 4 == 3 && Miller_Rabin(b)) puts("Yes"); else puts("No"); } else { ll t = a * a + 2 * b * b; if (Miller_Rabin(t)) puts("Yes"); else puts("No"); } } return 0; }
Problem B Gaussian Prime Factors (POJ 3361)
求一个数的高斯素因子。
Solution
我们根据高斯素数的判定原理,我们只需要将输入的数进行质因数分解,如果得到的质数是 4 x + 3 4x+3 4x+3 的形式就保存,不是就枚举,找到 a a a,求得 b b b 看 b b b 是否是整数,找到 a a a 和 b b b,保存 a + b i a+bi a+bi 和 a − b i a-bi a−bi,最后排序输出即可。
typedef long long ll; struct complex { ll a, b; char op; } c[1100]; ll cp; bool cmp(complex m, complex n) { bool ret = 0; if (m.a < n.a) ret = 1; if (m.a == n.a && m.b < n.b) ret = 1; if (m.a == n.a && m.b == n.b && m.op == '+' && n.op == '-') ret = 1; return ret; } void getResult(ll p) { ll i, j; if ((p - 3) % 4) { for (i = 1;; i++) { j = ll(sqrt(double(p - i * i))); if (i * i + j * j == p) { c[cp].a = i, c[cp].b = j, c[cp++].op = '+'; c[cp].a = i; c[cp].b = j, c[cp++].op = '-'; break; } } } else c[cp].a = p, c[cp].b = 0, c[cp++].op = '*'; } int main() { ll in, num = 0, i, j, k, tmp, isFir; while (scanf("%lld", &in) != EOF) { tmp = in; isFir = 1; cp = 0; printf("Case #%lld: ", ++ num); for (i = 2; i * i < tmp; i ++ ) { if (tmp % i == 0) { getResult(i); while (tmp % i == 0) tmp /= i; } } if (tmp != 1) getResult(tmp); sort(c, c + cp, cmp); for (i = 0; i < cp; i++) { if (i) printf(", "); if (!c[i].b) printf("%lld", c[i].a); else if (c[i].b == 1) printf("%lld%cj", c[i].a, c[i].op); else printf("%lld%c%lldj", c[i].a, c[i].op, c[i].b); } printf("\n"); } return 0; }
-
一个关于高斯整数的最小正整数问题 (2008年)
2021-04-24 03:39:47主要讨论了高斯整数多项式所表整数的计算,利用初等数论基本理论和方法,获得了一个含有n(n≥1)个高斯整数常量和变量的线性多项式虚部所表整数中最小正整数的精确显式表达,并进一步获得了该多项式虚部所表整数的... -
高斯整数 / 费马平方和定理 / 拉格朗日的四平方定理
2019-10-21 23:47:29一、高斯整数 形如。(其中a,b是整数)的复数被称为高斯整数,高斯整数全体记作Z[i]。注意到若 γ=a+bi 是高斯整数,则它是满足如下方程的代数整数: 通常我们使用希腊字母来表示高斯整数,例如α,β,γ和δ...一、高斯整数
形如
。(其中a,b是整数)的复数被称为高斯整数,高斯整数全体记作Z[i]。注意到若 γ=a+bi 是高斯整数,则它是满足如下方程的代数整数:
通常我们使用希腊字母来表示高斯整数,例如α,β,γ和δ。注意到若 n 是一个整数,则 n=n+0i 也是高斯整数。当我们讨论高斯整数的时候,把通常的整数称为有理整数。
加、减、乘运算
高斯整数在加、减、乘运算下是封闭的,正如下面定理所述。
定理1:设 α=x+iy 和 β=w+iz 是高斯整数,其中 x,y,w 和 z 是有理整数,则 α+β,α-β 和 αβ 都是高斯整数。
虽然高斯整数在加、减和乘运算下封闭,但是他们在除法运算下并不封闭,这一点与有理整数类似。此外,若 α=a+bi 是高斯整数,则a的范数 N(α)=
是非负有理整数。
整除性
我们可以像研究有理整数那样去研究高斯整数。整数的许多基本性质可以直接类推到高斯整数上。要讨论高斯整数的这些性质,我们需要介绍高斯整数类似于通常整数的一些概念。特别地,我们需要说明一个高斯整数整除另一个高斯整数的意义,并给出高斯素数的定义。
定义1:设 α 和 β 是高斯整数,我们称α整除β,是指存在一个高斯整数 γ 使得β=αγ。若α整除β,我们记作α|β ;若α 不整除β ,记作α
β 。
高斯整数的整除也满足有理整数整除的一些相同的性质。例如,若α,β和γ 是高斯整数,α|β,β|γ,则α|γ。再者,若α,β,γ,ν和μ 是高斯整数,γ|μ,γ|β,则γ|(μα+νβ)。
高斯素数
1, −1, i及−i都是高斯整数环里面的单位元。除此之外,在高斯整环里面不能因子分解的数称为高斯素数。高斯素数分为两类,其中一类是形式为4n+3(n是整数)的普通素数,如3,7等,它们在高斯整环里面也不能够因子分解。但是所有形式是4n+1的普通素数如5,13等,在高斯整环里面都可以唯一因子分解成两个共轭的高斯素数的乘积,如5=(2+i)(2-i)。需要注意的是,这里我们也可以写成5=(1+2i)(1-2i),这个是因为(2-i)i=1+2i,而i是单位元,所以我们可以认为这两种分解是等价的。此外,素数2也可以分解,即2=(1+i)(1-i)。
二、费马平方和定理
费马平方和定理是指由法国数学家费马在1640年提出的一个猜想,但他没有提出有力的数学证明,1747年,瑞士数学家莱昂哈德•欧拉提出证明后成为定理。
费马平方和定理的表述是:奇质数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
费马二平方定理(Fermat's Two Squares Theorem)
费马二平方定理是指除了2这个特殊的素数,所有的素数都可以分两类:被4除余1的素数,如5,13,17,29,37,41;第二类则是被4除余3的素数如3,7,11,19,23,31.第一类素数都能表示为两个整数的平方和,第二类都不能。
费马二平方定理指出,当且仅当或时,素数可以表示为两个非零平方之和。 并且这种表示是唯一的。
三、拉格朗日四平方定理(Lagrange's four-square theorem)
拉格朗日的四平方定理,也称为Bachet猜想,由Diophantus陈述缺乏必要条件而推论得出。它指出,每一个正整数可以写成的总和至多四个正方形。尽管该定理由费马使用无限下降来证明,但该证明被抑制了。欧拉无法证明该定理。拉格朗日(Lagrange)于1770年给出了第一个公开的证明,并利用了欧拉四方形恒等式。
拉格朗日的四平方定理(也称为Bachet猜想)指出,每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。它是費馬多邊形數定理和華林問題的特例。
-
高斯整数、高斯素数、费马平方和定理
2019-07-18 16:07:46高斯整数 a=x+y∗i (x,y∈Z)a = x+y*i\ \ (x,y\in Z)a=x+y∗i (x,y∈Z),则 aaa 为高斯整数。 aaa 的范为 N(a)=∣a2∣=x2+y2N(a)=|a^2|=x^2+y^2N(a)=∣a2∣=x2+y2。 若存在高斯整数 yyy,... -
lcfA 编码的 mimo 系统的不同 lcf-A cide:ber 主要取决于高斯整数的最小多项式-matlab开发
2021-06-01 11:49:25在这里,我们展示了编码为 lcf 的 mimo 系统的 ber 仅取决于高斯整数的最小多项式。 这是我们的分钟。 2x2 系统的方程是 x^2+i=0(其中 i 是复数 i) 两个不同的根集是 a.exp((-1i*pi)/4),exp((-1i*5*pi)/4) b.exp... -
偶数长度的完美高斯整数序列的新构造
2021-03-17 04:09:28偶数长度的完美高斯整数序列的新构造 -
高斯整数环Z[i]、整数环Z等UFD的算术基本定理的C++程序实现
2013-06-01 10:02:00代数和数论中的程序计算问题之高斯整数环Z[i]、整数环Z等UFD的算术基本定理的C++程序实现 -
HDU2650(高斯整数环)
2013-08-16 19:08:17我们把集合:叫做高斯整数环,其中Z表示通常的整数环,而用表示复数域上的整数环。 那么什么是环呢?就是通过加减乘三种运算后,仍然能满足本身性质的就叫做环。 范的定义:设,,定义a的范为 设,则 (1)为... -
BZOJ 1041: [HAOI2008]圆上的整点 (高斯整数,高斯质数,圆上整点数)
2020-02-07 15:40:17对互为共轭复数的高斯整数,将其分成两部分,每一对共轭复数留一个在左边,另一个留在右边,最后左边的高斯整数相乘得到的高斯整数和右边高斯整数相乘得到的高斯整数互为共轭复数,并且它们的乘积 = z = z = z ... -
数论概论读书笔记 36.高斯整数与唯一因子分解
2018-08-30 23:31:25高斯整数与唯一因子分解 稍微偏了点理论,数域的扩展,这里不详细记录了 主要是: 高斯整数的唯一分解 高斯整数带余除法 高斯整数公因数性质 高斯素数整除性质 勒让德两平方数之和定理 D1−D3D1−D3D_1-D_3差... -
HDU 2650 A math problem (高斯整数环)
2013-08-19 10:25:24我们把集合:叫做高斯整数环,其中Z表示通常的整数环,而用表示复数域上的整数环。 那么什么是环呢?就是通过加减乘三种运算后,仍然能满足本身性质的就叫做环。 范的定义:设,,定义a的范... -
HDU 2650 A math problem 高斯整数判定
2015-05-21 23:10:16我们把集合:叫做高斯整数环,其中Z表示通常的整数环,而用表示复数域上的整数环。 那么什么是环呢?就是通过加减乘三种运算后,仍然能满足本身性质的就叫做环。 范的定义:设,,定义a的范... -
高斯整数 and 高斯素数
2012-11-22 12:32:00http://zh.wikipedia.org/wiki/高斯整數 转载于:https://www.cnblogs.com/luotinghao/archive/2012/11/22/2782434.html -
数学家高斯的问题,一个有意思的小算法,根据高斯整数计算日期
2017-01-18 09:51:00数学家高斯的问题,一个有意思的小算法,根据整数计算日期 -
浅谈高斯素数([HAOI2008]圆上的整点)
2022-01-14 12:02:17把一个数在高斯整数域上分解为若干个复数因子的乘积,这种分解式是唯一的,而其中每个因子在高斯整数上不能再分,这些因子也就是高斯素数。 比如 5 = ( 2 + i ) ( 2 − i ) 5=(2+i)(2-i) 5=(2+i)(2−i),而 2 + i 2... -
LA 4079 高斯素数 高斯整数
2017-08-03 11:43:06#include #include #include #include using namespace std; int ok(int x) { for(int i=2;i(int)sqrt(x+0.5);i++) { if(x%i==0) return 0; } return 1; } int main() { int T,a,b;... wh -
[数论]高斯整数中的素数及费马平方和定理
2010-11-13 03:18:00<br /> <br />注:这是从新浪网转载过来的 链接:http://blog.sina.com.cn/s/blog_6e3d28f70100n64y.html -
近世代数--整环--高斯整环
2020-12-15 13:23:57近世代数--整环--高斯整环 博主是初学近世代数(群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。 高斯整环是一类重要的整环,高斯(Gauss)最先对这个环进行研究,... -
一种整数上离散高斯取样的常数时间实现方法
2021-07-07 06:45:53整数上的离散高斯取样是格密码体制实现的基本操作,也是决定安全性的重要因素,但可能受到计时攻击从而造成秘密信息的泄漏。为此,在Knuth-Yao算法的基础上,提出一种整数上离散高斯取样的常数时间实现方法。通过... -
整数阶一维高斯函数:执行任意正阶的高斯函数。-matlab开发
2021-06-01 19:01:40计算一维高斯函数: exp(-log(2)*(2*(x-x0)./FWHM).^(2*floor(abs(order)))); 在哪里: x = 坐标x0 = 功能中心FWHM = 函数的全宽半最大值阶 = 高斯阶 正态高斯是 1 阶的。 注意 FWHM = (1/e 半宽)/sqrt(2*log(2)) ... -
高斯消元整数消元模板
2016-06-17 10:52:06高斯消元就是来接方程组的。(可以跟矩阵联系在一起)#include #include #include #include #include using namespace std; const int MAXN = 1e2+5; int equ, var;///equ个方程 var个变量 int a[MA