數論與密碼學

2012年5月29日星期二

1.2同餘(Congruence)

定義：

有兩整數a、b，有一正整數N，若(a-b)可被N整除，

則稱整數a、b為對模N同餘，記為a≡b mod N

(即a與b之差為N的整數倍)

例如：

　　　11≡2 mod 9 19≡5 mod14 23≡11 mod12

Q： x ≡ 5 mod 7 求x ?

Ans： x=7N+5

重點：

對任意正整數同餘，可以把整數分為n個不相交的子集合，如下

N0= {x≡0 mod N} N1= {x≡1 mod N}

N2= {x≡2 mod N} …… Nn-1= {x≡N-1 mod N}

例如： N=4

N0= {x≡0 mod 4} N1= {x≡1 mod 4}

N2= {x≡2 mod 4} N3= {x≡3 mod 4}

※有關同餘的議題

1. 線性同餘 2. 二次剩餘 3. 指數同餘 4.多項式同餘

練習題：

1. 寫出一個線性同餘的方程式

2. 寫出一個二次剩餘的方程式

3. 寫出一個指數同餘的方程式

4. 寫出一個多項式同餘的方程式

Ans：

同餘方程式	一元方程式
ax≡b mod N	ax=b
ax²+bx≡c mod N	ax²+bx=c
a^x≡b mod N	a^x=b
f(x)=a_nxⁿ+a_n-1x^n-1+…+a₀≡b mod N	f(x)=a_nxⁿ+a_n-1x^n-1+…+a₀=b

1.2.1線性同餘(Linear Congruential)

Q：何謂線性？

Ans：滿足重疊定理的系統，稱為線性系統。

定義：

給定兩整數a、b，與正整數N，則ax≡b mod N就稱為線性同餘。

(1)若gcd(a,N)=d，且d不能整除於b，則ax≡b mod N無解

(2)若gcd(a,N)=d，且d整除於b，則ax≡b mod N洽有d個不同剩餘的解

(3)若gcd(a,N)=1，則ax≡b mod N有唯一解

若滿足ax≡1 mod N，且gcd(a,N)=1，a與N已知

則x稱為a對模數N的模反元素，記為x≡a^-1 mod N

此外a稱為x對模數N的模反元素

※ 目前被廣泛使用且發展歷史最久的亂數產生方式，即為線性同餘法。最早是在1951年由Lehmer所提出。

練習題：解 (1)3x=1
(2)3x≡1 mod7

Ans：

(1) x=1/3

(2) x= (7n+1)/3 =2n+ (n+1)/3

當n=2時 x=4+1=5

故得 x≡5 mod7

HW#4

想辦法解 (1)101x≡5 mod1234

(2)13x≡2 mod53

解答：

(1) x= 12n+ (22n+5)/101 令n1=(22n+5)/101

n=4n1+(13n1-5)/22 令n2=(13n1-5)/22

n1=n2+(9n2+5)/13 令n3=(9n2+5)/13

n2=n3+(4n3-5)/9 令n4= (4n3-5)/9

當n3=8時 → n2=11 → n1=19 → n=87 代入得x=1063

故得x≡1063 mod1234

(2) x= 4n+ (n+2)/13

當n=11時可得x=44+1 =45

故得x≡45 mod53

練習題：解 11x≡2 mod 45？

Ans：

　　 x= 4n+ (n+2)/11

當N=9時可得x=37
故得 x≡37 mod45

練習題：解 121x≡3 mod 1001？

Ans：

x= 8n+ (33n+3)/121 令n1=(33n+5)/121

n= 3n1+ (22n1-3)/33 令n2=(22n1-3)/33

n1= n2+ (11n2+3)/22 令n3=(11n2+3)/22

n2= 2n3+ 3/11 → 此題無解
因為121與1001不是互質

練習題：解 121x≡3 mod 1002？

Ans：

x= 8n+ (34n+3)/121 令n1=(34n+5)/121

n= 3n1+ (19n1-3)/34 令n2=(19n1-3)/34

n1= n2+ (15n2+3)/19 令n3=(15n2+3)/19

