2012年5月29日 星期二

程式撰寫練習(二)- 解線性同餘

利用涂老師自創演算法寫成一個程式來解出線性同餘，並建立表格 for N=3、4、5、6、7… 20。 (ax≡1 mod N)


一、程式碼

題目： 121x≡1  mod 1002
#include <iostream>
#include <math.h>
using namespace std;
void main()
{
           int n1,n2,n3,temp1,temp2,temp3,x,N;  //宣告變數
           int a=0,b=1;   //設定變數值
           n1=1002,n2=121;  
           n3=1;
           N=n1;
           while (n1%n2)  
           {
                     temp1=n1%n2;  //將所得餘數存到temp1值
                     temp2=n2-temp1;       
                     if(temp2<temp1) //比較哪個餘數較小
                     {
                                x=floor((double)n1/n2);
                                x=(int)x+1;
                                temp3=(b*x)-a;
                                a=b;
                                b=temp3;
                                n1=n2;
                                n2=temp2;
                     }
                     else
                     {
                      x=floor((double)n1/n2);
                     temp3=a-(b*x);
                     a=b;
                     b=temp3;
                     n1=n2;
                     n2=temp1;
                     }
                     if(n2==1)
                     {
                                if(b<0)b=b+N;
                                b=b*n3;
                                if(b>N)b=b%N;
                                cout<<"x= "<<b<<endl;
                                break;
                     }
           }

           system("pause");
}


二、結果



(1) 121x≡1  mod 1002之結果

   X=265

(2) 建立N =3~20 的表格
N=3
a
2
x
2
N=4
a
2
3
x
無解
3
N=5
a
2
3
4
x
3
2
4
N=6
a
2、3、4
5
x
無解
5
N=7
a
2
3
4
5
6
x
4
5
2
3
6
N=8
a
2、4、6
3
5
7
x
無解
3
5
7
N=9
a
3、6
2
4
5
7
8
x
無解
5
7
2
4
8
N=10
a
2、4、5、6、8
3
7
9
x
無解
7
3
9
N=11
a
2
3
4
5
6
7
8
9
10
x
6
4
3
9
2
8
7
5
10
N=12
a
2、3、4、6、8、9、10
5
7
11
x
無解
5
7
11
N=13
a
2
3
4
5
6
7
8
9
10
11
12
x
7
9
10
8
11
2
5
3
4
6
12
N=14
a
2、4、6、7、8、10、12
3
5
9
11
13
x
無解
5
3
11
9
13
N=15
a
3、5、6、9、10、12
2
4
7
8
11
13
14
x
無解
8
4
13
2
11
7
14
N=16
a
2、4、6、8、10、12、14
3
5
7
9
11
13
15
x
無解
11
13
7
9
3
5
15
N=17
a
2
3
4
5
6
7
8
9
10
11
12
x
9
6
13
7
3
5
15
2
12
14
10
a
13
14
15
16
x
4
11
8
16
N=18
a
2、4、6、8、10、12、14、3
9、15、16
5
7
11
13
17
x
無解
11
13
5
7
17
N=19
a
2
3
4
5
6
7
8
9
10
11
12
x
10
13
5
4
16
11
12
17
2
7
8
a
13
14
15
16
17
18
x
3
15
14
6
9
18
N=20
a
2、4、5、6、8、10、12、14、15、16、18
3
7
9
x
無解
7
3
9
a
11
13
17
19
x
11
17
13
19






張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)