n2= n3+ (4n3-3)/15 令n4=(4n3-3)/15

n3= 3n4+ (3n4+3)/4 令n5=(3n4+3)/4

n4= n5+ (n5-3)/3

當n5=3時 → n4=3 → n3=12 → n2=15 → n1=27 → n=96

已知n=96 可得x= 8*96 +(34*96+3)121 =795

故得 x≡795 mod 1002

※ 以下依序列出上述所列出的式子，並觀察所產生式子的規則

(1) 121x≡3 mod 1002	(2) 34n≡-3 mod 121
(3) 19n1≡3 mod 34	(4) 15n2≡-3 mod 19
(5) 4n3≡3 mod 15	(6) 3n4≡-3 mod 1002
(7) n5≡3 mod 3

※ 由上表可發現式子的規律性，有點類似之前所學的輾轉相除法。

程式撰寫練習(一)- 找出質數與質數個數

寫一個程式列出小於n之所有質數與個數，並找出最大質數

void main()

{

FILE *fp_out1 = fopen("D:\\data4.txt","w+"); //建立檔案路徑

FILE *fp_out2 = fopen("D:\\data5.txt","w+");

FILE *fp_out3 = fopen("D:\\data6.txt","w+");

int x,y,z,count1,count2,flag,N; //定義變數

int n1[1229],n2[10000]; //定義矩陣

count1=0; //初始化

count2=0;

//0到 10⁴ 質數

N=10000;

for(int i=2;i<N;i++)

{

flag=1; //設旗標為1

for(int j=2;j<i;j++)

{

if (i%j==0) //若餘數為0

{

flag=0; //令旗標為0

break;

}

flag=flag*1;

}

if(flag==1)

{

count1++;

fprintf(fp_out1,"%d\t%d\n",i,count1); //將結果寫到記事本

fprintf(fp_out2,"%d\n",i);

}

readData("D:\\data5.txt",n1, count1); //將0到10000之間的質數存成矩陣

//10⁴到10⁸質數

for(int i=10000;i<100000;i++)

{

flag=1;

for(int j=0;j<count1;j++)

{

if (i%n1[j]==0) //將1萬到1億每一個數除以矩陣內的每一數

{

flag=0;

break;

}

flag=flag*1;

}

if(flag==1)

{

count2++;

fprintf(fp_out3,"%d\t%d\n",i,count2);

}

system("pause");

}

結果 :

0到10⁴的質數個數(以千為單位)

千為單位	質數個數	最大質數
0~1	168	997
1~2	135	1999
2~3	127	2999
3~4	120	3989
4~5	119	4999
5~6	114	5987
6~7	117	6997
7~8	107	7993
8~9	110	8999
9~10	112	9973
總計	質數個數	最大質數
0~10000	1229	9973

0到10⁵的質數個數(以萬為單位)

萬為單位	質數個數	最大質數
0~1	1229	9973
1~2	1033	19997
2~3	983	29989
3~4	958	39989
4~5	930	49999
5~6	924	59999
6~7	878	69997
7~8	902	79999
8~9	876	89989
9~10	879	99991
總計	質數個數	最大質數
0~100000	9592	99991

0到10⁶的質數個數(以十萬為單位)

十萬為單位	質數個數	最大質數
0~1	9592	99991
1~2	8392	199999
2~3	8013	299993
3~4	7863	399989
4~5	7678	499979
5~6	7560	599999
6~7	7445	699967
7~8	7408	799999
8~9	7323	899981
9~10	7224	999983
總計	質數個數	最大質數
0~1000000	78498	999983

0到10⁷的質數個數(以佰萬為單位)

佰萬為單位	質數個數	最大質數
0~1	78498	999983
1~2	70435	1999993
2~3	67883	2999999
3~4	66330	3999971
4~5	65367	4999999
5~6	64336	5999993
6~7	63799	6999997
7~8	63129	7999993
8~9	62712	8999993
9~10	62110	9999991
總計	質數個數	最大質數
0~10000000	664599	9999991

2012年5月29日 星期二

1.2同餘(Congruence)

程式撰寫練習(一)- 找出質數與質數個數

2012年5月29日星期二